document: A GRASP heuristic for the mixed Chinese postman problem Arc routing problems -LRB- ARPs -RRB- consist of finding a traversal on a graph satisfying some conditions related to the links of the graph . In the Chinese postman problem -LRB- CPP -RRB- the aim is to find a minimum cost tour -LRB- closed walk -RRB- 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 -LRB- having edges and arcs -RRB- , the problem turns out to be NP-hard . In this paper , we present a heuristic algorithm for this problem , the so-called Mixed CPP -LRB- MCPP -RRB- , based on greedy randomized adaptive search procedure -LRB- GRASP -RRB- 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
doc_bio_tags: O B I O O B I I I B I I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I I O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O B I I I I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O