Show simple item record

Algorithms for Capacitated Vehicle Routing

dc.contributor.authorCharikar, Mosesen_US
dc.contributor.authorKhuller, Samiren_US
dc.contributor.authorRaghavachari, Balajien_US
dc.description.abstractGiven $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)en_US
dc.format.extent270486 bytes
dc.relation.ispartofseriesUM Computer Science Department; CS-TR-3847en_US
dc.relation.ispartofseriesUMIACS; UMIACS-TR-97-79en_US
dc.titleAlgorithms for Capacitated Vehicle Routingen_US
dc.typeTechnical Reporten_US
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_US
dc.relation.isAvailableAtUniversity of Maryland (College Park, Md.)en_US
dc.relation.isAvailableAtTech Reports in Computer Science and Engineeringen_US
dc.relation.isAvailableAtUMIACS Technical Reportsen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record