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

Resumen


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.

Texto completo:

PDF

Referencias


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. Rev. Col. Tec. De Avan., p.2-11.

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. Rev. Col. Tec. De Avan., p.91-97.

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. Rev. Col. Tec. De Avan., p.60-66.

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.




DOI: https://doi.org/10.24054/16927257.v31.n31.2018.2774

Enlaces refback

  • No hay ningún enlace refback.

Comentarios sobre este artículo

Ver todos los comentarios