Séminaire conjoint CRT-Chaire de recherche du Canada en distributique-Chaire de recherche du Canada en logistique et en transport

TITRE : A Polyhedral Study of the Network Pricing Problem with Connected Toll Arcs

CONFÉRENCIÈRE : Géraldine Heilporn, DIRO, Université de Montréal

DATE et ENDROIT : 23 avril, 10h30, salle 5441, Pavillon André-Aisenstadt, Campus de l’Université de Montréal

RESPONSABLE : Gilbert Laporte (514-343-6143)

RÉSUMÉ : Consider the tarification problem of maximizing the revenue generated by tolls set on a subset of arcs of a transportation network, where origin-destination flows (commodities) are assigned to shortest paths with respect to the sum of tolls and initial costs. This talk is concerned with a particular case of the above problem, in which all toll arcs are connected and constitute a path. Further, in order to allow for economies of scale, a complete toll subgraph is considered, where each arc corresponds to a subpath. Two variants of this problem are studied, with or without specific constraints linking together the tolls on the arcs. This problem is modelled as a linear mixed integer program, and is proved to be NP-complete. Next, several kinds of valid inequalities are proposed, which strengthen some constraints of the initial model. Their efficiency is first shown theoretically, as those are facet defining for the restricted two-commodity problem. Also, we prove that some of the valid inequalities proposed, together with several constraints of the linear program, give 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 this talk and a more classical design and pricing problem in economics.