Algorithm and knowledge engineering for the TSPTW problem

Stefan Edelkamp, Max Gath, Tristan Cazenave, Fabien Teytaud

TL;DR

This paper presents an enhanced Nested Monte-Carlo Search (NMC) algorithm for solving the Traveling Salesman Problem with Time Windows (TSPTW). By combining algorithmic refinements like beam search and memory optimization with knowledge engineering techniques to seed the search policy, the authors achieve significant speedups and improved performance on TSPTW benchmarks, paving the way for more efficient real-world logistics applications.

What Problem Does This Paper Address?

The Traveling Salesman Problem (TSP) is a classic optimization challenge: find the shortest route to visit a set of cities exactly once. The Traveling Salesman Problem with Time Windows (TSPTW) adds a crucial layer of complexity: each city must be visited within a specific time interval. This problem is computationally hard, meaning finding an optimal solution can be prohibitively time-consuming for even moderately sized instances. Existing exact solvers struggle with scalability, while heuristic approaches often sacrifice optimality for speed. This paper aims to bridge this gap by improving the efficiency and effectiveness of a randomized search algorithm, Nested Monte-Carlo Search (NMC), specifically for TSPTW, making it more practical for complex, real-world logistics scenarios.

Methods

The core of the paper's contribution lies in the "algorithm engineering" and "knowledge engineering" applied to an existing NMC algorithm with Policy Adaptation (NPRA).

Algorithmic Refinements: * Avoiding Copy Construction: The original NMC implementation involved frequent copying of search states, leading to significant overhead. The authors refactored this to reduce memory allocation and improve efficiency. * Reducing Memory Allocation: Policies at different search levels were pre-allocated to avoid dynamic memory allocation during search. * Merging Rollout and Evaluation: The process of generating successors and evaluating partial tours was combined, streamlining the search. * Beam Search: To balance search breadth and depth, a beam search strategy was implemented. This prunes less promising branches early on, focusing the search on a limited set of "best" successors. * Approximating the e-function: A computationally efficient approximation for the exponential function was used to speed up policy adaptation.

Knowledge Engineering: * Policy Adaptation: The algorithm uses a policy to guide its search, biasing it towards more promising moves. This policy is learned and adapted during the search. * Domain-Dependent Pruning: Specific rules were introduced to prune the search space based on TSPTW constraints. For example, if a time window constraint is violated by visiting a city, that city becomes the only option. * Elicitation of Knowledge (Prior Policy Seeding): To give the search a head start, the authors incorporated domain knowledge into the initial policy. This was done by using negative city-to-city distances, encouraging the search to explore closer cities first. They also explored using knowledge derived from the Assignment Problem heuristic.

Datasets

The paper evaluates its approach on several established TSPTW benchmark datasets:

  • Dumas Benchmark: Used for both smaller (N=20) and larger (N=40, N=60) instances.
  • Solomon-Potwin-Bengio Benchmark: A well-known benchmark suite for TSPTW.
  • Solomon-Peasant Benchmark: Another benchmark set used for evaluation.
  • AFG Benchmark: Used to test the algorithm's performance on various problem sizes.
  • Langevin Benchmark: A set of larger problems used to assess scalability.

The paper does not introduce new benchmark datasets.

Key Insights and Ideas

  • The Power of Engineering: The paper strongly emphasizes that even sophisticated algorithms like NMC can be significantly improved through meticulous "engineering" – optimizing memory usage, reducing redundant computations, and streamlining core processes. This highlights that practical performance often hinges on implementation details as much as algorithmic novelty.
  • Knowledge as a Shortcut: Seeding the search policy with domain-specific knowledge (like city distances) dramatically accelerates the discovery of good solutions. This suggests that hybrid approaches, combining the exploration power of randomized search with the guidance of expert knowledge, are highly effective for complex combinatorial problems.
  • Beam Search for Balanced Exploration: The introduction of beam search provides a tunable mechanism to balance the exploration of new paths (breadth) with the exploitation of promising ones (depth), leading to a more efficient search for optimal solutions.
  • Real-World Applicability: The authors demonstrate that their refined algorithm, mTSP, not only performs well on benchmarks but also shows promise for real-world logistics by being integrated into a multi-agent simulation system.

Key Results

  • Significant Speedup: The algorithmic refinements led to an improvement of "more than factor 10" in exploration efficiency compared to the original implementation. For example, a specific experiment showed a reduction in execution time from 2m31s to 11s for a large problem.
  • Competitive Performance: The mTSP solver consistently finds optimal or near-optimal solutions on various benchmarks. For instance, it solved all but 3 problems on the Dumas benchmark (N=40) within a 15-minute time limit, achieving state-of-the-art scores.
  • Faster than Optimal Solvers: For simpler instances, mTSP is significantly faster than provably optimal algorithms.
  • Impact of Knowledge Seeding: Seeding the policy with expert knowledge (e.g., the first few cities in a tour) drastically reduced solving time, enabling solutions in under a minute for problems that would otherwise take much longer.

Limitations and Future Work

Limitations: * No Proof of Optimality: As a randomized search algorithm, mTSP does not inherently provide a proof of optimality. The results are based on finding the best solution within a given time limit. * Parameter Tuning: While beam search offers a tunable parameter (beam width), finding the optimal settings for all problem instances might require further investigation.

Future Work: * Industrial Multi-Agent System: The authors envision integrating their solver into a multi-agent simulation system for industrial vehicle routing. This system would handle more complex constraints beyond time windows, such as limited driving times, premium contracts, and pickup/backhaul tasks. * Real-World Order Integration: The goal is to solve TSP instances derived from actual logistics orders, providing a more realistic evaluation of the algorithm's practical utility. * Lower Bound Computation: The use of lower bounds (e.g., from the Hungarian algorithm) in the multi-agent context is mentioned as a way to improve overall cluster solutions.

Summary updated

Abstract

The well-known traveling salesman problem (TSP) is concerned with determining the shortest route for a vehicle while visiting a set of cities exactly once. We consider knowledge and algorithm engineering in combinatorial optimization for improved solving of complex TSPs with Time Windows (TSPTW). To speed-up the exploration of the applied Nested Monte-Carlo Search with Policy Adaption, we perform beam search for an improved compromise of search breadth and depth as well as automated knowledge elicitation to seed the distribution for the exploration. To evaluate our approach, we use established TSPTW benchmarks with promising results. Furthermore, we indicate improvements for real-world logistics by its use in a multiagent system. Thereby, each agent computes individual TSPTW solutions and starts negotiation processes on this basis.
BibTeX
@inproceedings{edelkamp2013algorithm,
  author = {Stefan Edelkamp and Max Gath and Tristan Cazenave and Fabien Teytaud},
  title = {{Algorithm and knowledge engineering for the TSPTW problem}},
  booktitle = {CISched},
  year = {2013},
  url = {https://openreview.net/forum?id=BnsXuaiX_MA},
}
Figure