Analysis of pick-up and delivery and dial-a-ride problems dynamization methods and benchmark instances
DOI:
https://doi.org/10.14295/transportes.v28i4.2412Keywords:
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
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
Versions
- 2021-04-27 (3)
- 2021-04-27 (2)
- 2020-11-16 (1)
How to Cite
Issue
Section
License
Copyright (c) 2020 Renan Artur Lopes Eccel, Rodrigo Castelan Carlson
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who submit papers for publication by TRANSPORTES agree to the following terms:
- Authors retain copyright and grant TRANSPORTES the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors may enter into separate, additional contractual arrangements for the non-exclusive distribution of this journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in TRANSPORTES.
- Authors are allowed and encouraged to post their work online (e.g., in institutional repositories or on their website) after publication of the article. Authors are encouraged to use links to TRANSPORTES (e.g., DOIs or direct links) when posting the article online, as TRANSPORTES is freely available to all readers.
- Authors have secured all necessary clearances and written permissions to published the work and grant copyright under the terms of this agreement. Furthermore, the authors assume full responsibility for any copyright infringements related to the article, exonerating ANPET and TRANSPORTES of any responsibility regarding copyright infringement.
- Authors assume full responsibility for the contents of the article submitted for review, including all necessary clearances for divulgation of data and results, exonerating ANPET and TRANSPORTES of any responsibility regarding to this aspect.
