A GRASP heuristic for the mixed Chinese postman problem

摘要

Arc routing problems (ARPs) 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 linkds 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 linkds 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 NP-hard. In this paper, we present a heuristic algorithm for this problem, the so-called Mixed CPP (MCPP), based on greedy randomized adaptive search procedure (GRASP) techniques. The algorithm has been tested and compared with other known and recent methods from the literature on a wide collection of randomly generated instances, with up to 200 nodes and 600 links, producing encouraging computational results. As far as we know, this is the best heuristic algorithm for the MCPP, with respect to solution quality, published up to now.