Analysis of pick-up and delivery and dial-a-ride problems dynamization methods and benchmark instances
DOI:
https://doi.org/10.14295/transportes.v28i4.2412Palavras-chave:
Dinamização. Instâncias de benchmark. DDARP. DPDPTW.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.
Downloads
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: <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
Publicado
Versões
- 27-04-2021 (3)
- 27-04-2021 (2)
- 16-11-2020 (1)
Como Citar
Edição
Seção
Licença
Ao submeter um manuscrito para publicação neste periódico, todos os seus autores concordam, antecipada e irrestritamente, com os seguintes termos:
- Os autores mantém os direitos autorais e concedem à Revista TRANSPORTES o direito de primeira publicação do manuscrito, sem nenhum ônus financeiro, e abrem mão de qualquer outra remuneração pela sua publicação pela ANPET.
- Ao ser submetido à Revista TRANSPORTES, o manuscrito fica automaticamente licenciado sob a Licença Creative Commons Attribution, que permite o compartilhamento do trabalho com reconhecimento da autoria e da publicação inicial neste periódico.
- Os autores têm autorização para assumir contratos adicionais separadamente, para distribuição não exclusiva da versão do trabalho publicada neste periódico (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento da publicação inicial nesta revista, desde que tal contrato não implique num endosso do conteúdo do manuscrito ou do novo veículo pela ANPET.
- Os autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) depois de concluído o processo editorial. Como a Revista TRANSPORTES é de acesso livre, os autores são estimulados a usar links para o site da Revista TRANSPORTES nesses casos.
- Os autores garantem ter obtido a devida autorização dos seus empregadores para a transferência dos direitos nos termos deste acordo, caso esses empregadores possuam algum direito autoral sobre o manuscrito. Além disso, os autores assumem toda e qualquer responsabilidade sobre possíveis infrações ao direito autoral desses empregadores, isentando a ANPET e a Revista TRANSPORTES de toda e qualquer responsabilidade neste sentido.
- Os autores assumem toda responsabilidade sobre o conteúdo do trabalho, incluindo as devidas e necessárias autorizações para divulgação de dados coletados e resultados obtidos, isentando a ANPET e a Revista TRANSPORTES de toda e qualquer responsabilidade neste sentido.
