Heuristic Approach to the Chance Constrained Minimum Spanning K-core Problem

Abstract

This thesis presents metaheuristic approaches to solve a novel network design problem under uncertainty. The problem is an extension of the classical k-core based network model called as the minimum spanning k-core problem. The minimum spanning k-core problem aims to balance the network design objectives of robustness, reachability and cost effectiveness. The problem is further extended to a probabilistic version called as, the chance constrained minimum spanning k-core problem. The minimum spanning k-core problem can be used to design underlying transportation networks, telecommunication networks, electrical and power distribution networks etc. in robust manner. In this thesis, Greedy Randomized Adaptive Search Procedure (GRASP), a metaheuristic approach is developed to solve both versions of the minimum spanning k-core problem. Computational experiments are performed to study the effectiveness of GRASP on specially designed test instances. Computational results conclude that GRASP provides good quality feasible solutions and efficiently solve both versions of the minimum spanning k-core problem.