Mixed Chinese postman problem

<p>The mixed Chinese postman problem (MCPP or MCP) is the search for the shortest traversal of a graph with a set of vertices V, a set of undirected edges E with positive rational weights, and a set of directed arcs A with positive rational weights that covers each edge or arc at least once at minimal cost. The problem has been proven to be <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> by <a href="/facts/Christos_Papadimitriou/rXflR4or">Papadimitriou</a>. The mixed Chinese postman problem often arises in <a href="/facts/Arc_routing_Problem/pM9Aj6g3">arc routing problems</a> such as snow ploughing, where some streets are too narrow to traverse in both directions while other streets are bidirectional and can be plowed in both directions. It is easy to check if a mixed graph has a postman tour of any size by verifying if the graph is strongly connected. The problem is NP hard if we restrict the postman tour to traverse each arc exactly once or if we restrict it to traverse each edge exactly once, as proved by Zaragoza Martinez.
</p>

Mixed Chinese postman problem open-in-new

Mixed Chinese postman problem