| dc.description.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." | en_US |
