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

G-82-10

Integer Linear Programming Approach to the Vehicle Scheduling Problem

This paper considers a version of the vehicle scheduling problem (VSP) in which a non-negative weight is assigned to each city to be visited and where all vehicles are identical and have the same capacity. The weight assigned to a vehicle on a given route may not exceed this capacity. Cities can be visited more than once if it is economical to do so; however, some cities (with zero weights) may not be visited. This paper describes and optimal integer linear programming approach to the VSP, based on earlier work by Fleischmann and by the author.

, 9 pages