Eine Plattform für die Wissenschaft: Bauingenieurwesen, Architektur und Urbanistik
Eine Plattform für die Wissenschaft: Bauingenieurwesen, Architektur und Urbanistik
A Heuristic Algorithm for the Mixed Chinese Postman Problem
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 with slightly modified costs 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.
A Heuristic Algorithm for the Mixed Chinese Postman Problem
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 with slightly modified costs 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.
A Heuristic Algorithm for the Mixed Chinese Postman Problem
Yaoyuenyong, Kriangchai (Autor:in) / Charnsethikul, Peerayuth (Autor:in) / Chankong, Vira (Autor:in)
Optimization and Engineering ; 3 ; 157-187
01.06.2002
31 pages
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
A Heuristic Algorithm for the Mixed Chinese Postman Problem
| British Library Conference Proceedings | 2002
A Heuristic Algorithm for the Mixed Chinese Postman Problem
| Online Contents | 2002
Producing Postman Pat: The popular cultural construction of idyllic rurality
| Online Contents | 2008