Skip to content

CONCEPT Cited by 1 source

Traveling salesman problem

Definition

The traveling salesman problem (TSP) is the classic combinatorial-optimization problem: given a set of cities and the distances between each pair, find the shortest possible route that visits each city exactly once and returns to the origin. NP-hard in general; exact solutions infeasible beyond small inputs, so production systems rely on approximations, heuristics, and domain-specific solvers.

Wikipedia: Travelling salesman problem.

Why it matters for ridesharing dispatch

TSP is the academic shape of the rider-driver matching problem at Uber's scale:

  • Spatial component. The dispatch service picks which available driver to route to which incoming rider request.
  • Temporal component. Not just currently-available drivers — also drivers who'll become available in the near future (e.g., finishing a current trip within N seconds).
  • Variant shape. Not the pure textbook TSP (every city visited exactly once) but a TSP variant — dispatch must "look at the ETAs of currently available driver-partners [and] understand which drivers could be available in the near future" (Source: sources/2024-03-14-highscalability-brief-history-of-scaling-uber).

This TSP-variant framing is why Uber's 2014 dispatch rewrite introduced:

  • A geospatial index (S2, later H3) for fast spatial lookup of nearby drivers.
  • Ringpop gossip for dispatch nodes to share driver-supply state.
  • A matching optimizer running continually over these maintained-in-memory data structures.

Broader on-demand marketplace applicability

The same TSP-variant pattern applies to:

  • Food delivery dispatch (Uber Eats, Instacart, DoorDash) — driver-to-restaurant assignment + restaurant-to-customer delivery routing.
  • Package delivery (Uber Direct) — multi-stop vehicle routing with time windows (VRP — Vehicle Routing Problem, a TSP cousin).
  • Airport queue management — virtual queue mechanisms at airports are TSP-shaped when considering pick-up order + ETA optimization over available drivers.
Last updated · 517 distilled / 1,221 read