Tarification logit dans un réseau

Le problème de tarification qui nous intéresse ici consiste à maximiser le revenu généré par les usagers  d'un  réseau de transport. Pour se rendre à leurs destinations,  les usagers font un choix de route et utilisent  des arcs sur lesquels nous imposons des tarifs. Chaque route est caractérisée (aux yeux de l'usager) par sa "désutilité", une mesure de longueur généralisée tenant compte à la fois des tarifs et des autres coûts associés à son utilisation. Ce problème   a surtout été abordé  sous une modélisation déterministe de la demande selon laquelle seules des routes de désutilité minimale  se voient attribuer une mesure positive de flot. Le modèle déterministe  se prête bien à une résolution globale, mais pèche par manque de réalisme. Nous considérons ici une extension probabiliste de ce modèle, selon laquelle  les usagers d'un réseau sont alloués aux routes d'après un modèle de choix discret logit. Bien que le problème de tarification qui en résulte  est non linéaire et non convexe, il conserve néanmoins une forte composante combinatoire que nous exploitons à des fins algorithmiques.  Notre contribution se répartit en trois articles. Dans le premier, nous abordons le problème d'un point de vue  théorique pour le cas avec une paire origine-destination. Nous développons une analyse de premier ordre qui exploite les propriétés analytiques  de l'affectation logit et   démontrons la validité de règles de simplification de la topologie du réseau qui permettent de  réduire  la dimension du problème sans en modifier la solution. Nous   établissons ensuite l'unimodalité du problème  pour une vaste gamme de topologies et nous généralisons  certains de nos résultats au problème de la  tarification d'une ligne de produits.   Dans le deuxième article,  nous abordons le problème d'un point de vue  numérique pour le cas avec plusieurs paires origine-destination. Nous  développons des algorithmes qui exploitent  l'information locale et la parenté des formulations probabilistes et déterministes. Un des résultats de notre analyse est l'obtention de bornes  sur  l'erreur  commise par les modèles  combinatoires dans l'approximation du revenu logit. Nos essais numériques montrent qu'une approximation combinatoire rudimentaire permet  souvent d'identifier des solutions quasi-optimales.  Dans le troisième article, nous considérons l'extension du problème à une demande hétérogène. L'affectation de la demande y est donnée par un modèle de choix discret logit mixte  où la sensibilité au prix d'un usager est  aléatoire. Sous cette modélisation, l'expression du revenu n'est pas analytique et ne peut être évaluée de façon exacte. Cependant, nous démontrons  que l'utilisation  d'approximations non linéaires et combinatoires permet d'identifier des solutions quasi-optimales. Finalement, nous en profitons  pour illustrer la richesse du modèle, par le biais d'une interprétation économique, et examinons  plus particulièrement la contribution au revenu des différents groupes d'usagers. The network pricing problem  consists in finding tolls to set on a subset of a network's arcs, so to maximize a revenue expression. A fixed demand of commuters, going from their origins to their destinations, is assumed. Each commuter chooses a path of minimal "disutility", a measure of discomfort associated with the use of a path and which takes into account fixed costs and tolls. A deterministic modelling of commuter behaviour  is mostly  found in the literature, according to which positive flow is only assigned to \og shortest\fg\: paths. Even though the determinist pricing model is amenable to global optimization by the use of enumeration techniques, it has often been criticized for its lack of realism. In this thesis, we consider a probabilistic extension of this model involving a logit dicrete choice model. This more realistic model is non-linear and non-concave, but  still possesses strong combinatorial features.  Our analysis  spans  three separate articles. In the first we tackle the problem from a theoretical perspective for the case of a single origin-destination pair and  develop a first order analysis that exploits the logit assignment  analytical properties. We show the validity of   simplification rules to the network topology which  yield  a reduction in the problem dimensionality.  This enables us to establish the problem's unimodality    for a wide class of topologies. We also establish a parallel with the  product-line pricing problem, for which we generalize some of our results.  In our second article, we address the problem from a numerical point of view for the case where multiple origin-destination pairs are present. We work out algorithms that exploit both local information and the pricing problem specific combinatorial features.   We provide theoretical results which put in perspective the deterministic and probabilistic models, as well as numerical evidence  according to which  a very simple  combinatorial approximation can lead to the best solutions. Also, our experiments clearly indicate that under any reasonable setting, the logit pricing problem is much smoother, and admits less optima then its deterministic counterpart.    The third article is concerned with an extension  to an heterogeneous demand  resulting from  a mixed-logit discrete choice model. Commuter price sensitivity is assumed  random and the corresponding revenue expression admits no closed form expression. We devise  nonlinear and combinatorial approximation schemes for its evaluation and optimization, which allow us to obtain quasi-optimal solutions. Numerical experiments here indicate that the most realistic model yields the best solution, independently of how well the model can actually be solved.  We finally illustrate how the output  of the model can be used for economic purposes by evaluating the contributions to the revenue of various commuter groups.

Keyphrases: conception de réseau, modèles de choix discrets, programmation bi-niveau, optimisation combinatoire, optimisation non linéaire, logit, network design, discrete choice models, mixed-logit, bilevel programming, combinatorial optimization, nonlinear optimization, logit