Details

Network pricing problems: complexity, polyhedral study and solution approaches/Problèmes de tarification de réseaux: complexité, étude polyédrale et méthodes de résolution

by Heilporn, Géraldine

Abstract (Summary)
Consider the problem of maximizing the revenue generated by tolls set on a subset of arcs of a transportation network, where origin-destination ?ows (commodities) are assigned to shortest paths with respect to the sum of tolls and initial costs. This thesis is concerned with a particular case of the above problem, in which all toll arcs are connected and constitute a path, as occurs on highways. Further, as toll levels are usually computed using the highway entry and exit points, a complete toll subgraph is considered, where each toll arc corresponds to a toll subpath. Two variants of the problem are studied, with or without speci?c constraints linking together the tolls on the arcs. The problem is modelled as a linear mixed integer program, and proved to be NP-hard. Next, several classes of valid inequalities are proposed, which strengthen important constraints of the initial model. Their efficiency is ?rst shown theoretically, as these are facet de?ning for the restricted one and two commodity problems. Also, we prove that some of the valid inequalities proposed, together with several constraints of the linear program, provide a complete description of the convex hull of feasible solutions for a single commodity problem. Numerical tests have also been conducted, and highlight the real efficiency of the valid inequalities for the multi-commodity case. Finally, we point out the links between the problem studied in the thesis and a more classical design and pricing problem in economics. / Considérons le problème qui consiste à maximiser les pro?ts issus de la tari?cation d’un sous-ensemble d’arcs d’un réseau de transport, où les ?ots origine-destination (produits) sont affectés aux plus courts chemins par rapport aux tarifs et aux coûts initiaux. Cette thèse porte sur une structure de réseau particulière du problème ci-dessus, dans laquelle tous les arcs tarifables sont connectés et forment un chemin, comme c’est le cas sur une autoroute. Étant donné que les tarifs sont habituellement déterminés selon les points d’entrée et de sortie sur l’autoroute, nous considérons un sous-graphe tarifable complet, où chaque arc correspond en réalité à un sous-chemin. Deux variantes de ce problème sont étudiées, avec ou sans contraintes spéci?ques reliant les niveaux de tarifs sur les arcs. Ce problème peut être modélisé comme un programme linéaire mixte entier. Nous prouvons qu’il est NP-difficile. Plusieurs familles d’inégalités valides sont ensuite proposées, celles-ci renforçant certaines contraintes du modèle initial. Leur efficacité est d’abord démontrée de manière théorique, puisqu’il s’agit de facettes des problèmes restreints à un ou deux produits. Certaines des inégalités valides proposées, ainsi que plusieurs contraintes du modèle initial, permettent aussi de donner une description complète de l’enveloppe convexe des solutions réalisables d’un problème restreint à un seul produit. Des tests numériques ont également été menés, et mettent en évidence l’efficacité réelle des inégalités valides pour le problème général à plusieurs produits. En?n, nous soulignons les liens entre le problème de tari?cation de réseau étudié dans cette thèse et un problème plus classique de tari?cation de produits en gestion.
Bibliographical Information:

Advisor:Labbé, Martine; Doignon, Jean-Paul; Fiorini, Samuel; Fortz, Bernard; Marcotte, Patrice; Savard, Gilles; Gendron, Bernard; Gendreau, Michel; van Hoesel, Stan

School:Université libre de Bruxelles

School Location:Belgium

Source Type:Master's Thesis

Keywords:programmation mixte entière optimisation combinatoire network pricing combinatorial optimization tari?cation d mixed integer programming

ISBN:

Date of Publication:10/14/2008

© 2009 OpenThesis.org. All Rights Reserved.