Solución del MDVRP usando el algoritmo de búsqueda local iterada

Daniela  Ospina Toro; Eliana Mirledy  Toro Ocampo; Ramón Alfonso  Gallego Rendón

doi:10.24054/rcta.v1i31.139

Authors

Daniela Ospina Toro Universidad Tecnológica de Pereira
Eliana Mirledy Toro Ocampo Universidad Tecnológica de Pereira
Ramón Alfonso Gallego Rendón Universidad Tecnológica de Pereira

DOI:

https://doi.org/10.24054/rcta.v1i31.139

Keywords:

clusterización, heurísticas, ILS, infactibilidad, MDVRP

Abstract

En este artículo se propone una metodología para resolver el problema de ruteo considerando múltiples depósitos (MDVRP). El modelo contempla situaciones con y sin restricción de distancia. En el proceso de búsqueda se aceptan soluciones infactibles por sobrecarga en vehículos, depósitos y longitud de ruta, las cuales son llevadas como penalidades en la función objetivo. Para su solución es implementado el algoritmo de Búsqueda Local Iterada (Iterated Local Search). En la construcción de la solución inicial se usan heurísticas basadas en técnicas de clusterización. La metodología es verificada usando casos de prueba de la literatura, los resultados obtenidos y tiempos de cómputo son comparados con los registros existentes.

Downloads

Download data is not yet available.

References

Alvaréz, D., Toro-Ocampo, E., Gallego- Rendón, R. (2010). Algoritmo GRASP para resolver el problema de asignación de horarios en empresas de demanda variable. Revista Colombiana de Tecnologías de Avanzada (RCTA), ISSN: 1692-7257, 2(16).

Araque, J. A., Rodríguez, J. L. D., & Guerrero, A. S. (2017). Optimización por recocido simulado de un convertidor multinivel monofásico con modulación pwm sinusoidal de múltiple portadora. Revista Colombiana de Tecnologias de Avanzada, ISSN: 1692-7257, 1(27).

Araque, J. A., Díaz, J. L., & Gualdrón, O. E. (2013). Optimización del THD en un convertidor multinivel monofásico usando algoritmos genéticos. Revista Colombiana De Tecnologías De Avanzada, ISSN: 1692-7257, 1(21).

Clarke, G., & Wright, J. W. (1964). Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 12(4), 568–581.

Tillman, F. A. (1969). The Multiple Terminal Delivery Problem with Probabilistic Demands.pdf. Transportation Science, 3(3), 192–204.

Tillman, F. A., & Cain, T. M. (1972). An Upperbound Algorithm for the Single and Multiple Terminal Delivery Problem. Management Science, 18(11), 664–682.

Wren, A., & Holliday, A. (1972). Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points. Operational Research Quarterly (1970-1977), 23(3), 333–344.

Gillett, B. E., & Johnson, J. G. (1976). Multi-terminal vehicle-dispatch algorithm. Omega, 4(6), 711-718.

Gillett, B., & Miller, L. (1974). A Heuristic algorithm for the vehicle dispatch problem. European Journal of Operational Research, 22, 340–349.

Christofides, N., & Eilon, S. (1998). An Algorithm for the Vehicle-dispatiching Problem. Journal of the Operational Research Society, 8(2), 415–422.

Golden, B. L., Magnanti, T. L., & Nguyen, H. Q. (1977). Implementing vehicle routing algorithms. Networks, 7(2), 113–148.

Wasil, E., & Golden, B. L. (1993). A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions. American Journal of Mathematical and Management Sciences, 13(3–4), 371–406.

Dueck, G. (1993). New optimization heuristics; The great deluge algorithm and the record-to-record travel. Journal of Computational Physics, 104(1), 86–92.

S. Lin. (1965). Computer Solutions of the Traveling Salesman Problem. Bell System Technical Journal, 44(10), 2245–2269.

Renaud, J., Laporte, G., & Boctor, F. F. (1996). A tabu search heuristic for the multi-depot vehicle routing problem. Computers and Operations Research, 23(3), 229–235.

Renaud, J., Boctor, F. F., & Laporte, G. (1996). An improved petal heuristic for the vehicle routing problem. Journal of the Operational Research Society, 47(2), 329–336.

Cordeau, J. F., Gendreau, M., & Laporte, G. (1997). A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks, 30, 105–119.

Gendreau, M., Hertz, A., & Laporte, G. (1994). A Tabu Search Heuristic for the Vehicle Routing Problem. Management Science, 40(10), 1276–1290.

Salhi, S., & Sari, M. (1997). A multi-level composite heuristic for the multi-depot vehicle fleet mix problem. European Journal of Operational Research, 103(1), 95–112.

Ho, W., Ho, G. T. S., Ji, P., & Lau, H. C. W. (2008). A hybrid genetic algorithm for the multi-depot vehicle routing problem. Advances in Computer Science: Proceedings of the 6th WSEAS European Computing Conference (ECC’12).

Surekha, P., & Sumathi, S. (2011). Solution To Multi-Depot Vehicle Routing Problem Using Genetic Algorithms. World Applied Programming, (13), 118–131.

Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N., & Rei, W. (2012). A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems. Operations Research, 60(3), 611–624.

Laporte, G., Nobert, Y., & Arpin, D. (1984). Optimal solutions to capacitated multidepot vehicle routing problems, Vol. 44. Congressus Numerantium, Canada.

Laporte, G., Nobert, Y., & Taillefer, S. (1988). Solving a Family of Multi-Depot Vehicle Routing and Location-Routing Problems. Transportation Science, 22(3), 161–172.

Baldacci, R., & Mingozzi, A. (2009). A unified exact method for solving different classes of vehicle routing problems. Mathematical Programming, 120(2), 347–380.

Contardo, C., & Martinelli, R. (2014). A new exact algorithm for the multi-depot vehicle routing problem under capacity and route length constraints. Discrete Optimization, 12(1), 129–146.

Montoya-Torres, J. R., López Franco, J., Nieto Isaza, S., Felizzola Jiménez, H., & Herazo-Padilla, N. (2015). A literature review on the vehicle routing problem with multiple depots. Computers & Industrial Engineering, 79, 115–129.

Jain, A. K., & Dubes, R. C. (1988). Algorithms for clustering data. Prentice Hall.

Dantzig, G. B., & Ramser, J. H. (1959). The Truck Dispatching Problem. Management Science, 6(1), 80–91. https://doi.org/10.1287/mnsc.6.1.80

Barreto, S., Ferreira, C., Paixão, J., & Santos, B. S. (2007). Using clustering analysis in a capacitated location-routing problem. European Journal of Operational Research, 179(3), 968–977. https://doi.org/10.1016/j.ejor.2005.06.074

Zare Mehrjerdi, Y., & Nadizadeh, A. (2013). Using greedy clustering method to solve capacitated location-routing problem with fuzzy demands. European Journal of Operational Research, 229(1), 75–84.

Ocampo, E. M. T., Castaño, A. H. D., & Zuluaga, A. H. E. (2016). Desempeño de las técnicas de agrupamiento para resolver el problema de ruteo con múltiples depósitos. Tecno Lógicas, 19(36), 49–62. Retrieved from

Subramanian, A., & Dos Anjos Formiga Cabral, L. (2008). An ILS based heuristic for the vehicle routing problem with simultaneous pickup and delivery and time limit. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 4972 LNCS, pp. 135–146).

Subramanian, A., Drummond, L. M. A., Bentes, C., Ochi, L. S., & Farias, R. (2010). A parallel heuristic for the Vehicle Routing Problem with Simultaneous Pickup and Delivery. Computers & Operations Research, 37(11), 1899–1911.

Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2014). Implicit depot assignments and rotations in vehicle routing heuristics. European Journal of Operational Research, 237(1), 15–28.