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

G-82-05

Two Exact Algorithms for the Distance Constrained Vehicle Routing Problem

, et

This paper considers a version of the vehicle routing problem in which all vehicles are identical and where the distance travelled by any vehicle may not exceed a prespecified upper bound. The problem is first formulated as an integer program which is solved by means of a constraint relaxation procedure. Two exact algorithms are developed: one based on Gomory cutting planes and one on branch and bound. Numerical results are reported.

, 20 pages