Free Access
RAIRO-Oper. Res.
Volume 53, Number 1, January–March 2019
Page(s) 303 - 322
Published online 15 February 2019
  • 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. [CrossRef] [Google Scholar]
  • J.E. Beasley and N. Christofides, Vehicle routing with a sparse feasibility graph. Eur. J. Oper. Res. 98 (1997) 499–511. [Google Scholar]
  • J.M. Belenguer and E. Benavent, The capacitated arc routing problem: valid inequalities and facets. Comput. Optim. Appl. 10 (1998) 165–187. [Google Scholar]
  • J.M. Belenguer and E. Benavent, A cutting plane algorithm for the capacitated arc routing problem. Comput. Oper. Res. 30 (2003) 705–728. [Google Scholar]
  • 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. [Google Scholar]
  • C. Bode and S. Irnich, Cut-first branch-and-price-second for the capacitated arc-routing problem. Oper. Res. 60 (2012) 1167–1182. [Google Scholar]
  • 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. [Google Scholar]
  • 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. [CrossRef] [MathSciNet] [Google Scholar]
  • 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. [Google Scholar]
  • G.B. Dantzig and J.H. Ramser, The truck dispatching problem. Manage. Sci. 6 (1959) 80–91. [Google Scholar]
  • 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. [Google Scholar]
  • 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). [Google Scholar]
  • M. Dror editor, Arc Routing – Theory, Solutions and Applications. Kluwer Academic Publishers (2000). [Google Scholar]
  • 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. [Google Scholar]
  • 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. [Google Scholar]
  • 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 (2005). [Google Scholar]
  • G. Ghiani and G. Laporte, A branch-and-cut algorithm for the undirected rural postman problem. Math. Program. 87 (2000) 467–481. [Google Scholar]
  • G. Ghiani, R. Musmanno, G. Paletta and C. Triki, A heuristic for the periodic rural postman problem. Comput. Oper. Res. 32 (2005) 219–228. [Google Scholar]
  • F. Glover, Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13 (1986) 533–549. [Google Scholar]
  • B.L. Golden and R.T. Wong, Capacitated arc routing problems. Networks 11 (1981) 305–315. [Google Scholar]
  • 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). [Google Scholar]
  • J.T. Gross and J. Yellen, Graph Theory and its Applications, 2nd edition. CRC Press, Boca Raton, FL (2006). [Google Scholar]
  • G. Gutin and A.P. Punnen, The Traveling Salesman Problem and its Variations. Springer, Boston, MA (2006). [Google Scholar]
  • P. Hansen, The steepest ascent mildest descent heuristic for combinatorial programming, Presented at the Congress on Numerical Methods in Combinatorial Optimization. Capri, Italy (1986). [Google Scholar]
  • A. Hertz, G. Laporte and M. Mittaz, A tabu search heuristic for the capacitated arc routing problem. Oper. Res. 48 (2000) 129–135. [Google Scholar]
  • 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. [Google Scholar]
  • A. Kansou and A. Yassine, New upper bounds for the multi-depot capacitated arc routing problem. Int. J. Metaheuristics 1 (2010) 81–95. [CrossRef] [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • 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. [Google Scholar]
  • G. Laporte, Modeling and solving several classes of arc routing problems as travelling salesman problems. Comput. Oper. Res. 24 (1997) 1057–1061. [Google Scholar]
  • A.N. Letchford, Polyhedral results for some constrained arc-routing problems. Ph.D. thesis, Lancaster University, Lancaster, UK (1997). [Google Scholar]
  • A.N. Letchford and R.W. Eglese, The rural postman problem with deadline classes. Eur. J. Oper. Res. 105 (1998) 390–400. [Google Scholar]
  • 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. [Google Scholar]
  • J. Nešetřil and P.O. Mendez, Sparsity: Graphs, Structures and Algorithms. Springer, Berlin Heidelberg (2012). [Google Scholar]
  • A. Oukil, Exploiting sparsity in vehicle routing algorithms. Ph. D. thesis, Lancaster University, Lancaster, UK (2008). [Google Scholar]
  • M.W. Padberg and M.R. Rao, Odd minimum cut’sets and b-matchings. Math. Oper. Res. 7 (1982) 67–80. [CrossRef] [MathSciNet] [Google Scholar]
  • 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. [CrossRef] [Google Scholar]
  • M.W. Padberg and G. Rinaldi, Facet identification for the symmetric traveling salesman polytope. Math. Program. 47 (1990) 219–257. [Google Scholar]
  • 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. [CrossRef] [MathSciNet] [Google Scholar]
  • W.L. Pearn, A. Assad and B.L. Golden, Transforming arc routing into node routing problems. Comput. Oper. Res. 14 (1987) 285–288. [Google Scholar]
  • W.L. Pearn, Solvable cases of the k-person Chinese postman problem. Oper. Res. Lett. 16 (1994) 241–244. [CrossRef] [Google Scholar]
  • A. van Rooij and H. Wilf, The interchange graph of a finite graph. Acta Math. Acad. Sci. Hungar. 16 (1965) 263–269. [CrossRef] [Google Scholar]
  • 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. [Google Scholar]
  • A. Sbihi, A cooperative local search-based algorithm for the Multiple-Scenario Max-Min Knapsack problem. Eur. J. Oper. Res. 202 (2010) 339–346. [Google Scholar]
  • S. Skiena, Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. In Line graph, Section 4.1.5. p. 128 (1990) 135–139. [Google Scholar]
  • 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). [Google Scholar]
  • 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). [Google Scholar]
  • 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). [Google Scholar]
  • S.A. Welz, Optimal solutions for the capacitated arc routing problem using integer programming. Ph.D. thesis, University of Cincinnati, Cincinnati (1994). [Google Scholar]
  • D.B. West, Characterizing line graphs, 2nd edition. In: Introduction to Graph Theory. Prentice-Hall, Englewood Cliffs, NJ (2000) 279–282. [Google Scholar]
  • S. Wøhlk, Contributins to arc routing. Ph.D. thesis, University of Southern Denmark, Odense (2005). [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.