Winning AI4TSP: Solving the Travelling Salesperson Problem with Self-programming Machines

Summary

The 2021 AI4TSP Competition addressed the Travelling Salesperson Problem when travel times are sampled from probability distributions and locations carry rewards and time windows. With n locations, the number of possible tours is n!, making exhaustive enumeration impractical, while the competition also required decisions under uncertain travel outcomes. One track required a fixed tour optimized for expected performance across scenarios; the other allowed an adaptive policy to select the next location as time elapsed, with results evaluated across many instances and realizations. The Shopify-led team used dialectic search for the fixed-tour track and deep reinforcement learning for the on-the-fly track, and won first prize in both.

Context

The competition studied routing decisions that combine computational difficulty with uncertainty: travel times were unknown and sampled from probability distributions, while locations had rewards, fixed time windows, waiting requirements for early arrivals, and penalties for late arrivals.

Approach / What changed

The team used heuristic search in two forms. Dialectic search produced a fixed tour for the first track, while deep reinforcement learning produced a policy for the second track that selected the next location during execution based on elapsed time. Both approaches relied on learning from prior experience and automatically adjusting the algorithm.

Takeaways

• The first track required one tour to be selected in advance and evaluated by averaging performance over 100,000 travel-time scenarios, repeated ten times.
• The second track allowed decisions to be made at every location and evaluated each policy on 100 travel-time realizations for each of 1,000 TSP instances.
• The Shopify-led team won first prize in both AI4TSP competition tracks, using dialectic search in one and deep reinforcement learning in the other.

Related reading