A Bilevel Model for Toll Optimization on a Multicommodity Transportation Network

Luce Brotcorne
Luce Brotcorne
CRT, SMG, and LAMIH-ROI, Le Mont Houy, 59313 Valenciennes Cedex 9, France
Search for more papers by this author
,
Martine Labbé
Martine Labbé
ISRO and SMG, Université Libre de Bruxelles, CP 210/01, Boulevard du Triomphe, B-1050, Brussels, Belgium
Search for more papers by this author
,
Patrice Marcotte
Patrice Marcotte
CRT and DIRO, Université de Montréal, C.P. 6128, Succursale Centre-Ville, Montréal, Canada H3C 3J7
Search for more papers by this author
,
Gilles Savard
Gilles Savard
GERAD and MAGI, École Polytechnique de Montréal, C.P. 6079, Succursale Centre-Ville, Montréal, Canada H3C 3A7
Search for more papers by this author

Luce Brotcorne

CRT, SMG, and LAMIH-ROI, Le Mont Houy, 59313 Valenciennes Cedex 9, France

Search for more papers by this author

Martine Labbé

ISRO and SMG, Université Libre de Bruxelles, CP 210/01, Boulevard du Triomphe, B-1050, Brussels, Belgium

Search for more papers by this author

Patrice Marcotte

CRT and DIRO, Université de Montréal, C.P. 6128, Succursale Centre-Ville, Montréal, Canada H3C 3J7

Search for more papers by this author

Gilles Savard

GERAD and MAGI, École Polytechnique de Montréal, C.P. 6079, Succursale Centre-Ville, Montréal, Canada H3C 3A7

Search for more papers by this author

Published Online:1 Nov 2001https://doi.org/10.1287/trsc.35.4.345.10433

Abstract

We consider the problem of determining a set of optimal tolls on the arcs of a multicommodity transportation network. The problem is formulated as a bilevel mathematical program where the upper level consists in a firm that raises revenues from tolls set on arcs of the network, while the lower level is represented by a group of users travelling on shortest paths with respect to a generalized travel cost.

Cited by
- Optimizing post-disaster road restoration with reinforcement learning: A traveler-behavior-aware approach
  Reliability Engineering & System Safety, Vol. 273
- Adaptive Transfer Bilevel Evolutionary Optimization Algorithm Based on Gradient Diffusion
  Advances in Applied Mathematics, Vol. 15, No. 03
- A Review of Bilevel Optimization Methods, Emerging Applications, and Recent Advancements
  16 June 2026
- A bi-level mixed integer non-linear programming model to solve the billboard location problem in cities
  17 April 2025 | International Journal of Construction Management, Vol. 25, No. 16
- Railway pricing for automobile transport based on discrete choice model and cost accounting
  Research in Transportation Business & Management, Vol. 59
- Plan Your System and Price for Free: Fast Algorithms for Multimodal Transit Operations
  Siddhartha Banerjee; ,
  Chamsi Hssaine; ,
  Qi Luo; ,
  Samitha Samaranayake
  25 October 2024 | Transportation Science, Vol. 59, No. 1
- Geometric, Dynamic, and Stochastic Analysis of Wardrop-Schur Optimal Transport Networks: Theory and Applications, and Open Problems
  6 December 2025
- δ -perturbation of bilevel optimization problems: An error bound analysis
  Operations Research Perspectives, Vol. 13
- A Multiform Evolutionary Search Paradigm for Bilevel Multiobjective Optimization
  IEEE Transactions on Evolutionary Computation, Vol. 28, No. 6
- Strategic Traffic Management in Mixed Traffic Road Networks: A Methodological Approach Integrating Game Theory, Bilevel Optimization, and C-ITS
  16 December 2024 | Future Transportation, Vol. 4, No. 4
- Dynamic Usage Allocation and Pricing for Curb Space Operation
  Jisoon Lim,
  Neda Masoud
  6 June 2024 | Transportation Science, Vol. 58, No. 6
- Asymmetry in the complexity of the multi-commodity network pricing problem
  3 January 2024 | Mathematical Programming, Vol. 208, No. 1-2
- Modeling 5G shared base station planning problem using an evolutionary bi-level optimization algorithm
  Applied Soft Computing, Vol. 165
- The exactness of the ℓ1 penalty function for a class of mathematical programs with generalized complementarity constraints
  Fundamental Research, Vol. 4, No. 6
- Digital Transformation in Transportation Systems: Strategic User Behavior and System Efficiency
  Haripriya Pulyassary,
  Manxi Wu
  17 October 2024
- Allocation problem in cross-platform ride-hail integration
  Transportation Research Part B: Methodological, Vol. 188
- Single-leader multi-follower games for the regulation of two-sided mobility-as-a-service markets
  European Journal of Operational Research, Vol. 317, No. 3
- Unlocking efficiency: End-to-end optimization learning for recurrent facility operational planning
  Transportation Research Part E: Logistics and Transportation Review, Vol. 189
- On the Interplay Between Self-Driving Cars and Public Transportation
  IEEE Transactions on Control of Network Systems, Vol. 11, No. 3
- Evolutionary Bilevel Optimization: Algorithms and Applications
  1 August 2024
- Bilevel Optimization: Applications, Models and Solution Approaches
  29 December 2024
- Metaheuristics for bilevel optimization: A comprehensive review
  Computers & Operations Research, Vol. 161
- Integrated multimodal freight service network design and pricing with a competing service integrator and heterogeneous shipper classes
  Transportation Research Part E: Logistics and Transportation Review, Vol. 179
- Bilevel Programming for Manufacturers Operating in an Omnichannel Retailing Environment
  IEEE Transactions on Engineering Management, Vol. 70, No. 11
- Linkage Problem in Location Optimization of Dedicated Bus Lanes on a Network
  25 January 2023 | Transportation Research Record: Journal of the Transportation Research Board, Vol. 2677, No. 6
- Capturing Travel Mode Adoption in Designing On-Demand Multimodal Transit Systems
  Beste Basciftci,
  Pascal Van Hentenryck
  6 December 2022 | Transportation Science, Vol. 57, No. 2
- Mixed integer bilevel optimization with a k-optimal follower: a hierarchy of bounds
  8 December 2022 | Mathematical Programming Computation, Vol. 15, No. 1
- Bayesian Optimization with Multi-objective Acquisition Function for Bilevel Problems
  23 February 2023
- Hierarchical governance in invasive species survey campaigns
  Ecological Economics, Vol. 201
- Solving Bilevel Optimization Problems Using Kriging Approximations
  IEEE Transactions on Cybernetics, Vol. 52, No. 10
- A Catalog of Formulations for the Network Pricing Problem
  Quang Minh Bui,
  Bernard Gendron,
  Margarida Carvalho
  19 May 2022 | INFORMS Journal on Computing, Vol. 34, No. 5
- An iterative two-stage heuristic algorithm for a bilevel service network design and pricing model
  European Journal of Operational Research, Vol. 300, No. 2
- Data-driven optimization: A flexible route pricing method for Non-Truck Operating Common Carriers
  Transportation Research Part E: Logistics and Transportation Review, Vol. 161
- A Multifidelity Approach for Bilevel Optimization With Limited Computing Budget
  IEEE Transactions on Evolutionary Computation, Vol. 26, No. 2
- A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games
  Claudio Contardo,
  Jorge A. Sefair
  18 October 2021 | INFORMS Journal on Computing, Vol. 34, No. 2
- The multicommodity network flow problem: state of the art classification, applications, and solution methods
  23 April 2020 | Operational Research, Vol. 22, No. 1
- Transfer Learning-Based Parallel Evolutionary Algorithm Framework for Bilevel Optimization
  IEEE Transactions on Evolutionary Computation, Vol. 26, No. 1
- Geofence planning for electric scooters
  Transportation Research Part D: Transport and Environment, Vol. 102
- Optimal subsidy scheme design for promoting intermodal freight transport
  Transportation Research Part E: Logistics and Transportation Review, Vol. 157
- A bilevel game model for ascertaining competitive target prices for a buyer in negotiation with multiple suppliers
  7 February 2022 | RAIRO - Operations Research, Vol. 56, No. 1
- Modeling 5g Shared Base Station Planning Problemusing an Evolutionary Bi-Level Optimizationalgorithm
  SSRN Electronic Journal, Vol. 21
- Comprehensive Evaluation Model and Empirical Research on Railway Freight Rates in a Competitive Environment
  30 August 2021 | Transportation Research Record: Journal of the Transportation Research Board, Vol. 2675, No. 12
- Optimal governmental incentives for biomass cofiring to reduce emissions in the short-term
  12 February 2020 | IISE Transactions, Vol. 53, No. 8
- Transfer Learning Based Evolutionary Algorithm for Bi-level Optimization Problems
- A multi-commodity network model for optimal quantum reversible circuit synthesis
  22 June 2021 | PLOS ONE, Vol. 16, No. 6
- Optimal Operation of Transient Gas Transport Networks
  16 February 2021 | Optimization and Engineering, Vol. 22, No. 2
- An enhanced branch-and-bound algorithm for bilevel integer linear programming
  European Journal of Operational Research, Vol. 291, No. 2
- Bilevel optimization of conservation practices for agricultural production
  Journal of Cleaner Production, Vol. 300
- Balancing Large-Scale Wildlife Protection and Forest Management Goals with a Game-Theoretic Approach
  19 June 2021 | Forests, Vol. 12, No. 6
- Determining Optimum Toll Charges for Freight Vehicles Considering Multi-Stakeholder Objectives in Urban Conditions
  Transportation Journal, Vol. 60, No. 2
- Computing Feasible Points of Bilevel Problems with a Penalty Alternating Direction Method
  Thomas Kleinert,
  Martin Schmidt
  22 June 2020 | INFORMS Journal on Computing, Vol. 33, No. 1
- Bilevel Network Design
  9 December 2020
- A Survey on Mixed-Integer Programming Techniques in Bilevel Optimization
  EURO Journal on Computational Optimization, Vol. 9
- Plan Your System and Price for Free: Fast Algorithms for Multimodal Transit Operations
  SSRN Electronic Journal, Vol. 138
- Investigating the future supply distribution of industrial grade wood pellets in the global bioenergy market
  8 February 2018 | Biofuels, Vol. 11, No. 8
- On pricing-based equilibrium for network expansion planning. A multi-period bilevel approach under uncertainty
  European Journal of Operational Research, Vol. 287, No. 1
- A Practical Scheme to Compute the Pessimistic Bilevel Optimization Problem
  Bo Zeng
  12 May 2020 | INFORMS Journal on Computing, Vol. 32, No. 4
- A dual toll policy for maintaining risk equity in hazardous materials transportation with fuzzy incident rate
  International Journal of Production Economics, Vol. 227
- Parallel Differential Evolution Algorithms for Stackelberg-Nash Bilevel Optimization Problems
- A surrogate-assisted metaheuristic for bilevel optimization
  26 June 2020
- A Bilevel Programming Model for a Cohesive Decision-Making on Strategic Pricing and Production Distribution Planning for a Small-Scale Supplier
  28 May 2020 | International Game Theory Review, Vol. 22, No. 02
- Bilevel optimization based on iterative approximation of multiple mappings
  24 September 2019 | Journal of Heuristics, Vol. 26, No. 2
- Stackelberg Game Theory-Based Optimization Model for Design of Payment Mechanism in Performance-Based PPPs
  Journal of Construction Engineering and Management, Vol. 146, No. 4
- Tackling Large-Scale and Combinatorial Bi-Level Problems With a Genetic Programming Hyper-Heuristic
  IEEE Transactions on Evolutionary Computation, Vol. 24, No. 1
- Bilevel Optimization: Theory, Algorithms, Applications and a Bibliography
  24 November 2020
- Bilevel Optimization for On-Demand Multimodal Transit Systems
  19 September 2020
- Differential Evolution Algorithms for Solving Bilevel Optimization Problems Using Computational Clusters
- A Bilevel Model for Network Design and Pricing Based on a Level-of-Service Assessment
  Christine Tawfik,
  Sabine Limbourg
  23 October 2019 | Transportation Science, Vol. 53, No. 6
- A nested particle swarm algorithm based on sphere mutation to solve bi-level optimization
  8 March 2019 | Soft Computing, Vol. 23, No. 21
- When is it beneficial to provide freelance suppliers with choice? A hierarchical approach for peer-to-peer logistics platforms
  Transportation Research Part B: Methodological, Vol. 126
- A Julia package for bilevel optimization problems
  Journal of Open Source Software, Vol. 4, No. 39
- A New Bi-level PSO Algorithm based on Dynamic Constraint Processing and Approximate Navigation
- A Metaheuristic for Bilevel Optimization Using Tykhonov Regularization and the Quasi-Newton Method
- Traffic equilibrium with a continuously distributed bound on travel weights: the rise of range anxiety and mental account
  1 August 2018 | Annals of Operations Research, Vol. 273, No. 1-2
- Using Karush-Kuhn-Tucker proximity measure for solving bilevel optimization problems
  Swarm and Evolutionary Computation, Vol. 44
- A novel parameterised approximation approach based on bi-level programming for integration transport scheduling problem
  28 January 2018 | Journal of the Operational Research Society, Vol. 70, No. 2
- An efficient hybrid differential evolutionary algorithm for zbilevel optimisation problems
  9 September 2019 | Economic Research-Ekonomska Istraživanja, Vol. 32, No. 1
- Exact Solution of the Evasive Flow Capturing Problem
  Okan Arslan,
  Ola Jabali,
  Gilbert Laporte
  13 November 2018 | Operations Research, Vol. 66, No. 6
- A Physics-Inspired Algorithm for Bilevel optimization
- The Backpropagation Artificial Neural Network Based on Elite Particle Swam Optimization Algorithm for Stochastic Linear Bilevel Programming Problem
  Mathematical Problems in Engineering, Vol. 2018
- C-MPDM: Continuously-Parameterized Risk-Aware MPDM by Quickly Discovering Contextual Policies
- A reducibility method for the weak linear bilevel programming problems and a case study in principal-agent
  Information Sciences, Vol. 454-455
- Bilevel Optimization Based on Kriging Approximations of Lower Level Optimal Value Function
- A Competitive Approach for Bi-Level Co-Evolution
- A Review on Bilevel Optimization: From Classical to Evolutionary Approaches and Applications
  IEEE Transactions on Evolutionary Computation, Vol. 22, No. 2
- The Global Search Theory Approach to the Bilevel Pricing Problem in Telecommunication Networks
  25 August 2018
- A Hierarchical Approach to Enabling Supplier Choice In On-Demand Platforms
  SSRN Electronic Journal, Vol. 39
- Network Pricing of Congestion-Free Networks: The Elastic and Linear Demand Case
  Aimé Kamgaing Kuiteing,
  Patrice Marcotte,
  Gilles Savard
  8 July 2016 | Transportation Science, Vol. 51, No. 3
- Bayesian optimization approach of general bi-level problems
  15 July 2017
- Handling practicalities in agricultural policy optimization for water quality improvements
  1 July 2017
- Solving a supply-chain management problem using a bilevel approach
  1 July 2017
- A Value-Function-Based Exact Approach for the Bilevel Mixed-Integer Programming Problem
  Leonardo Lozano,
  J. Cole Smith
  11 April 2017 | Operations Research, Vol. 65, No. 3
- Line planning with user-optimal route choice
  European Journal of Operational Research, Vol. 259, No. 2
- Evolutionary bilevel optimization using KKT proximity measure
- Bi-Level Optimization as a Tool for Implementation of Intelligent Transportation Systems
  26 June 2017 | Cybernetics and Information Technologies, Vol. 17, No. 2
- Evolutionary algorithm for bilevel optimization using approximations of the lower level optimal solution mapping
  European Journal of Operational Research, Vol. 257, No. 2
- Fare Evasion in Transit Networks
  José Correa,
  Tobias Harks,
  Vincent J. C. Kreuzen,
  Jannik Matuschke
  2 February 2017 | Operations Research, Vol. 65, No. 1
- Evolutionary Bilevel Optimization: An Introduction and Recent Advances
  10 August 2016
- Adaptivity in Network Interdiction
  4 October 2017
- Approximated set-valued mapping approach for handling multiobjective bilevel problems
  Computers & Operations Research, Vol. 77
- Multi objective optimization for UAV navigation equipment test table design
- Solving optimistic bilevel programs by iteratively approximating lower level optimal value function
- Handling inverse optimal control problems using evolutionary bilevel optimization
- An Extended Network Interdiction Problem for Optimal Toll Control
  Electronic Notes in Discrete Mathematics, Vol. 52
- Achieving an optimal trade-off between revenue and energy peak within a smart grid environment
  Renewable Energy, Vol. 91
- A heuristic algorithm solving bilevel toll optimization problems
  The International Journal of Logistics Management, Vol. 27, No. 1
- Bilevel programming and price setting problems
  22 September 2015 | Annals of Operations Research, Vol. 240, No. 1
- A Parameterised Complexity Analysis of Bi-level Optimisation with Evolutionary Algorithms
  Evolutionary Computation, Vol. 24, No. 1
- A bilevel formulation of the pediatric vaccine pricing problem
  European Journal of Operational Research, Vol. 248, No. 2
- Recursive pipelined genetic propagation for bilevel optimisation
- A Numerical Study of the Logit Network Pricing Problem
  François Gilbert,
  Patrice Marcotte,
  Gilles Savard
  5 January 2015 | Transportation Science, Vol. 49, No. 3
- Transportation policy formulation as a multi-objective bilevel optimization problem
- Incorporating data envelopment analysis solution methods into bilevel multi-objective optimization
- Towards Understanding Bilevel Multi-objective Optimization with Deterministic Lower Level Decisions
  18 March 2015
- Easier than We Thought - A Practical Scheme to Compute Pessimistic Bilevel Optimization Problem
  SSRN Electronic Journal, Vol. 21
- A microeconomic interpretation for the system optimal traffic assignment problem with nonadditive path cost
  19 September 2014 | Transportation Planning and Technology, Vol. 37, No. 8
- Determining the Reasonable Scale of a Toll Highway Network in China
  Journal of Transportation Engineering, Vol. 140, No. 10
- Test Problem Construction for Single-Objective Bilevel Optimization
  Evolutionary Computation, Vol. 22, No. 3
- An improved bilevel evolutionary algorithm based on Quadratic Approximations
- Computation of the optimal tolls on the traffic network
  European Journal of Operational Research, Vol. 235, No. 1
- Mixed-logit network pricing
  27 July 2013 | Computational Optimization and Applications, Vol. 57, No. 1
- Evolutionary bilevel optimization
  6 July 2013
- Risk-Sharing in Highway Concessions: Contractual Diversity in Portugal
  Journal of Professional Issues in Engineering Education and Practice, Vol. 139, No. 2
- Bilevel programming and price setting problems
  5 October 2012 | 4OR, Vol. 11, No. 1
- Risk-neutral second best toll pricing
  Transportation Research Part B: Methodological, Vol. 48
- The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs
  7 October 2011 | Journal of Combinatorial Optimization, Vol. 25, No. 1
- Using emission functions in modeling environmentally sustainable traffic assignment policies
  Journal of Industrial & Management Optimization, Vol. 9, No. 2
- A Tabu search algorithm for the network pricing problem
  Computers & Operations Research, Vol. 39, No. 11
- A Bilevel Approach for the Optimal Control of Flows Through a Network
  IEEE Systems Journal, Vol. 6, No. 3
- Integrated operations planning and revenue management for rail freight transportation
  Transportation Research Part B: Methodological, Vol. 46, No. 1
- Reverse auction with buyer–supplier negotiation using bi-level distributed programming
  European Journal of Operational Research, Vol. 211, No. 3
- An exact algorithm for the network pricing problem
  Discrete Optimization, Vol. 8, No. 2
- A Bilevel Optimization Model for Large Scale Highway Infrastructure Maintenance Inspection and Scheduling Following a Seismic Event
  16 November 2010
- A polyhedral study of the network pricing problem with connected toll arcs
  3 December 2009 | Networks, Vol. 55, No. 3
- A parallel between two classes of pricing problems in transportation and marketing
  30 October 2009 | Journal of Revenue and Pricing Management, Vol. 9, No. 1-2
- PRICING GEOMETRIC TRANSPORTATION NETWORKS
  20 November 2011 | International Journal of Computational Geometry & Applications, Vol. 19, No. 06
- Toll Policies for Mitigating Hazardous Materials Transport Risk
  Patrice Marcotte,
  Anne Mercier,
  Gilles Savard,
  Vedat Verter,
  15 August 2008 | Transportation Science, Vol. 43, No. 2
- A continuous optimization model for a joint problem of pricing and resource allocation
  28 April 2009 | RAIRO - Operations Research, Vol. 43, No. 2
- Bilevel Programming: The Montreal School
  18 January 2017 | INFOR: Information Systems and Operational Research, Vol. 46, No. 4
- Joint Design and Pricing on a Network
  Luce Brotcorne,
  Martine Labbé,
  Patrice Marcotte,
  Gilles Savard,
  1 October 2008 | Operations Research, Vol. 56, No. 5
- An overview of Stackelberg pricing in networks
  European Journal of Operational Research, Vol. 189, No. 3
- New formulations and valid inequalities for a bilevel pricing problem
  Operations Research Letters, Vol. 36, No. 2
- An overview of bilevel optimization
  20 April 2007 | Annals of Operations Research, Vol. 153, No. 1
- Tariff Optimization in Networks
  Mustapha Bouhtou,
  Stan van Hoesel,
  Anton F. van der Kraaij,
  Jean-Luc Lutton,
  20 July 2007 | INFORMS Journal on Computing, Vol. 19, No. 3
- Joint optimization of pricing and resource allocation in competitive telecommunications networks
  16 April 2007 | Networks, Vol. 50, No. 1
- Approximate Mechanisms for the Graphical TSP and Other Graph Traversal Problems
- Chapter 10 Traffic Equilibrium
- Pareto‐Improving Contracts for Express Package Delivery Services
  1 January 2007 | Production and Operations Management, Vol. 16, No. 1
- Pricing and Resource Allocation for Point-to-Point Telecommunication Services in a Competitive Market: A Bilevel Optimization Approach
- Path-based formulations of a bilevel toll setting problem
- A regularization method for ill-posed bilevel optimization problems
  1 July 2006 | RAIRO - Operations Research, Vol. 40, No. 1
- A BILEVEL APPROACH TO OPTIMAL PRICING
  IFAC Proceedings Volumes, Vol. 39, No. 3
- Medium-Term Pricing and Operations Planning in Intermodal Transportation
  Li Li,
  Sridhar Tayur,
  1 February 2005 | Transportation Science, Vol. 39, No. 1
- References
- References
  19 February 2016
- Modeling private highways in networks with entry–exit based toll charges
  Transportation Research Part B: Methodological, Vol. 38, No. 3
- Methods for Congestion Pricing in Dynamic Traffic Networks
  IFAC Proceedings Volumes, Vol. 36, No. 14

Volume 35, Issue 4

November 2001

Pages 345-438

Article Information

Metrics

Information

Received:May 01, 2000
Accepted:January 01, 2001
Published Online:November 01, 2001

Cite as

Luce Brotcorne, Martine Labbé, Patrice Marcotte, Gilles Savard, (2001) A Bilevel Model for Toll Optimization on a Multicommodity Transportation Network. Transportation Science 35(4):345-358.

https://doi.org/10.1287/trsc.35.4.345.10433

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

A Bilevel Model for Toll Optimization on a Multicommodity Transportation Network

Abstract

Volume 35, Issue 4

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News