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).