Enhancing robustness of air transportation network

• Main Author: Yang, Changpeng
• Other Authors: Shu Jian Jun
• Format: Theses and Dissertations
• Language: English
• Published: 2018
• Subjects: DRNTU::Engineering::Mechanical engineering
• Online Access: http://hdl.handle.net/10356/74250
• Institution: Nanyang Technological University

The design of robust air transportation networks is crucial for improving a network’s ability to sustain/withstand failures and attacks. The difficulty lies in quantifying and optimizing the robustness. A comparison experiment shows that the total effective resistance, a spectral measure, is a promising measure satisfying the criteria that are intuitively predefined. Designing suitable strategies are the key challenges of this dissertation. Two strategies that are explicitly formulated for the minimization of the total effective resistance under several constraints are proposed to tackle the challenges. First considered is the flight route selection problem, in which a set of routes is chosen from a set of candidate routes to minimize the total effective resistance of the network. The corresponding problem is a nonlinear combinatorial optimization problem. In order to enhance system performance and computational efficiency, two approaches are proposed to deal with the problem based on small, medium and large-scale networks in terms of airport number. For small/medium-scale networks, an efficient method is developed by using convex relaxation with the step-by-step rounding technique. For large-scale networks, a submodular greedy algorithm is proposed to allow the system to handle a network size far beyond the capabilities of the convex relaxation method and to guarantee a bounded optimality gap, based on the monotone submodular characteristic of the objective function. Numerical experiments are performed on some real air transportation networks of small, medium and large-scale. A more general problem of creating robust network design under budget constraint, the route budget allocation problem, is also investigated. In this problem, both the edges to be added and their edge weights are allowed to be determined. The problem is solved exactly by a brute-force method to demonstrate its difficulty in obtaining an optimal solution. In order to achieve better computational efficiency, a convex relaxation method is proposed for the medium-scale networks, making use of the problem properties. For large-scale networks, a clustering-based convex relaxation method is proposed, in which the network dimensions can be reduced via the selection of critical airports. Three metrics, namely hub connectivity, number of flights, and passenger volume, are combined to define the hub hierarchy, and then the Gaussian mixture model is chosen to cluster the airports hierarchically. These two problems and their associated algorithms are tested on three levels of air transportation networks of small, medium, and large-scale. The outcomes indicate the tradeoff between the performance and computation time of these algorithms. Accordingly, the decision makers in different levels of organization could select the suitable algorithms.