A Mathematical Programming Framework for Network Capacity Control in Customer Choice-Based Revenue Management

RÉSUMÉ: Cette thèse est basée sur l'étude de différentes approches pour répondre à la problématique du contrôle de capacité pour les réseaux en gestion du revenu. Elle est composée de cinq chapitres. Le premier donne une vue d'ensemble de la thèse ainsi que la méthodologie suivie pour analyser chaque approche. Les trois chapitres suivants sont à mettre en lien avec des articles que nous avons soumis dans des revues internationales. Ils proposent de nouveaux modèles et algorithmes pour le contrôle de capacité en gestion du revenu. Les cinquième et sixième chapitres contiennent la conclusion et l'ouverture de la thèse. Nous décrivons, dans la suite, chaque chapitre plus précisément. Dans le chapitre deux, nous proposons une approche de programmation mathématique avec choix de clients afin d'estimer les bid prices variant dans le temps. Notre méthode permet de prendre facilement en compte les contraintes techniques et pratiques d'un système de réservation central contrairement aux solutions actuelles proposées dans la littérature. En plus d'avoir développé un filtre vérifiant la disponibilité de combinaisons de produits sous un contrôle par bid price, nous avons mis au point un algorithme de génération de colonnes où une puissante heuristique est utilisée pour résoudre le sous-Problème fractionnel qui est NP-difficile. Encore une fois nos résultats numériques sur des données simulées montrent que notre solution est meilleure que les approches actuelles. Dans le chapitre trois, nous développons une nouvelle méthode de programmation mathématique pour obtenir une allocation optimale des ressources avec un modèle de demande à choix non paramétriques. Notre méthode est alors complétement flexible et ne souffre pas des inefficacités des modèles paramétriques actuels comme ceux de type multinomial logit. Pour cela, nous avons modifié un algorithme de génération de colonnes afin de traiter efficacement des problèmes réels de grande taille. Nos résultats numériques montrent que notre méthode est meilleure que les méthodes de la littérature actuelle à la fois en qualité de la solution qu'en temps de résolution. Dans le chapitre quatre, nous analysons un nouveau programme mathématique avec choix de clients pour estimer des booking limits qui doivent respecter une hiérarchie (nesting) ainsi que des règles commerciales imposées par le système de réservation central. De la même manière qu'au chapitre précédent, nous identifions les combinaisons de produits respectant ou non la hiérarchie (nesting) fixée par la politique de contrôle et nous développons une heuristique basée sur la décomposition. En simulant le processus stochastique d'arrivée, nous montrons encore une fois l'efficacité de notre méthode pour résoudre des problèmes complexes. ABSTRACT: This dissertation, composed of five chapters, studies several policies concerned with the issue of capacity control in network revenue management. The first chapter provides an overview of the thesis, together with the general methodology used to analyze the control policies. In the next three chapters, each of which corresponding to a paper submitted to an international journal, we propose new models and algorithms for addressing network revenue management. The fifth and final chapter concludes the dissertation, opening avenues for further investigation. We now describe the content of each article in more detail. In Chapter 2, we propose a customer choice-based mathematical programming approach to estimate time-dependent bid prices. In contrast with most approaches in the literature, ours can easily accommodate technical and practical constraints imposed by central reservation systems. Besides developing a filter that checks the compatibility of feasible product combinations under bid price control, we develop a column generation algorithm where a powerful heuristic is used to solve the NP-hard fractional subproblem. Again, our computational results show, based on simulated data, that the new approach outperforms alternative approaches. In Chapter 3, we develop a new mathematical programming framework to derive optimal an optimal allocation of resources under a non-parametric choice model of demand. The implemented model is completely flexible and removes the inefficiencies of current parametric models, such as those of the ubiquitous multinomial logit. We develop for its solution a modified column generation algorithm that can efficiently address large scale, real world problems. Our computational results show that the new approach outperforms alternative approaches from the current literature, both in the terms of the quality of the solution and the required processing time. In Chapter 4, we analyze a novel customer choice-based mathematical program to estimate booking limits that are required to be nested, while simultaneously satisfying the business rules imposed by most central reservation system. Similar to what was accomplished in the previous chapter, we identify product combinations that are compatible (or not) with some nested control policy, and develop a decomposition-based heuristic algorithm. By simulating the stochastic arrival process, we again illustrate the efficiency of the method to tackle complex problems