Problema de Localización y Ruteo con Restricciones de Capacidad: Revisión de la Literatura

Resumen

En este artículo se hace una revisión exhaustiva del estado del arte de las metodologías de solución existentes para el problema combinado de localización y ruteo con restricciones de capacidad (CLRP). El problema de CLRP tiene una gran cantidad de aplicaciones prácticas en temas relacionados con transporte. Se ha propuesto el siguiente esquema de clasificación de acuerdo al método de solución: (1) Algoritmos Heurísticos Constructivos, (2) Algoritmos Heurísticos Basados en Clústeres, (3) Algoritmos Heurísticos Basados en Trayectoria, (4) Algoritmos Heurísticos Basados en Población, (5) Algoritmos Heurísticos Combinados, (6) Métodos Exactos. Se hace especial énfasis en fortalezas y debilidades de cada metodología publicada, identificando oportunidades de investigación y desarrollo en el área, en el contexto de la aplicación práctica de la problemática.

Palabras clave

Problemas de localización y ruteo, Revisión Literatura, Algoritmos Metaheurísticos, Métodos Exactos.

Referencias

• J. W. Escobar, R. Linfati and P. Toth, “A two-phase hybrid heuristic algorithm for the capacitated location-routing problem”, Computers & Operations Research,vol. 40 (1), pp. 70-79, 2012.
• G. Rand, “Methodological choices in depot location studies”,Operational Research Quarterly, vol. 27 (1), pp. 241-249, 1976.
• D. Tuzun, and L.I. Burke, “A two-phase tabú search approach to the location routing problem”, European Journal of Operational Research, vol. 116(1), pp. 87-99, 1999.
• C. Prins, C. Prodhon and R.W. Calvo.“Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking”, 4OR: A Quarterly Journal of Operations Research, vol. 4(3), pp. 221-238, 2006.
• S. Barreto et al., “Using clustering analysis in a capacitated location-routing problem”, European Journal of Operational Research, vol. 179(3), pp. 968-977, 2007.
• H. Min, V. Jayaraman and R. Srivastava “Combined location-routing problems: A synthesis and future research directions”, European Journal of Operational Research, vol. 108 (1), pp. 1-15, 1998.
• G. Nagy and S. Salhi, “Location-routing: issues, models and methods”,European Journal of Operational Research, vol. 177 (2), pp. 649-672, 2007.
• A. Hassanzadeh et al., Location-Routing Problem. Facility Location: Springer Verlag, 2009.
• C. Prodhon and C. Prins, “A survey of recent research on location-routing problems”, European Journal of Operational Research, vol. 238(1), pp. 1-17, 2014.
• C. Duhamel et al., “A GRASP×ELS approach for the capacitated location-routing problem”, Computers & Operations Research, vol. 37(11), pp. 1912-1923, 2010.
• G. Clarke and J.W. Wright, “Scheduling of vehicles from a central depot to a number of delivery points”, Operation Research,vol.12, pp. 568-581, 1964.
• S. Wolf and P. Merz, “Evolutionary local search for the super-peer selection problem and the p-hub median problem”, Lecture Notes in Computer Science, vol. 4771, pp. 1-15, 2007.
• R. B. Lopes et al.,“A decision-support tool for a capacitated location-routing problem”, Decision Support Systems, vol. 46(1), pp. 366-375, 2008.
• A. Nadizadehet al., “Using greedy clustering method to solve capacitated location-routing problem”, African Journal of Business Management, vol. 5(21), pp. 8470-8477, 2011.
• C. Prins et al., “Solving the capacitated location-routing problem by a cooperative Lagrangean relaxation-granular tabú search heuristic”, Transportation Science, vol. 41(4), pp. 470-483, 2007.
• V. F. Yu et al., ”A simulated annealing heuristic for the capacitated location routing problem”,Computers & Industrial Engineering, vol. 58(2), pp. 288-299, 2010.
• M. S. Jabal-Ameli, M.B. Aryanezhad and N. Ghaffari-Nasab, “A variable neighborhood descent based heuristic to solve the capacitated location-routing problem”, International Journal of Industrial Engineering Computations, vol. 2(1), pp. 141-154, 2011.
• H. Derbel et al., “A variable neighborhood search for the capacitated location-routing problem”, In 4th International Conference on Logistics (LOGISTIQUA), pp. 514-519, IEEE, 2011.
• V. C. Hemmelmayr, J. F. Cordeau and T. G. Crainic, “An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics”,Computers & Operations Research, vol. 39(12), pp. 3215-3228, 2012.
• A. Jokar and R. Sahraeian, “A Heuristic Based Approach to Solve a Capacitated Location-routing Problem”, Journal of Management and Sustainability, vol. 2(2), pp. 219-226, 2012.
• J. W. Escobar et al., “A Granular Variable Tabú Neighborhood Search for the capacitated location-routing problem”, Transportation Research, Part B: Methodological, vol. 67, pp. 344-356, 2014.
• S. Ropke and D. Pisinger, “An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows”,Transportation Science,vol. 40, pp. 455-472, 2006.
• C. Prins, C. Prodhon and R. W. Calvo, “A Memetic Algorithm with Population Management (MA|PM) for the Capacitated Location-Routing Problem”, Lecture Notes in Computer Science, vol. 3906, pp. 183-194, 2006.
• C. Duhamel et al., “A memetic approach for the capacitated location routing problem”, In Proceedings of the 9th EU/Meeting on Metaheuristics for Logistics and Vehicle Routing, Troyes, France. 2008.
• C. J. Ting and C. H. Chen, “A multiple ant colony optimization algorithm for the capacitated location routing problem”, International Journal of Production Economics, vol. 141(1), pp. 34-44, 2013.
• G. Laporte, Y. Nobert and D. Arpin, “An exact algorithm for solving a capacitated location-routing problem”, Annals of Operations Research, vol. 6(9), pp. 291-310, 1986.
• C. Contardo, J. F. Cordeau and B. Gendron, “A branch-and-cut algorithm for the capacitated location-routing problem”, In Conference CAOR 10, 2010.
• C. Contardo, B. Gendron and J. F. Cordeau, A branch-and-cut-and-price algorithm for the capacitated location-routing problem, CIRRELT, 2011.
• J. M. Belenguer et al., “A branch-and-cut method for the capacitated location-routing problem”, Computers & Operations Research, vol. 38(6), pp. 931-941, 2011.
• C. Contardo, B. Gendron and J. F. Cordeau, A computational comparison of flow formulations for the capacitated location-routing problem, CIRRELT, 2011.
• R. Baldacci, A. Mingozzi and R. W. Calvo, “An exact method for the capacitated location-routing problem”, Operations Research, vol. 59(5), pp. 1284-1296, 2011.
• T. Harks, F. G. Konig and J. Matuschke, “Approximation Algorithms for Capacitated Location Routing”, Technische Universitat Berlin, Institut fur Mathematik Straße des 17.Germany, 2012.
• L. Bouhafs and A. Koukam, “A combination of simulated annealing and ant colony system for the capacitated location-routing problem”, In Knowledge-Based Intelligent Information and Engineering Systems, pp. 409-416, Springer Berlin Heidelberg, 2006.
• C. Boulanger and F. Semet, “A column generation based heuristic for the capacitated location-routing problem”, In EU/Meeting Conference, EURO 2008.
• J. Yan et al., “A hybrid ant colony algorithm for the capacitated location-routing problem”,3rd International Conference on Intelligent System and Knowledge Engineering, pp. 38-43. IEEE, 2008.
• L. Bouhafs, A. Hajjam and A. Koukam, “A Tabú Search and Ant Colony System Approach for the Capacitated Location-Routing Problem”.Ninth ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, pp. 46-50, IEEE, 2008.
• S. Pirkwieser and G. R. Raidl, “Variable neighborhood search coupled with ILP-based very large neighborhood searches for the (periodic) location-routing problem”, In Hybrid Metaheuristics, pp. 174-189, Springer Berlin Heidelberg, 2010.
• A. Jokar and R. Sahraeian, “An Iterative two Phase Search Based Heuristic to Solve the Capacitated Location-Routing Problem”, Australian Journal of Basic & Applied Sciences, vol. 5(12), pp. 1613-1621, 2011.
• J. W. Escobar et al., “A comparison of three metaheuristic algorithms for the capacitated location-routing problem”,Proceedings of the fifth International Workshop on Freight Transportation and Logistics (ODYSSEUS), pp. 560-563, 2012.
• J. W. Escobar et al., “A computational comparison of heuristic algorithms for the capacitated location-routing problem”, Technical Report, University of Bologna, 2012.
• C. Contardo, J. F. Cordeau and B.Gendron, “A GRASP + ILP-based metaheuristic for the capacitated location-routing problem”,Technical Report CIRRELT, 2011.
• J. W. Escobar, R. Linfati and P. Toth, “A hybrid metaheuristic algorithm for the capacitated-location routing problem”, Proceedings of CLAIO/SBPO, Rio de Janeiro-Brazil, September 24-28, 2012.
• J. W. Escobar et al., “A metaheuristic algorithm based on a Granular Tabú Search within a Variable Neighborhood Search for the capacitated location-routing problem”, Proceedings of VEROLOG - First meeting of the EURO Working Group on Vehicle Routing and Logistics Optimization, pp. 78-79, Bologna-Italy, June 18-20, 2012.
• J. W. Escobar and R. Linfati, “Un algoritmo metaheurístico basado en recocido simulado con espacio de búsqueda granular para el problema de localización y ruteo con restricciones de capacidad”, Revista Ingenierías Universidad de Medellín, vol. 11(21), pp. 139-150, 2012.
• J. Jin, T. G. Crainic and A. Løkketangen, “A parallel multi-neighborhood cooperative tabú search for capacitated vehicle routing problems”, European Journal of Operational Research, vol. 222(3), pp. 441-451, 2012.
• P. Badeau et al., “A parallel tabú search heuristic for the vehicle routing problem with time windows”, Transportation Research, Part C: Emerging Technologies, vol. 5(2), pp. 109-122, 1997.
• J. F. Cordeau and M. Maischberger, “A parallel iterated tabú search heuristic for vehicle routing problems”, Computers & Operations Research, vol. 39(9), pp. 2033-2050, 2012.
• L. S. Ochi et al., “A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet. In Parallel and Distributed Processing, Springer Berlin Heidelberg, pp. 216-224,1998.
• A. Subramanian et al., “A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery”, Computers & Operations Research, vol. 37(11), 1899-1911, 2010.