The pickup and delivery problem with time windows : algorithms, instances, and solutions

Abstract

This work considers the Pickup and Delivery Problem with Time Windows. It is a hard combinatorial optimization problem that generalizes a number of vehicle routing problem and finds applications in courier and dial-a-ride services. The objective is to construct a good set of vehicle routes to service transportation requests from pickup to delivery locations while respecting vehicle capacity and service time constraints. To tackle the problem, we propose a hybrid method combining heuristic components with a mathematical programming formulation – a technique typically referred to as matheuristic. Furthermore, a method to generate instances for the problem based on open data and realistic travel times is provided. A new set of benchmarks is proposed considering the new generation procedure. Computational experiments demonstrate that the proposed method works well on a standard benchmark set of instances for which it found a number of new best-known solutions. On the other hand, results for the new set of instances are in disagreement with the observations for the standard benchmarks and demonstrate relevant differences between the two testbeds. The work presents a series of analyses and discussions regarding the experiments, main components, and variations of the matheuristic algorithm.

Este trabalho estuda o Problema de Coleta e Entrega com Janelas de Tempo. Trata-se de um difícil problema de otimização combinatória que generaliza problemas de roteamento de veículos, possuindo aplicações em serviços de entrega e transporte de passageiros. O objetivo é definir o melhor conjunto de rotas de veículos que atendam requisições de transporte entre locais de coleta e entrega, respeitando ao mesmo tempo a capacidade dos veículos e as restrições de tempos de serviço. Para resolver o problema, nós propomos um método híbrido combinando componentes heurísticos com programação matemática – uma técnica geralmente chamada de matheurística. Além disso, uma metodologia para gerar instâncias do problema que são baseadas em dados abertos e tempos de viagem reais é proposta. Um novo conjunto de testes foi gerado baseado nesta proposta. Experimentos computacionais demonstraram que o algoritmo proposto é capaz de obter bons resultados no conjunto padrão de testes da literatura, para o qual novas soluções também foram encontradas. Por outro lado, os resultados para o novo conjunto de instâncias diferem dos observados para o conjunto padrão e demonstram diferenças relevantes entre os dois conjuntos de teste. O trabalho apresenta Uma série de análises e discussões a respeito dos experimentos, principais componentes, e variações do algoritmo híbrido proposto.