ALGORITMOS PARA O PROBLEMA DE ROTEAMENTO DE VEÍCULOS COM CROSS-DOCKING - PDF
Download "ALGORITMOS PARA O PROBLEMA DE ROTEAMENTO DE VEÍCULOS COM CROSS-DOCKING"
Rita Desconhecida Bacelar
1 ALGORITMOS PARA O PROBLEMA DE ROTEAMENTO DE VEÍCULOS COM CROSS-DOCKING
3 VINÍCIUS WELLINGTON COELHO DE MORAIS ALGORITMOS PARA O PROBLEMA DE ROTEAMENTO DE VEÍCULOS COM CROSS-DOCKING Dissertação apresentada ao Programa de Pós-Graduação em Ciência da Computação do Instituto de Ciências Exatas da Universidade Federal de Minas Gerais - Departamento de Ciência da Computação como requisito parcial para a obtenção do grau de Mestre em Ciência da Computação. Orientador: Geraldo Robson Mateus Coorientador: Thiago Ferreira de Noronha Belo Horizonte Dezembro de 2012
4 c 2012, Vinícius Wellington Coelho de Morais. Todos os direitos reservados. M827a Morais, Vinícius Wellington Coelho de Algoritmos para o Problema de Roteamento de Veículos com Cross-Docking / Vinícius Wellington Coelho de Morais. Belo Horizonte, 2012 xxvi, 53 f. : il. ; 29cm Dissertação (mestrado) Universidade Federal de Minas Gerais - Departamento de Ciência da Computação Orientador: Geraldo Robson Mateus Coorientador: Thiago Ferreira de Noronha 1. Computação - Teses. 2. Otimização Combinatória Teses. 3. I. Orientador. 4. II.Coorientador. I. Título. CDU 519.6*61 (043)
7 Dedico este trabalho à minha mãe Cida, à minha Vó Ana, aos meus irmãos Vanessa, Vivian e Álvaro e ao meu padastro Alair.
9 Agradecimentos Esta dissertação é fruto de vinte meses de trabalho. Neste período várias pessoas contribuíram para o seu desenvolvimento. Gostaria de agradecer a todos pelo apoio. Agradeço à minha mãe, minha principal incentivadora. Aos meus irmãos, Vanessa, Vivian e Álvaro, que sempre foram a inspiração para meus esforços. A todos os meus familiares tio(as), primos(as), meu padastro e meus avós. Estes contribuíram diretamente para minha formação, caráter e personalidade. Aos meus amigos e colegas das repúblicas de Diamantina e Belo Horizonte: Drika, Danilo, Lucas Costa, Lucas Meirelles, Jucimara, Henrique, Tiago e Michelle. Sou grato por me receberem como família. Agradeço à Gigi e todos aqueles que estiveram comigo nos momentos de felicidade, tristeza e descontração. Obrigado pelo carinho! Aos amigos dos departamentos DECOM/UFVJM e DCC/UFMG. Aos amigos do LaPO/UFMG: Vitor Shiryu, Ramon, Rangel, Fernanda, Fernando, Gustavo, Januário, Afonso, Amadeu, Franklin, Phillippe Samer e Luis Henrique. Estes dividiram comigo o ambiente de trabalho e contribuíram diretamente com meu crescimento acadêmico e profissional. Aos meus orientadores. Professores Alessandro Vivas e Luciana Assis, na graduação, e Geraldo Robson e Thiago Noronha, na pós-graduação. Agradeço pela disposição, acompanhamento e orientação. Sou grato pela paciência, dedicação, ensinamentos e pelas respostas positivas aos meus trabalhos. Aos funcionários do DCC/UFMG, em especial as meninas da secretaria. Estes possibilitam o desenvolvimento deste trabalho. Finalmente, agradeço à CAPES (Coordenação de Aperfeiçoamento de Pessoal de Nível Superior), pela concessão da bolsa durante todo o período de realização deste mestrado. ix
11 Resumo Esta dissertação aborda o Problema de Roteamento de Veículos com Cross-Docking. Dados um conjunto de requisições por produtos, um único centro de consolidação (CD), e múltiplos fornecedores e consumidores, o problema consiste em definir rotas de custo mínimo para uma frota homogênea de veículos que realiza o transporte de produtos dos fornecedores aos consumidores via CD. Inicialmente, os veículos partem do CD em direção aos fornecedores, coletam os produtos e retornam ao ponto inicial para realizar o processo de consolidação. Em seguida, a mesma frota de veículos transporta os produtos aos consumidores. As rotas definidas devem respeitar as restrições de capacidade dos veículos e janela de tempo de cada fornecedor e consumidor. São propostas três heurísticas construtivas, uma heurística baseada na metaheurística Iterated Local Search e uma matheurística que integra esta última e um modelo de Programação Linear Inteira baseado em Particionamento de Conjuntos. Os algoritmos propostos foram avaliados em instâncias da literatura e comparados com as melhores heurísticas existentes para este problema. Os resultados obtidos mostram a eficiência das soluções implementadas. Palavras-chave: Roteamento de Veículos, Cross-Docking, Heurística, Matheurística, Otimização Combinatória. xi
13 Abstract This work addresses the Vehicle Routing Problem with Cross-Docking. Given a set of goods requests, a single Cross-Dock (CD), and several suppliers and customers, the problem consists in defining minimum cost set of routes for a fleet of identical vehicles that leaves the CD towards the suppliers, picks up the goods and returns to the initial point to perform the consolidation process. Thus, the same fleet of vehicles delivers the goods to the consumers. The routes designed must respect the capacity constraints of the vehicles as well as the time windows constraints. We proposed three constructive heuristics, a heuristic based on the Iterated Local Search metaheuristic, and a matheuristic that integrates the latter and a Integer Linear Programming model based on Set Partitioning. The algorithms were evaluated on instances from the literature and compared to the best existing heuristics for this problem. The results showed the efficiency of the implemented solutions. Keywords: Vehicle Routing, Cross-Docking, Heuristic, Matheuristic, Combinatorial Optimization xiii
15 Lista de Figuras 1.1 Ilustração de uma solução do VRPCD. São exibidas as rotas dos veículos v 1 e v 2. O primeiro parte do centro de consolidação, coleta os produtos das requisições r 4, r 1 e r 5 e retorna ao CD. O segundo veículo coleta os produtos de r 3 e r 2 e retorna ao CD. As requisições r 1, r 2 e r 5 são consolidadas no CD. Por fim, a mesma frota de veículos entrega os produtos nos seus respectivos consumidores Exemplo do processo de consolidação. O veículo v 1 coleta os produtos das requisições r 4, r 1 e r 5 nos fornecedores, ao mesmo tempo em que o veículo v 2 coleta os produtos de r 2 e r 3. Em seguida, os veículos consolidam as requisições r 1, r 2 e r 5 no CD. Após o processo de consolidação o veículo v 1 entrega os produtos das requisições r 2 e r 4 e o veículo v 2 entrega os produtos das requisições r 1, r 3 e r 5 aos seus consumidores Ilustração dos dois possíveis cenários de consolidação do VRPCD Ilustração de uma iteração da heurística 2S-NI. (a) mostra o estado da solução em que as requisições r 1, r 2 e r 3 já foram atribuídas ao veículo corrente. O próximo passo do algoritmo, demonstrado em (b), é definir a próxima requisição ainda não atribuída a ser alocada ao veículo. Na parte (c), a requisição r 4 é atribuída ao veículo uma vez que esta possui o menor valor de γ i,j Ilustração de uma iteração da heurística 2S-NN. Em (a), assumindo-se que r 1 foi a última requisição atribuída ao veículo na iteração anterior, é calculado a requisição de CRR com o menor γ i,l em relação a r l. Na Figura (b), a requisição r 3, definida como a de menor valor de γ i,l, é atribuída ao veículo corrente inserindo os seus nós fornecedor e consumidor nas rotas de coleta e entrega, respectivamente xv
16 3.3 Ilustração de uma iteração da heurística 2S-S. Em (a), cinco requisições são distribuídas entre seus respectivos fornecedores e consumidores. Em seguida, cada uma das requisições é atribuída a um veículo, conforme ilustrado em (b). Na parte (c), o par de requisições r 3 e r 1 é associado ao mesmo veículo Buscas Locais Interveiculares. Dada uma solução inicial (a), são ilustrados dois vizinhos gerados pelas buscas locais Exchange (b) e Realocate (c), aplicadas ao primeiro cenário do VRPCD Buscas Locais Inter rotas. Dada uma solução inicial (a), são ilustrados vizinhos gerados por movimentos executados pelas buscas locais Insertion(b), Swap(1,1)(c), Swap(2,1)(d) e Drop route (e), aplicados ao segundo cenário do VRPCD Buscas Locais Intrarota. Assumindo-se a solução inicial apresentada em (a), é ilustrado um movimento realizado pela busca local que avalia a vizinhança ReInsertion Intraroute (b) Ilustração de dois vizinhos gerados pelos operadores de perturbação Split e Random Exchange. Dada uma solução inicial, em um movimento Split divide-se as rotas do veículo v 2 em duas rotas menores. Enquanto no Random-Exchange, as requisições r 4 e r 2 nas rodas de coleta e as requisições r 1 e r 4 nas rotas de entrega são trocadas Gráfico de avaliação do impacto do tempo de espera no CD em relação ao custo das soluções para VRPCD, variando-se os tempos de preparo do veículo (A) e o tempo necessário para carregar ou recarregar cada unidade de produto (B) TTT plot para a instância 200b. Neste experimento, a probabilidade da matheurística SPILS-VRPCD encontrar uma solução tão boa quanto o alvo é sempre maior que o da heurística ILS-VRPCD. SPILS-VRPCD encontra a solução alvo em menos de 350 segundos com probabilidade igual 96%, enquanto a ILS-VRPCD alcança valores semelhantes ao alvo em 620 segundos TTT plot para a instância 200c. No experimento realizado, a heurística ILS-VRPCD define uma solução com custo igual a alvo em 1200, porém com probabilidade de 92% este encontra o alvo em 760 segundos. Já a matheurística SPILS-VRPCD define a solução alvo com probabilidade próxima a 100% em 1100 segundo. O grau de convergência da matheurística é maior do que o de ILS-VRPCD xvi
17 5.4 TTT plot para a instância 200d. Neste experimento a evolução da heurística ILS-VRPCD se mostrou bastante similar ao da matheurística SPILS- VRPCD. A probabilidade de se definir uma solução tão boa quanto o alvo a partir dos 750 segundos para ambos os algoritmos é relativamente próxima. Porém, o algoritmo SPILS-VRPCD apresenta uma convergência mais acentuada até os 500 segundos TTT plot para a instância 200e. Neste experimento, a probabilidade da SPILS-VRPCD encontrar uma solução tão boa quanto o alvo é maior do que a de ILS-VRPCD. Com probabilidade igual a 90%, SPILS-VRPCD define uma solução tão boa quanto alvo em 230 segundos, enquanto o ILS- VRPCD encontra uma solução com mesma probabilidade em 550 segundos. 45 xvii
19 Lista de Tabelas 5.1 Comparação das heurísticas construtivas para as instâncias de [Wen et al., 2009] Comparação de ILS-VRPCD com as melhores heurísticas da literatura para as instâncias de [Wen et al., 2009] Comparação da matheurística SPILS-VRPCD com as melhores heurísticas da literatura para as instâncias de [Wen et al., 2009] xix
21 Lista de Algoritmos 1 Heurística Two-Side Nearest Insertion Heurística Two-Side Nearest Neighbor Heurística Two-Side Savings Função GeraPoolInicial() Heurística ILS-VRPCD Matheurística SPILS-VRPCD xxi
23 Lista de Siglas 2S-NI 2S-NN 2S-S ALNS BCP CD CRR CVRP DVRP EDP HFVRP ILS MIP NI PDP SA SCM SP TS Two-Side Nearest Insertion Two-Side Nearest Neighbor Two-Side Savings Adaptive Large Neighbourhood Search Branch-and-Cut-and-Price Cross-Dock Conjunto de Requisições Candidatas Capacitaded Vehicle Routing Problem Distance Constrained Vehicle Routing Problem Express Delivery Problem Heretogeneous Fleet Vehicle Routing Problem Iterated Local Search Mixed Integer Programming Nearest Insertion Pickup and Delivery Problem Simulated Annealing Supply Chain Management Set Partitioning Tabu Search xxiii
24 TSP Traveling Salesman Problem TTT plot Time-To-Target value plots UTS VND VRP VRPB VRPCD VRPPD VRPSD Unified Tabu Search Variable Neighborhood Descent Vehicle Routing Problem Vehicle Routing Problem with Backhaul Vehicle Routing Problem with Cross-Docking Vehicle Routing Problem with Pickup and Delivery Vehicle Routing with Split Delivery VRPSPD Vehicle Routing Problem with Simultaneous Pickups and Deliveries VRPTW Vehicle Routing Problem with Time Windows xxiv
25 Sumário Agradecimentos Resumo Abstract Lista de Figuras Lista de Tabelas Lista de Siglas ix xi xiii xv xix xxiii 1 Introdução Definição do Problema Trabalhos Relacionados Problema de Roteamento de Veículos Capacitado Problemas de Coleta e Entrega Problema de Roteamento de Veículos com Janela de Tempo Problema de Roteamento de Veículos com Cross-Docking Formulação matemática Heurísticas para VRPCD Heurísticas Construtivas Two-Side Nearest Insertion Two-Side Nearest Neighbor Two-Side Savings Buscas Locais e Perturbação Buscas Locais Interveiculares Buscas Locais Inter-rotas xxv
26 3.2.3 Buscas Locais Intrarota Perturbações Heurística ILS-VRPCD Matheurística para o VRPCD SPILS-VRPCD Experimentos Computacionais Experimentos com Heurísticas Construtivas Experimentos com Heurística ILS-VRPCD Experimentos com Matheurística SPILS-VRPCD Conclusão e Trabalhos Futuros 47 Referências Bibliográficas 49 xxvi
27 Capítulo 1 Introdução Devido à globalização e ao aumento da produtividade industrial e agrícola, o sistema de distribuição de produtos está cada vez mais em evidência. Com o objetivo de (i) minimizar o tempo de espera por produtos e serviços, (ii) elevar os índices de satisfação dos consumidores, (iii) reduzir custos e consequentemente (iv) maximizar os ganhos, soluções eficientes são aplicadas em atividades logísticas. A partir destas necessidades surge o conceito de Gestão da Cadeia de Suprimentos (SCM, do inglês Supply Chain Management). A Cadeia de Suprimentos é o processo no qual diversas entidades de negócios (por exemplo, fornecedores, fabricantes, distribuidores e varejistas) integram suas ações para proporcionar uma melhor gestão do fluxo físico de materiais em uma rede logística. Esta também pode ser considerada sob uma rede de atividades responsáveis pela coleta, produção, armazenamento e transporte de mercadorias. Estas atividades possuem um certo grau de independência, porém a otimização de suas funções está diretamente vinculada ao desempenho da cadeia logística como um todo. Assim, o processo de otimização não deve ser visto apenas em função de uma única atividade [Jayaraman & Ross, 2003]. Segundo Chen et al. [2006],Cross-docking é um importante conceito vinculado ao armazenamento e gerenciamento do fluxo de produtos em um sistema de transporte. Nesta abordagem um conjunto de produtos vindos de diferentes fornecedores chega a um centro de consolidação (CD, do inglês Cross-Dock), onde as cargas são realocadas a uma frota de veículos e enviadas aos consumidores finais de forma a minimizar os custos de transporte. O termo consolidação é usado para se referir ao processo de agrupamento, preparo, carga e descarga de produtos em um CD [Napolitano, 2002]. Este processo é considerado de curto prazo, uma vez que os produtos não permanecem estocados por um período superior a um dia de trabalho [Yu & Egbelu, 2008]. 1
28 2 Capítulo 1. Introdução Existe um grande número de trabalhos na literatura relacionados a Cross-Docking [Ratliff et al., 1999; Apte & Viswanathan, 2003; Bookbinder, 2004; Bartholdi & Gue, 2004]. Estes se restringem à definir a localização dos centros de consolidação ou planejar o sequenciamento dos veículos no CD. Entretanto, poucos são os trabalhos que tratam do processo de consolidação integrado com a tarefa de roteamento dos veículos entre os fornecedores/consumidores e o CD [Liao et al., 2010]. A partir desta observação Lee et al. [2006] definiram o Problema de Roteamento de Veículos com Cross-Docking (VRPCD, do inglês Vehicle Routing Problem with Cross-Docking). No VRPCD são dados um único centro de consolidação, um conjunto de requisições, múltiplos fornecedores e consumidores, em que cada requisição está associada a um par fornecedor/consumidor. O problema consiste em minimizar os custos de transporte ao se atribuir rotas de coleta e entrega para uma frota de veículos que comecem e terminem no CD e que respeitem as restrições de capacidade dos veículos e janela de tempo em cada ponto da rede. Inicialmente, os veículos partem de sua origem em direção aos fornecedores, coletam suas requisições e retornam ao ponto inicial para realizar o processo de consolidação. Em seguida, a mesma frota de veículos entrega as requisições aos consumidores. Este problema é descrito formalmente a seguir. 1.1 Definição do Problema Nesta dissertação centra-se no VRPCD, assim como descrito em Wen et al. [2009]. Este pode ser definido em um grafo G = (N,E), em que o conjunto de nós é dado por N = P D {0}, onde P = {p 1, p 2,..., p n } é um conjunto de fornecedores, D = {d 1, d 2,..., d n } é um conjunto de consumidores e 0 um CD. Seja E = {(i, j) i, j P } {(i, j) i, j D} {(0, j) j {P D}} um conjunto de arestas e R = {r 1, r 2,..., r n } um conjunto com n requisições, em que cada requisição r i R de um produto q i é associada a um par {p i, d i }, tal que, p i P e d i D. Seja ainda, uma frota V de veículos com capacidade limitada Q. A cada requisição r i R é associada uma demanda positiva de produtos σ i, a cada aresta (i, j) E é associado um custo c ij (em tempo) e, para cada fornecedor p i P (ou consumidor d i D) é associado uma janela de tempo [a i, b i ], onde a i e b i representam o tempo mínimo e máximo de chegada do veículo ao nó i N. O VRPCD consiste em definir rotas de coleta e entrega que minimizem o tempo total trafegado pela frota de veículos, em que os produtos de cada requisição r i R são coletados em um fornecedor p i P e entregues a um consumidor d i D passando pelo CD, onde o processo de consolidação é realizado. As restrições do problema são as seguintes. (i) Tanto as rotas de coleta quanto
29 1.1. Definição do Problema 3 as rotas de entrega devem iniciar e terminar no CD. (ii) Cada fornecedor p i P (ou consumidor d i D) deve ser visitado uma única vez. (iii) A mesma frota de veículos deve ser usada no processo de coleta e entrega. (iv) O somatório das demandas transportadas, tanto em uma rota de coleta quanto em uma rota de entrega, não deve extrapolar a capacidade do veículo. (v) Cada fornecedor (ou consumidor) deve ser visitado dentro de sua janela de tempo. (vi) As etapas de roteamento e consolidação devem ocorrer dentro do horizonte de planejamento T. O tempo gasto pelo processo de consolidação é variável e é dado em função da quantidade de demanda por uma requisição, da penalidade imposta para carregar ou descarregar cada uma unidade de produto no CD mais um tempo fixo de preparo do veículo. Por exemplo, seja B o tempo para carregar (ou descarregar) cada unidade de produto no CD e A o tempo fixo de preparo do veículo, se A e B forem iguais a 10 e 2 minutos, respectivamente, e um veículo precisar consolidar os produtos de uma requisição com demanda de 22 unidades, então o tempo gasto para consolidar a requisição será de = 54 minutos. A Figura 1.1 ilustra o processo de roteamento do VRPCD. São mostrados dois pares de rotas para atender as demandas de cinco requisições, atribuídas aos veículos v 1 e v 2. As linhas tracejadas representam as rotas do veículo v 1, enquanto as linhas continuas retratam as rotas do veículo v 2. O veículo v 1 coleta os produtos das requisições r 4, r 1 e r 5 nos fornecedores e entrega os produtos das requisições r 2 e r 4 aos seus consumidores, ao mesmo tempo em que o veículo v 2 coleta os produtos das requisições r 3 e r 2 e entrega os produtos das requisições r 1, r 3 e r 5. p 4 d 2 d4 p 1 p 5 0 d 1 p 3 p 2 d 5 d 3 Coleta Consolidação Entrega Cross-Dock p i Fornecedores d i Consumidores Veículo v 1 Veículo v 2 Figura 1.1: Ilustração de uma solução do VRPCD. São exibidas as rotas dos veículos v 1 e v 2. O primeiro parte do centro de consolidação, coleta os produtos das requisições r 4, r 1 e r 5 e retorna ao CD. O segundo veículo coleta os produtos de r 3 e r 2 e retorna ao CD. As requisições r 1, r 2 e r 5 são consolidadas no CD. Por fim, a mesma frota de veículos entrega os produtos nos seus respectivos consumidores. O processo de consolidação das requisições r 1, r 2 e r 5 é detalhado na Figura 1.2.
30 4 Capítulo 1. Introdução No exemplo da Figura 1.1, os produtos das requisições r 1 e r 5, coletados pelo veículo v 1, e os produtos da requisição r 2, coletados pelo veículo v 2, são consolidados no CD. Em seguida, o veículo v 1 entrega os produtos das requisições r 2 e r 4, enquanto o veículo v 2 entrega os produtos das requisições r 1, r 3 e r 5. Fornecedores P Veículo Veículo Veículo Veículo Cross-Dock Consumidores D Figura 1.2: Exemplo do processo de consolidação. O veículo v 1 coleta os produtos das requisições r 4, r 1 e r 5 nos fornecedores, ao mesmo tempo em que o veículo v 2 coleta os produtos de r 2 e r 3. Em seguida, os veículos consolidam as requisições r 1, r 2 e r 5 no CD. Após o processo de consolidação o veículo v 1 entrega os produtos das requisições r 2 e r 4 e o veículo v 2 entrega os produtos das requisições r 1, r 3 e r 5 aos seus consumidores. Dois cenários podem ser considerados no VRPCD. No primeiro, os veículos coletam e entregam os produtos de suas requisições sem realizar consolidação no CD. No segundo, os veículos realizam o processo de consolidação, ou seja, pelo menos uma de suas requisições tem os produtos coletados e entregues por veículos diferentes. O segundo cenário é composto por dois casos: (i) um veículo pode coletar os produtos de uma requisição no fornecedor mas não entregá-los ao seu consumidor; (ii) um veículo pode não coletar os produtos de uma requisição no seu fornecedor mas pode entregá-los ao seu consumidor. p 4 d 2 d 3 p 4 d 2 d 3 p 1 p 3 d 1 p 5 0 d 5 d 4 p 1 p 3 p 6 p 5 0 d 6 d 1 d 5 d 4 p 2 p 2 Fig. (a): Primeiro cenário. O veículo v 1 coleta e entrega os produtos das requisições r 1, r 4 e r 5, passando pelo CD sem realizar o processo de consolidação. O veículo v 2 coleta e entrega os produtos das requisições r 2 e r 3 sem realizar consolidação no CD. Fig. (b): Segundo cenário. O veículo v 1 coleta os produtos das requisições r 4 e r 6, retorna ao CD, onde realiza a consolidação e em seguida entrega os produtos das requisições r 1, r 4, r 5 e r 6. v 2 coleta os produtos das requisições r 1, r 2, r 3 e r 5, retorna ao CD, onde realiza a consolidação e em seguida entrega os produtos das requisições r 2 e r 3. Cross-Dock p i Fornecedores d i Consumidores Veículo v 1 Veículo v 2 Figura 1.3: Ilustração dos dois possíveis cenários de consolidação do VRPCD.
31 1.1. Definição do Problema 5 A Figura 1.3(a) ilustra o primeiro cenário do VRPCD. O veículo v 1 coleta e entrega os produtos das requisições r 1, r 4 e r 5 e o veículo v 2 transporta os produtos das requisições r 2 e r 3, sem a necessidade de realizar consolidação. O segundo cenário do VRPCD é exemplificado na Figura 1.3(b), onde os produtos das requisições r 1, r 2, r 3 e r 5 são coletados pelo veículo v 2, enquanto os produtos das requisições r 4 e r 6 são coletados pelo v 1, no processo de entrega os produtos das requisições r 2 e r 3 são entregues por v 2 e os demais são entregues pelo veículo v 1. Neste exemplo, as requisições r 1 e r 5 são consolidadas no CD. Aspectos práticos e teóricos motivam o estudo e a resolução de VRPCD. Em termos operacionais a implementação de soluções para problemas de distribuição podem representar ganhos consideráveis, uma vez que, segundo Alvarenga et al. [2007] de 10% a 15% do valor das mercadorias comercializadas no mundo advêm dos custos de transportes. Empresas como a rede de supermercados Wal Mart [Jayaraman & Ross, 2003], a rede varejista de farmácias Walgreens [Chen et al., 2006], a montadora de veículos Toyota [Witt, 1998] e empresa dinamarquesa de logística e consultoria Transvision [Wen et al., 2009], já empregam com sucesso técnicas de Cross-Docking. Em termos teóricos VRPCD pertence à classe de problemas NP-Difícil, uma vez que pode ser reduzido ao Problema de Roteamento de Veículos (VRP, do inglês Vehicle Routing Problem) clássico [Lee et al., 2006]. Como não são conhecidos algoritmos polinomiais para essa classe de problemas, a resolução do VRPCD para instâncias de grande porte por meio de métodos exatos pode exigir um grande tempo computacional. Fato este que motiva o desenvolvimento de heurísticas e até mesmo algoritmos híbridos baseados em programação matemática, que podem encontrar soluções próximas às soluções ótimas, com um baixo custo computacional [Ribas et al., 2010]. Nesta dissertação são propostas heurísticas eficientes, baseadas em metaheurísticas e procedimentos exatos para resolver uma versão de VRPCD. As principais contribuições deste trabalho são: (i) o desenvolvimento de três heurísticas construtivas para VRPCD, baseadas em métodos clássicos da literatura de VRP; (ii) o desenvolvimento de uma heurística baseada na metaheurística Iterated Local Search (ILS), que trabalha apenas no espaço viável de soluções; (iii) desenvolvimento de uma matheurística baseada em ILS e em um modelo de Particionamento de Conjuntos, que obtém resultados superiores aos apresentados na literatura. O restante deste texto é organizado da seguinte forma. O Capítulo 2 apresenta uma revisão bibliográfica sobre diferentes versões de VRP e uma revisão detalhada sobre trabalhos relacionados ao VRPCD. No Capítulo 3, as heurísticas desenvolvidas para resolver o problema são descritas. A matheurística proposta é detalhada no Ca-
32 6 Capítulo 1. Introdução pítulo 4. Os experimentos computacionais são descritos no Capítulo 5. Por fim, as considerações finais são apresentadas no Capítulo 6.
33 Capítulo 2 Trabalhos Relacionados Neste capítulo é apresentada uma revisão bibliográfica sobre diferentes versões de VRP e uma revisão mais detalhada dos trabalhos relacionados ao VRPCD. A Seção 2.1 apresenta o Problema de Roteamento de Veículos Capacitado (CVRP, do inglês Capacitaded Vehicle Routing Problem). Os Problemas de Coleta e Entrega (PDP, do inglês Pickup and Delivery Problems) são apresentados na Seção 2.2. Algumas referências para o Problema de Roteamento de Veículos com Janela de Tempo (VRPTW, do inglês Vehicle Routing Problem with Time Windows) são descritas na Seção 2.3. Por fim, a revisão bibliográfica para VRPCD é apresentada na Seção Problema de Roteamento de Veículos Capacitado Seja G=(N,E) um grafo completo com o conjunto de nós N = {0} D, em que o nó 0 representa o depósito, D = {1,...,n} um conjunto de consumidores e E = {(i, j) : i, j N} o conjunto de arestas. Seja, ainda, V = {1,..., k} o conjunto de veículos homogêneos com capacidade limitada Q. Para cada consumidor i D é associado uma demanda não negativa σ i e para cada aresta (i, j) E é associado um custo c ij. CVRP consiste em definir rotas de custo mínimo para cada um dos veículos satisfazendo as seguintes restrições: (i) cada rota começa e termina no nó de depósito; (ii) cada consumidor deve ser visitado apenas uma vez e por um único veículo; (iii) o somatório das demandas de todos os consumidores de uma rota não deve exceder a capacidade do veículo. Proposto por Dantzig & Ramser [1959] como uma generalização do Problema do Caixeiro Viajante (TSP, do inglês Traveling Salesman Problem) e portanto NP-Difícil, 7
34 8 Capítulo 2. Trabalhos Relacionados CVRP foi a primeira versão de VRP a ser estudada. Baseadas neste diversas outras variantes foram propostas com um grande número de trabalhos publicados. Na literatura são descritos procedimentos baseados tanto em abordagens exatas quanto heurísticas para resolver o CVRP. Laporte [1992], Gendreau et al. [2001] e Cordeau et al. [2005] apresentam heurísticas. Enquanto, Aragao & Uchoa [2003] e Fukasawa et al. [2006] apresentaram algoritmos exatos para o CVRP e provaram a otimalidade para um conjunto de instâncias por meio de um algoritmo Branch-and- Cut-and-Price (BCP) Robusto. Os principais objetivos em se tratando de VRPs, definidos na literatura, são reduzir a distância total trafegada ou o número total de veículos utilizados. Em determinados contextos, quando uma demanda σ i é maior que a capacidade do veículo, para algum consumidor i D, este consumidor deve ser visitado mais de uma vez, definindo o Problema de Roteamento de Veículos com Entregas Fracionadas (VRPSD, do inglês Vehicle Routing with Split Delivery), referenciado por Dror et al. [1994]. Caso a frota de veículos seja heterogênea, o problema em questão é o Problema de Roteamento de Veículos com Frota Heterogênea (HFVRP, do inglês Heretogeneous Fleet Vehicle Routing Problem), abordado em Penna et al. [2011]. Quando restrições quanto à distância máxima trafegada são impostas, define-se o Problema de Roteamento de Veículos com Restrição de Distância (DVRP, do inglês Distance Constrained Vehicle Routing Problem). Nagarajan & Ravi [2012] apresentam um algoritmo aproximativo para este problema. 2.2 Problemas de Coleta e Entrega Seja N = P D, onde P = {p 1, p 2,..., p m } é um conjunto de nós de coleta e D = {d 1, d 2,..., d n } é um conjunto de nós de entrega. O Problema de Coleta e Entrega (PDP, do inglês Pickup and Delivery Problem), consiste em definir rotas de coleta ou entrega satisfazendo as demandas de cada nó i P D. Caso o processo de coleta seja realizado após a entrega o problema é referido como Problema de Roteamento de Veículos com Backhaul (VRPB, do inglês Vehicle Routing Problem with Backhaul) [Mosheiov, 1998]. PDP pode ser divido em dois grupos de problemas. (i) O primeiro, em que o transporte de produtos é realizado do depósito para os consumidores e dos consumidores para o depósito. (ii) O segundo, onde o transporte de cargas ocorre de consumidor a consumidor. O Problema de Roteamento de Veículos com Coleta e Entrega (VRPPD, do inglês Vehicle Routing Problem with Pickup and Delivery) é um caso do segundo
35 2.3. Problema de Roteamento de Veículos com Janela de Tempo 9 grupo [Parragh et al., 2008], em que o objetivo é reduzir a distância total trafegada pela frota de veículos. Um problema pertencente ao primeiro grupo é o Problema de Roteamento de Veículos com Coleta e Entrega Simultâneas (VRPSPD, do inglês Vehicle Routing Problem with Simultaneous Pickups and Deliveries) proposto por Min [1989], onde cada nó é associado a uma demanda de coleta e outra de entrega. Diversas variantes do PDP são detalhadas por Berbeglia et al. [2007] e Parragh et al. [2008]. Montané et al. [1997] definiram o Problema de Entrega Expressa (EDP, do inglês Express Delivery Problem), em que é preciso atender as demandas de um par ordenado origem-destino, utilizando um único ponto central, chamado de hub. O problema consiste em duas fases distintas: a fase de coleta, onde um veículo parte do hub atende os consumidores e retorna ao ponto de origem e a fase de entrega, onde é realizada a entrega a partir do ponto central. Métodos heurísticos para VRPPD e VRPSPD podem ser encontrados nos trabalhos de Dethloff [2001], Assis [2007] e Subramanian [2012]. Este último ainda apresenta um framework baseado em Brach-and-cut para diversas variantes do VRP. Outro trabalho a apresentar procedimentos matemáticos para VRPPD e outras variantes do VRP é o de Salani [2005]. 2.3 Problema de Roteamento de Veículos com Janela de Tempo Seja G=(N,E) um grafo completo com o conjunto de nós N={0} D, em que o nó 0 representa o depósito, D={1,..., n} um conjunto de consumidores e E={(i, j) : i, j N} um conjunto de arestas. Cada consumidor i D deve ser visitado uma única vez dentro de um determinado intervalo de tempo [a i, b i ], ou seja, o veículo deve atender o consumidor i depois do tempo a i e antes do tempo b i. A cada aresta (i, j) E é associado um custo c ij e um tempo t i,j para se percorrer do consumidor i ao j. VRPTW consiste em determinar rotas de entrega de produtos do depósito central aos consumidores do conjunto D, respeitando as restrições de capacidade e janela de tempo. Duas das mais importantes versões de VRPTW definidas na literatura são avaliadas sob os seguintes objetivos: (i) definir rotas de custo mínimo ou duração mínima para uma frota de veículos homogêneos e (ii) definir um número mínimo de veículos para atender todas as demandas do consumidores. Com o objetivo de definir rotas de custo mínimo, Ribas et al. [2010] apresentaram um algoritmo híbrido baseado nas metaheurísticas ILS e VND, além de uma formulação por Particionamento de Conjuntos. Alvarenga et al. [2007] e Brandão &
36 10 Capítulo 2. Trabalhos Relacionados Vasconcelos [2010] seguiram o mesmo princípio e desenvolveram métodos híbridos, o primeiro numa abordagem inspirada em algoritmos genéticos e o segundo no algoritmo Simulated Annealing (SA). Balakrishnan [1993] apresentou heurísticas baseadas nas heurísticas vizinho mais próximo e Savins [Clarke & Wright, 1964] com a motivação de reduzir o número de veículos, Ombuki et al. [2006] também abordaram o problema com este objetivo. Atualmente os melhores resultados para o VRPTW, com o objetivo de minimizar o custo total trafegado, foram os obtidos pelo algoritmo híbrido de Nagata et al. [2010]. Este método combina um eficiente operador de crossover com buscas locais extremamente eficientes. Os algoritmos ILS de Ibaraki et al. [2008], o Adaptive Large Neighbourhood Search (ALNS) de Pisinger & Ropke [2007], e o Unified Tabu Search (UTS) de Cordeau et al. [1997, 2001] também devem ser mencionados. Recentemente, Vidal et al. [2013] apresentaram uma detalhada revisão da literatura para o problema e algumas de suas variantes, além de propor um algoritmo híbrido para resolver estes problemas com um grande número de consumidores. Uma revisão mais ampla da literatura de VRPTW pode ser obtida nos trabalhos de Bräysy & Gendreau [2005a,b] e Golden et al. [2008]. 2.4 Problema de Roteamento de Veículos com Cross-Docking VRPCD é uma extensão de VRPPD que considera uma etapa de Cross-Docking. Na literatura, os trabalhos de Lee et al. [2006]; Liao et al. [2010]; Wen et al. [2009]; Tarantilis [2012] e Santos et al. [2010, 2011b,a] abordam as diferentes versões do problema. Estes consideraram algumas das seguintes restrições. (1) Cada rota, tanto de coleta quanto de entrega, iniciam e terminam no CD. (2) Cada nó i P D deve ser visitado uma única vez. (3) A mesma frota de veículos deve ser usada tanto no processo de coleta quanto no de entrega. (4) A capacidade dos veículos não deve ser extrapolada em nenhum ponto de uma rota. (5) Cada fornecedor (ou consumidor), assim como em VRPTW, deve ser visitado dentro de uma janela de tempo [a i, b i ], i P D. (6) Toda a etapa de roteamento deve ocorrer dentro de um horizonte de planejamento T; (7) Todos os veículos devem estar no CD durante a etapa de consolidação. Lee et al. [2006] propuseram a primeira versão de VRPCD. Nesta versão, são consideradas todas as restrições citadas anteriormente (1 a 7). Além disso, a cada veículo é associado um custo operacional. O objetivo é minimizar os custos de transportes associados ao custo operacional dos veículos utilizados e aos custos de roteamento. Para
37 2.4. Problema de Roteamento de Veículos com Cross-Docking 11 resolver o problema, os autores propuseram um algoritmo baseado na metaheurística Tabu Search (TS). Liao et al. [2010] abordaram a mesma versão do problema proposta em Lee et al. [2006] e também propuseram um algoritmo baseado em Busca Tabu. As principais diferenças entre esses dois trabalhos são suas heurísticas para geração da solução inicial e as buscas locais. Em Liao et al. [2010] é utilizado o operador de busca local Realocate, que remove consumidores de um veículo e os atribuí a outro. Já o algoritmo de Lee et al. [2006] é baseado no operador Exchange, que troca consumidores entre pares de rotas distintas. Outra diferença é que apenas o algoritmo de Liao et al. [2010] admite decrementar o número de veículos utilizados durante a execução do algoritmo. Os experimentos foram realizados com o mesmo conjunto de instâncias e o algoritmo de Liao et al. [2010] obteve melhores resultados. Em Wen et al. [2009] foi apresentada uma versão de VRPCD diferente daquela proposta por Lee et al. [2006]. Nesta versão os veículos passam pelo processo de consolidação tão logo terminem de realizar a coleta, sem a necessidade de estarem simultaneamente no CD. O processo de consolidação demanda um tempo para carga e descarga de produtos no CD, tempo este que é somado ao cálculo da janela de tempo na atividade de entrega. O objetivo do problema é definir um conjunto de rotas de coleta e entrega de tempo mínimo que passam obrigatoriamente pelo CD. Eles propuseram um conjunto de instâncias, uma formulação matemática para o problema e uma heurística eficiente baseada em TS. Tarantilis [2012] abordou a mesma versão do problema definida em Wen et al. [2009]. Este autor propôs um algoritmo baseado em um procedimento adaptativo multirestart associado à metaheurística TS, capaz de resolver as versões do problema com rotas abertas e rotas fechadas. A versão do problema com rotas abertas difere daquela com rotas fechadas em função das rotas iniciarem nos fornecedores e terminarem nos consumidores e não no CD. Tarantilis [2012] obteve melhores resultados que Wen et al. [2009], além de apresentar diferentes operadores de busca local. Santos et al. [2010, 2011b,a] abordaram outra versão de VRPCD, onde é considerado o custo fixo em se manipular as mercadorias no centro de consolidação. Porém, o roteamento não é limitado pelas restrições de janela de tempo. Nesta variante, também é considerado que todos os veículos devem estar simultaneamente no CD durante a consolidação. As principais contribuições de Santos et al. [2010] foram a proposta de modelos matemáticos e de algoritmos exatos baseados nestas formulações. Em Santos et al. [2011b] e Santos et al. [2011a], são apresentadas uma formulação por geração de colunas e um algoritmo branch-and-price para o problema, respectivamente. Nestes trabalhos, soluções ótimas para instâncias com até 30 requisições foram obtidas.
38 12 Capítulo 2. Trabalhos Relacionados Musa et al. [2010] direcionaram seus trabalhos ao problema de redes de Crossdocking, onde as cargas são transferidas de pontos de origem para pontos de destino passando por facilidades de cross-docking. Neste problema, busca-se minimizar o custo de transporte na rede, onde os veículos são carregados nos fornecedores e descarregados nos consumidores. O transporte pode ocorrer direta ou indiretamente por meio do CD. A principal diferença do trabalho de Musa et al. [2010] em relação ao VRPCD tratado nesta dissertação, e no trabalho de Wen et al. [2009], é que no contexto explorado por aqueles autores o objetivo do problema é criar um conjunto de rotas abertas que cobrem pares de pontos origem e destino, em que os veículos não iniciam e terminam suas rotas nos pontos centrais Formulação matemática A versão de VRPCD estudada nesta dissertação foi proposta por Wen et al. [2009]. Estes apresentaram uma formulação matemática, em que o conjunto de nós é dado por N=P D O, onde P ={p 1,..., p n } é um conjunto de fornecedores, D={d 1,..., d n } é um conjunto de consumidores e O = {o 1, o 2, o 3 e o 4 } representa o CD. Os nós o 1 e o 2 O representam os locais de início e término das rotas de coleta, enquanto o 3 e o 4 O são os locais de início e término das rotas de entrega, respectivamente. E={(i, j) i, j P } {(i, j) i, j D} {(0, j) j {P D}} é um conjunto de arestas e R = {r 1,..., r n } um conjunto de requisições, em que cada requisição r i R é associada a um par {p i, d i }, tal que, p i P e d i D. É considerado uma frota V de veículos homogêneos e os seguintes parâmetros: custo c ij (em tempo) da aresta (i, j) E; janela de tempo [a i, b i ] do nó i P D; demanda σ i de uma requisição r i R; a capacidade Q dos veículos; um tempo fixo A de preparo do veículo no CD; e um tempo B para carregar (ou descarregar) cada unidade de produto de uma requisição no CD. As variáveis de decisão do modelo são: x k ij, que assume 1 se o veículo k V percorre a aresta (i, j ) (0, caso contrário); u k i, que é igual a 1 se o veículo k V descarrega a requisição i no CD (0, caso contrário); ri k, que indica se o veículo k V recarrega a requisição i no CD; g k, que diz se o veículo k V é descarregado no CD; h k, que indica se o veículo k V é carregado no CD. Ainda são usadas as variáveis de tempo: s k i, o tempo em que o veículo k V deixa o nó i N; t k, o tempo no qual o veículo k V termina de descarregar no CD; w k, o tempo no qual o veículo k V começa a recarregar no CD; e ν i, o tempo no qual os produtos da requisição i R devem ser coletados no CD. Sendo assim, considerando que M é uma constante muito grande, a formulação
39 2.4. Problema de Roteamento de Veículos com Cross-Docking 13 matemática de VRPCD é dada por: Sujeito a: Minimizar c ij x k ij (2.1) (i,j) E k V x k ij = 1, i P D (2.2) j:(i,j) E k V i P j:(i,j) E i D j:(i,j) E j:(h,j) E j:(h,j) E j:(h,j) E σ i x k ij Q, k V (2.3) σ i x k ij Q, k V (2.4) x k hj = 1, h {o 1, o 3 }, k V (2.5) x k jh x k hj = 0, h P D, k V (2.6) j:(h,j) E x k jh = 1, h {o 2, o 4 }, k V (2.7) s k j s k i + c ij M (1 x k ij), (i, j) E, k V (2.8) a i s k i b i, i N, k V (2.9) u k i ri k = x k ij x k i+n,j, i P, k V (2.10) j P {o 2 } j D {o 4 } u k i + ri k 1, i P, k V (2.11) 1 M u k i g k u k i, k V (2.12) i P j P t k = s k o2 + A g k + B σ i u k i, k V (2.13) i P w k t k, k V (2.14) w k ν i M (1 r k i ), i P, k V (2.15) ν i t k M (1 u k i ), i P, k V (2.16)
40 14 Capítulo 2. Trabalhos Relacionados 1 M ri k h k ri k, k V (2.17) i P i P s k o3 = w k + A h k + B σ i ri k, k V (2.18) i P x k ij, u k i, r k i, g k, h k {0, 1}, i P, (i, j) E, k V (2.19) s k i, t k, w k 0, i N, k V (2.20) ν i 0, i P. (2.21) A função objetivo (2.1) minimiza o tempo total gasto pelos veículos para percorrer seus trajetos. A restrição (2.2) assegura que cada nó seja visitado por exatamente um veículo, uma única vez. As restrições (2.3) e (2.4) garantem que a capacidade dos veículos, tanto na coleta quanto na entrega, não sejam extrapoladas. A restrição (2.5) restringe que apenas uma rota de coleta e uma de entrega sejam definidas, para cada veículo, a partir do CD. A restrição (2.6) garante a conservação de fluxo. A restrição (2.7) força que as rotas retornem ao CD depois da coleta e da entrega. A restrição (2.8) define o tempo para um veículo percorrer dois nós consecutivamente. Já a restrição (2.9) obriga que cada nó seja visitado dentro de sua janela de tempo e que toda a operação ocorra dentro do horizonte de planejamento. As restrições de (2.10) a (2.18) exprimem a relação entre consumidores e fornecedores e tratam do processo de consolidação no CD. Mais precisamente, as restrições (2.10) e (2.11) expressam a ligação entre coleta e entrega. A restrição (2.12) define o valor de g k. A restrição (2.13) impõe que o tempo que um veículo k termina de descarregar no CD deve ser igual a soma do (i) tempo que o veículo chega no CD, (ii) do tempo fixo de preparo do veículo e (iii) do tempo necessário para descarregar cada unidade de requisição transportada. As restrições (2.14) a (2.16) definem a ordem das atividades no CD. Cada veículo só deve começar a carregar depois de realizar a descarga de produtos no CD. Os produtos de uma requisição r i só podem ser recarregados por um veículo depois que estes forem descarregados por outro (2.16). Consequentemente, o tempo de inicio para recarregar os produtos da requisição r i deve ser posterior ao tempo dos mesmos terem sido descarregados no CD. As restrições (2.17) e (2.18) descrevem o tempo no qual o veículo está preparado para deixar o CD e partir em direção aos consumidores. Por fim, as restrições (2.19) a (2.21) definem o domínio das variáveis de decisão do modelo. Como pode ser observado, todos os trabalhos que tratam heuristicamente de
41 2.4. Problema de Roteamento de Veículos com Cross-Docking 15 VRPCD propuseram algoritmos baseados em Busca Tatu. No entanto, nesta dissertação uma técnica diferente é utilizada. São propostas heurísticas baseadas na metaheurística ILS. Estas trabalham apenas no espaço viável de soluções e são capazes obter soluções comparáveis às da literatura.
43 Capítulo 3 Heurísticas para VRPCD VRPCD é uma extensão do clássico VRP, portanto ele é NP-Difícil [Lee et al., 2006]. Diversos algoritmos propostos para este último podem ser estendidos para resolver o VRPCD. Neste Capítulo, são apresentadas as heurísticas desenvolvidas para resolver o problema. Na Seção 3.1 são apresentadas as heurísticas construtivas propostas. As buscas locais e os mecanismos de perturbação são detalhados na Seção 3.2. Por fim, a metaheurística ILS é apresentada na Seção Heurísticas Construtivas Heurísticas construtivas são algoritmos que geram uma solução viável para um determinado problema com base em um conjunto de regras de construção. O principal objetivo destes procedimentos é construir soluções de boa qualidade com baixo custo computacional. Neste trabalho, são apresentadas três heurísticas para a geração de uma solução para VRPCD: Two-Side Nearest Insertion (2S-NI), Two-Side Nearest Neighbor (2S-NN) e Two-Side Savings (2S-S). Estas heurísticas não consideram o processo de consolidação, uma vez que nas soluções por elas geradas, o veículo que coleta uma requisição no fornecedor é sempre o mesmo que a entrega ao consumidor Two-Side Nearest Insertion 2S-NI é heurística construtiva baseada no algoritmo Nearest Insertion (NI), proposto por Rosenkrantz et al. [1977] para TSP. Seja o Conjunto de Requisições Candidatas (CRR), que inicialmente contém todas as requisições de R, c p i,j o custo da aresta (p i, p j ) e c d i,j o custo da aresta (d i, d j ), onde p i e d i são os respectivos nós fornecedor e consumidor de uma requisição r i já atribuída a um veículo, e p j e d j os respectivos nós 17
44 18 Capítulo 3. Heurísticas para VRPCD fornecedor e consumidor de uma requisição r j CRR. 2S-NI atribui iterativamente cada uma das requisições de CRR a um veículo. O algoritmo, primeiramente, cria um par de rotas de coleta e entrega vazias (rotas que começam e terminam no CD, sem visitar nenhum outro ponto) para um veículo v k V e, a cada iteração atribui uma requisição r j CRR, com o menor valor de γ i,j = c d i,j + c p i,j (ou seja, a requisição que possuir fornecedores e consumidores mais próximos das rotas de v k ), ao veículo v k. Quando a capacidade de um veículo é extrapolada um novo é criado. A atribuição de uma requisição r j CRR ao veículo v k se dá pela inserção do fornecedor p j P e do consumidor d j D nas rotas de coleta e entrega de v k, respectivamente. Esta inserção é feita na posição onde o acréscimo no custo da rota seja mínimo, respeitando as restrições do problema. A Figura 3.1 ilustra uma iteração da heurística 2S-NI. Na Figura 3.1(a) uma solução parcial é apresentada, onde as requisições r 1, r 2 e r 3 já foram atribuídas ao veículo corrente v k. Conforme ilustrado em 3.1(b), para cada requisição r j CRR é calculado o valor de γ i,j. Na Figura 3.1(c), a requisição r 4 é atribuída ao veículo v k, uma vez que esta possui o menor valor de γ i,j. (a) p 3 d 2 (b) p 3 d 2 (c) p 3 d 2 p 1 0 d 1 d 3 p i p 1 0 d 1 d i d 3 p 1 0 d 1 d 3 p 2 p 4 p 5 d 4 d 5 p 2 p 4 p j p 5 d 4 d 5 p 2 p 4 p 5 d 4 d 5 d j CD d i Consumidores p i Fornecedores Figura 3.1: Ilustração de uma iteração da heurística 2S-NI. (a) mostra o estado da solução em que as requisições r 1, r 2 e r 3 já foram atribuídas ao veículo corrente. O próximo passo do algoritmo, demonstrado em (b), é definir a próxima requisição ainda não atribuída a ser alocada ao veículo. Na parte (c), a requisição r 4 é atribuída ao veículo uma vez que esta possui o menor valor de γ i,j. O pseudocódigo da 2S-NI é apresentado no Algoritmo 2. Nas linhas 1, 2 e 3, são inicializados, respectivamente, o conjunto de requisição CRR, com todas as requisições do conjunto R, uma solução vazia (sem nenhuma rota) S e o identificador do veículo v k. Em seguida, na linha 4, uma requisição r j CRR é escolhida de forma aleatória. Nas linhas 5 e 6, são criadas duas rotas, uma de coleta (RC) e outra de entrega (RE), respectivamente. No laço das linhas 7 17, enquanto existir requisições em CRR, atribui
45 3.1. Heurísticas Construtivas 19 requisição por requisição ao veículo corrente v k. Na linha 9 e 10, se a atribuição da requisição r j não extrapola a capacidade do veículo v k, o fornecedor p j e o consumidor d j são inseridos respectivamente em suas rotas de coleta e entrega, com complexidade no pior caso de O( R ). Na linha 11, após atribuir r j nas rotas do veículo corrente, remove a requisição do conjunto CRR. Caso a atribuição de r j extrapole a capacidade do veículo, as rotas RC e RE são inseridas na solução S, na linha 13. Em seguida, novas rotas de coleta e entrega são criadas nas linhas 14 e 15. Um novo veículo é criado na linha 16. Após atribuir a requisição a um veículo, outra requisição r j que possuir o menor valor de γ i,j, é selecionada do conjunto CRR em O( R 2 ), no passo da linha 17. Ao final do procedimento, na linha 18, a solução S é retornada. A complexidade assintótica desta heurística é O( R 3 ). Algoritmo 1: Heurística Two-Side Nearest Insertion 1 Inicialize CRR; 2 S ; 3 v k 1; 4 Selecione uma requisição aleatória r j de CRR; 5 RC Crie rota de coleta vazia; 6 RE Crie rota de entrega vazia; 7 enquanto existir requisições em CRR faça 8 se a atribuição de r j não extrapola a capacidade do veículo v k então 9 Insira p j de r j em RC; 10 Insira d j de r j em RE; 11 Remova r j de CRR; 12 senão 13 Insira as rotas RC e RE em S; 14 RC Crie rota de coleta vazia; 15 RE Crie rota de entrega vazia; 16 v k v k +1; 17 Selecione a requisição r j de CRR com o menor valor de γ i,j ; 18 retorna S; Two-Side Nearest Neighbor 2S-NN é uma heurística proposta para VRPCD baseada no algoritmo Nearest-Neighbor, proposto por Solomon [1987] para VRPTW. O algoritmo 2S-NN, primeiramente, cria um par de rotas de coleta e entrega vazias (rotas que começam e terminam no CD, sem visitar nenhum outro ponto) para um veículo v k V. A cada iteração esta heurística atribui uma requisição r i CRR às rotas do veículo v k até que todas as requisições do
ALGORITMO ONLINE PARA O PROBLEMA DINÂMICO DE ROTEAMENTO DE VEÍCULOS
ALGORITMO ONLINE PARA O PROBLEMA DINÂMICO DE ROTEAMENTO DE VEÍCULOS HUMBERTO CÉSAR BRANDÃO DE OLIVEIRA ALGORITMO ONLINE PARA O PROBLEMA DINÂMICO DE ROTEAMENTO DE VEÍCULOS Tese apresentada ao Programa
Modelos de otimização para o Problema de Roteamento de Veículos com Cross-Docking Fernando Afonso Santos 1,2 Alexandre Salles da Cunha 2 1 Universidade Federal de Itajubá Rua São Paulo, 377 - Bairro Amazonas
ESTUDO DA INCORPORAÇÃO DE CROSS-DOCKING AO PROBLEMA DE ROTEAMENTO DE VEÍCULOS
ESTUDO DA INCORPORAÇÃO DE CROSS-DOCKING AO PROBLEMA DE ROTEAMENTO DE VEÍCULOS Vinicius W. C. Morais Universidade Federal de Minas Gerais (UFMG) Av. Antônio Carlos, 6627 Pampulha Belo Horizonte MG CEP 31270-901
Um Algoritmo Branch-and-price para o Problema de Roteamento de Veículos com Cross-Docking para Frotas Heterogêneas
Um Algoritmo Branch-and-price para o Problema de Roteamento de Veículos com Cross-Docking para Frotas Heterogêneas Fernando Afonso Santos 1,2 1 Universidade Federal de Itajubá Campus Itabira Rua São Paulo,
APLICAÇÃO DO MÉTODO DE COLETA E ENTREGA SIMULTÂNEA À LOGÍSTICA REVERSA DE MERCADORIAS
APLICAÇÃO DO MÉTODO DE COLETA E ENTREGA SIMULTÂNEA À LOGÍSTICA REVERSA DE MERCADORIAS Christiany Loss Rigo Universidade Federal do Espírito Santo Programa de Pós-Graduação em Engenharia Civil Transportes