Solving Multi-Objective Hub Location Problems with Robustness

Abstract

Hub location problems (HLP) are considered in many logistic, telecommunications, and computer problems, where the design of these networks are optimized based on some objective(s) related to the cost or service. In those cases, direct routing between any origin and destination is not viable due to economic or technological constraints. From the seminal work of O'Kelly~\cite{OKelly86}, a huge number of works have been published in the literature. Early contributions were focused on analogue facility location problems, considering some assumptions to simplify the network design. Recent works have studied more complex models by incorporating additional real-life features and relaxing some assumptions, although the input parameters are still assumed to be known in most of the HLPs considered in the literature. This assumption is unrealistic in practice, since there is a high uncertainty on relevant parameters of real problems, such as costs, demands, or even distances. Consequently, a decision maker usually prefer several solutions with a low uncertainty in their objectives functions instead of the optimum solution of an assumed deterministic objective function. In this work we use a three-objective Integer Linear Programming model of the p-hub location problem where the average transportation cost, its variance, and the processing time in the hubs are minimized. The number of variables is $O(n^4)$ where $n$ is the number of nodes of the graph. ILP solvers can only solve small instances of the problems and we propose in this work the use of a recent hybrid algorithm combining a heuristic and exact methods: Construct, Merge, Solve, and Adapt