A Machine Learning Preprocessor to Speed Up the Solution of a Bus Scheduling Problem with Controlled Trip Shifting

À ce jour, l’optimisation s’est avérée être l’une des stratégies les plus efficaces pour accroître la volonté des gens d’utiliser les transports en commun, améliorant ainsi leurs avantages pour l’environnement, la société et l’économie en général. Pour ce faire, les entreprises de trans-port public ont augmenté leurs ressources afin d’optimiser leurs systèmes, par exemple en utilisant des techniques d’optimisation et l’intelligence artificielle, qui non seulement aident les entreprises à réduire les coûts, mais améliorent également l’expérience des passagers. Pour s’assurer que chaque trajet est couvert au moindre coût possible, les systèmes de transport en commun gèrent la conception des lignes de bus, y compris le choix des horaires empruntés par chaque bus et l’emplacement de chaque gare routière. Une fois que l’horaire, qui précise la fréquence des départs des autobus et l’heure de début de chaque voyage d’autobus, a été déterminé, les autobus sont affectés aux voyages. Ensuite, en fonction de leur disponibilité, les chauffeurs sont jumelés aux bus. De nombreux algorithmes exacts et heuristiques ont été proposés pour gérer ces étapes de planification, et certains auteurs ont même combiné certaines de ces étapes pour générer de meilleures solutions. Le problème de planification de véhicules à plusieurs dépôts (MDVSP) résout un problème de planification de bus où les véhicules sont stockés dans deux dépôts ou plus. Dans ce mémoire, on étudie le MDVSP avec Controlled Trip Shifting (MDVSP-CTS), qui permet des ajustements contrôlés des horaires et envisage la possibilité de modifier légèrement l’heure de départ des trajets. D’autre part, le décalage des trajets doit être limité pour éviter un impact négatif sur le niveau de service aux passagers. Selon des travaux antérieurs effectués dans [1], le programme MDVSP-CTS est résolu à l’aide d’une heuristique à deux phases. L’algorithme heuristique à deux phases vise à atteindre des temps de traitement applicables à l’industrie du transport. La première phase est résolue à l’aide d’une heuristique de génération de colonnes pour obtenir les horaires des véhicules, tandis que la deuxième phase est résolue à l’aide d’un solveur de programmation linéaire mixte en nombres entiers (MILP) pour trouver le meilleur horaire basé sur les horaires de bus précédemment calculés dans la phase I. Par rapport au modèle MDVSP, le modèle MDVSP-CTS est plus grand car il intègre des copies de voyage pour permettre le changement de voyage. Ici, une approche heuristique est utilisée pour réduire les temps de calcul, qui peuvent être encore accélérés en prenant en compte un sous-ensemble approprié de trajets qui peuvent être décalés. Pour accélérer ce modèle d’optimisation, on utilise un modèle de prédiction pour nous aider à déterminer automatiquement quels trajets sont des candidats appropriés pour la sélection en tant que trajets avec décalage. Pour prédire si un trajet doit être décalé ou non, on développe un modèle d’apprentissage au-tomatique qui peut être formé à l’aide de données du monde réel et peut prédire les trajets qui pourraient avoir un changement d’horaire. Par conséquent, on est en mesure d’ajuster dynamiquement l’heure de départ des trajets de bus potentiels prédits par le modèle. Pour résoudre le modèle d’apprentissage automatique, on divise aléatoirement les données en instances d’apprentissage, de validation et de test. Enfin, on utilise la précision du modèle comme critère pour évaluer le succès des prédictions. Cette étude fournit et discute une comparaison de trois scénarios : autoriser le déplacement de tous les déplacements, autoriser uniquement les déplacements dont on prévoit qu’ils ont le potentiel d’être déplacés, et autoriser également uniquement les déplacements dont le déplace-ment est déterminé en fonction du premier scénario. Il est prometteur de constater que notre modèle d’apprentissage automatique a pu accélérer le modèle d’optimisation avec une réduction du temps de calcul d’un peu plus de 50% pour nos instances de test, tout en maintenance une qualité de solution similaire en moyenne. Le modèle d’apprentissage automatique suggéré, dans lequel nous avons utilisé les trajets dé-calés prédits extraits comme sous-ensemble de trajets à décaler, a exécuté les algorithmes heuristiques plus rapidement lorsque nous avons utilisé un sous-ensemble des trajets réels à décaler. Ce résultat a été obtenu malgré le fait que la précision du modèle de prédiction était de 89%, alors que la précision des trajets décalés réels est de 100%. tant, cette méthode accélère l’algorithme d’optimisation des horaires de bus qui était auparavant proposé pour les systèmes de planification du transport en commun par bus.