Back to Search
Start Over
Computational benchmarking of exact methods for the bilevel discrete network design problem
- Source :
- Transportation Research Procedia, Transportation Research Procedia, Elsevier, 2020, 47, pp.11-18. ⟨10.1016/j.trpro.2020.03.067⟩
- Publication Year :
- 2020
- Publisher :
- HAL CCSD, 2020.
-
Abstract
- 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, we examine the literature on exact methodologies for the DNDP and attempt to categorize the main approaches employed. We introduce a new set of benchmarking instances for the DNDP and implement 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.
- Subjects :
- 050210 logistics & transportation
Mathematical optimization
Computer science
05 social sciences
0211 other engineering and technologies
Scale (descriptive set theory)
02 engineering and technology
Benchmarking
Bilevel optimization
[SHS]Humanities and Social Sciences
Set (abstract data type)
Network planning and design
Travel time
021105 building & construction
0502 economics and business
Traffic equilibrium
Subjects
Details
- Language :
- English
- ISSN :
- 23521465
- Database :
- OpenAIRE
- Journal :
- Transportation Research Procedia, Transportation Research Procedia, Elsevier, 2020, 47, pp.11-18. ⟨10.1016/j.trpro.2020.03.067⟩
- Accession number :
- edsair.doi.dedup.....3e9b36489ec1545e537fcf1e41fbc1ef