Efficient solution approaches for the bi-criteria p-hub median and dispersion problem

In this paper, we study the bi-criteria p-hub median and dispersion problem, that arises in the design of hub networks where the dispersion of hubs is desired to mitigate the risk of disruptions. The problem is formulated as a bi-objective mixed integer program, where the first objective is to minimize the total cost of routing the flows through p hubs and the second objective is to maximize the minimum distance (or dispersion) among the selected p hub locations themselves. We present two exact solution approaches that guaranteed to obtain the entire non-dominated Pareto frontier. The first is a cutting plane method in which a p-hub median problem with a particular dispersion distance is solved at each iteration. Three formulations of the problem, based on the different type of cuts and preprocessing, are presented. We study the dominance relationship among the three formulations. Through computational experiments, we show that the proposed cutting plane method is efficient in solving medium size instances of the problem and our strongest formulation is at least 40% computationally faster than the others. For solving large instances of the problem, we present a decomposition method where the p-hub median problem with dispersion distance is solved using an accelerated Benders decomposition approach. We present several problem specific enhancements to the algorithm such as starting with a better solution, efficient ways of solving decomposed subproblem and adding Pareto optimal Benders cuts to the master problem. The computational results on the Turkish network (TR81), US423, and Australian Post (AP) dataset show that the cutting plane algorithm with the proposed decomposition procedure is three to four times faster than the commercial solver.