Groupe d’études et de recherche en analyse des décisions

# On the Distance Constrained Vehicle Routing Problem

## Chung-Lung Li, L Levi et Martin Desrochers

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 worst-case analysis for a class of heuristics. We present a heuristic that provides a good worst-case result when the customers are relatively close to the depot.

, 25 pages