Arc Routing Problems

In this talk we present recent results obtained for several Arc Routing Problems defined on "windy" graphs. A windy graph is an undirected graph in which the cost of traversing an edge (i,j) in a given direction, c(i,j), can be different from the cost of traversing it in the opposite direction, c(j,i). In particular we describe several constructive heuristics, and study their worst case behavior, as well as metaheuristics of Multi-Start and Scatter Search type. A polyhedral study of the Windy General Routing Problem is also presented and it is described how it has been used for the design and implementation of a Branch and Cut algorithm capable of solving to optimality WGRP instances of large size. Since undirected, directed and mixed graphs are special cases of windy graphs, most of the theoretical results obtained for the WGRP and the algorithms designed for its approximate or exact resolution can be applied to many other ARP's.