Arc Routing: Theory, Solutions and Applications

by Moshe Dror (Editor)

Overview

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.

Product Details

ISBN-13:	9781461370260
Publisher:	Springer US
Publication date:	10/04/2012
Edition description:	Softcover reprint of the original 1st ed. 2000
Pages:	483
Product dimensions:	6.10(w) x 9.25(h) x 0.04(d)

Table of Contents

1 A Historical Perspective on Arc Routing.- 1.1 Introduction.- 1.2 The Chinese Postman Problem.- 1.3 The Rural Postman Problem.- 1.4 The Capacitated Arc Routing Problem.- 1.5 Research Outlooks.- I Theory.- 2 Traversing Graphs: The Eulerian and Hamiltonian Theme.- 3 Matching: Arc Routing and the Solution Connection.- 4 Arc Routing: Complexity and Approximability.- 5 Chinese Postman and Euler Tour Problems in Bi-directed Graphs.- II Solutions.- 6 Polyhedral Theory for Arc Routing Problems.- 7 Linear Programming Based Methods for Solving Arc Routing Problems.- 8 Transformations and Exact Node Routing Solutions by Column Generation.- 9 Heuristic Algorithms.- III Applications.- 10 Roadway Snow and Ice Control.- 11 Scheduling of Local Delivery Carrier Routes for the United States Postal Service.- 12 Livesk Feed Distribution and Arc Traversal Problems.

Editorial Reviews

Around 1736 well known German mathematician Leonhard Euler was asked whether there was a route for a marching band that started and ended on an island by crossing the seven connecting bridges only once each. His demonstration that there was not was the foundation of arc routing, which has since become a fundamental optimization concept in operations research and found many applications in transportation, telecommunications, manufacturing, the Internet, and other areas. Scholars of business, engineering, and mathematics, most from North America and Europe, examine such topics as the Eulerian and Hamiltonian theme, complexity and approximability, polyhedral theory, transformations and exact node routing solutions by column generation, heuristic algorithms, roadway snow and ice control, postal routes, and livestock feed distribution. Annotation c. Book News, Inc., Portland, OR (booknews.com)

Booknews