Master Thesis Defense - February 2, 2015: Graph Partitioning of Transportation Networks under Disruption

Mona Ghavidelsyooki

Monday, February 2, 2015 at 11:00
Room EV011.119

You are invited to attend the following M.A.Sc. (Information Systems Security) thesis examination.

Examining Committee

Dr. C. Wang, Chair
Dr. A. Awasthi, Supervisor
Dr. M. Debbabi, CIISE Examiner
Dr. M. Chen, External Examiner (MIE)

Abstract

This research is concerned with providing a solution capable of treating network complexity and scalability effectively so that it overcomes administrative, environmental and technique boundaries. One good approach dealing with this matter is applying graph partitioning techniques. Graph partitioning is an optimization problem with the aim of dividing a large geographical network into manageable size districts called sub-networks with less complexity in favor of balancing the workload and minimizing the communication among them, with the aim of maximizing their independency as much as possible.

Over the past decades various models have been developed in such a way to satisfy a multi-objective problem such as delivery time and managerial cost. In real life, due to inevitable changes during network’s lifetime, it is vital to offer survivability and resilience in the existence of network failure and disruption. Further, it is essential to maintain functionality in critical facilities and high priority connections in the time of crisis. This paper suggests two partitioning techniques called “Hierarchical recursive progression “(HRP) and “Hierarchical recursive progression “(HRP) to solve the scalability as well as complexity of a network. For this matter, the initial balanced partition is produced on a predefined network. Furthermore two different approaches namely “complete failure update “and “partial failure update” are proposed and demonstrated in the occurrence of network disruption.

In sum, the three main objectives of this thesis are as follows:

1.     Modeling disruption on logistics networks

2.     Assuring and strengthen connectivity in the disrupted network for routing purposes

3.     Developing partitioning approaches in favor of generating roughly equal sized and balanced partitions in the disrupted network.