The mixed general routing polyhedron

The mixed general routing polyhedron

0.00 Avg rating0 Votes
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: , ,
Keywords: programming: integer, programming: network
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.