A Dual Variable Approximation-Based Descent Method for a Bi-level Continuous Dynamic Network Design Problem

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.