2000 | OriginalPaper | Chapter
ARC Routing
Authors : Prof. H. A. Eiselt, Prof. C.-L. Sandblom
Published in: Integer Programming and Network Models
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Arc routing problems are among the earliest problems known in the theory of graphs. The source is the Swiss mathematician Leonhard Euler and his famed Königsberg Bridge Problem posed in 1736. It concerns a walk across the seven bridges of Königsberg that lead across the Pregel River; see Figure II.35a. The question Euler asked was whether or not a walk would exist on which each of the bridges is crossed exactly once. When presenting the problem and its solution to the St. Petersburg Academy, Euler did not use the geographical picture of the city, river, and bridges, but a graph-theoretical representation of them which represents bridges as edges, and the ends of the bridges at an island or the banks of the river as nodes. This representation is shown in Figure II.35b.