Decomposition methods for large-scale network expansion problems

Network expansion problems are a special class of multi-period network design problems in which arcs can be opened gradually in different time periods but can never be closed. Motivated by practical applications, the authors focus on cases where demand between origin-destination pairs expands over a discrete time horizon. Arc opening decisions are taken in every period, and once an arc is opened it can be used throughout the remaining horizon to route several commodities. The authors' model captures a key timing trade-off: the earlier an arc is opened, the more periods it can be used for, but its fixed cost is higher, since it accounts not only for construction but also for maintenance over the remaining horizon. An overview of practical applications indicates that this trade-off is relevant in various settings. For the capacitated variant, the authors develop an arc-based Lagrange relaxation, combined with local improvement heuristics. For uncapacitated problems, the authors develop four Benders decomposition formulations and show how taking advantage of the problem structure leads to enhanced algorithmic performance. The authors then utilize real-world and artificial networks to generate 1080 instances, with which the authors conduct a computational study. Their results demonstrate the efficiency of their algorithms. Notably, for uncapacitated problems the authors are able to solve instances with 2.5 million variables to optimality in less than two hours of computing time. Finally, the authors provide insights into how instance characteristics influence the multi-period structure of solutions.


  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01765197
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Dec 30 2020 3:14PM