Efficient algorithms under dynamic graphs to solve the Capacitated Arc Routing Problem with feasible sparse graph
RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 1, pp. 303-322.

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.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2018087
Classification : 90B06, 90C05, 90C10, 90C27, 90C59
Mots-clés : Routing problems, graph theory, sparsity, tabu search
Tfaili, Sara 1 ; Dkhil, Hamdi 1 ; Sbihi, Abdelkader 1 ; Yassine, Adnan 1

1 
@article{RO_2019__53_1_303_0,
     author = {Tfaili, Sara and Dkhil, Hamdi and Sbihi, Abdelkader and Yassine, Adnan},
     title = {Efficient algorithms under dynamic graphs to solve the {Capacitated} {Arc} {Routing} {Problem} with feasible sparse graph},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {303--322},
     publisher = {EDP-Sciences},
     volume = {53},
     number = {1},
     year = {2019},
     doi = {10.1051/ro/2018087},
     zbl = {1414.90062},
     mrnumber = {3912475},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2018087/}
}
TY  - JOUR
AU  - Tfaili, Sara
AU  - Dkhil, Hamdi
AU  - Sbihi, Abdelkader
AU  - Yassine, Adnan
TI  - Efficient algorithms under dynamic graphs to solve the Capacitated Arc Routing Problem with feasible sparse graph
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2019
SP  - 303
EP  - 322
VL  - 53
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2018087/
DO  - 10.1051/ro/2018087
LA  - en
ID  - RO_2019__53_1_303_0
ER  - 
%0 Journal Article
%A Tfaili, Sara
%A Dkhil, Hamdi
%A Sbihi, Abdelkader
%A Yassine, Adnan
%T Efficient algorithms under dynamic graphs to solve the Capacitated Arc Routing Problem with feasible sparse graph
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2019
%P 303-322
%V 53
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2018087/
%R 10.1051/ro/2018087
%G en
%F RO_2019__53_1_303_0
Tfaili, Sara; Dkhil, Hamdi; Sbihi, Abdelkader; Yassine, Adnan. Efficient algorithms under dynamic graphs to solve the Capacitated Arc Routing Problem with feasible sparse graph. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 1, pp. 303-322. doi : 10.1051/ro/2018087. http://www.numdam.org/articles/10.1051/ro/2018087/

[1] A.A. Assad and B.L. Golden, Arc routing methods and applications, edited by M.G. Ball, T.L. Magnanti, C.L. Monma and G.L. Nemhauser. In: Network Routing, Handbooks in Operations Research and Management Science, Elsevier (1995) 375–483. | DOI | MR | Zbl

[2] J.E. Beasley and N. Christofides, Vehicle routing with a sparse feasibility graph. Eur. J. Oper. Res. 98 (1997) 499–511. | DOI | Zbl

[3] J.M. Belenguer and E. Benavent, The capacitated arc routing problem: valid inequalities and facets. Comput. Optim. Appl. 10 (1998) 165–187. | DOI | MR | Zbl

[4] J.M. Belenguer and E. Benavent, A cutting plane algorithm for the capacitated arc routing problem. Comput. Oper. Res. 30 (2003) 705–728. | DOI | MR | Zbl

[5] J.M. Belenguer, E. Benavent, P. Lacomme and C. Prins, Lower and upper bounds for the mixed capacitated arc routing problem. Comput. Oper. Res. 33 (2006) 3363–3383. | DOI | MR | Zbl

[6] C. Bode and S. Irnich, Cut-first branch-and-price-second for the capacitated arc-routing problem. Oper. Res. 60 (2012) 1167–1182. | DOI | MR | Zbl

[7] A. Corberán and J.M. Sanchis, The general routing problem polyhedron: facets from the RPP and GTSP polyhedra. Eur. J. Oper. Res. 108 (1998) 538–550. | DOI | Zbl

[8] A. Corberán, A. Letchford and J.M. Sanchis, A cutting plane algorithm for the general routing problem. Math. Program. Ser. A 90 (2001) 291–316. | DOI | MR | Zbl

[9] A. Corberán, R. Mart and J.M. Sanchis, A GRASP heuristic for the mixed Chinese postman problem. Eur. J. Oper. Res. 142 (2002) 70–80. | DOI | MR | Zbl

[10] G.B. Dantzig and J.H. Ramser, The truck dispatching problem. Manage. Sci. 6 (1959) 80–91. | DOI | MR | Zbl

[11] C. Demetrescu, I. Finocchi and G. Italiano, Dynamic graphs. Chapter 10.2, edited by J. Gross and J. Yellen. In: Handbook of Graph Theory. CRC Press (2003) 985–1014.

[12] C. Demetrescu, I. Finocchi and G. Italiano, Dynamic graphs. Chapter 22, edited by D.P. Mehta and S. Sahni. In: Handbook of Data Structures and Applications. CRC Press (2004).

[13] M. Dror editor, Arc Routing – Theory, Solutions and Applications. Kluwer Academic Publishers (2000). | DOI | Zbl

[14] H.A. Eiselt, A historical perspective on arc routing, edited by M. Dror, . In: Arc Routing: Theory, Solutions and Applications, Springer, Boston, MA (2000) 1–16. | Zbl

[15] L. Foulds, H. Longo and J. Martins, A compact transformation of arc routing problems into node routing problems. Ann. Oper. Res. 226 (2015) 177–200. | DOI | MR | Zbl

[16] Z. Fekete and L. Szegö, A note on [k, l]-sparse graphs. Egrerváry Research Group on Combinatorial Optimization, Pázmány P. sétány 1/C, H1117, Budapest, Hungary www.cs.elte.hu/egres (2005).

[17] G. Ghiani and G. Laporte, A branch-and-cut algorithm for the undirected rural postman problem. Math. Program. 87 (2000) 467–481. | DOI | MR | Zbl

[18] G. Ghiani, R. Musmanno, G. Paletta and C. Triki, A heuristic for the periodic rural postman problem. Comput. Oper. Res. 32 (2005) 219–228. | DOI | MR | Zbl

[19] F. Glover, Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13 (1986) 533–549. | DOI | MR | Zbl

[20] B.L. Golden and R.T. Wong, Capacitated arc routing problems. Networks 11 (1981) 305–315. | DOI | MR | Zbl

[21] D. Gòmez-Cabrero, J.M. Belenguer and E. Benavent, Cutting plane and column generation for the capacitated arc routing problem, Presented at ORP3Valencia, Spain (2005).

[22] J.T. Gross and J. Yellen, Graph Theory and its Applications, 2nd edition. CRC Press, Boca Raton, FL (2006). | MR | Zbl

[23] G. Gutin and A.P. Punnen, The Traveling Salesman Problem and its Variations. Springer, Boston, MA (2006). | Zbl

[24] P. Hansen, The steepest ascent mildest descent heuristic for combinatorial programming, Presented at the Congress on Numerical Methods in Combinatorial Optimization. Capri, Italy (1986).

[25] A. Hertz, G. Laporte and M. Mittaz, A tabu search heuristic for the capacitated arc routing problem. Oper. Res. 48 (2000) 129–135. | DOI | MR | Zbl

[26] A. Kansou and A. Yassine, 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–1045.

[27] A. Kansou and A. Yassine, New upper bounds for the multi-depot capacitated arc routing problem. Int. J. Metaheuristics 1 (2010) 81–95. | DOI | MR | Zbl

[28] R.M. Karp, Reducibility among combinatorial problems edited by R.E. Miller and J.W. Thatcher. In: Complexity of Computer Computations.. Plenum, New York, NY (1972) 85–103. | DOI | MR | Zbl

[29] P. Lacomme, C. Prins and W. Ramadane-Chérif, 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–852.

[30] G. Laporte, Modeling and solving several classes of arc routing problems as travelling salesman problems. Comput. Oper. Res. 24 (1997) 1057–1061. | DOI | MR | Zbl

[31] A.N. Letchford, Polyhedral results for some constrained arc-routing problems. Ph.D. thesis, Lancaster University, Lancaster, UK (1997).

[32] A.N. Letchford and R.W. Eglese, The rural postman problem with deadline classes. Eur. J. Oper. Res. 105 (1998) 390–400. | DOI | Zbl

[33] H. Longo, M. Poggi De Aragão and E. Uchoa, Solving capacitated arc routing problems using a transformation to the CVRP. Comput. Oper. Res. 33 (2006) 1823–1837. | DOI | Zbl

[34] J. Nešetřil and P.O. Mendez, Sparsity: Graphs, Structures and Algorithms. Springer, Berlin Heidelberg (2012). | DOI | MR | Zbl

[35] A. Oukil, Exploiting sparsity in vehicle routing algorithms. Ph. D. thesis, Lancaster University, Lancaster, UK (2008).

[36] M.W. Padberg and M.R. Rao, Odd minimum cut’sets and b-matchings. Math. Oper. Res. 7 (1982) 67–80. | DOI | MR | Zbl

[37] M.W. Padberg and G. Rinaldi, Optimization of a 532 city symmetric traveling salesman problem by branch and cut. Oper. Res. Lett. 6 (1987) 1–7. | DOI | MR | Zbl

[38] M.W. Padberg and G. Rinaldi, Facet identification for the symmetric traveling salesman polytope. Math. Program. 47 (1990) 219–257. | DOI | MR | Zbl

[39] M.W. Padberg and G. Rinaldi, A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33 (1991) 60–100. | DOI | MR | Zbl

[40] W.L. Pearn, A. Assad and B.L. Golden, Transforming arc routing into node routing problems. Comput. Oper. Res. 14 (1987) 285–288. | DOI | Zbl

[41] W.L. Pearn, Solvable cases of the k-person Chinese postman problem. Oper. Res. Lett. 16 (1994) 241–244. | DOI | MR | Zbl

[42] A. Van Rooij and H. Wilf, The interchange graph of a finite graph. Acta Math. Acad. Sci. Hungar. 16 (1965) 263–269. | DOI | MR | Zbl

[43] Y. Saruwatari, R. Hirabayashi and N. Nishida, Node duplication lower bounds for the capacitated arc routing problem. J. Oper. Res. Soc. Jpn. 35 (1992) 119–133. | MR | Zbl

[44] A. Sbihi, A cooperative local search-based algorithm for the Multiple-Scenario Max-Min Knapsack problem. Eur. J. Oper. Res. 202 (2010) 339–346. | DOI | MR | Zbl

[45] S. Skiena, Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. In Line graph, Section 4.1.5. p. 128 (1990) 135–139. | MR | Zbl

[46] J.S. Sniezek, The capacitated arc routing problem with vehicle/site dependencies: an application of arc routing and partitioning. Ph.D. thesis, University of Maryland (2001).

[47] S. Tfaili, Contribution aux graphes creux pour le problème de tournées sur arcs déterministe et robuste: théorie et algorithmes, Ph.D. thesis, Université Le Havre Normandie, Le Havre (2017).

[48] S. Tfaili, H. Dkhil, A. Sbihi and A. Yassine, A transformation technique for arc routing problems into node routing problems with a sparse feasible graph, Working Paper (2016).

[49] S.A. Welz, Optimal solutions for the capacitated arc routing problem using integer programming. Ph.D. thesis, University of Cincinnati, Cincinnati (1994).

[50] D.B. West, Characterizing line graphs, 2nd edition. In: Introduction to Graph Theory. Prentice-Hall, Englewood Cliffs, NJ (2000) 279–282.

[51] S. Wøhlk, Contributins to arc routing. Ph.D. thesis, University of Southern Denmark, Odense (2005).

Cité par Sources :