Planifier les horaires dans le domaine du transport peut se révéler un véritable casse-tête. Avec des milliers d’employés et des centaines de trajets à gérer, le nombre de possibilités est tellement immense qu’il est difficile, voire impossible de les énumérer de façon explicite. Le défi est toujours de trouver une planification aux plus faibles coûts. Le professeur au Département de mathématiques et de génie industriel de Polytechnique Montréal, Issmail El Hallaoui, a développé une façon plus rapide et plus efficace d’y arriver.
Agréger plusieurs tâches permet de réduire la taille du problème et le nombre de combinaisons possibles.
Dans les transports en commun ou en aviation, la répartition des tâches est souvent réalisée à l’aide de modèles de partitionnement d’ensemble qui ont toutefois leurs limites : ils peuvent, entre autres, générer des milliards de combinaisons dont il faut ensuite tenter d’extraire l’horaire le moins coûteux, et ce, dans un laps de temps raisonnable.
Avec son équipe, le chercheur a développé un nouveau modèle à partir d’une observation très simple : un chauffeur d’autobus reste souvent dans le même véhicule pendant sa journée de travail et peut effectuer plusieurs trajets consécutifs sans quitter son siège. Pourquoi ne pas regrouper ces segments en une seule tâche ? En effet, agréger plusieurs tâches permet de réduire la taille du problème et le nombre de combinaisons possibles.
L’équipe d’Issmail El Hallaoui a ainsi réussi à trouver la solution optimale à un problème comportant 2 000 tâches en seulement une minute grâce à son nouvel outil de planification des horaires, alors que les solveurs commerciaux y arrivent difficilement en…10 heures ! Déjà, l’industrie de l’aviation utilise ce nouveau programme informatique pour gérer son personnel et résoudre un problème qui comporte 50 000 vols. L’équipe de recherche souhaite maintenant tirer profit de l’historique de planification des horaires afin d’améliorer les résultats du solveur et son temps de calcul.
