{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T10:53:15Z","timestamp":1770979995876,"version":"3.50.1"},"reference-count":51,"publisher":"EDP Sciences","issue":"1","license":[{"start":{"date-parts":[[2019,2,15]],"date-time":"2019-02-15T00:00:00Z","timestamp":1550188800000},"content-version":"vor","delay-in-days":45,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2018,9,21]]},"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>In this paper we develop several approaches to approximately solve the capacitated arc routing problem (CARP) on sparse graphs namely sparse CARP. First, we give a mathematical model for the sparse CARP and we present a brief survey about a transformation technique to transform the sparse CARP into a sparse capacitated vehicle routing problem namely sparse CVRP. Later, we propose several approaches to solve the sparse CARP by solving its equivalent obtained sparse CVRP. The first approach is a constructive heuristic (CH) used to construct an initial feasible solution. The second approach is an improving randomized procedure (IRP) used to improve the quality of the initial solution. Finally, we introduce the main adapted tabu search approach (TS) under a sparse dynamic graph. The algorithm starts by applying the first two procedures CH and IRP and attempts to compute a better solution for the sparse CARP. Extensive computational tests on randomly generated problem instances show the effectiveness of the proposed approach. The TS algorithm yields satisfactory results within reasonable computational time. The approach outperformed also the commercial solver Cplex v12.71 which was able to solve only small instances with relatively a big CPU time for medium size instances.<\/jats:p>","DOI":"10.1051\/ro\/2018087","type":"journal-article","created":{"date-parts":[[2018,10,3]],"date-time":"2018-10-03T18:51:23Z","timestamp":1538592683000},"page":"303-322","source":"Crossref","is-referenced-by-count":1,"title":["Efficient algorithms under dynamic graphs to solve the Capacitated Arc Routing Problem with feasible sparse graph"],"prefix":"10.1051","volume":"53","author":[{"given":"Sara","family":"Tfaili","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hamdi","family":"Dkhil","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5890-1667","authenticated-orcid":false,"given":"Abdelkader","family":"Sbihi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adnan","family":"Yassine","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2019,2,15]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Assad A.A. and Golden B.L., Arc routing methods and applications, edited by Ball M.G., Magnanti T.L., Monma C.L. and Nemhauser G.L.. In: Network Routing, Handbooks in Operations Research and Management Science, Elsevier (1995) 375\u2013483.","DOI":"10.1016\/S0927-0507(05)80109-4"},{"key":"R2","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1016\/S0377-2217(96)00048-3","volume":"98","author":"Beasley","year":"1997","journal-title":"Eur. J. Oper. Res."},{"key":"R3","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1023\/A:1018316919294","volume":"10","author":"Belenguer","year":"1998","journal-title":"Comput. Optim. Appl."},{"key":"R4","doi-asserted-by":"crossref","first-page":"705","DOI":"10.1016\/S0305-0548(02)00046-1","volume":"30","author":"Belenguer","year":"2003","journal-title":"Comput. Oper. Res."},{"key":"R5","doi-asserted-by":"crossref","first-page":"3363","DOI":"10.1016\/j.cor.2005.02.009","volume":"33","author":"Belenguer","year":"2006","journal-title":"Comput. Oper. Res."},{"key":"R6","doi-asserted-by":"crossref","first-page":"1167","DOI":"10.1287\/opre.1120.1079","volume":"60","author":"Bode","year":"2012","journal-title":"Oper. Res."},{"key":"R7","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1016\/S0377-2217(96)00337-2","volume":"108","author":"Corber\u00e1n","year":"1998","journal-title":"Eur. J. Oper. Res."},{"key":"R8","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/PL00011426","volume":"90","author":"Corber\u00e1n","year":"2001","journal-title":"Math. Program. Ser. A"},{"key":"R9","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1016\/S0377-2217(01)00296-X","volume":"142","author":"Corber\u00e1n","year":"2002","journal-title":"Eur. J. Oper. Res."},{"key":"R10","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","volume":"6","author":"Dantzig","year":"1959","journal-title":"Manage. Sci."},{"key":"R11","unstructured":"Demetrescu C., Finocchi I. and Italiano G., Dynamic graphs. Chapter 10.2, edited by Gross J. and Yellen J.. In: Handbook of Graph Theory. CRC Press (2003) 985\u20131014."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Demetrescu C., Finocchi I. and Italiano G., Dynamic graphs. Chapter 22, edited by Mehta D.P. and Sahni S.. In: Handbook of Data Structures and Applications. CRC Press (2004).","DOI":"10.1201\/9781420035179.ch36"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Dror M. editor, Arc Routing \u2013 Theory, Solutions and Applications. Kluwer Academic Publishers (2000).","DOI":"10.1007\/978-1-4615-4495-1"},{"key":"R14","unstructured":"Eiselt H.A., A historical perspective on arc routing, edited by Dror M., . In: Arc Routing: Theory, Solutions and Applications, Springer, Boston, MA (2000) 1\u201316."},{"key":"R15","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1007\/s10479-014-1732-1","volume":"226","author":"Foulds","year":"2015","journal-title":"Ann. Oper. Res."},{"key":"R16","unstructured":"Fekete Z. and Szeg\u00f6 L., A note on [k, l]-sparse graphs. Egrerv\u00e1ry Research Group on Combinatorial Optimization, P\u00e1zm\u00e1ny P. s\u00e9t\u00e1ny 1\/C, H1117, Budapest, Hungary www.cs.elte.hu\/egres (2005)."},{"key":"R17","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1007\/s101070050007","volume":"87","author":"Ghiani","year":"2000","journal-title":"Math. Program."},{"key":"R18","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/S0305-0548(03)00213-2","volume":"32","author":"Ghiani","year":"2005","journal-title":"Comput. Oper. Res."},{"key":"R19","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1016\/0305-0548(86)90048-1","volume":"13","author":"Glover","year":"1986","journal-title":"Comput. Oper. Res."},{"key":"R20","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1002\/net.3230110308","volume":"11","author":"Golden","year":"1981","journal-title":"Networks"},{"key":"R21","unstructured":"G\u00f2mez-Cabrero D., Belenguer J.M. and Benavent E., Cutting plane and column generation for the capacitated arc routing problem, Presented at ORP3Valencia, Spain (2005)."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"Gross J.T. and Yellen J., Graph Theory and its Applications, 2nd edition. CRC Press, Boca Raton, FL (2006).","DOI":"10.1201\/9781420057140"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Gutin G. and Punnen A.P., The Traveling Salesman Problem and its Variations. Springer, Boston, MA (2006).","DOI":"10.1007\/b101971"},{"key":"R24","unstructured":"Hansen P., The steepest ascent mildest descent heuristic for combinatorial programming, Presented at the Congress on Numerical Methods in Combinatorial Optimization. Capri, Italy (1986)."},{"key":"R25","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1287\/opre.48.1.129.12455","volume":"48","author":"Hertz","year":"2000","journal-title":"Oper. Res."},{"key":"R26","unstructured":"Kansou A. and Yassine A., A two ant colony approaches for the multi-depot capacitated arc routing problem. In: Proc. of International Conference on Computers and Industrial Engineering (2009) 1040\u20131045."},{"key":"R27","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1504\/IJMHEUR.2010.033124","volume":"1","author":"Kansou","year":"2010","journal-title":"Int. J. Metaheuristics"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"Karp R.M., Reducibility among combinatorial problems edited by Miller R.E. and Thatcher J.W.. In: Complexity of Computer Computations.. Plenum, New York, NY (1972) 85\u2013103.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"R29","unstructured":"Lacomme P., Prins C. and Ramadane-Ch\u00e9rif W., Evolutionary algorithms for multiperiod arc routing problems. In: Proc. of the 9th Int. Conf. on Information Processing and Management of the Uncertainty in Knowledge-Based systems (IPMU 2002).ESIA-Univ. of Savoie (2002) 845\u2013852."},{"key":"R30","doi-asserted-by":"crossref","first-page":"1057","DOI":"10.1016\/S0305-0548(97)00013-0","volume":"24","author":"Laporte","year":"1997","journal-title":"Comput. Oper. Res."},{"key":"R31","unstructured":"Letchford A.N., Polyhedral results for some constrained arc-routing problems. Ph.D. thesis, Lancaster University, Lancaster, UK (1997)."},{"key":"R32","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1016\/S0377-2217(97)00090-8","volume":"105","author":"Letchford","year":"1998","journal-title":"Eur. J. Oper. Res."},{"key":"R33","doi-asserted-by":"crossref","first-page":"1823","DOI":"10.1016\/j.cor.2004.11.020","volume":"33","author":"Longo","year":"2006","journal-title":"Comput. Oper. Res."},{"key":"R34","unstructured":"Ne\u0161et\u0159il J. and Mendez P.O., Sparsity: Graphs, Structures and Algorithms. Springer, Berlin Heidelberg (2012)."},{"key":"R35","unstructured":"Oukil A., Exploiting sparsity in vehicle routing algorithms. Ph. D. thesis, Lancaster University, Lancaster, UK (2008)."},{"key":"R36","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1287\/moor.7.1.67","volume":"7","author":"Padberg","year":"1982","journal-title":"Math. Oper. Res."},{"key":"R37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0167-6377(87)90002-2","volume":"6","author":"Padberg","year":"1987","journal-title":"Oper. Res. Lett."},{"key":"R38","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF01580861","volume":"47","author":"Padberg","year":"1990","journal-title":"Math. Program."},{"key":"R39","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1137\/1033004","volume":"33","author":"Padberg","year":"1991","journal-title":"SIAM Rev."},{"key":"R40","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0305-0548(87)90065-7","volume":"14","author":"Pearn","year":"1987","journal-title":"Comput. Oper. Res."},{"key":"R41","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/0167-6377(94)90073-6","volume":"16","author":"Pearn","year":"1994","journal-title":"Oper. Res. Lett."},{"key":"R42","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF01904834","volume":"16","author":"van Rooij","year":"1965","journal-title":"Acta Math. Acad. Sci. Hungar."},{"key":"R43","doi-asserted-by":"crossref","first-page":"119","DOI":"10.15807\/jorsj.35.119","volume":"35","author":"Saruwatari","year":"1992","journal-title":"J. Oper. Res. Soc. Jpn."},{"key":"R44","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/j.ejor.2009.05.033","volume":"202","author":"Sbihi","year":"2010","journal-title":"Eur. J. Oper. Res."},{"key":"R45","unstructured":"Skiena S., Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. In Line graph, Section 4.1.5. p. 128 (1990) 135\u2013139."},{"key":"R46","doi-asserted-by":"crossref","unstructured":"Sniezek J.S., The capacitated arc routing problem with vehicle\/site dependencies: an application of arc routing and partitioning. Ph.D. thesis, University of Maryland (2001).","DOI":"10.1137\/1.9780898718515.ch11"},{"key":"R47","unstructured":"Tfaili S., Contribution aux graphes creux pour le probl\u00e8me de tourn\u00e9es sur arcs d\u00e9terministe et robuste: th\u00e9orie et algorithmes, Ph.D. thesis, Universit\u00e9 Le Havre Normandie, Le Havre (2017)."},{"key":"R48","unstructured":"Tfaili S., Dkhil H., Sbihi A. and Yassine A., A transformation technique for arc routing problems into node routing problems with a sparse feasible graph, Working Paper (2016)."},{"key":"R49","unstructured":"Welz S.A., Optimal solutions for the capacitated arc routing problem using integer programming. Ph.D. thesis, University of Cincinnati, Cincinnati (1994)."},{"key":"R50","unstructured":"West D.B., Characterizing line graphs, 2nd edition. In: Introduction to Graph Theory. Prentice-Hall, Englewood Cliffs, NJ (2000) 279\u2013282."},{"key":"R51","unstructured":"W\u00f8hlk S., Contributins to arc routing. Ph.D. thesis, University of Southern Denmark, Odense (2005)."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2018087\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T06:18:58Z","timestamp":1662185938000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2018087"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":51,"journal-issue":{"issue":"1"},"alternative-id":["ro170191"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2018087","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"1290-3868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}