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.
[1] The problem has been proven to be NP-complete by Papadimitriou.
[2] The mixed Chinese postman problem often arises in arc routing problems 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.
[3][4] The mathematical definition is: Input: A strongly connected, mixed graph
Question: is there a (directed) tour that traverses every edge in
[5] The main difficulty in solving the Mixed Chinese Postman problem lies in choosing orientations for the (undirected) edges when we are given a tight budget for our tour and can only afford to traverse each edge once.
We then have to orient the edges and add some further arcs in order to obtain a directed Eulerian graph, that is, to make every vertex balanced.
If there are multiple edges incident to one vertex, it is not an easy task to determine the correct orientation of each edge.
[6] The mathematician Papadimitriou analyzed this problem with more restrictions; "MIXED CHINESE POSTMAN is NP-complete, even if the input graph is planar, each vertex has degree at most three, and each edge and arc has cost one.
"[7] The process of checking if a mixed graph is Eulerian is important to creating an algorithm to solve the Mixed Chinese Postman problem.
The degrees of a mixed graph G must be even to have an Eulerian cycle, but this is not sufficient.
[8] The fact that the Mixed Chinese Postman is NP-hard has led to the search for polynomial time algorithms that approach the optimum solution to reasonable threshold.
Frederickson developed a method with a factor of 3/2 that could be applied to planar graphs,[9] and Raghavachari and Veerasamy found a method that does not have to be planar.
[10] However, polynomial time cannot find the cost of deadheading, the time it takes a snow plough to reach the streets it will plow or a street sweeper to reach the streets it will sweep.
[11][12] Given a strongly connected mixed graph
, the MCPP consists of finding a minim-cost tour passing through each link
denotes the set of edges with exactly one endpoint in
(indegree) denotes the number of arcs enter
(outdegree) is the number of arcs leaving
(degree) is the number of links incident with
of vertices, the difference between the number of arcs directed from
, and the number of arcs directed from
, is no greater than the number of undirected edges joining
It is a well known fact that a mixed graph
is even and symmetric, then G is also balanced (and Eulerian).
can be solved exactly in polynomial time.
A paper published by Hua Jiang et.
al laid out a genetic algorithm to solve the mixed chinese postman problem by operating on a population.