Analys of pickup and delivery and dial-a-ride problems dynamization methods and benchmark instances

Renan Artur Lopes Eccel, Rodrigo Castelan Carlson

Resumo


As instâncias de benchmark disponíveis para as versões dinâmicas do problema de coleta e entrega com janelas de tempo (PDPTW - Pickup and Delivery Problem with Time Windows) e do problema dial-a-ride (DARP - Dial-A-Ride Problem) não compartilham as mesmas características e não necessariamente cobrem todas as características de situações reais. Analisa-se conjuntos de instâncias de PDPTW e DARP dinâmicos (DPDPTW e DDARP) atualmente disponíveis para uso e os métodos usados para gerá-los a partir de instâncias estáticas. Cada método de dinamização é aplicado a cada instância estática originalmente usada por eles. As instâncias dinâmicas resultantes são analisadas com as medidas de grau de dinamismo e urgência, bem como pelo número de pedidos estáticos e a correlação entre os limites inferiores das janelas de tempo de coleta e os instantes de chegada dos pedidos. Os resultados mostram que os conjuntos estudados apresentam baixa variabilidade de grau de dinamismo e urgência independentemente do método ou da instância estática usados para a dinamização.


Palavras-chave


Dinamização. Instâncias de benchmark. DDARP. DPDPTW.

Texto completo:

PDF (English)

Referências


Agatz, N.; A. Erera; M. Savelsbergh and X. Wang (2012) Optimization for Dynamic Ride-Sharing: A Review. European Journal of Operational Research, v. 223, n. 2, p. 295–303. DOI: 10.1016/j.ejor.2012.05.028

Alonso-González, M. J.; T. Liu; O. Cats; N. Van Oort and S. Hoogendoorn (2018) The Potential of Demand-Responsive Transport as a Complement to Public Transport: An Assessment Framework and an Empirical Evaluation. Transportation Research Record, v. 2672, n. 8, p. 879–889. DOI: 10.1177/0361198118790842

Berbeglia, G.; J.-F. Cordeau and G. Laporte (2012) A Hybrid Tabu Search and Constraint Programming Algorithm for the Dynamic Dial-a-Ride Problem. INFORMS Journal on Computing, v. 24, n. 3, p. 343–355. DOI: 10.1287/ijoc.1110.0454

Cordeau, J.-F. and G. Laporte (2003) A Tabu Search Heuristic for the Static Multi-Vehicle Dial-a-Ride Problem. Transportation Research Part B: Methodological, v. 37, n. 6, p. 579–594. DOI: 10.1016/S0191-2615(02)00045-0

Dumas, Y.; J. Desrosiers and F. Soumis (1991) The Pickup and Delivery Problem with Time Windows. European Journal of Operational Research, v. 54, n. 1, p. 7–22. DOI: 10.1016/0377-2217(91)90319-Q

Eccel, R. A. L. (2019) Problemas Dinâmicos de Coleta e Entrega com Janelas de Tempo: Análise de Instâncias de Benchmark. Dis-sertação (mestrado). Programa de Pós-graduação em Engenharia de Automação e Sistemas, Universidade Federal de Santa Catarina. Florianópolis. Available at: (accessed on 19/10/2020).

Eccel, R. A. L. (2020) renan-eccel/instances-DDARP-DPDPTW: v1.2. Available at: (ac-cessed on 19/10/2020). DOI: 10.5281/zenodo.4107192

Eccel, R. A. L. and R. C. Carlson (2019) Problemas Dinâmicos de Coleta e Entrega com Janelas de Tempo: Análise das Instân-cias de Benchmark. 33º Congresso da Associação Nacional de Pesquisa e Ensino em Transportes, ANPET, Balneário Camboriú. Available at: < http://www.anpet.org.br/anais/documentos/2019/Log%C3%ADstica/Log%C3%ADstica%20Urbana%20e%20Planejamento%20e%20Opera%C3%A7%C3%A3o%20de%20Sistemas%20Log%C3%ADsticos/6_603_AC.pdf> (accessed on 19/10/2020).

Fabri, A. and P. Recht (2006) On Dynamic Pickup and Delivery Vehicle Routing with Several Time Windows and Waiting Times. Transportation Research Part B: Methodological, v. 40, n. 4, p. 335–350. DOI: 10.1016/j.trb.2005.04.002

Fulton, L.; J. Mason and D. Meroux (2017) Three Revolutions in Urban Transportation. Institute for Transportation & Develop-ment Policy, Davis, CA.

Gendreau, M.; F. Guertin; J.-Y. Potvin and R. Séguin (2006) Neighborhood Search Heuristics for a Dynamic Vehicle Dispatching Problem with Pick-Ups and Deliveries. Transportation Research Part C: Emerging Technologies, v. 14, n. 3, p. 157–174. DOI: 10.1016/j.trc.2006.03.002

Li, H. and A. Lim (2003) A Metaheuristic for the Pickup and Delivery Problem with Time Windows. International Journal on Artificial Intelligence Tools, v. 12, n. 2, p. 173–186. DOI: 10.1142/S0218213003001186

Maciejewski, M.; J. Bischoff; S. Hörl and K. Nagel (2017) Towards a Testbed for Dynamic Vehicle Routing Algorithms. In: Bajo, J.; Z. Vale; K. Hallenborg; A. P. Rocha; P. Mathieu; P. Pawlewski; E. Del Val; P. Novais; F. Lopes; N. D. Duque Méndez; V. Julián and J. Holmgren (eds.) Highlights of Practical Applications of Cyber-Physical Multi-Agent Systems. Communications in Com-puter and Information Science. Springer International Publishing, p. 69–79. DOI: 10.1007/978-3-319-60285-1_6

Mendoza, J. E.; C. Guéret; M. Hoskins; H. Lobit; V. Pillac; T. Vidal and D. Vigo (2014) VRP-REP: The Vehicle Routing Problem Repository. Third meeting of the EURO Working Group on Vehicle Routing and Logistics Optimization (VeRoLog). Oslo, Norway.

Mitrovic-Minic, S. and G. Laporte (2004) Waiting strategies for the dynamic pickup and delivery problem with time windows. Transportation Research Part B: Methodological, v. 38, n. 7, p. 635–655. DOI: 10.1016/j.trb.2003.09.002

Pankratz, G. (2005) Dynamic Vehicle Routing by Means of a Genetic Algorithm. International Journal of Physical Distribution & Logistics Management, v. 35, n. 5, p. 362–383. DOI: 10.1108/09600030510607346

Pankratz, G. and V. Krypczyk (2009) Benchmark Data Sets for Dynamic Vehicle Routing Problems. Available at: (accessed on 01/07/2020).

Parragh, S. N.; K. F. Doerner and R. F. Hartl (2008) A Survey on Pickup and Delivery Problems: Part II: Transportation Be-tween Pickup and Delivery Locations. Journal für Betriebswirtschaft, v. 58, n. 2, p. 81–117.

Pillac, V.; M. Gendreau; C. Guéret and A. L. Medaglia (2013) A Review of Dynamic Vehicle Routing Problems. European Journal of Operational Research, v. 225, n. 1, p. 1–11. DOI: 10.1016/j.ejor.2012.08.015

Psaraftis, H. N. (1988) Dynamic Vehicle Routing Problems. In: Vehicle Routing: Methods and Studies. North-Holland, p. 223–248.

Psaraftis, H. N.; M. Wen and C. A. Kontovas (2015) Dynamic Vehicle Routing Problems: Three Decades and Counting. Net-works, v. 67, n. 1, p. 3–31. DOI: 10.1002/net.21628

Pureza, V. and G. Laporte (2008) Waiting and Buffering Strategies for the Dynamic Pickup and Delivery Problem with Time Windows. INFOR: Information Systems and Operational Research, v. 46, n. 3, p. 165–175. DOI: 10.3138/infor.46.3.165

Ropke, S.; J.-F. Cordeau and G. Laporte (2007) Models and Branch-and-Cut Algorithms for Pickup and Delivery Problems with Time Windows. Networks, v. 49, n. 4, p. 258–272. DOI: 10.1002/net.20177

Schilde, M.; K. F. Doerner and R. F. Hartl (2011) Metaheuristics for the Dynamic Stochastic Dial-a-Ride Problem with Expected Return Transports. Computers & Operations Research, v. 38, n. 12, p. 1719–1730. DOI: 10.1016/j.cor.2011.02.006

Uchoa, E.; D. Pecin; A. Pessoa; M. Poggi; T. Vidal and A. Subramanian (2017) New Benchmark Instances for the Capacitated Vehicle Routing Problem. European Journal of Operational Research, v. 257, n. 3, p. 845–858. DOI: 10.1016/j.ejor.2016.08.012

Van Lon, R. R. R. S.; E. Ferrante; A. E. Turgut; T. Wenseleers; G. Vanden Berghe and T. Holvoet (2016) Measures of Dynamism and Urgency in Logistics. European Journal of Operational Research, v. 253, n. 3, p. 614–624. DOI: 10.1016/j.ejor.2016.03.021




DOI: https://doi.org/10.14295/transportes.v28i4.2412

Métricas do artigo

Carregando Métricas ...

Metrics powered by PLOS ALM


Direitos autorais 2020 Renan Artur Lopes Eccel, Rodrigo Castelan Carlson

TRANSPORTES (ISSN: 2237-1346) é uma publicação da ANPET - Associação Nacional de Pesquisa e Ensino em Transportes (www.anpet.org.br)

 

Licença Creative Commons

Este obra está licenciado com uma Licença Creative Commons Atribuição-NãoComercial-CompartilhaIgual 4.0 Internacional.