Computational benchmarking of exact methods for the bilevel discrete network design problem

The discrete network design problem (DNDP) is a well-studied bilevel optimization problem in transportation. The goal of the DNDP is to identify the optimal set of candidate links (or projects) to be added to the network while accounting for users’ reaction as governed by a traffic equilibrium. Several approaches have been proposed to solve the DNDP exactly using single-level, mixed-integer programming reformulations, linear approximations of link travel time functions, relaxations and decompositions. To date, the largest DNDP instances solved to optimality remain of small scale and existing algorithms are no match to solve realistic problem instances involving large numbers of candidate projects. In this work, the author examines the literature on exact methodologies for the DNDP and attempts to categorize the main approaches employed. The author introduces a new set of benchmarking instances for the DNDP and implements three solution methods to compare computational performance and outline potential directions for improvement. For reproducibility purposes and to promote further research on this challenging bilevel optimization problem, all implementation codes and instance data are provided in a publicly available repository.

• Record URL:
  https://doi.org/10.1016/j.trpro.2020.03.067
• Record URL:
  http://www.sciencedirect.com/science/article/pii/S2352146520302465
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/issn/23521465
• Supplemental Notes:
  • © 2020 David Rey. Published by Elsevier B.V. Abstract reprinted with permission of Elsevier.
• Authors:
  • Rey, David
• Conference:
  • 22nd EURO Working Group on Transportation Meeting, EWGT 2019
  • Location: Barcelona , Spain
  • Date: 2019-9-18 to 2019-9-20
• Publication Date: 2020

Language

• English

Media Info

• Media Type: Web
• Features: References; Tables;
• Pagination: pp 11-18
• Serial:
  • Transportation Research Procedia
  • Volume: 47
  • Issue Number: 0
  • Publisher: Elsevier
  • ISSN: 2352-1465
  • Serial URL: http://www.sciencedirect.com/science/journal/23521465/
• Publication flags:

  Open Access (libre)

Subject/Index Terms

• TRT Terms: Algorithms; Optimization; Traffic assignment; Traffic equilibrium; Travel time
• Subject Areas: Highways; Operations and Traffic Management;

Filing Info

• Accession Number: 01743431
• Record Type: Publication
• Files: TRIS
• Created Date: Jun 22 2020 12:02PM