Abstract
This paper presents a novel filtering algorithm for the weighted circuit constraint in Constraint Programming, specifically designed for the Traveling Salesman Problem (TSP) and the TSP with Time Windows (TSPTW). The core contribution is the introduction of the ln-path relaxation, a Lagrangian relaxation solved via dynamic programming. We prove that the lower bounds derived from this method are mathematically incomparable to traditional Held-Karp and Assignment Problem relaxations. Experimental results on TSPLIB and TSPTW benchmarks demonstrate that the ln-path approach significantly enhances pruning power and solving speed, particularly in problems with tight time windows where node position information is critical.
Introduction
Efficiently solving routing problems like the Traveling Salesman Problem (TSP) in Constraint Programming (CP) requires powerful filtering techniques for the "weighted circuit" constraint. This constraint ensures that a set of nodes forms a single Hamiltonian circuit of minimum cost. Filtering involves identifying and removing edges (arcs) from the search space that cannot be part of an optimal solution, a process heavily dependent on the quality of the lower bound provided by problem relaxations.
Relaxation Techniques and Incomparability
The authors compare three primary relaxation techniques used for cost-based filtering:
- Held-Karp (HK) Relaxation: Based on the minimum 1-tree problem, it is highly effective for symmetric TSPs but often ignores directed path information.
- Assignment Problem (AP): This relaxes the TSP by allowing sub-circuits. The authors improve upon standard AP filtering by using Johnson’s algorithm to compute exact reduced costs.
- ln-path Relaxation: A Lagrangian relaxation of the n-path problem that seeks a path of exactly $n+1$ arcs.
A key theoretical insight of this work is that the lower bounds from these three methods are incomparable. This means that depending on the graph structure, any one of these relaxations might provide a tighter bound than the others.
The ln-path Relaxation and Position-Based Filtering
The ln-path relaxation is the central contribution of this research. Unlike HK or AP, it utilizes dynamic programming, which allows it to naturally incorporate information about the position of a node in the sequence. This is a significant advantage for the TSP with Time Windows (TSPTW), where the time at which a node is visited strictly limits its possible positions in the tour.
The authors derive new filtering rules for both next variables (determining the successor of a node) and pos variables (determining the position of a node). While the dynamic programming approach has a computational complexity of $O(n^3)$, it becomes highly efficient in the sparse graphs typical of TSPTW instances.
Experimental Evaluation
The proposed methods were evaluated on TSPLIB (asymmetric instances) and several TSPTW benchmark sets (Ascheuer, Pesant, Dumas, Gendreau, and Ohlmann & Thomas).
- Lower Bound Quality: On Dumas and Gendreau instances, the ln-path relaxation provided a tighter lower bound at the root node than Held-Karp. For example, on Dumas instances, the ln-path gap was 1.85% compared to 3.08% for HK.
- Pruning Power: The ln-path approach was significantly more effective at reducing the domain of position variables. In the Ascheuer dataset, it reduced possible node positions to nearly half of what HK achieved.
- Solving Efficiency: For medium-sized instances with tight time windows, the enhanced filtering significantly reduced the time required to find and prove optimal solutions.
Conclusion
The ln-path relaxation provides a powerful alternative for filtering the weighted circuit constraint, especially in highly constrained routing problems like the TSPTW. Although computationally more intensive than simpler relaxations, its ability to exploit node position information leads to superior pruning. Future research may explore hybrid propagators that dynamically combine these incomparable relaxations to leverage their individual strengths.
Summary updated