Article ID: | iaor20032021 |
Country: | Netherlands |
Volume: | 142 |
Issue: | 1 |
Start Page Number: | 70 |
End Page Number: | 80 |
Publication Date: | Oct 2002 |
Journal: | European Journal of Operational Research |
Authors: | Corbern A., Sanchis J.M., Mart R. |
Keywords: | vehicle routing & scheduling, heuristics |
Arc routing problems consist of finding a traversal on a graph satisfying some conditions related to the links of the graph. In the Chinese postman problem (CPP) the aim is to find a minimum cost tour (closed walk) traversing all the links of the graph at least once. Both the Undirected CPP, where all the links are edges that can be traversed in both ways, and the Directed CPP, where all the links are arcs that must be traversed in a specified way, are known to be polynomially solvable. However, if we deal with a mixed graph (having edges and arcs), the problem turns out to be