This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Li, C.-L. Articles by Desrochers, M. Search for Related Content

On the Distance Constrained Vehicle Routing Problem

Washington University, St. Louis, Missouri
Columbia University, New York, New York
GERAD and Ecole Polytechnique, Montreal, Canada

We analyze the vehicle routing problem with constraints on the total distance traveled by each vehicle. Two objective functions are considered: minimize the total distance traveled by vehicles and minimize the number of vehicles used. We demonstrate a close relationship between the optimal solutions for the two objective functions and perform a worst case analysis for a class of heuristics. We present a heuristic that provides a good worst case result when the number of vehicles used is relatively small.

Subject classifications: networks/graphs; heuristics: worst case analysis; transportation; vehicle routing: distance constrained vehicle routing problem.