Mixed Chinese postman problem

The mathematical definition is:

Input: A strongly connected, mixed graph $G=(V,E,A)$ with cost $c(e)\backslash geq0$ for every edge $e\; \backslash subset\; E\; \backslash cup\; A$ and a maximum cost $c\_\{max\}$.

Question: is there a (directed) tour that traverses every edge in $E$ and every arc in $A$ at least once and has cost at most $c\_\{max\}$?{{Cite journal |last1=Edmonds |first1=Jack |last2=Johnson |first2=Ellis L. |date=December 1973 |title=Matching, Euler tours and the Chinese postman |url=http://dx.doi.org/10.1007/bf01580113 |journal=Mathematical Programming |volume=5 |issue=1 |pages=88–124 |doi=10.1007/bf01580113 |s2cid=15249924 |issn=0025-5610}}

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.{{Cite book |last=Corberán |first=Ángel |title=Arc Routing: Problems, Methods, and Applications |year=2015 |isbn=978-1-61197-366-2}} 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."{{Cite journal |last=Papadimitriou |first=Christos H. |date=July 1976 |title=On the complexity of edge traversing |journal=Journal of the ACM |volume=23 |issue=3 |pages=544–554 |doi=10.1145/321958.321974 |s2cid=8625996 |issn=0004-5411|doi-access=free }}

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.{{Cite book |last=Randolph. |first=Ford, Lester |url=http://worldcat.org/oclc/954124517 |title=Flows in Networks |date=2016 |publisher=Princeton University Press |isbn=978-1-4008-7518-4 |oclc=954124517}}

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,{{Cite journal |last=Frederickson |first=Greg N. |date=July 1979 |title=Approximation Algorithms for Some Postman Problems |journal=Journal of the ACM |volume=26 |issue=3 |pages=538–554 |doi=10.1145/322139.322150 |s2cid=16149998 |issn=0004-5411|doi-access=free }} and Raghavachari and Veerasamy found a method that does not have to be planar.{{Cite journal |last1=Raghavachari |first1=Balaji |last2=Veerasamy |first2=Jeyakesavan |date=January 1999 |title=A 3/2-Approximation Algorithm for the Mixed Postman Problem |url=http://dx.doi.org/10.1137/s0895480197331454 |journal=SIAM Journal on Discrete Mathematics |volume=12 |issue=4 |pages=425–433 |doi=10.1137/s0895480197331454 |issn=0895-4801}} 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.{{Cite book |last=Zaragoza Martinez |first=Francisco |title=2006 Seventh Mexican International Conference on Computer Science |chapter=Complexity of the Mixed Postman Problem with Restrictions on the Edges |date=2006 |chapter-url=http://dx.doi.org/10.1109/enc.2006.9 |pages=3–10 |publisher=IEEE |doi=10.1109/enc.2006.9|isbn=0-7695-2666-7 |s2cid=17176905 }}{{Cite book |last=Zaragoza Martinez |first=Francisco |title=2006 3rd International Conference on Electrical and Electronics Engineering |chapter=Complexity of the Mixed Postman Problem with Restrictions on the Arcs |date=September 2006 |chapter-url=http://dx.doi.org/10.1109/iceee.2006.251877 |pages=1–4 |publisher=IEEE |doi=10.1109/iceee.2006.251877|isbn=1-4244-0402-9 }}

Given a strongly connected mixed graph $G=(V,E,A)$ with a vertex set $V$, and edge set $E$, an arc set $A$ and a nonnegative cost $c\_e$ for each $e\; \backslash in\; E\; \backslash cup\; A$, the MCPP consists of finding a minim-cost tour passing through each link $e\backslash in\; E\; \backslash cup\; A$ at least once.

Given $S\backslash subset\; V$, $\backslash delta^+(S)=\backslash \{(i,j)\backslash in\; A:i\backslash in\; S,\; j\; \backslash in\; V\; \backslash backslash\; S\; \backslash \}$, $\backslash delta^-(S)=\backslash \{\; (i,j)\backslash in\; A:i\backslash in\; V\backslash backslash\; S,\; j\; \backslash in\; S\; \backslash \}$, $\backslash delta(S)$ denotes the set of edges with exactly one endpoint in $S$, and $\backslash delta^\backslash star=\backslash delta(S)\backslash cup\; \backslash delta^+(S)\; \backslash cup\; \backslash delta^-$. Given a vertex $i$, $d\_i^-$(indegree) denotes the number of arcs enter $i$, $d\_i^+$(outdegree) is the number of arcs leaving $i$, and $d\_i$ (degree) is the number of links incident with $i$.{{Cite book |last=Corberán |first=Ángel |title=Arc Routing: Problems, Methods, and Applications |year=2015 |isbn=978-1-61197-366-2}} Note that $d\_i=|\backslash delta^\backslash star(\backslash \{\{i\}\backslash \})|$. A mixed graph $G=(V,E,A)$ is called even if all of its vertices have even degree, it is called symmetric if $d\_i^-=d\_i^+$ for each vertex $i$, and it is said to be balanced if, given any subset $S$ of vertices, the difference between the number of arcs directed from $S$ to $V\backslash backslash\; S$, $|\backslash delta^+(S)|$, and the number of arcs directed from $V\backslash backslash\; S$ to $S$, $|\backslash delta^-(S)|$, is no greater than the number of undirected edges joining $S$ and $V\; \backslash backslash\; S$, $|\backslash delta\; (S)|$.

It is a well known fact that a mixed graph $G$ is Eulerian if and only if $G$ is even and balanced.{{Cite book |last=Ford |first=L.R. |title=Flows in Networks |publisher=Princeton University Press |year=1962 |location=Princeton, N.J.}} Notice that if $G$ is even and symmetric, then G is also balanced (and Eulerian). Moreover, if $G$ is even, the $MCPP$ can be solved exactly in polynomial time.{{Cite journal |last1=Edmonds |first1=Jack |last2=Johnson |first2=Ellis L. |date=December 1973 |title=Matching, Euler tours and the Chinese postman |url=http://dx.doi.org/10.1007/bf01580113 |journal=Mathematical Programming |volume=5 |issue=1 |pages=88–124 |doi=10.1007/bf01580113 |s2cid=15249924 |issn=0025-5610}}

1. Given an even and strongly connected mixed graph $G=(V,E,A)$, let $A\_1$ be the set of arcs obtained by randomly assigning a direction to the edges in $E$ and with the same costs. Compute $s\_i=d\_i^--d\_i^+$ for each vertex i in the directed graph $(V,\; A\backslash cup\; A\_1)$. A vertex $i$ with will be considered as a source (sink) with supply demand $s\_i(-s\_i)$. Note that as $G$ is an even graph, all supplies and demands are even numbers (zero is considered an even number).
2. Let $A\_2$ be the set of arcs in the opposite direction to those in $A\_1$ and with the costs of those corresponding edges, and let $A\_3$ be the set of arcs parallel to $A\_2$ at zero cost.
3. To satisfy the demands $s\_i$ of all the vertices, solve a minimum cost flow problem in the graph $(V,\; A\backslash cup\; A\_1\backslash cup\; A\_2\backslash cup\; A\_3)$, in which each arc in $A\backslash cup\; A\_1\backslash cup\; A\_2$ has infinite capacity and each arc in $A\_3$ has capacity 2. Let $x\_\{ij\}$ be the optimal flow.
4. For each arc $(i,j)$ in $A\_3$ do: If $x\_\{ij\}=2$, then orient the corresponding edge in $G$ from $i$ to $j$ (the direction, from $j$ to $i$, assigned to the associated edge in step 1 was "wrong"); if $x\_\{ij\}=0$, then orient the corresponding edge in $G$ from $j$ to $i$ (in this case, the orientation in step 1 was "right"). Note the case $x\_\{ij\}=1$ is impossible, as all flow values through arcs in $A\_3$ are even numbers.
5. Augment $G$ by adding $x\_\{ij\}$ copies of each arc in $A\; \backslash cup\; A\_1\; \backslash cup\; A\_2$. The resulting graph is even and symmetric.

When the mixed graph is not even and the nodes do not all have even degree, the graph can be transformed into an even graph.

• Let $\backslash mathrm\{G=\backslash \{V,E,A\backslash \}\}$ be a mixed graph that is strongly connected. Find the odd degree nodes by ignoring the arc directions and obtain a minimal-cost matching. Augment the graph with the edges from the minimal cost matching to generate an even graph $\backslash mathrm\{G\text{'}=\backslash \{V\text{'},E\text{'},A\text{'}\backslash \}\}$.
• The graph is even but is not symmetric and an eulerian mixed graph is even and symmetric. Solve a minimum cost flow problem in $G\text{'}$ to obtain a symmetric graph that may not be even $G\text{'}\text{'}$.
• The final step involves making the symmetric graph $G$ even. Label the odd degree nodes $V\_O$. Find cycles that alternate between lines in the arc set $A$ \backslash A and lines in the edge set $E$ that start and end at points in $V\_O$. The arcs in $A$\backslash A should be considered as undirected edges, not as directed arcs.

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. The algorithm performed well compared to other approximation algorithms for the MCPP.{{Citation |last1=Jiang |first1=Hua |title=Genetic Algorithm for Mixed Chinese Postman Problem |date=2010 |url=http://link.springer.com/10.1007/978-3-642-16493-4_20 |work=Advances in Computation and Intelligence |volume=6382 |pages=193–199 |editor-last=Cai |editor-first=Zhihua |place=Berlin, Heidelberg |publisher=Springer Berlin Heidelberg |doi=10.1007/978-3-642-16493-4_20 |isbn=978-3-642-16492-7 |access-date=2022-10-25 |last2=Kang |first2=Lishan |last3=Zhang |first3=Shuqi |last4=Zhu |first4=Fei |series=Lecture Notes in Computer Science |editor2-last=Hu |editor2-first=Chengyu |editor3-last=Kang |editor3-first=Zhuo |editor4-last=Liu |editor4-first=Yong}}

• Capacitated arc routing problem

{{Reflist}}

Category:Computational problems in graph theory