A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: Theory and experiments

René van Bevern, Christian Komusiewicz, Manuel SorgeNetworks 2017 · OpenReview

TL;DR

This paper introduces a novel parameterized approximation algorithm for the complex Mixed and Windy Capacitated Arc Routing Problem (MWCARP). The algorithm achieves constant-factor approximations when the number of disconnected road network components is small, a common scenario in real-world applications. This work bridges a theoretical gap and provides a practical approach that outperforms existing heuristics on benchmark datasets.

What Problem Does This Paper Address?

The Capacitated Arc Routing Problem (CARP) is a fundamental challenge in logistics and operations research, aiming to find the most cost-effective routes for vehicles to service demands on a network of roads. This paper tackles a more complex variant: the Mixed and Windy Capacitated Arc Routing Problem (MWCARP). "Mixed" means the road network can have both one-way (directed arcs) and two-way (undirected edges) roads. "Windy" refers to roads where the cost of travel can differ depending on the direction (e.g., uphill vs. downhill). Existing CARP algorithms often struggle with these complexities, and the theoretical understanding of approximation algorithms for MWCARP was incomplete. Specifically, the paper addresses the lack of constant-factor approximation algorithms for MWCARP, especially when the road network is divided into multiple disconnected components.

Methods

The core of the paper's contribution lies in a parameterized approximation algorithm. It leverages a connection between MWCARP and the Traveling Salesperson Problem (TSP). The algorithm builds upon a "route first, cluster second" strategy. First, it computes an approximate "giant tour" that covers all required arcs, drawing on a parameterized approximation for the Mixed and Windy Rural Postman Problem (MWRPP). This MWRPP approximation is itself derived from a parameterized approximation for the Directed Rural Postman Problem (DRPP), which in turn is linked to the asymmetric Traveling Salesperson Problem (TSP).

A key innovation is how the algorithm handles the number of weakly connected components ($C$) in the subgraph induced by positive-demand arcs. The approximation factor of the algorithm is parameterized by $C$, meaning it performs better when $C$ is small. For instance, when $C$ is logarithmic in the number of vertices, the algorithm achieves a constant-factor approximation. The paper also introduces a new benchmark dataset, "Ob," specifically designed to have a moderate number of connected components, allowing for a more thorough evaluation of algorithms' performance in scenarios beyond the typical $C=1$ case.

Datasets

The paper evaluates its algorithm on existing benchmark datasets:

  • lpr and mval: These datasets are for the mixed (but not windy) CARP.
  • egl-large: This dataset is for the undirected CARP.

Additionally, the authors introduce a new benchmark set called Ob. This set is generated by taking instances from lpr and egl-large and artificially dividing them into multiple components (2 to 5) by removing edges and creating "bridges" that represent crossings over a river. This new dataset is crucial for testing algorithms' performance when the number of connected components ($C$) is greater than one, a scenario often overlooked in existing benchmarks.

Key Insights and Ideas

  • Parameterization by Connected Components: The approximation quality of the algorithm critically depends on the number of weakly connected components ($C$) in the demand subgraph. This is a significant insight, suggesting that future research and benchmarking should consider this parameter more carefully.
  • Bridging Theory and Practice: The paper successfully connects theoretical results on TSP and DRPP to practical approximation algorithms for the complex MWCARP.
  • "Route First, Cluster Second" with a Twist: While the "route first, cluster second" paradigm is not new, the paper demonstrates its effectiveness when the "route first" step uses a theoretically grounded MWRPP approximation, rather than purely heuristic methods.
  • New Benchmark for a Key Parameter: The creation of the "Ob" dataset is a valuable contribution, enabling more robust evaluation of algorithms under varying network connectivity conditions.

Key Results

  • The proposed algorithm achieves a parameterized approximation factor of $O(a(C) + \text{constant})$ for MWCARP, where $a(C)$ is the approximation factor for TSP on $C$ vertices.
  • When the number of connected components $C$ is small (e.g., $C \in O(\log n)$), the algorithm provides a constant-factor approximation.
  • Experimental results on the lpr, mval, and egl-large benchmark sets show that the algorithm, especially with certain service direction heuristics, outperforms existing polynomial-time heuristics.
  • The algorithm solved three instances from the mval dataset to optimality, which other polynomial-time heuristics did not.
  • The new "Ob" benchmark set was generated to simulate cities divided by a river, creating instances with $C > 1$.

Limitations and Future Work

  • Approximation Factor: The theoretical approximation factors, particularly for MWCARP, are somewhat large (e.g., $8a(C+1) + 27$). While experiments show good practical performance, there's room for theoretical improvement.
  • Windy Aspect: While the theory covers windy graphs, the experimental evaluation primarily uses non-windy instances. Further experiments on truly windy instances would be beneficial.
  • Theoretical Question: The paper poses an open question: can the $(a(C) + 3)$-approximation for MWRPP be improved to $(a(C) + 3/2)$, analogous to results for the Mixed Chinese Postman Problem?
  • Heuristic Enhancements: The paper discusses several heuristic enhancements for service direction and tour splitting, suggesting that further exploration of these could yield even better practical results.
  • Benchmark Coverage: The authors note that many existing benchmarks have $C=1$, limiting the evaluation of algorithms' performance on the key parameter $C$. The "Ob" dataset aims to address this, and future work could involve generating more such instances.

Summary updated

BibTeX
@inproceedings{bevern2017parameterized,
  author = {René van Bevern and Christian Komusiewicz and Manuel Sorge},
  title = {{A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: Theory and experiments}},
  booktitle = {Networks},
  year = {2017},
  url = {https://openreview.net/forum?id=gF0YtiOVpC},
}
Figure