🧩 Constraint Solving POTD:Problem of the Day: The Chinese Postman Problem

[github-actions[bot]]

Problem Statement

The Chinese Postman Problem (CPP) asks: given a weighted graph representing a network of streets or routes, what is the shortest closed walk that traverses every edge at least once?

This differs from the Traveling Salesman Problem (TSP), which visits every vertex. Here, we must cover every edge.

Concrete Instance

Consider a mail carrier delivering letters on a street network:

• 6 intersections (vertices)
• 7 streets (edges) with distances:
  • A–B: 2, B–C: 3, C–D: 2, D–E: 4, E–F: 3, F–A: 5, B–D: 6

Goal: Find the shortest route that traverses all 7 streets and returns to the starting point, repeating some streets if necessary.

Output: The total distance of the optimal route.

---

Why It Matters

Mail delivery & waste collection: Postal carriers and garbage trucks must traverse every street in their assigned zone at least once. CPP directly models this routing requirement.

Snow plowing & road maintenance: Municipal services must plow or repair every road before returning to the depot. CPP captures the essence of minimizing travel distance while ensuring complete coverage.

Network inspection: Utility companies inspecting gas lines, electrical cables, or water mains need efficient routes covering all segments.

---

Modeling Approaches

Approach 1: Graph-Theoretic / Matching (Classic CPP)

Paradigm: Pure combinatorial optimization using graph theory.

Key idea:

• If all vertices have even degree, the graph is Eulerian—a closed walk traversing each edge exactly once exists.
• If some vertices have odd degree, add duplicated edges to make all vertices even.
• Find a minimum-weight perfect matching on odd-degree vertices.
• The result is an Eulerian graph; find any Eulerian circuit.

Decision variables: Which edges to duplicate (binary assignment).

Constraints: Every vertex must have even degree after duplication.

Trade-offs:

• ✅ Elegant, theoretically sound; polynomial-time solvable (via matching algorithms).
• ❌ Requires recognizing odd-degree vertices and solving a matching subproblem.
• Best for: Moderate-sized, dense networks.

---

Approach 2: Integer Linear Programming (ILP)

Paradigm: MIP formulation with flow conservation.

Key idea:

• Decision variable x_e ∈ Z+ = number of times edge e is traversed.
• Flow constraints ensure a connected closed walk.
• Minimize total cost: ∑ cost(e) × x_e.

Constraints:

• Each edge traversed at least once: x_e ≥ 1 ∀ e
• Flow conservation: in-degree equals out-degree at each vertex
• Connectivity: single connected component

Trade-offs:

• ✅ Flexible; easily adapted for variants (constraints, asymmetric costs).
• ❌ General-purpose solver; no special structure exploitation.
• Best for: Small-to-medium instances, or when constraints are complex.

Example Model (Pseudo-code)

minimize:
  sum over all edges e: cost(e) * x_e

subject to:
  # Each edge traversed at least once
  x_e >= 1                          for all edges e

  # Flow conservation: in-degree = out-degree
  sum(x_e : e = (u, *)) == 
  sum(x_e : e = (*, u))            for all vertices u

  # Non-negativity
  x_e >= 0                          for all edges e
  x_e in Z                          (integer)

---

Key Techniques

1. Odd-Degree Vertex Matching

The CPP reduces to finding a minimum-weight perfect matching on vertices of odd degree. After matching, duplicate these edges and solve the Eulerian circuit problem—linear-time via Hierholzer's or Fleury's algorithm.

2. Chinese Postman Variants: Directedness

• Undirected CPP: Use matching (polynomial).
• Directed CPP: More complex; requires checking if a closed walk exists (strong connectivity) and solving a circulation problem.

3. Relaxation & Bounds

For heuristic or approximation approaches, relax the integer constraint or use LP relaxation to obtain a lower bound. A simple heuristic: traverse the MST twice (2-approximation for undirected graphs).

---

Challenge Corner

Can you extend the Chinese Postman Problem to handle this real-world scenario?

Suppose the mail carrier has a maximum working day of 8 hours, and certain streets cannot be traversed during rush hour (9–10 AM). How would you model this as a time-dependent, capacitated variant?

Additionally: if the graph is directed (one-way streets), does the solution method change fundamentally?

---

References

1. Korte, B., & Vygen, J. (2018). Combinatorial Optimization: Theory and Algorithms (6th ed.). Springer. – Comprehensive treatment of graph algorithms and the CPP.

2. Dror, M. (Ed.). (2000). Arc Routing: Theory, Solutions and Applications. Kluwer Academic. – Definitive reference for arc-routing problems.

3. Christofides, N. (1973). "Graph theory: An algorithmic approach." Computer Science and Applied Mathematics. – Classic text introducing matchings and Eulerian paths.

4. Eiselt, H. A., Gendreau, M., & Laporte, G. (1995). "Arc routing problems, Part I: The Chinese postman problem." Operations Research, 43(2), 231–242. – Seminal survey of CPP variants and solution methods.

---

Discussion: What challenges have you encountered when routing vehicles or workers to cover all streets? Share your problem variations or solution approaches in the comments!

Generated by 🧩 Constraint Solving — Problem of the Day · 29.3 AIC · ⌖ 4.3 AIC · ⊞ 25.4K · ◷

• expires on Jun 21, 2026, 4:08 AM UTC-08:00

[github-actions[bot]]

This discussion was automatically closed because it expired on 2026-06-21T12:08:01.381Z.

Closed by Workflow