🧩 Constraint Solving POTD:Problem of the Day: Arc Routing Problem

[github-actions[bot]]

Problem of the Day: The Arc Routing Problem

Problem Statement

The Arc Routing Problem (ARP) asks: given a network (graph), find the minimum-cost tour that traverses every edge (or a required subset of edges) at least once. Unlike the Traveling Salesman Problem, which focuses on visiting nodes, arc routing emphasizes covering edges—think street sweeping, mail delivery, or inspecting pipelines.

Concrete Instance

Imagine a small village with 5 streets (edges) that a garbage truck must traverse:

• Streets: (A–B, 8 km), (B–C, 6 km), (C–D, 7 km), (D–A, 5 km), (B–D, 4 km)
• Start and end at depot A
• Each street must be traversed at least once
• Minimize total distance

A valid solution might traverse: A→B→C→D→B→A, covering all edges with total distance 30 km (including the repeated edge B–D used twice).

Input/Output Specification

• Input: Undirected/directed graph G = (V, E), edge costs c(e), depot location, required edges R ⊆ E
• Output: A closed walk starting and ending at the depot that traverses all edges in R at least once
• Objective: Minimize total traversal cost

---

Why It Matters

Street Maintenance & Cleaning: Cities use arc routing to plan road sweeping, snow plowing, and pothole inspection routes. Efficient routing saves fuel and labor costs.

Utility Inspection: Gas, water, and electrical companies must periodically inspect all pipeline/wire segments. Arc routing ensures complete coverage with minimal inspector travel time.

Postal & Last-Mile Delivery: Mail carriers and parcel couriers must visit every street on their assigned route; arc routing optimizes their daily rounds.

Network Maintenance: Telecom companies and fiber-optic providers need to inspect all links in their infrastructure network.

---

Modeling Approaches

Approach 1: Integer Linear Programming (ILP)

Model the problem as a flow-based MIP:

• Decision variable: x_e ∈ Z+ = number of times edge e is traversed
• Constraint: For each edge in required set R, x_e ≥ 1
• Constraint: For each node v, the sum of flows through v respects Eulerian requirements (degree constraints)
• Objective: Minimize Σ c(e) · x_e

Trade-offs: Natural encoding, strong LP relaxations, but can be slow on large graphs; degree constraints scale quadratically.

Approach 2: Constraint Programming with Graph Algorithms

Decompose the problem:

1. Solve the Chinese Postman Problem (CPP) relaxation to find the minimum cost Eulerian augmentation
2. Use CP to enforce tour structure and optimize over augmented edges
3. Apply search strategies targeting symmetric solutions

Trade-offs: Leverages specialized CP propagation, can prune infeasible augmentations early, but requires custom global constraints for Eulerian path requirements.

Example Model (ILP Pseudo-code)

minimize: sum(cost[e] * x[e] for e in E)

subject to:
  for each edge e in required_edges:
    x[e] >= 1
  
  for each node v:
    sum(x[e] for e incident to v) is even  # Eulerian condition
  
  x[e] >= 0, integer for all e
  tour_connectivity_constraints (e.g., subtour elimination)

---

Key Techniques

1. Chinese Postman Relaxation

The CPP asks: "What's the minimum cost to add/repeat edges so the graph becomes Eulerian?" Solving CPP gives a lower bound for ARP and suggests which edges to traverse multiple times. Algorithms (e.g., matching on odd-degree vertices) run in polynomial time for undirected graphs.

2. Symmetry Breaking & Subtour Elimination

Arc routing solutions often have high symmetry (different orderings of the same edge traversals). Use degree-sequence constraints and break symmetries via canonical tours. For large instances, use lazy subtour-elimination callbacks in branch-and-cut rather than enumerating all upfront.

3. Cutting Planes & Separation Oracles

Strengthen the LP relaxation with comb inequalities and other cutting planes derived from the Eulerian structure. These tighten bounds in B&C, reducing search space and improving convergence.

---

Challenge Corner

Open Questions for Readers:

1. Capacity Augmentation: If the vehicle has a capacity limit (can traverse at most k edges before returning to the depot), how would you model this? What global constraints would help prune infeasible partial solutions?

2. Symmetry Breaking: The set of all solutions for a simple cycle is exponentially large (different starting points, directions). What symmetry-breaking constraints would reduce the search space while preserving optimality?

3. Real-World Extensions: In practice, traversal costs differ by direction (downhill vs. uphill, or traffic patterns). How would you extend the model to handle asymmetric costs? What new challenges arise?

---

References

• Christofides, N. (1973). "The Chinese Postman Problem." Networks, 8(8), 221–232. — Foundational work on the relaxation.
• Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming, Chapter on Graph Problems. — Comprehensive CP perspective on routing variants.
• Eiselt, H. A., Gendreau, M., & Laporte, G. (1995). "Arc Routing Problems, Part I & II." Operations Research, 43(2), 231–242. — Classic survey covering problem variants and heuristics.
• COIN-OR/OR-Tools Documentation: Examples of vehicle routing and arc routing formulations in production solvers.

---

Next Challenge: Can you solve this by hand for the 5-street instance? Try different Eulerian augmentations and compare total costs!

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 8.37 AIC · ⌖ 6.99 AIC · ⊞ 6.5K · ◷

• expires on Oct 26, 2026, 3:36 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #70503.