Algorithms for Capacitated Vehicle Routing
| dc.contributor.author | Charikar, Moses | en_US |
| dc.contributor.author | Khuller, Samir | en_US |
| dc.contributor.author | Raghavachari, Balaji | en_US |
| dc.date.accessioned | 2004-05-31T22:48:30Z | |
| dc.date.available | 2004-05-31T22:48:30Z | |
| dc.date.created | 1997-11 | en_US |
| dc.date.issued | 1998-10-15 | en_US |
| dc.description.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) | en_US |
| dc.format.extent | 270486 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/923 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-3847 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-97-79 | en_US |
| dc.title | Algorithms for Capacitated Vehicle Routing | en_US |
| dc.type | Technical Report | en_US |