OPtimizing solutions for the pickup and delivery problem

Abstract

Pickup and Delivery Problems are a variation of Vehicle Routing Problems that arise in many real-world transportation scenarios, such as product delivery and courier services. This work studies the Pickup and Delivery Problem with Time Windows, in which goods have to be transported from one location to another, respecting certain time restrictions and the capacity of the vehicles. It aims at minimizing the number of vehicles used, as well as the operational costs to perform all routes. To solve this problem, a mathematical formulation is used and an algorithm is proposed by embedding a Variable Neighborhood Descent method into an Iterated Local Search metaheuristic. Experiments are carried out with standard literature instances, showing that the algorithm is able to deliver good solutions in reasonable time up to a certain number of locations and vehicles. A real-world case study is conducted together with a partner company, which provided the data to generate a set of new instances based on the case. Experiments are done to evaluate how well the proposed algorithm can handle the different scenario. Results show the proposed algorithm produces good solutions for most instances of the real-world case.

Problemas de Coleta e Entrega de Produtos são uma variação dos Problemas de Roteamento de Veículos, os quais têm um amplo número de aplicações reais em transportes, como entrega de produtos e serviços de correios. Este trabalho estuda o Problema de Coleta e Entrega de Produtos com Janelas de Tempo, no qual produtos devem ser transportados de um local para o outro, respeitando certas restrições de tempo e a capacidade de cada veículo. O objetivo é minimizar o número de veículos usados, assim como o custo total de operação das rotas. Para resolver este problema, uma formulação matemática é utilizada e um algoritmo é proposto através da implementação de um método de Descida com Variação de Vizinhança dentro de uma Busca Local Iterada. Experimentos foram realizados com instâncias padrões da literatura, demonstrando que o algoritmo é capaz de encontrar boas soluções em tempo razoável, para até um número limite de locais e veículos. Um estudo sbore um caso real é feito juntamente com uma empresa parceira, a qual forneceu dados para a geração de um novo conjunto de instâncias baseado nesse caso de estudo. Experimentos foram realizados para avaliar como o algoritmo proposto se comportaria neste cenário diferente. Os resultados demonstram que o método produz boas soluções para grande parte das instâncias dos casos reais.