The capacitated single allocation hub maximal covering problem with hub installation costs

Abstract

This study considers a variant of the hub maximal covering problem that assumes single allocation scheme, hub capacities and hub installation costs. The objective of the problem is to find optimal locations for opening hubs and optimal allocations of each non-hub node to one of the installed hubs with sufficient capacity such that the sum of uncovered demands for all origin-destination pairs and the hub installation costs is minimized. In the hub location literature, this problem is denoted as the capacitated single allocation hub maximal covering problem. Two four-index integer linear mathematical formulations of the considered problem are presented, together with reformulations into a two-index and a three-index mixed integer linear program. Each of the four presented mathematical formulations is used within the framework of an exact solver to find solutions for the set of modified Australian Post hub instances. The results obtained are compared in respect to the number of optimal solutions and the quality of the upper bounds obtained by the exact solver, as well as the computational times required when using the considered mathematical formulations.