Loading post…
Shopify2023-10-18Benchmark
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.
Source and freshness
- Source
- shopify.engineering
- Published
- Added to Yomu
- Last updated
Summaries are generated from the original by a language model. Check the original before relying on it.
Keep reading
Related reading
The Good Stuff
Paid picks we use ourselves. Links carry a referral code — a subscription through one earns us a commission at no extra cost to you.
The best engineering reads, once a week
One useful email. Unsubscribe anytime.