A GVNS algorithm applied to the single allocation hub location problem with heterogeneous economies of scale

• Published in: Computers & operations research 2023-11, Vol.159, p.106350, Article 106350
• Main Authors: Freitas, Nayane Carvalho, de Sá, Elisangela Martins, de Souza, Sérgio Ricardo
• Format: Article
• Language: English
• Subjects: Heterogeneous economies of scale; Hub location problem; Meta-heuristics; Single allocation
• ISSN: 0305-0548
• DOI: 10.1016/j.cor.2023.106350

This paper addresses the single allocation hub location problem with heterogeneous economies of scale. This problem consists of selecting the nodes to establish the hubs in order to minimize the total cost of installing the hubs and routing demand flows, assuming that there is an economy of scale that depends on the amount of flow routed in each arc. We proposed a formulation to model the problem and an algorithm based on the General Variable Neighborhood Search (GVNS) meta-heuristic to handle the problem. Computational experiments were performed using instances from the literature with up to 500 nodes. The results show that the GVNS algorithm is effective for solving the instances in terms of runtime and solution quality. The results also show that the proposed formulation outperforms the literature formulation when activating the Benders decomposition method available in the CPLEX solver. •Improved the description of the problem.•Improves Section “Selection of the order for exploring the neighborhood structures”.•Extends the computational results for CCL instances.•Includes Analysis and Discussion of Results.