TY - JOUR
T1 - A Dantzig-Wolfe Decomposition Based Heuristic Scheme for Bi-level Dynamic Network Design Problem
AU - Lin, Dung Ying
AU - Karoonsoontawong, Ampol
AU - Waller, S. Travis
N1 - Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.
PY - 2011/3
Y1 - 2011/3
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=79953063896&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79953063896&partnerID=8YFLogxK
U2 - 10.1007/s11067-008-9093-4
DO - 10.1007/s11067-008-9093-4
M3 - Article
AN - SCOPUS:79953063896
VL - 11
SP - 101
EP - 126
JO - Networks and Spatial Economics
JF - Networks and Spatial Economics
SN - 1566-113X
IS - 1
ER -