Computer Science – Data Structures and Algorithms
Scientific paper
2009-05-27
Computer Science
Data Structures and Algorithms
20 pages, 1 figure
Scientific paper
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 tour 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 tour 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.
Frederickson Greg N.
Wittman Barry
No associations
LandOfFree
Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation Algorithms for the Traveling Repairman and Speeding Deliveryman Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-527846