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.

Abstract

To date, optimization has proven to be one of the most effective strategies for raising people’s willingness to use public transportation, hence enhancing its advantages for the environment, society, and economy in general. In order to accomplish this, public transportation companies have raised their resources in order to optimize their systems, such as by utilizing optimization techniques and artificial intelligence, which not only helps companies decrease costs but also enhances the passenger experience. To ensure that every trip is covered at the lowest possible cost, public transportation systems manage the design of bus lines, including choosing the schedules taken by each bus and the locations of each bus terminal. Once the timetable, which specifies the frequency of bus depar-tures and the time each bus trip will begin, has been determined, the buses are assigned to the trips. Then, based on their availability, the drivers are paired with the buses. Many exact and heuristic algorithms have been proposed to handle these planning steps, and some authors have even combined some of these steps to generate better solutions. The Multiple Depot Vehicle Scheduling Problem (MDVSP) addresses a bus scheduling problem where the vehicles are stored in two or more depots. In this thesis, we study the MDVSP with Controlled Trip Shifting (MDVSP-CTS), which allows for controlled schedule adjustments, and considers the option of slightly changing the trip departure time. On the other hand, trip shifting needs to be kept under control to prevent a negative impact on the level of passenger service. According to previous work done in [1], the MDVSP-CTS program is solved using a two-phase heuristic. The two-phase heuristic algorithm aims to achieve processing times that can be ap-plied to the transportation industry. The first phase is solved using a column generation heuristic to obtain the vehicle schedules, while the second phase is solved using a Mixed Integer Linear Programming (MILP) solver to find the best timetable based on the previously-computed bus schedules in phase I. As compared to the MDVSP model, the MDVSP-CTS model is larger since it incorporates trip copies to allow trip shifting. Here, a heuristic approach is used to reduce computation times, which can be further sped up by taking into account a suitable subset of trips that can be shifted. To speed up this optimization model, we use a prediction model to assist us in automatically determining which trips are suitable candidates for selection as shifting trips. To predict whether a trip should be shifted or not, we develop a machine learning model that can be trained using real-world data and can predict trips that might have a change in their schedule to shift ahead or backward. Therefore, we are able to dynamically adjust the departure time for the potential bus trips predicted by the model. To solve the machine learning model, we randomly split the data into train, validation and test instances. Finally, we use the model’s accuracy as a criterion to assess how successful the pre-dictions are. This study provides and discusses a comparison of three scenarios : allowing all trips to be shif-ted, allowing only trips that are anticipated to have the potential to be shifted, and also allowing only trips that are determined to be shifted based on the first scenario. It is promising to observe that our machine learning model was able to speed up the optimization model with a compu-tational time reduction of over 50%, while preserving the same solution quality on average. The suggested machine learning model, in which we used the extracted predicted shifted trips as the subset of trips to be shifted, ran the heuristic algorithms faster when we used a subset of the actual trips to be shifted. This result was obtained despite the fact that the accuracy of the prediction model was 89%, whereas the accuracy of the actual shifted trips is 100%. Overall, it can be concluded that by further enhancing the existing optimization model, this method speeds up the bus schedule optimization algorithm that was previously offered for bus transit planning systems.