Hybrid Algorithm Enhanced with Artificial Intelligence Applied to the Bi-Objective Open Capacitated Arc Routing Problem

Main Article Content

B J Macias http://orcid.org/0000-0002-8752-7061
C A Amaya http://orcid.org/0000-0003-1537-1616


genetic algorithm, memetic algorithm, multi-objective optimization, CARP, OCARP, MO-OCARP, neural networks, local search


The arc routing problem with a variable starting/ending position (Open Capacitated Arc Routing Problem - OCARP), in its classic version, pursues the best strategy to serve a set of customers located in the network arcs using vehicles. Compared to the Capacitated Arc Routing Problem (CARP), the OCARP lacks of constrains that guarantee that each vehicle ought to start and end the tour at a given vertex (also known as a depot). The aim of this paper is to propose a heuristic to find an efficient frontier for the main objective functions: minimize the number of vehicles and the total cost. Additionally, a hybrid algorithm that complements the genetic algorithm with artificial intelligence operator is proposed.


Download data is not yet available.
Abstract 677 | PDF (Español) Downloads 363 HTML (Español) Downloads 204


B. L. Golden and R. T. Wong, “Capacitated arc routing problems,”Networks, vol. 11, no. 3, pp. 305–315, 1981. [Online].

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