Algoritmo memético con operadores de inteligencia artificial para el CARP con inicio y fin no determinado y bi-objetivo
Main Article Content
Keywords
algoritmo genético, algoritmo memético, optimización multiobjetivo, CARP, OCARP, MO-OCARP, redes neuronales, búsqueda local, ruteo de vehículos sobre arcos.
Resumen
El Problema de ruteo de vehículos sobre arcos con punto de inicio/fin variable (Open Capacitated Arc Routing Problem - OCARP), en su versión clásica, busca determinar la mejor estrategia para servir un conjunto de clientes localizados en los arcos de una red usando vehículos. A diferencia del Capacitated Arc Routing Problem (CARP), el OCARP no tiene las restricciones que aseguran que cada vehículo debe iniciar y terminar su ruta en un vértice dado (también conocido como depósito). El objetivo de este trabajo es proponer una heurística para encontrar la frontera eficiente dados dos objetivos: minimizar el número de vehículos y minimizar el costo total. Adicionalmente se propone complementar la heurística, la cual es basada en algoritmos genéticos, con operadores de inteligencia artificial.
Descargas
Referencias
Available:http://dx.doi.org/10.1002/net.3230110308 27, 30
L. Santos, J. Coutinho-Rodrigues, and J. R. Current, “An improved heuristic for the capacitated arc routing problem,” Computers & Operations Research, vol. 36, no. 9, pp. 2632 – 2637, 2009. [Online]. Available:http://www.sciencedirect.com/science/article/pii/S0305054808002281 27
W. L. Pearn, “Augmentinsert algorithms for the capacitated arc routing problem,” Computers & Operations Research, vol. 18, no. 2, pp. 189 – 198,1991. [Online]. Available: http://www.sciencedirect.com/science/article/pii/030505489190089A 27
R. W. E. Leon Y. O. Li, “An interactive algorithm for vehicle routeing for winter - gritting,” The Journal of the Operational Research Society, vol. 47, no. 2, pp. 217–228, 1996. [Online]. Available: http://www.jstor.org/stable/2584343 27
P. Lacomme, C. Prins, and W. Ramdane-Cherif, “Competitive memetic algorithms for arc routing problems,” Annals of Operations Research, vol.131, no. 1-4, pp. 159–185, 2004. [Online].Available:http://dx.doi.org/10.1023/B%3AANOR.0000039517.35989.6d 27
A. Corberán and C. Prins, “Recent results on arc routing problems: An annotated bibliography,” Networks, vol. 56, no. 1, pp. 50–69, 2010. [Online].Available: http://dx.doi.org/10.1002/net.20347 27
P.Lacomme, C. Prins, and M. Sevaux, “A genetic algorithm for a bi-objective capacitated arc routing problem,” Computers & Operations Research, vol. 33, no. 12, pp. 3473 – 3493, 2006, part Special Issue:Recent Algorithmic Advances for Arc Routing Problems. [Online]. Available:http://www.sciencedirect.com/science/article/pii/S0305054805000730 27,
, 32, 34
F. L. Usberti, P. M. França, and A. L. M. França, “The open capacitated arc routing problem,” Computers & Operations Research,vol. 38, no. 11, pp. 1543 – 1555, 2011. [Online]. Available:http://www.sciencedirect.com/science/article/pii/S0305054811000244 27, 30, 38
R. Liu, Z. Jiang, N. Geng, and T. Liu, “A heuristic approach for the open capacitated arc routing problem,” in Supply Chain Management and Information Systems (SCMIS), 2010 8th International Conference on, Oct 2010,pp. 1–6. 27
F. L. Usberti, P. M. França, and A. L. M. França, “{GRASP} with evolutionary path-relinking for the capacitated arc routing problem,”Computers & Operations Research, vol. 40, no. 12, pp. 3206 – 3217,2013. [Online]. Available:
http://www.sciencedirect.com/science/article/pii/S0305054811003029 28
R. Y. Fung, R. Liu, and Z. Jiang, “A memetic algorithm for the open capacitated arc routing problem,” Transportation Research Part E: Logisticsand Transportation Review, vol. 50, pp. 53 – 67, 2013. [Online].
Available:http://www.sciencedirect.com/science/article/pii/S1366554512000932 28
L. Grandinetti, F. Guerriero, D. Laganá, and O. Pisacane, “An optimizationbased heuristic for the multi-objective undirected capacitated arc routing problem,” Computers & Operations Research, vol. 39, no. 10, pp. 2300– 2309, 2012. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0305054811003649 28
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: Nsga-ii,” Evolutionary Computation, IEEE Transactions on, vol. 6, no. 2, pp. 182–197, Apr 2002. 28, 32, 33, 40, 41
E. Zitzler, L. Thiele, M. Laumanns, C. Fonseca, and V. da Fonseca, “Performance assessment of multiobjective optimizers: an analysis and review,”Evolutionary Computation, IEEE Transactions on, vol. 7, no. 2, pp. 117–132,April 2003. 28, 40
Y. Mei, K. Tang, and X. Yao, “Decomposition-based memetic algorithm for multiobjective capacitated arc routing problem,” Evolutionary Computation,IEEE Transactions on, vol. 15, no. 2, pp. 151–165, April 2011. 28
E. Zitzler, “Evolutionary algorithms for multiobjective optimization: Methods and applications,” 1999. 28
W. Hart, N. Krasnogor, and J. Smith, Eds., Recent Advances in Memetic Algorithms, 2004. 28
T. Munakata, Fundamentals of the New Artificial Intelligence: Neural, Evolutionary,Fuzzy and More (Texts in Computer Science), 2nd ed. Springer Publishing Company, Incorporated, 2008. 29
S. Nissen, “Implementation of a Fast Artificial Neural Network Library (fann),” Report, Department of Computer Science University of Copenhagen (DIKU), vol. 31, 2003. 29
T. Murata, H. Nozawa, H. Ishibuchi, and M. Gen, “Modification of localsearch directions for non-dominated solutions in cellular multiobjective genetic algorithms for pattern classification problems,” in Evolutionary Multi-Criterion Optimization, ser. Lecture Notes in Computer Science,C. Fonseca, P. Fleming, E. Zitzler, L. Thiele, and K. Deb, Eds. Springer Berlin Heidelberg, 2003, vol. 2632, pp. 593–607. [Online]. Available:http://dx.doi.org/10.1007/3-540-36970-8_42 34
E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, no. 1, pp. 269–271, 1959. 38
E. Zitzler and L. Thiele, “Multiobjective optimization using evolutionary algorithms - a comparative case study,” in Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, ser.PPSN V. London, UK, UK: Springer-Verlag, 1998, pp. 292–304. [Online].Available: http://dl.acm.org/citation.cfm?id=645824.668610 41