A neighborhood search-based heuristic for the dynamic vehicle routing problem

Wilton Gustavo Gomes da Costa

ORCID iD Federal University of Mato Grosso do Sul (UFMS), Campo Grande, Mato Grosso do Sul, Brasil

Ricardo Santos

ORCID iD Federal University of Mato Grosso do Sul (UFMS), Campo Grande, Mato Grosso do Sul, Brasil

Willy Alves de Oliveira Soler

ORCID iD Federal University of Mato Grosso do Sul (UFMS), Campo Grande, Mato Grosso do Sul, Brasil

Bianca de Almeida Dantas

ORCID iD Federal University of Mato Grosso do Sul (UFMS), Campo Grande, Mato Grosso do Sul, Brasil

Resumo

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.

Palavras-chave


2-Opt*; DSNR; dynamic vehicle routing; local search heuristic; k-means greedy; QRP sweep


Texto completo:

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.


DOI: http://dx.doi.org/10.18265/2447-9187a2024id8297

O arquivo PDF selecionado deve ser carregado no navegador caso tenha instalado um plugin de leitura de arquivos PDF (por exemplo, uma versão atual do Adobe Acrobat Reader).

Como alternativa, pode-se baixar o arquivo PDF para o computador, de onde poderá abrí-lo com o leitor PDF de sua preferência. Para baixar o PDF, clique no link abaixo.

Caso deseje mais informações sobre como imprimir, salvar e trabalhar com PDFs, a Highwire Press oferece uma página de Perguntas Frequentes sobre PDFs bastante útil.

Download do PDF
Imprimir artigo
Exibir metadados
Como citar este documento

Visitas a este artigo: 23

Total de downloads do artigo: 38