Article ID: | iaor20041758 |
Country: | Germany |
Volume: | 96 |
Issue: | 1 |
Start Page Number: | 103 |
End Page Number: | 137 |
Publication Date: | Jan 2003 |
Journal: | Mathematical Programming |
Authors: | Corbern A., Sanchis J.M., Romero A. |
Keywords: | programming: integer, programming: network |
In Arc Routing Problem, ARPs, the aim is to find on a graph a minimum cost traversal satisfying some conditions related to the links of the graph. Due to restrictions to traverse some streets in a specified way, most applications of ARPs must be modeled with a mixed graph. Although several exact algorithms have been proposed, no polyhedral investigations have been done for ARPs on a mixed graph. In this paper we deal with the Mixed General Routing Problem which consists of finding a minimum cost traversal of a given link subset and a given vertex subset of a mixed graph. A formulation is given that uses only one variable for each link (edge or arc) of the graph. Some properties of the associated polyhedron and some large families of facet-inducing inequalities are described. A preliminary cutting-plane algorithm has produced very good lower bounds over a set of 100 randomly generated instances of the Mixed Rural Postman Problem. Finally, applications of this study to other known routing problems are described.