Models for Integrated Demand Forecasting and Planning: Application to Large-scale Transportation Networks and Impact Assessment

Pour une meilleure gestion de leurs opérations, les compagnies de transport ont mis en place des outils d'aide à la décision. Les décisions suggérées par ces outils reposent fortement sur les prévisions de demande, et peuvent affecter considérablement leur rentabilité. Les compagnies aériennes par exemple, utilisent des systèmes de gestion du revenu pour le transport de passagers. Les compagnies de transport de marchandises quant à elles, résolvent des problèmes de conception de réseaux de service, dont l'objectif est de définir les services à offrir sur leur réseau pour transporter la demande à coût minimal. Les prévisions de demande, la planification et la rentabilité des compagnies de transport sont donc très fortement reliées. Dans cette thèse organisée en trois articles, nous réalisons des études interdisciplinaires portant sur l'intégration de la prévision de la demande et de la planification pour des réseaux de transport de grande taille, et sur l'analyse de l'impact sur des indicateurs de performance. Tout d'abord, nous présentons pour la première fois le problème d'estimation de la demande périodique relatif aux décisions tactiques des compagnies de transport de marchandises. Ce problème incorpore à la fois le problème de prévision de la demande, et le problème de planification. Pour des raisons de complexité et de faisabilité, les modélisations cycliques et déterministes de ce dernier sont majoritairement utilisées en pratique pour les problèmes de grande taille. Celles-ci reposent sur l'hypothèse d'une demande fixe, connue et identique à chaque période de l'horizon de planification, appelée la demande périodique. Nous proposons une méthodologie en deux étapes pour son estimation, de façon à minimiser les coûts tactiques. L'objectif de la première étape est d'estimer la demande à venir pour toutes les commodités transportées, à chaque période. Nous développons et comparons des modèles de prévisions issus des statistiques et de l'apprentissage automatique utilisant d'importantes caractéristiques extraites des données. Puis, la deuxième étape définit la demande périodique comme la solution d'un problème multi-niveaux qui intègre le problème de planification et dont l'objectif est de transporter la demande prévue à coût minimal. C'est un problème difficile car les niveaux inférieurs sont de grande taille, non convexes, non différentiables et combinatoires. Nous le résolvons sur un petit ensemble discret de solutions réalisables. Des résultats numériques produits avec les données de la division intermodale de la Compagnie des Chemins de fer nationaux du Canada montrent que notre méthodologie permet de réduire considérablement les coûts par rapport au cas où la demande périodique est égale à la moyenne des prévisions, une pratique répandue chez les transporteurs. Dans un deuxième temps, nous élargissons le problème d'estimation de la demande périodique introduit précédemment, et définissons cette dernière comme étant une fonction linéaire de la moyenne des prévisions. Nous proposons donc une nouvelle formulation multi-niveaux du problème, dans laquelle les variables de décisions sont désormais les coefficients de la fonction linéaire pour toutes les commodités transportées. De par la complexité du problème, nous explorons deux pistes pour sa résolution: les méta-heuristiques et les algorithmes d'optimisation de boîte noire. Toutes deux exploitent la propriété de résolution séquentielle, affirmant que les niveaux inférieurs de la formulation peuvent être résolus séquentiellement lorsque les variables de premier niveau sont fixées. Nous proposons deux nouvelles méta-heuristiques de recherche locale, et comparons leurs résultats avec un logiciel de boîte noire dont les meilleures performances sont obtenues sur des problèmes avec peu de variables. Toutefois, les réseaux de transport de grande taille rencontrés en pratique transportent des centaines de commodités, ce qui correspond à des centaines de variables. Pour réduire le nombre de variables tout en conservant des bonnes solutions, nous présentons des approches heuristiques ayant pour but de créer des groupes de commodités ayant la même valeur de coefficient. Les groupes sont créés à partir de la structure du réseau ou de l'analyse de la distribution de la demande sur l'horizon de planification. Cette méthodologie surpasse les performances indiquées dans un premier temps sur le problème du réseau intermodal, et génère une amélioration des coûts. De plus, les heuristiques de groupement permettent non seulement d'obtenir les meilleurs résultats, mais elle rendent également l'utilisation des logiciels de boîte noire possible pour les applications de grande taille. Dans un dernier temps, nous nous concentrons sur l'évaluation de l'impact d'une amélioration apportée à un outil d'aide à la décision. L'objectif est d'estimer, pour un transporteur, l'impact sur des indicateurs de performance tels que le revenu et le chiffre d'affaires. Nous considérons le cas particulier du système de gestion du revenu d'une compagnie aérienne, et proposons une approche qui évalue l'impact sur le revenu, indépendamment du type d'amélioration apportée au système. Le problème d'estimation de l'impact est intrinsèquement difficile car le revenu qui aurait été obtenu sans l'amélioration, en maintenant le système inchangé, n'est pas observable. L'approche que nous proposons repose sur des modèles dont l'objectif est d'estimer ce revenu, et qui nécessitent uniquement les données d'observation du revenu. L'impact est alors calculé comme étant la différence entre le revenu observé, résultant de l'amélioration, et le revenu estimé. Des résultats numériques issus des données d'Air Canada montrent que les modèles d'estimation du revenu non observable sont précis, et permettent d'estimer même un impact de petite ampleur.

Abstract

Decision-making systems deployed in transportation companies are used for efficiency and better planning of their operations. Such systems rely on demand forecasts, and the decisions they suggest can substantially affect the profitability of a carrier. Airlines, for instance, use Revenue Management Systems for their passenger-based activities. Freight carriers solve service network design problems for their tactical planning, optimizing the services to offer to transport the demand at minimal cost. Hence the strong link between demand forecasting, planning and profitability. In this research organized in three papers, we carry out interdisciplinary studies that focus on integrating demand forecasting and planning for large-scale transportation networks, and analyzing the impact on key performance indicators. First, we introduce the periodic demand estimation problem that integrates demand forecasting with planning for tactical decisions of a freight carrier. Cyclic and deterministic formulations of tactical planning problems prevail in practice, due to the complexity and feasibility of large-scale applications. This is our focus. Those formulations assume that the demand is fixed, known and repeated at each period of the planning horizon. We refer to the latter as periodic demand. We propose a two-step methodology to estimate it. The first step consists in forecasting demand for each commodity transported in the network at each period of the planning horizon. We develop and compare models based on statistics and machine learning literature exploiting important features extracted from the data. The second step defines the periodic demand as a solution to a multilevel mathematical program which integrates the planning problem and aims at transporting the forecasted demand at minimal cost. The lower levels are non-convex, non-differentiable and combinatorial, hence the difficulty of solving the multilevel program. We apply the methodology on the intermodal network of the Canadian National Railway Company. Computational experiments on a limited feasible set of periodic demand show that this methodology allows substantial reduction of the tactical planning costs compared to the common practice which consists in taking the periodic demand as the average of the demand forecasts. Second, we extend the periodic demand estimation problem and define the periodic demand as a deviation from the average of the demand forecasts. We propose a new multilevel formulation for the periodic demand estimation problem, where the decision variables are now the deviation coefficients for all commodities transported in the network. Due to the complexity of the problem, we explore two avenues for its resolution, namely metaheuristics and blackbox optimization algorithms. Both use the sequential property specific to our multilevel formulation, asserting that when the first-level variables are fixed, the lower levels can be solved sequentially. We propose two local search metaheuristics and compare their performances with an off-the-shelf blackbox solver known to perform best for problems with few variables. However, large-scale transportation networks met in practice carry hundreds of commodities, resulting in hundreds of deviation coefficient variables. To reduce the number of variables while keeping high-quality solutions, we propose heuristic approaches creating clusters of commodities having equal deviation coefficients. The clusters are formed by either exploiting the structure of the network or analyzing the distribution of demand over the planning horizon. The proposed methodology outperforms previous findings and yields decreases in costs on the Canadian National Railway Company application. Moreover, the clustering heuristics allow to reach the best tactical costs and leverage the use of off-the-shelf blackbox solvers even for large-scale applications. Finally, we propose a counterfactual prediction approach for the impact assessment problem of an improvement to a decision-making system. The objective is to assess the impact on a key performance indicator of the carrier, such as the revenue or the income. We focus on the Revenue Management System of an airline, and the impact on the revenue. The approach is independent of the improvement itself and only needs the revenue data. Since the revenue that would have been without improving the system is not observable, we propose to estimate it with counterfactual prediction models. We can then estimate the impact as the difference between the observed impacted revenue and estimated non-impacted revenue. Computational experiments with data from Air Canada show that both linear and deep-learning models are highly accurate for aggregated counterfactual revenue predictions, which allows to estimate small impacts.