Algorithms for Capacitated Vehicle Routing
Files
Publication or External Link
Date
Advisor
Citation
DRUM DOI
Abstract
Given $n$ identical objects (pegs), placed at arbitrary initial locations, we consider the problem of transporting them efficiently to $n$ target locations (slots) with a vehicle that can carry at most $k$ pegs at a time. This problem is referred to as $k$-delivery TSP, and it is a generalization of the Traveling Salesman Problem. We give a 5-approximation algorithm for the problem of minimizing the total distance traveled by the vehicle.
There are two kinds of transportations possible --- one that could
drop pegs at intermediate locations and pick them up later in the
route for delivery (preemptive) and one that transports pegs to their targets
directly (non-preemptive).
In the former case, by exploiting the freedom to drop, one
may be able to find a shorter delivery route.
We construct a non-preemptive tour that is within a factor 5
of the optimal preemptive tour.
In addition we show that the ratio
of the distances traveled by an optimal non-preemptive tour versus a
preemptive tour is bounded by 4.
(Also cross-referenced as UMIACS-TR-97-79)