Solving Large Scale Instances of Hub Location Problems with a Sub-problem Using an Exact Method

Abstract

Large scale instances of NP-hard problems cannot be solved to optimality with limited computational resources. A general approach is to use a heuristic method to obtain an approximate solution. However, when the model of a problem contains a sub-problem, it is possible to perform an exhaustive search on some subset of all sub-problems, thus improving solutions or confirming the optimality of existing solutions on the given subset. In this paper we demonstrate one such approach, for solving the Single Allocation Hub Location Problems (SAHLP), the capacitated version (CSAHLP) and the uncapacitated (USAHLP) version. An exhaustive search is performed for all hub configurations with small number of hubs (the location part) and for each one CPLEX is employed to solve the sub-problem for that hub configuration (the allocation part of the whole problem). We tested this method on USAHLP and CSAHLP test instances between 100 and 200 nodes, for which the optimal solutions are not known. Our extensive computational tests have resulted in 2 improved solutions and confirmed that other best known solutions may be considered optimal, in the sense of tested hub configurations with a certain number of hubs.