Un algoritmo metaheurístico para el problema de localización y ruteo con flota heterogénea
Main Article Content
Keywords
problema de localización y ruteo, Flota heterogénea, búsqueda tabú granular, algoritmos Metaheurísticos
Resumen
Consideramos el problema de localización y ruteo con flota heterogénea (LRPH, por sus siglas en inglés), en el cual se busca determinar los depósitos a ser abiertos, los clientes a ser asignados a cada depósito, y las rutas a ser construidas para satisfacer las demandas de los clientes, considerando una flota de vehículos con capacidad diversa y costos de utilización asociados. El objetivo es minimizar la suma de los costos asociados con la apertura de depósitos, los costos de los vehículos utilizados, y los costos variables directamente relacionados con las distancias recorridas. En este artículo, se propone un algoritmo metaheurístico basado en una búsqueda tabú granular para la resolución del problema. Experimentos computacionales en instancias adaptadas de la literatura, muestran que el algoritmo propuesto es capaz de obtener, en tiempos computacionales razonables, soluciones de alta calidad demostrando su efectividad.
MSC: 68Qxx; 68W40
Descargas
Referencias
[2] G. Nagy and S. Salhi, “Location-routing: Issues, models and methods,” EuropeanJournal of Operational Research, vol. 177, no. 2, pp. 649–672, 2007.57
[3] S. Salhi, A. Imran, and N. A. Wassan, “The multi-depot vehicle routingproblem with heterogeneous vehicle fleet: Formulation and a variable neighborhoodsearch implementation,” Computers & Operations Research, 2013.57
[4] C. Prins, C. Prodhon, A. Ruiz, P. Soriano, and R. W. Calvo, “Solving thecapacitated location-routing problem by a cooperative lagrangean relaxationgranulartabu search heuristic,” Transportation Science, vol. 41, no. 4, pp.470–483, 2007. 57, 59, 61, 70, 71, 73
[5] C. Duhamel, P. Lacomme, C. Prins, and C. Prodhon, “A GRASP × ELSapproach for the capacitated location-routing problem,” Computers & OperationsResearch, vol. 37, no. 11, pp. 1912–1923, 2010. 57
[6] V. F. Yu, S.-W. Lin, W. Lee, and C.-J. Ting, “A simulated annealing heuristicfor the capacitated location routing problem,” Computers & IndustrialEngineering, vol. 58, no. 2, pp. 288–299, 2010. 57
[7] J. Willmer Escobar, R. Linfati, and P. Toth, “A two-phase hybrid heuristicalgorithm for the capacitated location-routing problem,” Computers &Operations Research, vol. 40, no. 1, pp. 70–79, 2013. 57, 68
[8] J. H. Bookbinder and K. E. Reece, “Vehicle routing considerations in distributionsystem design,” European Journal of Operational Research, vol. 37,no. 2, pp. 204–213, 1988. 58
[9] S. Salhi and M. Fraser, “An integrated heuristic approach for the combinedlocation vehicle fleet mix problem,” Studies in Locational Analysis, vol. 8,pp. 3–21, 1996. 58, 59
[10] T.-H. Wu, C. Low, and J.-W. Bai, “Heuristic solutions to multi-depotlocation-routing problems,” Computers & Operations Research, vol. 29,no. 10, pp. 1393–1415, 2002. 58
[11] D. Ambrosino and M. Grazia Scutellà, “Distribution network design: Newproblems and related models,” European Journal of Operational Research,vol. 165, no. 3, pp. 610–624, 2005. 58
[12] H. Gunnarsson, M. Rönnqvist, and D. Carlsson, “A combined terminal locationand ship routing problem,” Journal of the Operational Research Society,vol. 57, no. 8, pp. 928–938, 2005. 58
[13] M. T. C. S. JIS, Computers and intractability A Guide to the Theory ofNP-Completeness. WH Freeman and Company, 1979. 58
[14] G. Laporte, “The vehicle routing problem: An overview of exact and approximatealgorithms,” European Journal of Operational Research, vol. 59, no. 3,pp. 345–358, 1992. 61
[15] P. Toth and D. Vigo, The vehicle routing problem. Siam, 2002, vol. 9. 61
[16] C. H. Papadimitriou and K. Steiglitz, Combinatorial optimization: algorithmsand complexity. Courier Dover Publications, 1998. 61
[17] P. Toth and D. Vigo, “The granular tabu search and its application to thevehicle-routing problem,” INFORMS Journal on Computing, vol. 15, no. 4,pp. 333–346, 2003. 62, 65
[18] C. Blum and A. Roli, “Metaheuristics in combinatorial optimization: Overviewand conceptual comparison,” ACM Computing Surveys (CSUR), vol. 35,no. 3, pp. 268–308, 2003. 62
[19] S. Lin and B. W. Kernighan, “An effective heuristic algorithm for thetraveling-salesman problem,” Operations research, vol. 21, no. 2, pp. 498–516, 1973. 64
[20] K. Helsgaun, “An effective implementation of the lin–kernighan traveling salesmanheuristic,” European Journal of Operational Research, vol. 126, no. 1,pp. 106–130, 2000. 64
[21] J. Barceló and J. Casanovas, “A heuristic lagrangean algorithm for the capacitatedplant location problem,” European Journal of Operational Research,vol. 15, no. 2, pp. 212–226, 1984. 64
[22] J. G. Klincewicz and H. Luss, “A lagrangian relaxation heuristic for capacitatedfacility location with single-source constraints,” Journal of the OperationalResearch Society, pp. 495–500, 1986. 64
[23] M. Gendreau, A. Hertz, and G. Laporte, “A tabu search heuristic for thevehicle routing problem,” Management science, vol. 40, no. 10, pp. 1276–1290, 1994. 67
[24] É. Taillard, “Parallel iterative search methods for vehicle routing problems,”Networks, vol. 23, no. 8, pp. 661–673, 1993. 67
[25] B. Golden, A. Assad, L. Levy, and F. Gheysens, “The fleet size and mixvehicle routing problem,” Computers & Operations Research, vol. 11, no. 1,pp. 49–66, 1984. 69, 70
[26] N. Christofides and J. E. Beasley, “A tree search algorithm for the p-medianproblem,” European Journal of Operational Research, vol. 10, no. 2, pp. 196–204, 1982. 70, 73
[27] S. P. Coy, B. L. Golden, G. C. Runger, and E. A. Wasil, “Using experimentaldesign to find effective parameter settings for heuristics,” Journal of Heuristics,vol. 7, no. 1, pp. 77–97, 2001. 71