ERA

Download the full-sized PDF of Application of ILP-based Heuristic and Dantzig-Wolfe Decomposition to Solve the Multi-period Survivable Network Augmentation ProblemDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R39P2WB7X

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Graduate Studies and Research, Faculty of

Collections

This file is in the following collections:

Theses and Dissertations

Application of ILP-based Heuristic and Dantzig-Wolfe Decomposition to Solve the Multi-period Survivable Network Augmentation Problem Open Access

Descriptions

Other title
Subject/Keyword
Multi-period network planning
Integer linear programming
Shared backup path protection
Type of item
Thesis
Degree grantor
University of Alberta
Author or creator
Wang, Yali
Supervisor and department
Doucette, John (Department of Mechanical Engineering)
Examining committee member and department
Zuo, Ming (Department of Mechanical Engineering)
Tian, Zhigang (Department of Mechanical Engineering)
Doucette, John (Department of Mechanical Engineering)
Department
Department of Mechanical Engineering
Specialization
Engineering Management
Date accepted
2016-07-07T10:45:46Z
Graduation date
2016-06:Fall 2016
Degree
Master of Science
Degree level
Master's
Abstract
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.
Language
English
DOI
doi:10.7939/R39P2WB7X
Rights
This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for the purpose of private, scholarly or scientific research. 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.
Citation for previous publication
Y. Wang, J. Doucette, “ILP-based Heuristic Method for the Multi-period Survivable Network Augmentation Problem,” Reliable Network Design and Modeling (RNDM 2016), accepted: 17-June, 2016.

File Details

Date Uploaded
Date Modified
2016-07-07T16:45:47.610+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 1368443
Last modified: 2016:11:16 16:15:00-07:00
Filename: Wang_Yali_201607_M.Sc..pdf
Original checksum: 0641d60c2762ed4ede26379997985500
Well formed: true
Valid: true
File title: Microsoft Word - Yali Wang-M.Sc. thesis-final-Jun29 -new
File author: xihui2
Page count: 134
Activity of users you follow
User Activity Date