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

G-89-04

A Matching Based Savings Algorithm for the Vehicle Routing Problem

et

In this paper, we address the problem of routing a fleet of vehicles from a central depot to customers with known demands. We consider the classical vehicle routing problem (VRP), where the vehicles are identical. The objective is to find a set of routes with the least total travel costs. We present a new savings heuristic, based on the weighted matching problem. The maximum weight matching enable to choose the route fusion in a non-myopic way. Computational results are provided for a number of known problems in order to compare the performance of the different methods.

, 19 pages

Ce cahier a été révisé en août 1989