Grafo para la evaluación automática de soluciones vecinas en problemas de enrutamiento de vehículos
DOI:
https://doi.org/10.5281/zenodo.14333111Palabras clave:
grafo de evaluación, evaluación automática de soluciones vecinas, problema de enrutamiento de vehículos, MSC 90B06, MSC 90C59, MSC 68T20, MSC 90C27Resumen
En este trabajo se presenta el concepto de grafo de evaluación para una solución de un Problema de Enrutamiento de Vehículos. A partir de este grafo es posible obtener el costo de una solución vecina de una manera eficiente y automática. Que el costo se obtenga de manera eficiente significa que para calcularlo se realizan la menor cantidad de operaciones posible. Que sea automático significa que no es necesario programar un código para calcularlo, solo es necesario programar cómo se evalúa una solución cualquiera. Para evaluar la factibilidad de usar esta propuesta, se comparan los tiempos de ejecución de dos variantes de un algoritmo para resolver el problema de Enrutamiento de Vehículos con Restricciones de Capacidad. En la primera variante, el costo de los vecinos se calcula usando la propuesta presentada en este trabajo, mientras que en la segunda variante este costo se calcula usando un método en el que se usan todas las optimizaciones posibles para ese problema específico. Los tiempos de ejecución de la propuesta realizada están entre 1,72 y 4,17 veces el tiempo del algoritmo optimizado para ese problema específico, y tiene la ventaja de que no es necesario programar un método que calcule el costo de los vecinos, ya que este se obtiene a partir del grafo de evaluación.
Descargas
Citas
Arnold, F. y K. Sorensen: Knowledge-guided local search for the vehicle routing problem. Computers & Operations Research, 105:32–46, 2019. https://www.sciencedirect.com/science/article/pii/S0305054819300024.
Asghari, M., S. Mirzapour Al-e hashem y J. Mohammad: Green vehicle routing problem: A state-of-the-art review. International Journal of Production Economics, 231, jan 2021. https://www.sciencedirect.com/science/article/pii/S0925527320302607.
Dantzig, G.B. y J.H. Ramser: The Truck Dispatching Problem. Management Science, 6, Octubre 1959. https://pubsonline.informs.org/doi/abs/10.1287/mnsc.6.1.80.
Derbel, H., B. Jarboui y P. Siarry: Green Transportation and New Advances in Vehicle Routing Problems. Springer, 2020, ISBN 9783030453114. https://link.springer.com/book/10.1007/978-3-030-4
-1.
Erdelic, T. y T. Caric: A Survey on the Electric Vehicle Routing Problem: Variants and Solution Approaches. Journal of Advanced Transportation, 2019, may 2019. https://onlinelibrary.wiley.com/doi/abs/10.1155/2019/5075671.
Gendreau, M. y J. Y. Potvin: Handbook of Metaheuristics. International Series in Operations Research & Management Science 272. Springer International Publishing, 3rd edición, 2019. https://link.sprin ger.com/book/10.1007/978-3-319-91086-4.
Ghorbani, E., M. Alinaghian, G.B. Gharehpetian, S. Mohammadi y G. Perboli: A Survey on Environmentally Friendly Vehicle Routing Problem and a Proposal of Its Classification. Sustainability, 12, oct 2020. https://www.mdpi.com/2071-1050/12/21/9079.
Goel, R. y R. Maini: Vehicle routing problem and its solution methodologies: a survey. International Journal of Logistics Systems and Management vol. 28 iss. 4, 28, 2017. https://www.inderscienceonline.com/doi/abs/10.1504/IJLSM.2017.087786.
Griewank, A. y A.Walther: Evaluating derivatives: principles and techniques of algorithmic differentiation. Society for Industrial and Applied Mathematic, second edición, 2008. https://epubs.siam.org/doi/pdf/10.1137/1.9780898717761.bm.
Groer, C., B. Golden y E.Wasil: A library of local search heuristics for the vehicle routing problem. Mathematical Programming Computation, 2, apr 2010. https://link.springer.com/article/10.1007/s12532-010-0013-5.
Hansen, P., N. Mladenovic y J.A. Moreno Perez: Variable neighbourhood search: methods and applications. 4OR: A Quarterly Journal of Operations Research, 6, nov 2008. https://link.springer.com/article/10.1007/s10288-008-0089-1.
Hof, J. y M. Schneider: An adaptive large neighborhood search with path relinking for a class of vehicle routing problems with simultaneous pickup and delivery. Networks, 74, apr 2019. https://onlinelibrary.wiley.com/doi/abs/10.1002/net.21879.
Laporte, G.: Fifty Years of Vehicle Routing. Transportation Science, 43, nov 2009. https://pubsonline.informs.org/doi/abs/10.1287/trsc.1090.0301.
Lima, I. y colaboradores: CVRPLIB: Capacitated Vehicle Routing Problem Library. http://vrp.atd-lab.inf.puc-rio.br.
Marwa, A., T. Said, J. Bassem y E. Mansour: A variable neighborhood search algorithm for the capacitated vehicle routing problem. Electronic Notes in Discrete Mathematics, 58, Abril 2017. https://www.sciencedirect.com/science/article/pii/S1571065317300665.
Mohamed, N.H., S. Salhi, G. Nagy y N.A. Mohamed: A matheuristic approach for the split delivery vehicle routing problem: an efficient set covering-based model with guided route generation schemes. International Journal of Mathematics in Operational Research, 2019. https://www.inderscienceonline.com/doi/abs/10.1504/IJMOR.2019.101613.
Montagné, R., D. Torres Sanchez y H.O. Storbugt: VRPy: A Python package for solving a range of vehicle routing problems with a column generation approach. Journal of Open Source Software, 5(55):2408, 2020. https://joss.theoj.org/papers/10.21105/joss.02408.pdf.
Mor, A. y M.G. Speranza: Vehicle routing problems over time: a survey. 4OR: A Quarterly Journal of Operations Research, mar 2020. https://link.springer.com/article/10.1007/s10479-021-04488-0.
Pop, P.C. y A. Horvat-Marc: Local search heuristics for the generalized vehicle routing problem. En 2012 International Conference on System Modeling and Optimization (ICSMO 2012), IPCSIT, volumen 23, páginas 84–87, 2012. https://www.academia.edu/download/41333655/Local_search_heuristics_for_the_generali20160119-18577-l8g8ng.pdf.
Praveen, V., P. Keerthika, A. Sarankumar y G. Sivapriya: A Survey on Various Optimization Algorithms to Solve Vehicle Routing Problem. En IEEE 2019 5th International Conference on Advanced Computing & Communication Systems (ICACCS). IEEE, mar 2019. https://ieeexplore.ieee.org/abstract/document/8728417/.
Prodhon, C. y C. Prins: Metaheuristics for Vehicle Routing Problems, páginas 407–437. Springer International Publishing, 2016. https://link.springer.com/chapter/10.1007/978-3-319-45403-0_15.
Tolga, K.C., J. Ola y L. Gilbert: Thirty years of heterogeneous vehicle routing. European Journal of Operational Research 2016-feb vol. 249 iss. 1, 249, feb 2016. https://www.sciencedirect.com/science/article/pii/S0377221715006530.
Toth, P. y D. Vigo: The Vehicle Routing Problem Problems, Methods, and Applications. Monographs on Discrete Mathematics and Applications. SIAM, 2a edición, 2014, ISBN 1611973589. https://epubs.siam.org/doi/abs/10.1137/1.9781611973594.fm.
Villavicencio Sánchez, E.D. Nuñez de: Propuesta de exploración ágil de cualquier vecindad en un VRP. Tesis de Diploma, Facultad de Matemática y Computación, Universidad de La Habana, 2018.
Wang, X., Tsan Ming Choi, Zhiying Li y Shuai Shao: An Effective Local Search Algorithm for the Multidepot Cumulative Capacitated Vehicle Routing Problem. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 50(12):4948–4958, 2020. https://ieeexplore.ieee.org/abstract/document/8844993/.
Publicado
Versiones
- 2024-06-27 (6)
- 2025-09-12 (5)
- 2025-06-17 (4)
- 2025-06-17 (3)
- 2024-12-09 (2)
- 2024-12-09 (1)
Cómo citar
Número
Sección
Licencia
Derechos de autor 2024 Fernando Raul Rodriguez Flores, José J. Rodríguez Salgado
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0.
Esta licencia permite copiar y redistribuir el material en cualquier medio o formato bajo los siguientes términos: se debe dar crédito de manera adecuada, no se puede hacer uso del material con propósitos comerciales, y si remezcla, transforma o crea a partir del material, no podrá distribuir el material modificado. Bajo la licencia mencionada, los autores mantienen los derechos de autor de su trabajo.
