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

[github-actions[bot]]

Problem Statement

The Arc Routing Problem (ARP) asks: Given a graph with edges that must be traversed (or serviced), find a least-cost route (or set of routes) that visits every required edge.

Unlike the node-focused Traveling Salesman Problem, arc routing focuses on edge traversal, making it ideal for scenarios where the service is performed on the edge itself—not just at nodes.

Concrete Example

Consider a road maintenance crew that must inspect and repair every street in a neighborhood:

• Vertices: street intersections (A, B, C, D, E)
• Required edges: streets that need repair [(A–B), (B–C), (C–D), (D–E), (E–A), (B–D)]
• Costs: time to traverse each street
• Goal: find a single route starting and ending at a depot (say, A) that traverses all required edges exactly once, minimizing total time

This is the Chinese Postman Problem variant. If not all edges can be traversed exactly once (because the graph isn't Eulerian), some edges must be repeated.

Input: Undirected graph G = (V, E), edge weights w: E → R+, required edges E_r ⊆ E, depot node(s)
Output: Minimum-cost closed walk covering all required edges

---

Why It Matters

1. Winter Road Maintenance
Municipalities must plow or salt every street in their area. The plowing truck travels street by street, and the goal is to minimize total distance (or time) spent on unnecessary repositioning.

2. Postal & Package Delivery
Delivery routes must cover every street segment in an assigned zone. The postman/driver wants to avoid rewalking streets unnecessarily—optimizing arc traversals directly impacts efficiency.

3. Utility Inspection & Maintenance
Electric, water, and gas utilities need to inspect every pipe/cable section. Arc routing minimizes the cost of traversing the entire network.

4. Refuse Collection
Garbage trucks must collect from every street. Solving the arc routing problem minimizes fuel costs and wear on vehicles.

---

Modeling Approaches

Approach 1: Graph-Theoretic (Eulerian Augmentation)

Paradigm: Pure graph theory with minimum-cost matching.

Idea: If the graph already has an Eulerian tour (all vertices have even degree), traverse it once. Otherwise, add minimum-cost copies of edges to make it Eulerian, then traverse the augmented graph.

Decision variables & constraints:

• Identify odd-degree vertices in the subgraph induced by required edges.
• Find a minimum-weight perfect matching on odd-degree vertices.
• Add matching edges (duplicates) to the required edge set.
• Compute an Eulerian tour on the augmented graph.

Trade-offs:
✓ Elegant and polynomial-time solvable (matching + Eulerian decomposition)
✗ Limited flexibility for directedness, time windows, or multiple vehicles
✓ Optimal for the undirected Chinese Postman Problem

Approach 2: Mixed-Integer Programming (MIP)

Paradigm: Integer linear programming with flow-based formulation.

Decision variables:

• x_e = number of times edge e is traversed (≥1 for required edges)
• y_v = flow at vertex v (auxiliary for Eulerian tour construction)

Constraints:

• For each required edge e ∈ E_r: x_e ≥ 1
• Eulerian condition: in-degree = out-degree at each vertex
• Flow conservation: ensure connectivity

Objective: minimize Σ_e w_e · x_e

Trade-offs:
✓ Naturally handles directed graphs, time windows, multiple vehicles
✓ Commercial solvers (CPLEX, Gurobi) can find optimal solutions
✗ More variables/constraints than graph-theoretic approach; weaker polytime guarantees for complex variants
✓ Suitable for practical problem sizes (100–1000 edges)

Example Model Pseudo-code (Directed ARP)

minimize:
  sum{ e in EDGES } cost[e] * x[e]

subject to:
  // Required edges must be traversed at least once
  x[e] >= 1,  for all e in REQUIRED_EDGES
  
  // Eulerian condition: in-degree = out-degree at each node
  for all v in NODES:
    sum{ (u,v) in EDGES } x[(u,v)] == sum{ (v,w) in EDGES } x[(v,w)]
  
  // Non-negativity
  x[e] >= 0,  for all e in EDGES

---

Key Techniques

1. Eulerian Path Decomposition

Check if a graph has an Eulerian trail (all vertices have even degree, or exactly two have odd degree). If not, the problem requires edge duplication. The T-join algorithm efficiently identifies the minimum-cost edge set to add.

2. Blossom Algorithm for Matching

When multiple odd-degree vertices exist, find the minimum-weight perfect matching among them using Edmond's Blossom algorithm. This ensures the augmented graph has an Eulerian tour.

3. Vehicle Routing with Multiple Depots

For real-world extensions—multiple garbage trucks, multiple starting depots—the arc routing problem becomes a Vehicle Routing Arc Problem (VRAP). Decompose the problem:

• Partition required edges among vehicles.
• Solve a Chinese Postman variant for each vehicle.
• Heuristics like cluster-first, route-second work well.

---

Challenge Corner

Open Question: Suppose edge traversal time is not constant—traversing edge e in direction 1→2 costs w_12, but 2→1 costs w_21 (e.g., uphill vs. downhill). How would you model and solve the Asymmetric Arc Routing Problem? What symmetry-breaking constraints help?

Bonus Extension: What if you also need to avoid traversing certain edges during rush hours? How would you encode time-dependent costs into an MIP formulation?

---

References

1. Christofides, N. (1976). Worst-case analysis of a new heuristic for the traveling salesman problem. Tech. Report, Grad. School of Industrial Admin., Carnegie-Mellon University. — Foundational work on approximations; includes edge-routing variants.

2. Eiselt, H. A., Gendreau, M., & Laporte, G. (1995). Arc Routing Problems, Part I: The Chinese Postman Problem. Operations Research, 43(2), 231–242. — Comprehensive overview of arc routing and its variants.

3. Duan, Z., Urquhart, R., & McCall, J. (2011). Investigating the Performance of a Hybrid Evolutionary Algorithm in a Vehicle Arc Routing Problem. In Proc. GECCO, 733–740. — Modern heuristics for vehicle arc routing.

4. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.), MIT Press. — Chapter on graph algorithms includes matching and Eulerian tours.

Warning

Firewall blocked 1 domain

The following domain was blocked by the firewall during workflow execution:

• awmgmcpg

To allow these domains, add them to the network.allowed list in your workflow frontmatter:

network:
  allowed:
    - defaults
    - "awmgmcpg"

See Network Configuration for more information.

Generated by 🧩 Constraint Solving — Problem of the Day · 10.4 AIC · ⌖ 13.6 AIC · ⊞ 5.2K · ◷

• expires on Jul 10, 2026, 4:11 AM UTC-08:00