- 175 views
- 360 downloads
Application of ILP-based Heuristic and Dantzig-Wolfe Decomposition to Solve the Multi-period Survivable Network Augmentation Problem
-
- Author / Creator
- Wang, Yali
-
Multi-period planning is a cost efficient method for designing backbone networks and has been widely used for many years. To ensure the quality of the network service, network survivability has also become a critical requirement in network planning and design. The purpose of this thesis is to take multi-period incremental demands, network survivability and economies of scale into account, and to focus on the optimization of network topology design, working demand routing, and spare capacity allocation. To fulfill this objective, an integer linear programming (ILP) model for a multi-period survivable network augmentation (MPSNA) problem is developed, and the shared backup path protection (SBPP) mechanism is used. However, the MPSNA problem is very time-consuming to solve even for a very small network. To overcome this difficulty, a four-stage ILP-based heuristic method is developed to solve the MPSNA problem. In addition, the effectiveness of the implementation of the Dantzig-Wolfe decomposition for solving the MPSNA is also investigated.
-
- Subjects / Keywords
-
- Graduation date
- Fall 2016
-
- Type of Item
- Thesis
-
- Degree
- Master of Science
-
- License
- This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.