Essays on capacitated hub location problems

Abstract

"This thesis studies three essays based on hub location problems (HLPs) wherein hubs have limited capacities. We specifically look at two issues that can severely degrade the performance of a hub-and-spoke network: i) congestion at hubs, and ii) interdiction of hubs. In the first essay, we study an HLP that includes setting up hubs with appropriate capacity levels to minimize the capacity installation and congestion costs. The resulting mixed-integer non-linear program (MINLP) models in the literature are challenging to solve. Hence, we propose two new MINLP models of the problem, which outperform the existing two models in the literature. Next, we present nine different MISOCP-based reformulations for each of the MINLP models. From our extensive computational experiments using two well-known datasets, we suggest the overall MISOCP-based reformulation, which solves the problem 20–60 times faster compared to the existing model/method in the literature. In the second essay, we extend the first essay by considering the effect of congestion in a capacitated hub-and-spoke network subjected to interdiction. We model the problem as a bi- level (max-min) program between an adversary (attacker) and a network operator (defender). The adversary acts first at the upper-level to interdict a subset of the hubs. The network operator acts second at the lower level to route the flows through the remaining surviving hubs to minimize the routing and congestion costs, which the adversary at the upper level tries to maximize. Incorporating congestion at the lower level introduces non-linearity, rendering the bi-level problem extremely challenging to solve. To this end, we propose two exact alternate solution approaches: i) an inner-approximation based approach (IBA); and ii) a second-order conic programming-based approach (SBA). Our computational studies suggest that IBA consistently outperforms SBA for all the tested instances. In the third essay, we study the interdiction problem of a capacitated hub-and-spoke network subjected to uncertain demand. We model it as a robust optimization problem, wherein the demand uncertainty is modelled using different uncertainty sets, namely column, ellipsoidal, hose, and hybrid. Introducing robustness in the interdiction problem results in a tri-level formulation, for which we propose single level reductions. We show that accounting for uncertainty can result in a significantly different set of critical hubs."