Analysis of pick-up and delivery and dial-a-ride problems dynamization methods and benchmark instances

Authors

DOI:

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

Keywords:

Dynamization. Benchmark instances. DDARP. DPDPTW.

Abstract

The available benchmarks for the dynamic versions of the Pickup and Delivery Problem with Time Windows (PDPTW) and the Dial-A-Ride Problem (DARP) do not share the same characteristics and may not cover all the range of characteristics of real situations. We analyze sets of instances of the dynamic PDPTW (DPDPTW) and the dynamic DARP (DDARP) currently available for use, and the methods used to generate them from static instances. We apply each dynamization method to each of the static instances that were originally used by these methods. The resulting dynamic instances are analyzed with the measures of degree of dynamism and urgency, as well as with the number of static requests and the correlation between lower limits of the pickup time window and the requests arrival times. The results show that the obtained dynamic instances present low variability in the degree of dynamism and urgency, irrespective of the method or static instance used for dynamization.

Downloads

Download data is not yet available.

Author Biographies

Renan Artur Lopes Eccel, Federal University of Santa Catarina

Programa de Pós-Graduação em Engenharia de Automação e Sistemas

Rodrigo Castelan Carlson, Federal University of Santa Catarina

Programa de Pós-Graduação em Engenharia de Automação e Sistemas

References

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: <http://tede.ufsc.br/teses/PEAS0339-D.pdf> (accessed on 19/10/2020).

Eccel, R. A. L. (2020) renan-eccel/instances-DDARP-DPDPTW: v1.2. Available at: <https://zenodo.org/record/4107192> (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:<https://web.archive.org/web/20120622022350/http://www.fernuni-hagen.de:80/WINF/inhalte/benchmark_data.htm> (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

Downloads

Published

2020-11-16 — Updated on 2021-04-27

Versions

How to Cite

Eccel, R. A. L., & Carlson, R. C. (2021). Analysis of pick-up and delivery and dial-a-ride problems dynamization methods and benchmark instances. TRANSPORTES, 28(4), 103–116. https://doi.org/10.14295/transportes.v28i4.2412 (Original work published November 16, 2020)

Issue

Section

Artigos Vencedores do Prêmio ANPET Produção Científica