6533b82afe1ef96bd128c127
RESEARCH PRODUCT
A GRASP heuristic for the mixed Chinese postman problem
Rafael MartíÁNgel CorberánJosé M. Sanchissubject
Information Systems and ManagementGeneral Computer ScienceHeuristic (computer science)GRASPMixed graphManagement Science and Operations ResearchIndustrial and Manufacturing EngineeringCombinatoricsTree traversalRoute inspection problemModeling and SimulationGraph (abstract data type)Arc routingGreedy randomized adaptive search procedureMathematicsofComputing_DISCRETEMATHEMATICSMathematicsdescription
Abstract 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 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 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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2002-10-01 | European Journal of Operational Research |