Stochastic Bilevel Pricing Problems over a Transportation Network

Dans cette thèse, nous étudions le problème de tarification sur un réseau sous des hypothèses d'incertitude (stochastiques). Elle comporte cinq chapitres. Les premier et deuxième chapitres sont une introduction générale et une introduction à la programmation biniveau, au modèle biniveau pour la tarification sur un réseau et à la programmation stochastique, respectivement. Mes deux articles soumis sont contenus dans les chapitres 3 et 4 et nous concluons cette thèse par le chapitre 5. Dans le chapitre 3, nous considérons une extension stochastique à deux étapes du modèle de tarification biniveau introduit par Labbée et al. (1998). Dans la première étape, le meneur (leader), au niveau supérieur, fixe les tarifs sur un sous-ensemble d'arcs du réseau dans le but de maximiser son revenu, tandis qu'au niveau inférieur, les flots sont affectés aux chemins les moins onéreux du réseau de transport multiflots. Dans la deuxième étape, on introduit une incertitude sur la demande et les coûts (qui deviennent stochastiques) et ajoutons la contrainte que les nouveaux tarifs ne doivent pas être trop éloignés de ceux obtenus à la première étape. Nous considérons deux types de tolérances, une absolue et l'autre proportionnelle pour chaque arc tarifé du réseau, afin d'éviter le problème de tarifs excessifs. Nous reformulons notre modèle biniveau stochastique à deux étapes en un problème biniveau stochastique à une étape (standard) afin de déterminer une borne supérieure valide du revenu. Ceci nous a permis de mettre en évidence certaines propriétés de la fonction objectif tel que son caractère continu et linéaire par morceaux, dans le cas de la tolérance absolue. Nous appliquons notre approche à trois petits exemples de réseaux de transport aériens ayant des topologies, des commodités et des scénarios différents. Nous comparons la validité de notre modèle en comparant la solution stochastique obtenue en remplaçant les terms aléatoires par leur espérance. Enfin, nous présentons des résultats numériques pour des instances générées aléatoirement, sur du réseaux à 40 nœuds et 200 arcs, pour diverses formulations du modèle. L'analyse des résultats numériques montre que le modèle qui suppose des tarifs égaux sur les deux étapes est plus complexe en raison de la limitation sévère sur les tarifs. Par ailleurs, le modèle où la demande est la seule variable aléatoire est moins complexe à puisque, plus court chemin du suiveur est le même dans les deux phases (étapes). Au chapitre 4, nous présentons trois variantes du problème de tarification biniveau stochastique en définissant le temps de déplacement, la fiabilité du chemin et la capacité des lienes comme des variables aléatoires. Dans la première variante, nous introduisons des désutilités stochastiques au niveau du meneur. Ces dernières sont modélisées comme fonction des coûts fixes, des tarifs, des délais et de la fiabilité. Les deux dernières désutilités (délai et fiabilité) représentent la situation où les meneurs sont prêts à compromettre leur temps d'arrivée cible (deadline) pour une plus grande fiabilité. Pour ce faire, les termes de désutilité sont exprimés par des quotients du délai sur la fiabilité, où et le numérateur le dénominateur sont aléatoires. Le modèle considère l'espérance mathématique de la fonction objectif du leader et un comportement ``wait and see'' (attente - action) pour le suiveur. Un exemple illustre l'application du modèle à des réseaux de télécommunications ou des compagnies aériennes. Nous effectuons également une analyse de sensibilité à l'égard des variations des pénalités sur les délais et les dates limites (deadline) de différents ensembles de coûts fixes. Dans la deuxième variante, on considère un modèle qui prend en compte plusieurs caractéristiques de la première variante avec deux différences majeures: (1) une pénalité sur le délai est encourue par le leader et (2) la fiabilité d'un arc est maintenant fonction du flot qui le traverse, ainsi que et d'une capacité aléatoire. Une contrainte probabiliste, dont le rôle est d'éviter le débordement et d'assurer le fonctionnement fiable du système, est alors imposée au leader. Dans ce contexte, le choix du trajet du suiveur n'est pas influencé par la fiabilité des trajets car la contrainte imposée au niveau supérieur assure un niveau de service adéquat. Nous reformulons le modèle comme un problème de programmation linéaire mixte en nombres entiers, en transformant les contraintes probabilistes en contraintes linéaires. Nous montrons alors que la fonction du revenu est continu par rapport au vecteur de capacité. Nous illustrons l'application du modèle à un réseau de transport et nous montrons comment les changements dans le seuil de probabilité et le paramètre de proportion de la capacité de conception affectent le revenu. Enfin, la troisième variante considère la congestion, ce qui est un problème fréquent dans les transports urbains (résultant de conditions météorologiques, de travaux, de demande excédentaire) et dans les télécommunications (résultant du trafic et de la dégradation du réseau). En général la congestion est directement liée à la qualité de service. Contrairement à la deuxième variante où la qualité de service est imposée à l'aide d'une contrainte probabiliste, la troisième variante modélise explicitement la congestion par une fonction volume-délai du type BPR (Bureau of Public Roads). Nous présentons un exemple et une analyse de sensibilité du revenu en fonction des changements des paramètres de proportion de la capacité de conception et du seuil de probabilité.

Abstract

This dissertation studies the network ricing problem (NPP) under uncertainty assumptions. It has five chapters. The first and second chapters give a general introduction to this thesis and the second chapter provides an introduction to bilevel programming (BP), the BP model of NPP, and stochastic programming. Chapters 3 and 4 contain my two submitted papers and we conclude this thesis in Chapter 5. In Chapter 3, we consider a two-stage stochastic extension of the bilevel pricing model introduced by Labbée et al. (1998). In the first stage, the leader sets tariffs on a subset of arcs of a transportation network with the goal of maximizing profits, and at the lower level, flows are assigned to the cheapest paths of a multicommodity transportation network. In the second stage, we introduce uncertain information (stochastic demand and market prices) and the constraint that tariffs should not differ too greatly from those set in the first stage. We consider two forms of predetermined threshold restrictions (absolute restriction (AR) and proportional restriction (PR)) on each tariff arc of the network to avoid the excessive-tariff problem. We further provide a single-stage reformulation of the two-stage SBP to calculate a valid upper bound for the revenue. We derive a few propositions to show some properties of the value function of our model such as its continuity and piecewise linearity in the AR case. We present three small airline-network examples with different network topologies, numbers of commodities, and outcomes of the random variables. We also give the stochastic and the expected solution of the expected value (EEV) solutions to indicate the value of the model and the stochastic solution. Finally, we present numerical results for randomly generated instances with 40 nodes and 200 arcs for various formulations of the model. The analysis of the numerical results shows that the model that assumes equal tariffs for both stages is more complex because of the tight restriction on the tariffs. The model that assumes that the demand is the only random variable is less complex because of the shortest-path equality for the follower problems in both stages. In Chapter 4, we introduce three variations of the stochastic bilevel pricing problem by considering delay, path/link reliability, and link capacity as random variables. In the first variation, we introduce stochastic disutility at the user level. This is modeled as a function of fixed costs, tariffs, tardiness, and reliability, and represents the situation where users are ready to compromise their target arrival time (deadline) for higher reliability. To achieve this goal, the disutility terms are expressed as the ratio of tardiness to reliability, both the numerator and denominator being random. The model considers the expectation form of the leader's objective function and ``wait and see” behavior for the follower. An example is presented to show the application of the model to telecom/airline networks. We also carry out a sensitivity analysis with respect to changes in the tardiness penalties and deadlines for different sets of fixed costs. In the second variation, we consider a framework that takes into account several features from the first variation. However, there are two differences. First, a tardiness penalty is incurred by the leader. Second, the reliability of an arc is now related to the flow that it carries and to a random capacity. A chance constraint, whose role is to prevent overflow and ensure the reliable performance of the system, is then imposed on the leader. In this setting, the path choice of the follower is not influenced by the reliability of the paths, since the constraint imposed at the upper level ensures a predetermined level of service. We reformulate the model as a linear MIP by transforming the chance constraints to linear constraints and show that the value function of the revenue is a continuous function with respect to the design-capacity proportion parameter. We illustrate the application of the model to telecom/transportation networks and show how changes in the probability level and the proportion parameter can change the revenue. Finally, the third variation considers congestion, which is a common issue in urban transportation (arising from construction, weather conditions, excess demand) and in telecommunications (arising from traffic, network degradation). It is directly related to the ``quality of service.'' In contrast with the second variation, where the quality of service is enforced by a chance constraint, the third variation explicitly models congestion via a volume-delay function of the BPR (Bureau of Public Roads). We present an example and a sensitivity analysis to show the effects on the revenue of changes in the design-capacity proportion parameter and the probability level.