Approximation algorithms for deadline-TSP and vehicle routing with time-windows

TLDR

Deadline‑TSP and Vehicle Routing with Time‑Windows ask for a path from a start node that visits as many vertices as possible within their deadlines or time‑windows in a metric space, and no good approximations were known for these problems before. The authors aim to provide approximation algorithms for these problems, delivering an O(log n) algorithm for Deadline‑TSP, an O(log² n) algorithm for the Time‑Window problem, and a bicriteria (1/ε)-approximation that exceeds deadlines by a factor 1+ε. They achieve this by developing a constant‑factor approximation for a generalized orienteering problem with fixed start and end nodes, which serves as a subroutine for the proposed algorithms. In the process, they obtain a 3‑approximation for the generalized orienteering problem, improving upon the previous best 4‑approximation.

Abstract

Given a metric space G on n nodes, with a start node r and deadlines D(v) for each vertex v, we consider the Deadline-TSP problem of finding a path starting at r that visits as many nodes as possible by their deadlines. We also consider the more general Vehicle Routing with Time-Windows problem, in which each node v also has a release-time R(v) and the goal is to visit as many nodes as possible within their "time-windows" [R(v),D(v)]. No good approximations were known previously for these problems on general metric spaces. We give an O(logn) approximation algorithm for Deadline-TSP, and extend this algorithm to an O(log2n) approximation for the Time-Window problem. We also give a bicriteria approximation algorithm for both problems: Given an ε>0, our algorithm produces a (1/ε) approximation, while exceeding the deadlines by a factor of 1+ε. We use as a subroutine for these results a constant-factor approximation that we develop for a generalization of the orienteering problem in which both the start and the end nodes of the path are fixed. In the process, we give a 3-approximation to the orienteering problem, improving on the previously best known 4-approximation of [6].