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

G-82-12

Routes avec horaire traité par génération des colonnes

, et

Le problème considère un ensemble de parcours ayant chacun un lieu de début, un lieu de fin, une durée, un coût et un intervalle de temps pendant lequel ils doivent être effectués. Les parcours sont donnés a priori et peuvent consister en la visite d'un ou plusieurs points. Il faut trouver le nombre, l'horaire et les routes de véhicules pour effectuer chacun des parcours dans l'intervalle de temps imposé et ce en minimisant les coûts de déplacements entre les parcours. Ce problème est une généralisation du m voyageur de commerce.

Nous avons mis au point une méthode optimale traitant le temps comme une variable continue et trouvant simultanément les horaires et les routes de véhicules. La méthode procède par génération de colonnes produites par un sous-problème de chemin le plus court avec contraintes de temps. Des résultats numériques sont présentés.

, 27 pages