A dual variable approximation-based descent method for a bi-level continuous dynamic network design problem

Dung-Ying Lin

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)


The transportation network design problem (NDP) considers modifying network topology or parameters, such as capacity, to optimize system performance by taking into account the selfish routing behavior of road users. The nature of the problem naturally lends itself to a bi-level formulation of a problem that represents a static case of a Stackelberg game. The NDP is complex because users' individual objectives do not necessarily align with system-wide objectives; thus, it is difficult to determine the optimal allocation of limited resources. To solve the bi-level dynamic NDP, this study develops a dual variable approximation-based heuristic, which identifies the system-wide gradient as a descent direction, and designs an iterative solution framework. Descent direction-based approaches designed to solve bi-level programming problems typically suffer from non-differentiability, which can hamper the solution process. The proposed method addresses this issue by approximating the descent direction with dual variables that correspond to cell transmission model constraints and using the constructed rational direction to iteratively decrease the upper-level objective while maintaining the feasibility of the lower-level program. The proposed method was empirically applied to three networks of various sizes. The results obtained from this empirical solution were compared with the results from an exact Kth-best algorithm and a genetic algorithm. The promising results demonstrate the efficacy and efficiency of the proposed descent method.

Original languageEnglish
Pages (from-to)581-594
Number of pages14
JournalComputer-Aided Civil and Infrastructure Engineering
Issue number8
Publication statusPublished - 2011 Nov 1

All Science Journal Classification (ASJC) codes

  • Civil and Structural Engineering
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Computational Theory and Mathematics


Dive into the research topics of 'A dual variable approximation-based descent method for a bi-level continuous dynamic network design problem'. Together they form a unique fingerprint.

Cite this