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

Main Article Content

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

Keywords

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

Abstract

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.

Downloads

Download data is not yet available.
Abstract 1199 | PDF (Español) Downloads 766 HTML (Español) Downloads 339

References

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

Article Sidebar

PDF (Español) HTML (Español)
Published
Feb 22, 2016
DOI https://doi.org/10.17230/ingciencia.12.23.2

Article Details

How to Cite
Macias, B. J., & Amaya, C. A. (2016). Hybrid Algorithm Enhanced with Artificial Intelligence Applied to the Bi-Objective Open Capacitated Arc Routing Problem. Ingeniería Y Ciencia, 12(23), 25–46. https://doi.org/10.17230/ingciencia.12.23.2
Issue
Vol. 12 No. 23 (2016)
Section
Articles
Supporting Agencies
Universidad de los Andes

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).