Optimization Online


A polyhedral study of the Network Pricing Problem with Connected Toll Arcs

Géraldine Heilporn (gheilpor***at***ulb.ac.be)
Martine Labbé (mlabbe***at***ulb.ac.be)
Patrice Marcotte (marcotte***at***iro.umontreal.ca)
Gilles Savard (gilles.savard***at***polymtl.ca)

Abstract: Consider the problem that consists in maximizing the revenue generated by tolls set on a subset of arcs of a transportation network, and where origin-destination flows are assigned to shortest paths with respect to the sum of tolls and initial costs. In this work, we address the instance where toll arcs must be connected, as occurs on highways. Our main results are concerned with the theoretical complexity of the problem and its variants, the design of valid inequalities, and facet description for the single commodity case.

Keywords: Network Pricing, Bilevel Programming, Combinatorial Optimization.

Category 1: Applications -- OR and Management Sciences (Yield Management )

Category 2: Integer Programming ((Mixed) Integer Linear Programming )

Citation: To appear in Networks.


Entry Submitted: 07/26/2007
Entry Accepted: 07/26/2007
Entry Last Modified: 10/01/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society