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.