Title

Approximation algorithms for the traveling repairman and speeding deliveryman problems

Document Type

Article

Publication Title

Algorithmica

Publication Date

4-1-2012

Abstract

Constant-factor, polynomial-time approximation algorithms are presented for two variations of the traveling salesman problem with time windows. In the first variation, the traveling repairman problem, the goal is to find a path that visits the maximum possible number of locations during their time windows. In the second variation, the speeding deliveryman problem, the goal is to find a path that uses the minimum possible speedup to visit all locations during their time windows. For both variations, the time windows are of unit length, and the distance metric is based on a weighted, undirected graph. Algorithms with improved approximation ratios are given for the case when the input is defined on a tree rather than a general graph. The algorithms are also extended to handle time windows whose lengths fall in any bounded range.

Volume

62

Issue

3-4

First Page

1198

Last Page

1221

DOI

10.1007/s00453-011-9515-4

ISSN

01784617

E-ISSN

14320541

Link to Full Text

Share

COinS