Approximation algorithms for time-constrained vehicle routing problems.

摘要

This dissertation discusses a number of vehicle routing problems in which a visit to a location counts only if it occurs within a specified time window. These problems can be viewed as time-constrained variations of the Traveling Salesman Problem (TSP). Specifically, we consider the Traveling Repairman Problem, in which the goal of the agent is to visit as many locations as possible during their time windows, traveling at some specified speed. We consider the related Speeding Deliveryman Problem, in which all locations must be visited during their time windows and the goal is to find the minimum speed at which it is possible to do so. We then unite these two problems into a problem parameterized on speedup. In this problem, the goal is to find the maximum number of locations that can be visited at various levels of speedup over a reference speed. Finally, we consider some multivehicle versions of these problems.;Because all of these problems are NP-hard, the primary goal of this research is to produce polynomial-time, approximation algorithms for each problem considered. With reasonable assumptions about the structure of the underlying graph and the lengths of time windows, we are able to devise approximation algorithms whose performance comes within a constant factor of optimal for many of these problems.