×

Algorithms for capacitated vehicle routing. (English) Zbl 1009.90095

Summary: 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 (nonpreemptive). In the former case, by exploiting the freedom to drop, one may be able to find a shorter delivery route. We construct a nonpreemptive 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 nonpreemptive tour versus a preemptive tour is bounded by 4.

MSC:

90C27 Combinatorial optimization
90B20 Traffic problems in operations research
90C59 Approximation methods and heuristics in mathematical programming
68R10 Graph theory (including graph drawing) in computer science
05C38 Paths and cycles
05C85 Graph algorithms (graph-theoretic aspects)
68W10 Parallel algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI