Variable Neighborhood Search Algorithm for the Single Assignment Incomplete Hub Location Problem with Modular Capacities and Direct Connections

Abstract

In distribution systems such as airlines and express package delivery, the use of hub-and-spoke networks is common, and flow consolidation at hub facilities is essential for cost reduction. While a constant discount factor is typically used to model cost reduction in interhub links, this paper explores an extension of the incomplete hub location problem with modular capacity that enables direct connections between non-hub nodes. The modified approach, called MHLPDC, aims to locate a set of hub facilities, connect each non-hub node to a hub, and activate hub facility links, access arc links, and direct links between non-hub nodes to minimize network costs. The MHLPDC integrates link activation decisions into the decision-making process and utilizes modular arc costs to model the flow dependence of transportation costs in all arcs. To solve the problem, the paper presents a mixed-integer mathematical programming formulation and heuristic algorithm based on a greedy randomized adaptive search and variable neighborhood search approach. The proposed algorithm produces high-quality solutions, as demonstrated through computational experiments on benchmark instances with up to 40 nodes. Furthermore, a sensitivity analysis of the optimal network structure indicates that increasing the discount factor, by varying hub and access arc capacities as well as the associated variable costs, results in fewer hubs being established and more direct shipments between non-hub nodes being permitted.

Keywords

• Hub-and-Spoke network
• Hub location
• Flow dependent costs
• Direct connection
• Heuristic algorithms
• Integer programming