When Travel Times Are Unknown

Optimization problems are rarely as clean as their textbook formulations. In practice, the data an algorithm optimizes against is often an estimate, and decisions must hold up across a range of possible realities. That was the premise of the AI4TSP Competition, which examined the Travelling Salesperson Problem (TSP) under uncertainty.

Shopify optimization expert Meinolf Sellmann, together with Tapan Shah at GE Research, Kevin Tierney, Fynn Schmitt-Ulms, and Andre Hottung from the University of Bielefeld, took first prize in both tracks of the competition. The work is relevant to Shopify’s own fulfillment systems, which rely on estimated data to make routing and scheduling decisions.

The Problem Setup

In the classic TSP, a salesperson must visit a set of locations and return home, with all travel times known in advance. The goal is to minimize total travel time. The competition added several layers of difficulty:

  • Travel times were not known upfront but sampled from a probability distribution.
  • Each location carried a specific reward, and the objective was to collect as many rewards as possible within a fixed time budget.
  • Each location had a time window: arriving early meant waiting, arriving late incurred penalties.

Even with known travel times, the problem is computationally brutal. For a TSP with n locations, the number of possible tours is n!. The authors note that even a computer capable of evaluating one tour per atom in the universe at Planck-time speed, running from the Big Bang to the present day, could not enumerate all tours for a 91-location instance. The largest competition instances had 200 locations, implying more than 10375 candidate solutions.

Two Tracks, Two Strategies

The competition’s first track required a single, fixed tour to be chosen for each instance. That tour was then executed across 100,000 sampled travel-time scenarios, and the average performance determined the winner. The challenge is to design a tour that works well in expectation across all possible travel-time realizations.

The second track allowed for adaptive behavior. Contestants could decide the next location to visit at each step, based on elapsed time. The policy was evaluated on 100 travel-time realizations for each of 1,000 instances.

Sellmann’s team used heuristic search for both tracks, but in very different forms. For the offline decision in track one, they applied dialectic search. For the online decision-making in track two, they turned to deep reinforcement learning.

Searching Without Certainty

Hard optimization problems demand search. Systematic search methods track explored solutions efficiently but are rigid: the search controller must follow a structure dictated by the search record. Heuristic search is more flexible. It may revisit candidates, but the controller can steer toward promising regions opportunistically and escape local basins of attraction.

For the first track, the team’s dialectic search approach was deliberately self-tuning. It learns from prior runs and adjusts its own parameters automatically, allowing the search to improve without human intervention. The same philosophy carried over to the reinforcement learning solution in the second track, where the machine learned a policy for the online problem.

Self-Programming Algorithms

At the core of both winning approaches is a broader shift in how algorithms are built. Rather than hand-crafting a solution for a hard problem, the modern approach is to build a system that can write the algorithm itself. The principle: if we cannot develop an algorithm with sufficient performance for a task, we build an algorithm that can build that algorithm for us, automatically.

AlphaFold, DeepMind’s protein structure prediction system, is one prominent example of this paradigm. Human-designed algorithms had failed for decades to achieve practically useful accuracy; the self-taught system succeeded. Sellmann’s earlier work demonstrated the same effect in optimization, when a self-tuned dialectic search approach won at the MaxSAT Evaluation 2016, taking first place in four of nine categories and ten medals overall.

For problems where concise theory is elusive and hunches dominate execution, machine-generated algorithms are increasingly outperforming their human-designed counterparts. The AI4TSP results are one more data point in that trend.