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

Dung-Ying Lin

研究成果: Article同行評審

17 引文 斯高帕斯(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.

頁(從 - 到)581-594
期刊Computer-Aided Civil and Infrastructure Engineering
出版狀態Published - 2011 11月 1

All Science Journal Classification (ASJC) codes

  • 土木與結構工程
  • 電腦科學應用
  • 電腦繪圖與電腦輔助設計
  • 計算機理論與數學


深入研究「A dual variable approximation-based descent method for a bi-level continuous dynamic network design problem」主題。共同形成了獨特的指紋。