A Dantzig-Wolfe Decomposition Based Heuristic Scheme for Bi-level Dynamic Network Design Problem
Research output: Contribution to journal › Research article › Contributed › peer-review
Contributors
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.
Details
Original language | English |
---|---|
Pages (from-to) | 101-126 |
Number of pages | 26 |
Journal | Networks and Spatial Economics |
Volume | 11 |
Issue number | 1 |
Publication status | Published - Mar 2011 |
Peer-reviewed | Yes |
Externally published | Yes |
External IDs
ORCID | /0000-0002-2939-2090/work/141543904 |
---|
Keywords
ASJC Scopus subject areas
Keywords
- Cell transmission model, Dantzig-Wolfe decomposition, Dual variables approximation, Dynamic network design