Questions?
Home > Glossary > Route Optimization > Chinese Postman Problem (CPP): Complete Guide with Solutions 2024
The Chinese Postman Problem (CPP) is a kind of routing problem in which a postman must determine the quickest path to carry mail to every address on a certain set of streets. The issue is made more difficult by the possibility that some streets must be traversed more than once to finish the delivery route.
The goal of CPP is to find a route that reaches every street (or edge) at least once and returns to the starting location while reducing the overall distance traveled. It was first introduced by a Chinese mathematician named Kwan Mei-Ko in 1962 while studying a problem related to postal delivery in Beijing. This is the reason it is referred to as the “Chinese Postman Problem.”
There is no known algorithm that can solve the problems of vehicle routing in polynomial time for all instances because it is known to be NP-hard. This problem is useful in several fields including circuit design, DNA sequencing, and transportation planning.
The key variables in the Chinese Postman Problem include the number of edges (streets), their lengths, and whether they must be traversed once or multiple times. These factors influence the overall complexity of the problem and the optimization approach needed to minimize travel distance.
The Chinese Postman Problem’s practical relevance lies in its adaptability to transportation planning scenarios. It provides insights into route optimization and network analysis, offering foundational strategies for designing efficient systems and improving logistical operations.
Graph theory studies the properties and applications of graphs that consist of vertices (or nodes) connected by edges (or links).
Here are the basic components.
A graph G is formally defined as G = (V, E), where V represents vertices and E represents edges.
The Chinese Postman Problem (CPP) focuses on determining the shortest closed path that you need to reach every edge of a graph at least once. The mathematical formulation can be expressed as follows:
Minimize ⅀dexe
In different cases that need efficient route planning, you can apply CPP.
Below are the two examples.
The CPP helps develop strategies to ensure the efficient movement of products or people across networks.
The Chinese Postman Problem (CPP) is also known as the Route Inspection Problem. It is a difficult problem to solve using conventional methods, which means it can take a very long time to identify the optimal solution. However, researchers have found that there are shortcuts that can be utilized to find the answer more quickly for specific kinds of graphs.
Researchers have employed heuristic algorithms as one approach to solve the Chinese Postman Problem. Using approximation methods to create solutions that are close to the optimum solution is another way to handle the Chinese Postman Problem’s complexity.
As we have learned the complexity of the Chinese Postman Problem, let us find out how it works:
The goal of the Chinese Postman Problem in graph theory involves finding the shortest path that passes by each edge of a given graph at least once. The objective is to make sure that all edges are covered as well as possible.
We must first identify the odd vertices, or vertices with an odd number of edges, to solve CPP. This is crucial because the starting and ending sites must have an equal number of edges.
After locating the odd vertices, we must couple them so that the total weight of the edges connecting them is as low as possible. This step makes sure that there are an equal amount of edges on each vertex.
The new graph that is produced next has both the original graph and the newly added edges from step three. The vertices of this new graph must all be of even degree.
Finally, if your input graph has the Euler circuit, it is a path that precisely traverses each graph edge. The CPP can be resolved by taking this route.
Even if the Chinese Postman Problem may appear to be challenging, the above steps guarantee that all graph edges are covered in the most effective way possible.
The Chinese Postman Problem (CPP) can be solved using several different algorithms. Typical algorithms include the following:
def hierholzer(graph):
stack = []
circuit = []
current_vertex = list(graph.keys())[0]
while stack or graph[current_vertex]:
if not graph[current_vertex]:
circuit.append(current_vertex)
current_vertex = stack.pop()
else:
stack.append(current_vertex)
next_vertex = graph[current_vertex].pop()
graph[next_vertex].remove(current_vertex)
current_vertex = next_vertex
return circuit
This algorithm ensures that the final result is at most 1.5 times better than the weighted CPP’s ideal solution. The technique operates by first locating the graph’s lowest spanning tree, then locating a minimum weight match between vertices of odd degrees, and finally locating an Euler circuit that encompasses all of the graph’s edges.
def christofides(graph):
mst = minimum_spanning_tree(graph)
odd_vertices = [v for v in mst if degree(mst, v) % 2 == 1]
matching = minimum_weight_perfect_matching(odd_vertices, graph)
eulerian_graph = combine(mst, matching)
eulerian_circuit = find_eulerian_circuit(eulerian_graph)
hamiltonian_path = convert_to_hamiltonian(eulerian_circuit)
return hamiltonian_path
A graph matching algorithm called the Blossom can be used to get the least weight match between vertices in the graph with odd degrees. This approach is built on the idea of augmenting pathways, which are paths that alternate between matched and unmatched edges while beginning and ending with unmatched vertices.
In general, every one of these algorithms offers a unique strategy for resolving the Chinese Postman Problem.
def blossom(graph):
matching = {}
def find_augmenting_path(start):
# Implement BFS or DFS to find an augmenting path
pass
for vertex in graph:
if vertex not in matching:
path = find_augmenting_path(vertex)
if path:
# Update matching with the new augmenting path
return matching
Below are a few widespread misunderstandings about the Chinese Postman Problem, including:
To properly understand the variety of applications and intricacy of the Chinese Postman Problem, it is crucial to dispel these misconceptions.
The Chinese Postman Problem (CPP) is a well-known problem in graph theory that has several real-world applications. It is significant to remember that CPP applies to a variety of industries, including circuit board design and transportation, in addition to postal delivery.
Furthermore, there are a number of widespread misconceptions about CPP, including the notion that it is effective in all situations and that it only applies to undirected graphs. The fundamentals of CPP and its applications can be helpful in many different industries, and computer science research is still being done in this area.
Rakesh Patel, author of two defining books on reverse geotagging, is a trusted authority in routing and logistics. His innovative solutions at Upper Route Planner have simplified logistics for businesses across the board. A thought leader in the field, Rakesh's insights are shaping the future of modern-day logistics, making him your go-to expert for all things route optimization. Read more.
Wait!
Grab a FREE Trial of Upper
Grab a FREE Trial of Upper TODAY!