## Abstract

The capacitated vehicle routing problem (CVRP) involves distributing identical items from a depot to a set of demand locations using a single capacitated vehicle. We introduce the heterogeneous capacitated vehicle routing problem, a generalization of CVRP to the setting of multiple vehicles having nonuniform speeds, and present for it a constant-factor approximation algorithm.

Our
main contribution is an approximation algorithm for the heterogeneous
traveling salesman problem, which is the special case of heterogeneous
CVRP with uncapacitated vehicles. Given a metric denoting distances between vertices, a depot *r* containing *k* vehicles having respective speeds {λi}ki=1

, the objective in heterogeneous TSP is to find a tour for each vehicle (starting and ending at *r*) so that every vertex is covered in some tour and the maximum completion time is minimized; the completion time of a vehicle is the distance traveled divided by its speed.

Our algorithm relies on a new approximate minimum spanning tree construction called *Level-Prim*, which is related to but different from *Light Approximate Shortest-path Trees*. We also extend the widely used tour-splitting technique to nonuniform speeds, using ideas from the 2-approximation algorithm for scheduling in unrelated machines.

Original language | English |
---|---|

Journal | Mathematics of Operations Research |

Volume | 41 |

Issue number | 1 |

Pages (from-to) | 318-331 |

ISSN | 0364-765X |

DOIs | |

Publication status | Published - 2016 |