A heuristic algorithm for the mixed Chinese Postman Problem

A heuristic algorithm for the mixed Chinese Postman Problem

0.00 Avg rating0 Votes
Article ID: iaor20042262
Country: Netherlands
Volume: 3
Issue: 2
Start Page Number: 157
End Page Number: 187
Publication Date: Jun 2002
Journal: Optimization and Engineering
Authors: , ,
Keywords: networks: path
Abstract:

The Chinese Postman Problem (CPP) is to find a minimum-cost Eulerian tour in a given graph. CPP is efficiently solvable when the original graph is either undirected or directed. For a mixed graph consisting of both edges and arcs, the Mixed Chinese Postman Problem (MCPP) is known to be NP-complete. Many heuristics and optimal algorithms have been devised for solving MCPPs. A new heuristic is proposed. The heuristic finds the initial solution by using a Minimum Cost Flow algorithm; then it repeatedly uses the shortest path algorithm and slightly modified cost of the edges/arcs. The heuristic improves the solution by trying to find the correct direction of unoriented edges and simultaneously it deletes some of the additional edges/arcs. A number of previous heuristics are tested, analyzed, and compared with the proposed approach. Based upon computational results, the proposed heuristic on average outperforms all previous heuristics.

Reviews

Required fields are marked *. Your email address will not be published.