---
title: "Winning AI4TSP: Solving the Travelling Salesperson Problem with Self-programming Machines"
description: "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."
---

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

[Shopify](https://yomu.fyi/company/shopify) · 2023-10-18 · Oct 6, 2021

**Type:** Benchmark

## 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.

**Tags:** [Machine Learning](https://yomu.fyi/topic/machine-learning), [Performance](https://yomu.fyi/topic/performance), [Scalability](https://yomu.fyi/topic/scalability)

- Source: [Shopify](https://shopify.engineering/travelling-salesperson-problem-ai4tsp)
- Source URL: https://shopify.engineering/travelling-salesperson-problem-ai4tsp
- Ingested by Yomu: 2026-08-30T15:29:03.303Z

[Read original post](https://shopify.engineering/travelling-salesperson-problem-ai4tsp)