Problemas dinâmicos de coleta e entrega com janelas de tempo: análise de instâncias de benchmark

Abstract

O problema de coleta e entrega com janelas de tempo (PDPTW - Pickup and Delivery Problem with Time Windows e o problema dial-a-ride (DARP - Dial-A-Ride Problem) dinâmicos não possuem instâncias de benchmark que sejam amplamente usadas, o que dificulta a comparação de diferentes algoritmos de solução. Por esse motivo, este trabalho tem como propósito analisar os conjuntos de instâncias de problemas PDPTW e DARP dinâmicos atualmente disponíveis para uso, assim como os métodos usados para gerálas. Como base para análise serão usadas duas medidas, grau de dinamismo e urgência, que caracterizam a distribuição dos pedidos dinâmicos das instâncias. Isto é feito com a finalidade de auxiliar a escolha de conjuntos de instâncias de interesse para teste de novos algoritmos, ou, caso necessário, a escolha de um método para geração de novas instâncias. Os resultados de análise mostram que, em sua maioria, os conjuntos estudados apresentam baixa variabilidade em suas medidas de dinamismo e urgência. Isso acontece principalmente por causa do método utilizado para geração das instâncias.

Abstract: The dynamic PDPTW (Pickup and Delivery Problem with Time Windows) and DARP (Dial-A-Ride Problem) do not have widely used benchmarks, which makes it difficult to compare different solution algorithms. For this reason, this dissertation aims to analyze the sets of instances of dynamic PDPTW and DARP currently available for use, as well as the methods used to generate them. As a basis for analysis two measures will be used: degree of dynamism and urgency, which characterize the instances dynamic requests distribution. This is done in order to help reserachers choose interesting sets of instances to test new algorithms, or, if necessary, the choice of a method for generating new instances. The analysis results show that most of the studied sets have low variability in their measures of dynamism and urgency. This characteristic is mainly caused by the method used to generate the instances.