Ré-optimisation de plans d'expédition de marchandises par cargos aériens

Lorsque des clients veulent transporter des marchandises d'un endroit à un autre par cargos aériens, il est très commun que les clients soient facturées seulement pour la capacité qu'ils ont utilisée et non pour la capacité réservée. À cause de cette politique de réservation, les clients réservent plus de capacité qu'il leur est réellement nécessaire. Il est aussi courant que les clients ne se présentent pas à l'aéroport le jour du décollage. Pour compenser cela, les compagnies ont recours à la surréservation, c'est-à-dire qu'elles vendent plus de capacité qu'elles n'en disposent réellement. Un mauvais seuil de surréservation peut occasionner deux situations : soit il est trop faible et on aurait pu accepter plus de demandes, soit trop de demandes ont été acceptées et toutes les demandes ne peuvent être chargées dans l'avion. Une certaine partie de ces demandes devra être ré-assignée à d'autres vols. Cette étape a généralement lieu quelques heures avant le départ. Ce mémoire présente, sous la forme d'un article, une méthode de ré-optimisation qui est appliquée à un plan d'expédition et dont l'objectif est de minimiser l'espérance de débordement sur un réseau aérien. Pour réduire cette dernière, les marchandises des avions plus à même de déborder sont ré-assignées à des avions moins remplis. Afin de décrire le comportement des clients, nous avons introduit une distribution qui combine une distribution de Bernoulli à une distribution normale. L'originalité de cette distribution est qu'elle permet de bien capturer le cas où les clients ne se présentent pas à l'aéroport et qu'elle traduit la différence entre la marchandise réelle et la marchandise réservée. Par la suite, nous avons développé deux modèles mathématiques en nombres entiers dont la fonction objectif est l'espérance du débordement sur le réseau. Ces modèles mathématiques, utilisés en ré-optimisation, ont permis de produire des plans d'expédition plus robustes avec moins de débordements tout en permettant une utilisation plus homogène des avions sur l'ensemble du réseau, créant ainsi de l'espace pour accepter plus de demandes sur les vols les plus saturés. Dans le premier modèle, la fonction objectif est approximée à l'aide de scénarios. Dans le second modèle, la fonction objectif est calculée analytiquement en utilisant la distribution introduite. La fonction objectif obtenue étant non-linéaire, nous l'avons approximé afin d'avoir un modèle résolvable à l'aide de solveurs commerciaux. Pour tester la précision et la rapidité de notre modèle, nous avons simulé un plan d'expédition en se basant sur un fichier de données contenant l'ensemble des vols pour le mois de mai 2017. Lors de la phase expérimentale, nous avons comparé les résultats obtenus à l'aide du modèle analytique à ceux obtenus avec le modèle par scénarios. Nous avons obtenu des solutions de qualité similaire mais le modèle analytique permet d'obtenir des solutions en des temps de calculs relativement inférieurs. De plus, un autre avantage de ce modèle est qu'il nécessite seulement de connaître la probabilité de non-présentation d'un client, la moyenne et la variance de la distribution décrivant la quantité de marchandises qu'un client souhaite transporter. Il n'est pas nécessaire de connaitre la distribution dans sa totalité, ce qui réduit considérablement le travail de préparation des données. Finalement, les résultats prometteurs, obtenus au cours de ce projet, ont permis d'évaluer la précision et le temps de résolution sur un vrai réseau de grande taille et encouragent à tester notre méthode sur des données industrielles pour voir son efficacité réelle.

Abstract

When customers want to transport goods from one place to another by air cargo, it is very common for customers to be billed only for the capacity they have used and not for the reserved capacity. As a result of this reservation policy, customers are booking more capacity than they really need. It is also common for customers not to show up at the airport on the day of departure. In order to compensate for this potential waste of capacity, airfreight carriers resort to overbooking, i.e., they sell more capacity than is actually available. Nevertheless, a wrong overbooking threshold can lead to two cases: either it is too low and more requests could have been accepted, or too many requests have been accepted and not all of them can be loaded on the aircraft. Some of these requests will have to be reassigned to other flights. This stage usually takes place a few hours before departure. This thesis presents, in the form of an article, a reoptimization method that is applied to a shipping plan, and whose objective is minimize the expectation of overflow on the whole network. To reduce this expectation, the commodities from aircrafts that are more likely to overflow are reassigned to aircrafts that are less filled. In order to describe customer behaviour, we introduced a distribution that combines a Bernoulli distribution with a normal distribution. The originality of this distribution is that it makes it possible to capture the case where customers do not show up at the airport and that it reflects the difference between the actual commodities and the booked commodities. Subsequently, we developed two integer mathematical models whose objective function is the expectation of overflow on the network. These mathematical models, used in reoptimization, have made it possible to produce more robust shipping plans with fewer overflows but also to have a more homogeneous use of aircraft throughout the network, thus creating space to accept more requests on the most saturated flights. In the first model, the objective function is approximated using scenarios. In the second model, the objective function is calculated analytically using the introduced distribution. The objective function obtained being nonlinear, we approximated it in order to have a model that can be solved using commercial solvers. To test the accuracy and quality of our model, we simulated a shipping plan based on a data file containing all the flights for May 2017. In the experiments, we compared the results obtained using the analytical model with those obtained using the scenario-based model. We have obtained solutions of similar quality, but the analytical model allows us to obtain solutions in relatively shorter computation times. In addition, another advantage of this model is that it only requires knowing the probability of no-show of a client, as well as the average and the variance of the distribution describing the quantity of goods that a client wishes to transport. It is not necessary to know the entire distribution, which considerably reduces the work of data preparation. Finally, the promising results obtained during this project made it possible to evaluate the accuracy and solution time on a real large network and encourage us to test our method on industrial data to see its real effectiveness.