Mixed Chinese postman problem
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]
Mathematical Definition
The mathematical definition is:
Input: A strongly connected, mixed graph with cost for every edge and a maximum cost .
Question: is there a (directed) tour that traverses every edge in and every arc in at least once and has cost at most ?[5]
Computational complexity
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]
Eulerian graph
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]
Approximation
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]
Formal definition
Given a strongly connected mixed graph with a vertex set , and edge set , an arc set and a nonnegative cost for each , the MCPP consists of finding a minim-cost tour passing through each link at least once.
Given , , , denotes the set of edges with exactly one endpoint in , and . Given a vertex , (indegree) denotes the number of arcs enter , (outdegree) is the number of arcs leaving , and (degree) is the number of links incident with .[13] Note that . A mixed graph is called even if all of its vertices have even degree, it is called symmetric if for each vertex , and it is said to be balanced if, given any subset of vertices, the difference between the number of arcs directed from to , , and the number of arcs directed from to , , is no greater than the number of undirected edges joining and , .
It is a well known fact that a mixed graph is Eulerian if and only if is even and balanced.[14] Notice that if is even and symmetric, then G is also balanced (and Eulerian). Moreover, if is even, the can be solved exactly in polynomial time.[15]
Even MCPP Algorithm
- Given an even and strongly connected mixed graph , let be the set of arcs obtained by randomly assigning a direction to the edges in and with the same costs. Compute for each vertex i in the directed graph . A vertex with will be considered as a source (sink) with supply demand . Note that as is an even graph, all supplies and demands are even numbers (zero is considered an even number).
- Let be the set of arcs in the opposite direction to those in and with the costs of those corresponding edges, and let be the set of arcs parallel to at zero cost.
- To satisfy the demands of all the vertices, solve a minimum cost flow problem in the graph , in which each arc in has infinite capacity and each arc in has capacity 2. Let be the optimal flow.
- For each arc in do: If , then orient the corresponding edge in from to (the direction, from to , assigned to the associated edge in step 1 was "wrong"); if , then orient the corresponding edge in from to (in this case, the orientation in step 1 was "right"). Note the case is impossible, as all flow values through arcs in are even numbers.
- Augment by adding copies of each arc in . The resulting graph is even and symmetric.
Heuristic algorithms
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 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 .
- The graph is even but is not symmetric and an eulerian mixed graph is even and symmetric. Solve a minimum cost flow problem in to obtain a symmetric graph that may not be even .
- The final step involves making the symmetric graph even. Label the odd degree nodes . Find cycles that alternate between lines in the arc set and lines in the edge set that start and end at points in . The arcs in should be considered as undirected edges, not as directed arcs.
Genetic algorithm
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.[16]
See also
References
- ^ Minieka, Edward (July 1979). "The Chinese Postman Problem for Mixed Networks". Management Science. 25 (7): 643–648. doi:10.1287/mnsc.25.7.643. ISSN 0025-1909.
- ^ Papadimitriou, Christos H. (July 1976). "On the complexity of edge traversing". Journal of the ACM. 23 (3): 544–554. doi:10.1145/321958.321974. ISSN 0004-5411. S2CID 8625996.
- ^ Zaragoza Martinez, Francisco (September 2006). "Complexity of the Mixed Postman Problem with Restrictions on the Arcs". 2006 3rd International Conference on Electrical and Electronics Engineering. IEEE. pp. 1–4. doi:10.1109/iceee.2006.251877. ISBN 1-4244-0402-9.
- ^ Zaragoza Martinez, Francisco (2006). "Complexity of the Mixed Postman Problem with Restrictions on the Edges". 2006 Seventh Mexican International Conference on Computer Science. IEEE. pp. 3–10. doi:10.1109/enc.2006.9. ISBN 0-7695-2666-7. S2CID 17176905.
- ^ Edmonds, Jack; Johnson, Ellis L. (December 1973). "Matching, Euler tours and the Chinese postman". Mathematical Programming. 5 (1): 88–124. doi:10.1007/bf01580113. ISSN 0025-5610. S2CID 15249924.
- ^ Corberán, Ángel (2015). Arc Routing: Problems, Methods, and Applications. ISBN 978-1-61197-366-2.
- ^ Papadimitriou, Christos H. (July 1976). "On the complexity of edge traversing". Journal of the ACM. 23 (3): 544–554. doi:10.1145/321958.321974. ISSN 0004-5411. S2CID 8625996.
- ^ Randolph., Ford, Lester (2016). Flows in Networks. Princeton University Press. ISBN 978-1-4008-7518-4. OCLC 954124517.
{{cite book}}
: CS1 maint: multiple names: authors list (link) - ^ Frederickson, Greg N. (July 1979). "Approximation Algorithms for Some Postman Problems". Journal of the ACM. 26 (3): 538–554. doi:10.1145/322139.322150. ISSN 0004-5411. S2CID 16149998.
- ^ Raghavachari, Balaji; Veerasamy, Jeyakesavan (January 1999). "A 3/2-Approximation Algorithm for the Mixed Postman Problem". SIAM Journal on Discrete Mathematics. 12 (4): 425–433. doi:10.1137/s0895480197331454. ISSN 0895-4801.
- ^ Zaragoza Martinez, Francisco (2006). "Complexity of the Mixed Postman Problem with Restrictions on the Edges". 2006 Seventh Mexican International Conference on Computer Science. IEEE. pp. 3–10. doi:10.1109/enc.2006.9. ISBN 0-7695-2666-7. S2CID 17176905.
- ^ Zaragoza Martinez, Francisco (September 2006). "Complexity of the Mixed Postman Problem with Restrictions on the Arcs". 2006 3rd International Conference on Electrical and Electronics Engineering. IEEE. pp. 1–4. doi:10.1109/iceee.2006.251877. ISBN 1-4244-0402-9.
- ^ Corberán, Ángel (2015). Arc Routing: Problems, Methods, and Applications. ISBN 978-1-61197-366-2.
- ^ Ford, L.R. (1962). Flows in Networks. Princeton, N.J.: Princeton University Press.
- ^ Edmonds, Jack; Johnson, Ellis L. (December 1973). "Matching, Euler tours and the Chinese postman". Mathematical Programming. 5 (1): 88–124. doi:10.1007/bf01580113. ISSN 0025-5610. S2CID 15249924.
- ^ Jiang, Hua; Kang, Lishan; Zhang, Shuqi; Zhu, Fei (2010), Cai, Zhihua; Hu, Chengyu; Kang, Zhuo; Liu, Yong (eds.), "Genetic Algorithm for Mixed Chinese Postman Problem", Advances in Computation and Intelligence, Lecture Notes in Computer Science, vol. 6382, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 193–199, doi:10.1007/978-3-642-16493-4_20, ISBN 978-3-642-16492-7, retrieved 2022-10-25