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.


  • English

Media Info

Subject/Index Terms

Filing Info

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