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

G-86-09

Problème de plus court chemin pour la confection de tournées de véhicules avec cueillette, livraison et contraintes d'horaires

et

Cet article traite d'un problème de plus court chemin sous contraintes. Il s'agit du chemin d'un véhicule complétant un sous-ensemble de demandes de transport ayant chacune une origine et une destination. Les contraintes additionnelles portent sur la capacité du véhicule et sur des intervalles de temps. Ce problème intervient pour la génération de tournées admissibles lors de la résolution par génération de colonnes du problème de fabrication de tournées de plusieurs véhicules. Nous proposons un algorithme de programmation dynamique très efficace pour le résoudre. Il utilise de nombreux critères qui éliminent les états ne satisfaisant par les contraintes. Des procédures heuristiques d'accélération sont également proposées.

, 30 pages