A neighborhood search-based heuristic for the dynamic vehicle routing problem
DOI:
https://doi.org/10.18265/2447-9187a2024id8297Palavras-chave:
2-Opt*, DSNR, dynamic vehicle routing, local search heuristic, k-means greedy, QRP sweepResumo
The Vehicle Routing Problem (VRP) is a classical optimization problem that aims to find routes for a fleet of vehicles to meet the demands of a set of customers. Due to its wide applicability, especially in the logistics sector, numerous VRP variants exist. One such variant is the Dynamic Vehicle Routing Problem (DVRP), where new customer demands may arise after the initial routing has been defined. The combinatorial nature of the DVRP makes it challenging to find high-quality feasible solutions within a reasonable runtime for real-world large-sized problems, motivating the development of heuristic approaches to address this issue. This paper presents a new heuristic algorithm, Dynamic Search per Neighbors Routes (DSNR), which uses neighborhood search approaches based on the 2-Opt* operator to allocate new delivery packages to existing routes. The DSNR algorithm was evaluated on instances from the Loggibud benchmark, representing real data from three different Brazilian cities. Regarding distance and number of vehicles, the proposed approach outperforms two other techniques from the literature: the QRP Sweep (QRPS) and the K-Means Greedy (KG). The DSNR achieved gains ranging from 15% to 17% in distance and final delivery costs.
Downloads
Referências
BARÁN, B.; SCHAERER, M. A multiobjective ant colony system for vehicle routing problem with time windows. In: IASTED CONFERENCE APPLIED INFORMATICS, 21., 2003, Innsbruck. Proceedings […]. Innsbruck, 2003, p. 97-102, 2003. Available at: https://www.cnc.una.py/publicaciones/1_75.pdf. Accessed on: 11 june 2024.
BERTSIMAS, D. J.; VAN RYZIN, G. Stochastic and dynamic vehicle routing with general demand and interarrival time distributions. Advances in Applied Probability, v. 25, n. 4, p. 947-978, 1993. DOI: https://doi.org/10.2307/1427801.
BRÄYSY, O.; GENDREAU, M. Vehicle routing problem with time windows, Part II: Metaheuristics. Transportation Science, v. 39, n. 1, p. 119-139, 2005. DOI: https://doi.org/10.1287/trsc.1030.0057.
CHEN, S.; CHEN, R.; GAO, J. A monarch butterfly optimization for the dynamic vehicle routing problem. Algorithms, v. 10, n. 3, 107, 2017. DOI: https://doi.org/10.3390/a10030107.
COMERT, S. E.; YAZGAN H. R.; KIR S.; YENER F. A cluster first-route second approach for a capacitated vehicle routing problem: a case study. International Journal of Procurement Management (IJPM), v. 11, n. 4, p. 399-419, 2018. DOI: https://dx.doi.org/10.1504/IJPM.2018.092766.
DANTZIG, G. B.; RAMSER, J. H. The truck dispatching problem. Management Science, v. 6, n. 1, p. 80-91, 1959.
FAHRION, R.; WREDE, M. On a principle of chain-exchange for vehicle-routing problems (1-VRP). Journal of the Operational Research Society, v. 41, n. 9, p. 821-827, 1990.
FONSECA-GALINDO, J. C.; SURITA, G. C.; MAIA NETO, J.; CASTRO, C. L.; LEMOS, A. P. A multi-agent system for solving the dynamic capacitated vehicle routing problem with stochastic customers using trajectory data mining. Expert Systems with Applications, v. 195, 116602, 2022. DOI: https://doi.org/10.1016/j.eswa.2022.116602.
GAMBARDELLA, L. M.; TAILLARD, É.; AGAZZI, G. MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. In: CORNE, D.; DORIGO, M.; GLOVER, F. (ed.). New ideas in optimization. London: McGraw-Hill, 1999. p. 63-76.
GILLETT, B. E.; MILLER, L. R. A heuristic algorithm for the vehicle-dispatch problem. Operations Research, v. 22, n. 2, p. 340-349, 1974.
HONG, L. An improved LNS algorithm for real-time vehicle routing problem with time windows. Computers & Operations Research, v. 39, n. 2, p. 151-163, 2012. DOI: https://doi.org/10.1016/j.cor.2011.03.006.
KILBY, P.; PROSSER, P.; SHAW, P. Dynamic VRPs: a study of scenarios. Report APES-06-1998. University of Strathclyde Technical Report, v. 1, n. 11, 1998.
KOÇ, Ç.; BEKTA?, T.; JABALI, O.; LAPORTE, G. Thirty years of heterogeneous vehicle routing. European Journal of Operational Research, v. 249, n. 1, p. 1-21, 2016. DOI: https://doi.org/10.1016/j.ejor.2015.07.020.
LACKNER, A. Dynamische Tourenplanung mit ausgewählten metaheuristiken: eine untersuchung am beispiel des kapazitätsrestriktiven dynamischen tourenplanungsproblems mit zeitfenstern. Göttingen: Cuvillier Verlag, 2004. (Göttinger Wirtschaftsinformatik).
LARSEN, A. The dynamic vehicle routing problem. 2000. Ph.D Thesis (Doctorate in Mathematical Modelling) – Technical University of Denmark, Lyngby, 2000. Available at: https://backend.orbit.dtu.dk/ws/portalfiles/portal/5261816. Accessed on: 11 june 2024.
LARSEN, A.; MADSEN, O.; SOLOMON, M. Partially dynamic vehicle routing: models and algorithms. Journal of the Operational Research Society, v. 53, n. 6, p. 637-646, 2002. DOI: https://doi.org/10.1057/palgrave.jors.2601352.
LENSTRA, J. K.; KAN, A. H. G. R. Complexity of vehicle routing and scheduling problems. Networks, v. 11, p. 221-227, 1981. DOI: https://doi.org/10.1002/net.3230110211.
LOGGIBUD. loggiBUD: Loggi Benchmark for Urban Deliveries. 2021. GitHub repository. Available at: https://github.com/loggi/loggibud. Accessed on: 11 june 2024.
MARINAKIS, Y.; MARINAKI, M. A hybrid genetic: particle swarm optimization algorithm for the vehicle routing problem. Expert Systems with Applications, v. 37, n. 2, p. 1446-1455, 2010. DOI: https://doi.org/10.1016/j.eswa.2009.06.085.
MARINAKIS, Y.; MIGDALAS, A.; PARDALOS, P. M. Multiple phase neighborhood search: GRASP based on Lagrangean relaxation, random backtracking Lin-Kernighan and path relinking for the TSP. Journal of Combinatorial Optimization, v. 17, n. 2, p. 134-156, 2009. DOI: https://doi.org/10.1007/s10878-007-9104-2.
MILLER, C. E.; TUCKER, A. W.; ZEMLIN, R. A. Integer programming formulation of traveling salesman problems. Journal of the ACM (JACM), v. 7, n. 4, p. 326-329, 1960. DOI: https://doi.org/10.1145/321043.321046.
MONTEMANNI, R.; GAMBARDELLA, L. M.; RIZZOLI, A. E.; DONATI, A. V. Ant colony system for a dynamic vehicle routing problem. Journal of Combinatorial Optimization, v. 10, n. 4, p. 327-343, 2005. DOI: https://doi.org/10.1007/s10878-005-4922-6.
NECULA, R.; BREABAN, M.; RASCHIP, M. Tackling dynamic vehicle routing problem with time windows by means of ant colony system. In: 2017 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC), 2017, Donostia. Proceedings […]. Donostia: IEEE, 2017. p. 2480-2487. DOI: https://doi.org/10.1109/CEC.2017.7969606.
PILLAC, V.; GENDREAU, M.; GUÉRET, C.; MEDAGLIA, A. L. A review of dynamic vehicle routing problems. European Journal of Operational Research, v. 225, n. 1, p. 1-11, 2013. DOI: https://doi.org/10.1016/j.ejor.2012.08.015.
PILLAC, V.; GUÉRET, C.; MEDAGLIA, A. A fast re-optimization approach for dynamic vehicle routing. Research Report, Ecole des Mines de Nantes, 2012. Available at: https://hal.science/hal-00739782. Accessed on: 11 june 2024.
PSARAFTIS, H. N. Dynamic vehicle routing problems. In: GOLDEN, B. L.; ASSAD, A. A. (ed.). Vehicle routing: methods and studies. North Holland: Elsevier, v. 16, p. 223-248, 1988.
RALPHS, T. K.; KOPMAN, L.; PULLEYBLANK, W. R.; TROTTER, L. E. On the capacitated vehicle routing problem. Mathematical Programming, v. 94, n. 2, p. 343-359, 2003. DOI: https://doi.org/10.1007/s10107-002-0323-0.
RESENDE, M. G. C.; RIBEIRO, C. C. Greedy randomized adaptive search procedures. In: GLOVER, F.; KOCHENBERGER, G. A. (Eds.). Handbook of metaheuristics. Boston: Springer, 2003. p. 219-249. DOI: https://doi.org/10.1007/0-306-48056-5_8.
RIOS, B. H. O.; XAVIER, E. C.; MIYAZAWA, F. K.; AMORIM, P.; CURCIO, E.; SANTOS, M. J. Recent dynamic vehicle routing problems: a survey. Computers & Industrial Engineering, v. 160, 107604, 2021. DOI: https://doi.org/10.1016/j.cie.2021.107604.
SILVA JÚNIOR, O. S.; LEAL, J. E.; REIMANN, M. A multiple ant colony system with random variable neighborhood descent for the dynamic vehicle routing problem with time windows. Soft Computing, v. 25, n. 4, p. 2935-2948, 2021. DOI: https://doi.org/10.1007/s00500-020-05350-4.
SOLOMON, M. M. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, v. 35, n. 2, p. 254-265, 1987.
VAN VEEN, B.; EMMERICH, M.; YANG, Z.; BÄCK, T.; KOK, J. Ant colony algorithms for the dynamic vehicle routing problem with time windows. In: VICENTE, J. M. F.; ÁLVAREZ SÁNCHEZ, J. R.; LÓPEZ, F. P.; MOREO, F. J. T. (eds.) Natural and artificial computation in engineering and medical applications. Berlin: Springer, 2013. p. 1-10. DOI: https://doi.org/10.1007/978-3-642-38622-0_1.
YANG, Z.; VAN OSTA, J.-P.; VAN VEEN, B.; VAN KREVELEN, R.; VAN KLAVEREN, R.; STAM, A.; KOK, J.; BÄCK, T.; EMMERICH, M. Dynamic vehicle routing with time windows in theory and practice. Natural Computing, v. 16, n. 1, p. 119-134, 2017. DOI: https://doi.org/10.1007/s11047-016-9550-9.
Downloads
Edição
Seção
Licença
• O(s) autor(es) autoriza(m) a publicação do artigo na revista;
• O(s) autor(es) garante(m) que a contribuição é original e inédita e que não está em processo de avaliação em outra(s) revista(s), nem esteja publicado em anais de congressos e/ou portais institucionais;
• A revista não se responsabiliza pelas opiniões, ideias e conceitos emitidos nos textos, por serem de inteira responsabilidade de seu(s) autor(es). Opiniões e perspectivas expressas no texto, assim como a precisão e a procedência das citações, são de responsabilidade exclusiva do(s) autor(es), e contribuem para a promoção dos:
- Princípios FAIR (Findable, Accessible, Interoperable, and Reusable – localizável, acessível, interoperável e reutilizável);
- Princípios DEIA (diversidade, equidade, inclusão e acessibilidade).
• É reservado aos editores o direito de proceder ajustes textuais e de adequação do artigos às normas da publicação.
Responsabilidades dos autores e transferência de direitos autorais
Os autores devem declarar a originalidade do estudo, bem como o fato de que este não foi publicado anteriormente ou está sendo considerado para publicação em outro meio, como periódicos, anais de eventos ou livros. Ao autorizarem a publicação do artigo na Revista Principia, os autores devem também responsabilizar-se pelo conteúdo do manuscrito, cujos direitos autorais, em caso de aprovação, passarão a ser propriedade exclusiva da revista. A Declaração de Responsabilidades dos Autores e Transferência de Direitos Autorais deverá ser assinada por todos os autores e anexada ao sistema como documento suplementar durante o processo de submissão. Clique no link abaixo para fazer o download do modelo.
Esta revista, seguindo as recomendações do movimento de Acesso Aberto, proporciona seu conteúdo em Full Open Access. Assim os autores conservam todos seus direitos permitindo que a Revista Principia possa publicar seus artigos e disponibilizar pra toda a comunidade.
A Revista Principia adota a licença Creative Commons 4.0 do tipo atribuição (CC-BY). Esta licença permite que outros distribuam, remixem, adaptem e criem a partir do seu trabalho, inclusive para fins comerciais, desde que lhe atribuam o devido crédito pela criação original.
Os autores estão autorizados a enviar a versão do artigo publicado nesta revista em repositório institucionais, com reconhecimento de autoria e publicação inicial na Revista Principia.
