Capacitated Vehicle Routing with Non-Uniform Speeds

Inge Li Gørtz, Marco Molinaro, Viswanath Nagarajan, R. Ravi

Research output: Contribution to journalJournal articleResearchpeer-review

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 languageEnglish
JournalMathematics of Operations Research
Volume41
Issue number1
Pages (from-to)318-331
ISSN0364-765X
DOIs
Publication statusPublished - 2016

Cite this