Algorithms for capacitated vehicle routing

Moses Charikar*, Samir Khuller, Balaji Raghavachari

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

30 Scopus citations

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 (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.

Original languageEnglish (US)
Pages (from-to)665-682
Number of pages18
JournalSIAM Journal on Computing
Volume31
Issue number3
DOIs
StatePublished - 2002

Keywords

  • Approximation algorithms
  • Graphs
  • Traveling salesman problem
  • Vehicle routing

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Algorithms for capacitated vehicle routing'. Together they form a unique fingerprint.

Cite this