Problèmes de tournées en viabilité hivernale utilisant la prévision des volumes d'épandage

Cette thèse combine deux domaines de recherche différents appliqués au déneigement : la recherche opérationnelle et la science des données. La science des données a été utilisée pour développer un modèle de prédiction de quantité de sel et d'abrasif avec une méthodologie d'apprentissage machine; par la suite, ce modèle est pris en compte pour la confection des tournées de véhicules. La confection des tournées a été élaborée en utilisant des outils de la recherche opérationnelle, qui servent à optimiser les tournées en considérant plusieurs contraintes et en intégrant les données réelles. La thèse est le fruit d'une collaboration avec deux villes québécoises, Granby et Saint-Jean-sur- Richelieu. Elle traite une application réelle en viabilité hivernale, qui est l'opération d'épandage. Cette opération est une activité nécessaire, dont le but est d'assurer une meilleure circulation routière. Cependant, cela se réalise avec un coût économique et environnemental important. Par conséquent, la réduction de ce coût devient une grande préoccupation. Cette thèse contribue significativement aux opérations d'épandage : premièrement, nous prédisons la quantité nécessaire de sel et d'abrasif à épandre afin d'éviter le surépandage; deuxièmement, nous optimisons les tournées des opérations d'épandage en considérant la variation de la quantité. La première contribution de cette thèse consiste en un modèle de prédiction des quantités de sel et d'abrasif pour chaque segment de rue et pour chaque heure, en utilisant des algorithmes d'apprentissage machine. L'importance de cette contribution réside d'une part dans l'intégration des données géomatiques avec les données météo-routières, et d'autre part dans l'extraction des variables importantes (feature engineering) pour le modèle de prédiction. Plusieurs algorithmes d'apprentissage machine ont été évalués : (les forêts aléatoires, les arbres extrêmement aléatoires, les réseaux de neurones artificiels, Adaboost, Gradient Boosting Machine et XGBoost). Le modèle élaboré par XGBoost a réalisé une meilleure performance. Le modèle de prédiction permet non seulement de prédire les quantités de sel et d'abrasif nécessaires à épandre mais aussi, d'identifier les variables les plus importantes pour la prédiction. Cette information représente un outil de décision intéressant pour les gestionnaires. L'identification des variables importantes pourrait améliorer les opérations de déneigement. D'après les résultats trouvés, le facteur humain (conducteur) influence significativement la quantité d'épandage; donc, le contrôle de ce facteur peut améliorer considérablement ces opérations. La deuxième contribution introduit un nouveau problème dans la littérature : le problème de tournées de véhicules générales avec capacité dont la quantité de sel et d'abrasif dépend du temps. Le problème est basé sur l'hypothèse que le modèle de prédiction est capable de fournir la quantité d'épandage pour chaque segment et pour chaque heure avec une bonne précision. Le fait d'avoir cette information pour chaque heure et pour chaque segment de rue, introduit la notion du temps dépendant. Le nouveau problème est modélisé à l'aide d'une formulation mathématique sur le graphe original, ce qui présente un défi de modélisation. En effet, il est difficile d'associer des temps de début et de fin uniques à un arc ou à une arête. Une métaheuristique basée sur la stratégie de destruction et construction a été développée pour résoudre les grandes instances. La métaheuristique est inspirée de SISRs (Slack Induction by String Removals). Elle considère la demande dépendante du temps et la présence des arêtes par la méthode d'évaluation basée sur la programmation dynamique. De nouvelles instances ont été créées à partir des instances des problèmes de tournées de véhicules générales avec contrainte de capacité avec demande fixe. Elles ont été générées à partir de différents types de fonction dont la demande dépend du temps. La troisième contribution propose une nouvelle approche, dans le but de présenter le niveau de priorité des rues (la hiérarchie de service) sous forme d'une fonction linéaire dépendante du temps. Le problème présenté dans cette contribution concerne des tournées de véhicules générales hiérarchiques avec contrainte de capacité sous l'incertitude de la demande. Lorsque les données collectées ne permettent pas de développer un bon modèle de prédiction, la notion de demande dépendante du temps n'est plus valide. L'approche robuste a démontré une grande réussite pour traiter et résoudre les problèmes avec incertitude. Une métaheuristique robuste a été proposée pour résoudre les deux cas réels de Granby et de Saint-Jean-sur-Richelieu. La métaheuristique a été validée par un modèle mathématique sur les petites instances générées à partir des cas réels. La simulation de Monte Carlo a été utilisée pour évaluer les différentes solutions proposées. En outre, elle permet d'offrir aux gestionnaires un outil de décision pour comparer les différentes solutions robustes, et aussi pour comprendre le compromis entre le niveau de robustesse souhaité et d'autres mesures de performances (coût, risque, niveau de service).

Abstract

This thesis combines two different fields applied to winter road maintenance : operational research and data science. Data science was used to develop a prediction model for the quantity of salt and abrasive with a machine learning methodology, later this model is considered for building vehicles routing. This route planning was developed using operational research which seeks to optimize routes by looking at several constraints and by integrating real data. The thesis which is the fruit of a collaboration with two Canadian cities Granby and Saint-Jean-sur-Richelieu, deals with a real application in winter road maintenance which is the spreading operation. The spreading operation presents an activity necessary for winter road maintenance, in order to ensure better road traffic. However, this road safety comes with a significant economic and environmental cost, which creates a great concern in order to reduce the economic and environmental impact. This thesis contributes significantly in the spreading operations : firstly, predicting the necessary quantity of salt and abrasive to be spread in order to avoid over-spreading, secondly optimizing the spreading operations routes considering quantity variations. The first contribution of this thesis is to develop a prediction model for the quantities of salt and abrasive using machine learning algorithms, for each street segment and for each hour. The importance of this contribution lies in the integration of geomatic data with weather-road data, and also the feature engineering. Several machine learning algorithms were evaluated (Random Forest, Extremely Random Trees, Artificial Neural Networks, Adaboost, Gradient Boosting Machine and XGBoost); ultimately XGBoost performed better. The prediction model not only predicts the amounts of salt and abrasive needed to spread, but also identifies the most important variables in the model. This information presents an interesting decision-making tool for managers. The identification of important variables could improve snow removal operations. According to the results, the human factor (driver) significantly influences the amount of spreading, so controlling this factor can significantly improve the spreading operations.The second contribution introduces a new problem in the literature : the mixed capacitated general routing problem with time-dependent demand; the problem is based on the assumption that the prediction model is able to provide the amount of spreading for each segment and for each hour with good accuracy. Having this information for each hour and for each street segment introduces the concept of time dependency. The new problem was modeled using a mathematical formulation on the original graph, which presents a modeling challenge since it is difficult to associate a unique starting and ending time to an arc or edge. A meta-heuristic based on the destruction and construction strategy has been developed to solve large-scale instances. The meta-heuristic is inspired by SISRs considers time-dependent demand and the presence of edges by an evaluation method based on dynamic programming. New instances were created from the instances of the mixed capacitated general routing problem with fixed demand; the new instances were generated from different types of function where the demand varies with time. The third contribution proposes a new approach to present the service hierarchy or the priority level of streets, as a time-dependent linear function. The problem addressed in this contribution concerns the hierarchical mixed capacitated general routing problems under demand uncertainty. When the collected data does not allow the development of a good prediction model, the concept of time-dependent demand is no longer valid. The robust approach has demonstrated great success in resolving and dealing with problems with uncertainty. A robust meta-heuristic was proposed to solve the two real cases Granby and Saint-Jean-sur-Richelieu, the meta-heuristic was validated by a mathematical model on small instances generated from the real cases. The Monte Carlo simulation was used, on the one hand, to evaluate the different solutions proposed, and, on the other hand, to offer managers a decision tool to compare the different robust solutions and also to understand the trade-off between the desired level of robustness, and other performance measures (cost, risk, level of service).