A Dantzig-Wolfe Decomposition Based Heuristic Scheme for Bi-level Dynamic Network Design Problem |
| |
Authors: | Dung-Ying Lin Ampol Karoonsoontawong S Travis Waller |
| |
Affiliation: | (1) Department of Civil, Architectural & Environmental Engineering, University of Texas at Austin, 1 University Station, C1761, Austin, TX 78712, USA;(2) School of Transportation Engineering, Institute of Engineering, Suranaree University of Technology, 111 University Avenue, Muang, Nakhonratchasima 30000, Thailand |
| |
Abstract: | We present a heuristic to solve the NP-hard bi-level network design problem (NDP). The heuristic is developed based on the
Dantzig-Wolfe decomposition principle such that it iteratively solves a master problem and a pricing problem. The master problem
is the budget allocation linear program solved by CPLEX to determine the budget allocation and construct a modified cell transmission
network for the pricing problem. The pricing problem is the user-optimal dynamic traffic assignment (UODTA) solved by an existing
combinatorial algorithm. To facilitate the decomposition principle, we propose a backward connectivity algorithm and complementary
slackness procedures to efficiently approximate the required dual variables from the UODTA solution. The dual variables are
then employed to augment a new column in the master program in each iteration. The iterative process repeats until a stopping
criterion is met. Numerical experiments are conducted on two test networks. Encouraging results demonstrate the applicability
of the heuristic scheme on solving large-scale NDP. Though a single destination problem is considered in this paper, the proposed
scheme can be extended to solve multi-destination problems as well. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|