Anytime Algorithms for Multi-Objective Hub Location Problems

Abstract

In many logistic, telecommunications and computer networks, direct routing of commodities between any origin and destination is not viable due to economic and technological constraints. Hub locations problems (HLPs) are considered in that cases, where the design of these networks are optimized based on some objective(s) related on the cost or service. A huge number of papers have been published since the seminal work of O’Kelly. Early works were focused on analogue facility location problems, considering some assumptions to simplify network design. Recent works have studied more complex models that relax some of these assumptions and incorporate additional real-life features. In most HLPs considered in the literature, the input parameters are assumed to be known and deterministic. However, in practice, this assumption is unrealistic since there is a high uncertainty on relevant parameters, such as costs, demands or even distances. As a result, a decision maker usually prefer several solutions with a low uncertainty in their objectives functions. In this work, anytime algorithms are proposed to solve the multi-objective hub location problems with uncertainty. The proposed algorithms can be stopped at any time, yielding a set of efficient solutions (belonging to the Pareto front) that are well spread in the objective space.