Heuristic approaches to the double vehicle routing problem with multiple stacks

Abstract

In a world, that in a fast pace, has become increasingly needed in consumable and nonconsumable goods, the logistics in the transportation of these products has been put to the test, being one of the most important stages in the relationship between the pro-duction process and the end user. It is said that at least 30% of the costs between the industry and the end user are solely determined by the cost of transportation. A novel problem arose followed by a question that was encountered in a real-life scenario. The Double Routing Vehicle Problem with Multiple Stacks (DVRPMS) consists in a Dou-ble Traveling Salesman Problem with Multiple Stacks (DTSPMS) with multiple vehicles. Both problems appeared for the urgent need of optimizing intermodal transportation in the european context. It consists in gathering costumer inquires from a pickup region and loading them in a set of stacks inside a container that must not be rearranged for security reasons. The container moves to a delivery region and the items gathered must be delivered according the last-in-first-out policy of the stacks. In this work, four heuristics were proposed based on the Iterated Local Search (ILS), Variable Neighborhood Descent and Simulated Annealing (SA) metaheuristics. The DVRPMS was extended to a modi-fied version where the items offered are bigger than the vehicle fleet capacities. An exact model approach is proposed and three other heuristics, based on the ILS, SA and Tabu Search are proposed and tested. The approaches presented in this work were tested by computational experiments and a statistical analysis was made to chose the best com-bination of parameters. Good results were found, providing a better average than the current literature.

Em um mundo que, em tempo acelerado, tem-se tornado cada vez mais necessitado em bens consumíveis e não consumíveis, a logística no transporte destes produtos tem sido colocada à prova, sendo uma das etapas mais importantes da relação entre o processo de produção e o usuário final. Cerca de um terço dos custos logísticos desta relação (produção-usuário) são determinados pelo custo de transporte dos bens, tornando essa operação muito importante. Um novo problem surgiu a partir de um entrave encontrado numa situação prática. O Problema do Roteamento de Veículos Duplo com Múltiplas Pilhas (DVRPMS) consiste em um Problema do Caixeiro Viajante com Múltiplas Pilhas (DTSPMS) com múltiplos veículos. Os dois problemas apareceram pela necessidade urgente em otimizar o transporte intermodal em um contexto europeu. Consiste em coletar pedidos em uma região de coleta e carregá-los num conjunto de pilhas dentro de um container, que não deve ser rearranjado por razões de segurança. O container então é levado a região de entrega e os itens são entregues seguindo a política das pilhas, em que os itens do topo, coletados por último, devem ser entregues primeiro. Nesta dissertação, quatro heurísticas baseadas na busca local iterativa (ILS), na descida em vizinhança variável (VND) e no recozimento simulado (SA) são propostas. O problema foi estendido para uma versão onde há uma oferta de itens maior do que a capacidade da frota de veículos. Um método exato é proposto juntamente com outras três heurísticas baseadas no ILS, SA e na busca tabu (TS). Os algoritmos propostos foram testados em experimentos computacionais e análises estatísticas foram feitas com intenção de encontrar a melhor combinação de parâmetros para estas heurísticas. Os resultados encontrados foram bons, tendo encontrado melhores médias que a literatura atual.