Problème de tarification sur un réseau avec demande élastique et contraintes de capacité

Plusieurs extensions du problème de tarification sur un réseau introduit par Labbé et al. (1998) (modélisé sous la forme d'un programme à deux niveaux) ont été étudiées mais aucun, à notre connaissance, ne considère la demande élastique, qui est le sujet de cette thèse. Plus précisément, ne nous considérons le problème de maximisation des revenus générés par les tarifs imposés sur un sous-ensemble d'arcs d'un réseau de transport multi-produits, en tenant compte que la demande est affectée aux chemins de plus petit coût et dépend du coût total (coût fixe + tarif) de ces chemins, et que certains arcs du réseau ont une capacité finie. Cette thèse porte sur une étude de modélisation suivie d'une mise en œuvre d'algorithmes et puis d'une étude numérique du problème de tarification sur un réseau avec demande élastique et contraintes de capacité à partir d'une étude approfondie des aspects théoriques. Dans la première partie, nous étudions le problème de tarification sur un réseau avec demande élastique. Nous proposons, lorsque la demande est linéaire, trois formulations quadratiques en variables mixtes (MIP). Puis, nous montrons qu'il existe des cas où le problème est polynomial. Lorsque la demande est non linéaire, nous développons deux méthodes exactes basées sur une surapproximation des fonctions non linéaires de la fonction objectif d'un programme non linéaire en variables mixtes. Les tests numériques mettent en évidence l'efficacité de l'une des méthodes exactes sur les instances de petite et moyenne taille. Puis, nous développons deux heuristiques basées sur une méthode de région de confiance. Ces heuristiques fournissent des solutions situées en moyenne à 1% de la borne supérieure de la meilleure méthode exacte avec des temps de calcul raisonnable sur des instances de grande taille. L'analyse de sensibilité montre que la difficulté de résolution du problème diminue lorsque l'élasticité de la demande augmente. Dans la deuxième partie, nous étudions le problème de tarification sur un réseau avec demande élastique où nous incorporons les capacités explicites sur les arcs du réseau. Pour ce faire, nous commençons par prouver que les contraintes de capacité peuvent être déplacées au premier niveau. Il s'en suit que les coûts des chemins utilisés, pour un produit donné, sont tous égaux. Ainsi, le problème du second niveau se réduit à un problème de plus court chemin par produit comme dans le cas du problème sans contraintes de capacité. La technique utilisée pour reformuler le problème sans contraintes de capacité en un programme à un niveau est utilisée pour obtenir un programme à un niveau. Par la suite, les méthodes développées dans le cas du problème sans contraintes de capacité de la première partie sont adaptées pour résoudre le problème avec contraintes de capacité. Ainsi, lorsque la demande est linéaire, un programme quadratique en variables mixtes est développé. Dans le cas non linéaire, deux méthodes exactes sont développées et les tests numériques montrent l'efficacité de l'une d'elles sur des instances de petite taille. Une heuristique basée sur une méthode de région de confiance est développée et ses solutions sont situées à 2% de la borne supérieure sur les instances de taille moyenne et grande. Nous remarquons que la difficulté de résolution du problème augmente avec les valeurs des capacités sur les arcs. L'analyse de sensibilité montre que l'élasticité de la demande n'a pas d'influence sur la résolution du problème dans le cas linéaire tandis qu'elle augmente lorsque l'élasticité augmente dans le cas non linéaire.

Abstract

Several extensions of the network pricing problem introduced by Labbé et al. (1998) (modeled as a bilevel program) have been studied but none, to the best of our knowledge, involves elastic demand, which is the topic of this thesis. More specifically, we consider the problem of maximizing the revenue raised from tolls set on a subset of arcs of a multi-commodity transportation network, taking into account that demand is assigned to cheapest paths, and is actually dependent on the total cost (initial cost of carrying the products + toll) of these paths and some arcs of network have finite capacity. This thesis is concerned with a modeling study followed by an implementation of algorithms and then a numerical study of the network pricing problem with elastic demand and capacity constraints, from the in-depth study of theoretical aspects. In the first part, we study network pricing problem with elastic demand. In the case of linear demand-cost relationship, we propose three mixed integer (MIP) quadratic formulations. Then, we show that special cases can be solved in polynomial time. In the case of nonlinear demand functions, we develop two exact methods based on an over-estimation of nonlinear functions in the objective function of a non linear mixed integer program. Numerical tests highlight the efficiency of one of the exact methods on small and medium-size instances. Then, we design two heuristics based on a trust-region approach. Heuristics provide solutions whose objective lie within $1\%$ of the upper bound of the best exact method with reasonable Cpu times, even on large instances. Indeed, sensibility analysis show that the difficulty of resolution of the problem decreases with the value of the cost elasticity of demand. In the second part, we deal with the network pricing problem with elastic demand where we incorporate explicit capacities on arcs of the network. First, we prove that capacity constraints can be moved to the first level. It follows that the path used, for each product, have the same cost. Then, the second level problem reduces to a set of independent shortest-paths problem as in the case of the problem without capacity constraints. The technique used to remodel the problem without capacity constraints as one level program is used to get a one level program. Thereafter, the methods developed for the problem without capacity constraints in the first part is adapted to solve the problem with capacity constraints. Then, in the case of linear demand, we propose a mixed integer (MIP) quadratic program. In the case of non linear demand, we develop two exact methods and numerical tests show the efficiency of one of the exact methods on small-size instances. A heuristic based on a trust-region approach is also designed and its solutions lie within 2% of the upper bound on medium and large-size instances. We remark that larger the value of capacity on arcs is, the more difficult the resolution of the problem is. Sensibility analysis shows that elasticity has no influence on the resolution of the problem in the linear case while it increases with elasticity in the non linear case.