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

G-89-44

Confection d'itinéraires pour le transport adapté

Un ensemble d'algorithmes permettant de confectionner les itinéraires et l'horaire des véhicules en vue du transport de personnes handicapées est présenté. L'approche proposée se divise en trois phases. Pour assurer la faisabilité des niveaux inférieurs, les différents niveaux de décisions ne sont pas pris de façon disjointe. Dans la première phase, les requêtes sont réparties entre les véhicules (phase de "clustering"). Cette phase est résolue par une approche heuristique de mini-regroupement des requêtes suivi d'un routage optimal des véhicules par génération de colonnes. Cette approche est une modification de la méthode "cluster first - route second" laquelle permet un regroupement plus intelligent des requêtes. Dans la deuxième phase, on réordonne optimalement les requêtes de chaque véhicule en solutionnant un problème de voyageur de commerce avec contraintes additionnelles de temps, de priorité et de capacité. Et dans la troisième phase, l'horaire de chaque véhicule est ré-optimisé en conservant leur itinéraire fixe. L'approche entière est testée sur des données réelles comportant 1890 requêtes ainsi qu'un ensemble de 133 pièces de travail.

, 208 pages