Arc Routing

1. Front Matter

   Pages i-xxiv

   PDF

2. A Historical Perspective on Arc Routing

   1. A Historical Perspective on Arc Routing

      • H. A. Eiselt, Gilbert Laporte

      Pages 1-16

3. Theory

   1. Front Matter

      Pages 17-17

      PDF

   2. Traversing Graphs: The Eulerian and Hamiltonian Theme

      • Herbert Fleischner

      Pages 19-87

   3. Matching: Arc Routing and the Solution Connection

      • Ulrich Derigs

      Pages 89-132

   4. Arc Routing: Complexity and Approximability

      • Moshe Dror

      Pages 133-169

   5. Chinese Postman and Euler Tour Problems in Bi-Directed Graphs

      • Ellis L. Johnson

      Pages 171-196

4. Solutions

   1. Front Matter

      Pages 197-197

      PDF

   2. Polyhedral Theory for Arc Routing Problems

      • Richard W. Eglese, Adam N. Letchford

      Pages 199-230

   3. Linear Programming Based Methods for Solving Arc Routing Problems

      • E. Benavent, A. Corberán, J. M. Sanchis

      Pages 231-275

   4. Transformations and Exact Node Routing Solutions by Column Generation

      • Moshe Dror, André Langevin

      Pages 277-326

   5. Heuristic Algorithms

      • Alain Hertz, Michel Mittaz

      Pages 327-386

5. Applications

   1. Front Matter

      Pages 387-387

      PDF

   2. Roadway Snow and Ice Control

      • James F. Campbell, André Langevin

      Pages 389-418

   3. Scheduling of Local Delivery Carrier Routes for the United States Postal Service

      • Lawrence Bodin, Laurence Levy

      Pages 419-442

   4. Livestock Feed Distribution and Arc Traversal Problems

      • Moshe Dror, Janny M. Y. Leung, Paul A. Mullaseril

      Pages 443-464

6. Back Matter

   Pages 465-483

   PDF

Arc Routing: Theory, Solutions and Applications is about arc traversal and the wide variety of arc routing problems, which has had its foundations in the modern graph theory work of Leonhard Euler. Arc routing methods and computation has become a fundamental optimization concept in operations research and has numerous applications in transportation, telecommunications, manufacturing, the Internet, and many other areas of modern life. The book draws from a variety of sources including the traveling salesman problem (TSP) and graph theory, which are used and studied by operations research, engineers, computer scientists, and mathematicians. In the last ten years or so, there has been extensive coverage of arc routing problems in the research literature, especially from a graph theory perspective; however, the field has not had the benefit of a uniform, systematic treatment. With this book, there is now a single volume that focuses on state-of-the-art exposition of arc routing problems, that explores its graph theoretical foundations, and that presents a number of solution methodologies in a variety of application settings. Moshe Dror has succeeded in working with an elite group of ARC routing scholars to develop the highest quality treatment of the current state-of-the-art in arc routing.

• Graph
• Graph theory
• Matching
• Node
• Polyhedral Theory
• algorithms
• linear optimization
• operations research
• optimization

• Department of Management Information Systems, University of Arizona, Tucson, USA

  Moshe Dror

Policies and ethics