Machine Learning for Booking Control

La gestion des revenus est une approche analytique que les entreprises utilisent pour maximiser leurs profits. Cette thèse se concentre sur le problème du contrôle de l'acceptation et de rejet de réservations : Étant donné une capacité limitée, accepter une demande de réservation ou la rejeter afin de réserver de la capacité pour de futures réservations avec des revenus potentiellement plus élevés. Ce problème peut être formulé comme un programme dynamique stochastique à horizon fini, où l'acceptation d'une demande entraîne un profit et, à la fin de la période de réservation, le coût d'exécution des réservations acceptées est encouru. Le coût de l'exécution des demandes est appelé le problème de la prise de décision opérationnelle et, dans de nombreuses applications, il nécessite la résolution de problèmes non triviaux de programmation en nombres entiers mixtes. Ce travail propose d'entraîner un modèle prédictif pour approximer la valeur de la solution du problème de prise de décision opératioNnelle par l'apprentissage supervisé. Les prédictions peuvent ensuite être exploitées par de la programmation dynamique approximative générale et de l'apprentissage par renforcement pour résoudre le problème du contrôle des réservations. Cette méthodologie est ensuite évaluée sur deux problèmes de contrôle de réservation issus de la littérature. Le premier problème est un problème de logistique de distribution, pour lequel cette méthodologie produit des politiques qui permettent d'obtenir des bénéfices significativement plus élevés avec un temps de calcul réduit par rapport aux solutions de base. La deuxième application est une application de fret aérien, où la performance de cette approche se situe juste en dessous de l'état de l'art. Bien que les résultats obtenus dans cette thèse ne soient pas complètement compétitifs par rapport à l'état de l'art, plusieurs directions pour les travaux futurs existent qui pourraient, nous l'espérons, conduire à une amélioration supplémentaire. En outre, la méthodologie présentée dans cette thèse est générale, c'est-à-dire qu'elle peut facilement être étendue à de nombreux problèmes à horizon fini et, pour cette raison, elle apporte une contribution notable au contrôle des réservations.

Abstract

Revenue management is an analytic approach which companies utilize to maximize profit. This thesis focuses on the problem of controlling booking accept/reject decisions: Given a limited capacity, accept a booking request or reject it to reserve capacity for future bookings with potentially higher revenue. This problem can be formulated as a finite-horizon stochastic dynamic program, where accepting a request results in a profit and at the end of the booking period the cost of fulfilling the accepted bookings is incurred. The cost of fulfilling requests is referred to as the operational decision-making problem, and in many applications requires the solution of non-trivial mixed-integer programming problems. This work proposes to train a predictor to approximate the solution value of the operational decision-making problem through supervised learning. The predictions can then be leveraged within general-purpose approximate dynamic programming and reinforcement learning to solve the booking control problem. This methodology is then evaluated on two booking control problems from the literature. The first problem is a distributional logistics problem, where this methodology produces policies that result in significantly higher profit at a reduced computing time when compared to baselines. The second application is an airline cargo application, where this approach falls just short of state-of-the-art baselines. Although the results achieved in this thesis are not competitive with the state-of-the-art, there are several directions for future work that can hopefully lead to further improvement. Furthermore, the methodology presented in this thesis is general, i.e., can easily be extended to many end-of-horizon problems and for this reason, it provides a valuable contribution to booking control.