Solving Hub Location Problems With Profits Using Variable Neighborhood Search

This paper proposes variable neighborhood search (VNS) heuristics to solve hub network design problems with profits, which are uncapacitated hub location problems with incomplete hub networks. These problems seek to locate hub facilities, design hub networks, and assign spokes to hubs to maximize total profits. Six problems consisting of multiple allocation, single allocation, and r-allocation strategies, with optional direct connections, are solved. Unlike hub location problems that minimize costs satisfying all service demands, the operators can choose to satisfy a subset of travel demands to maximize profits. Although exact methods and heuristics are both commonly used for solving hub location problems, the problems with profits are mainly solved by the former. Therefore, VNS-based heuristics are proposed to solve six variants of hub location problems. The proposed heuristics have the same shaking procedure to escape local optima, while neighborhood structures in the improvement procedure depend on the allocation strategies. To evaluate the heuristics, this study also designs enhanced Benders decomposition methods which are exact algorithms. Computational experiments on existing benchmark datasets reveal an extraordinary performance of the heuristics. For the instances that can be solved by exact methods, the heuristics solve over 90% to optimality while being one to three orders of magnitude faster than the commercial solver CPLEX and Benders decomposition. Given the outstanding accuracy, with significantly reduced computational cost, the study contributes to the usage of heuristics for hub location problems with profits, especially for larger-scale networks, where exact methods cannot be executed because of limited computational resources.