Learning-Augmented Algorithms for TSP and Vehicle Routing Problems

We consider a canonical vehicle-routing problem in which a sequence of point-to-point requests arrives online and must be inserted into the schedule to minimize the total travel time required to serve them. This captures classical problems such as the online Traveling Salesperson Problem (TSP) and the online Stacker Crane Problem. Our main result is a learning-augmented algorithm with a competitive ratio of $3.5$ when the input requests are drawn from (possibly non-identical) distributions, given just a *single sample* from each distribution as offline predictions. This is in sharp contrast to the best-known logarithmic bounds without offline predictions. We further extend this result in two directions: first, by showing that the algorithm can be made *robust* to adversarial noise in the samples, and second, by considering a fleet of $m>1$ vehicles rather than a single vehicle. Finally, we complement our theoretical results with empirical evaluations.