A proficient and optimal local search algorithm for the establishment and operation of single-allocation hub-and-spoke transportation networks

Alizadeh Firozi, Mona; Kiani, Vahid; Karimi, Hossein

doi:10.22124/jmm.2026.31635.2848

A proficient and optimal local search algorithm for the establishment and operation of single-allocation hub-and-spoke transportation networks

Articles in Press

Document Type : Research Article

Authors

¹ Industrial Engineering Department, Faculty of Engineering, University of Bojnord, Bojnord, Iran

² Computer Engineering Department, Faculty of Engineering, University of Bojnord, Bojnord, Iran

10.22124/jmm.2026.31635.2848

Abstract

Hub-and-spoke networks are vital in transportation planning for cost-effective transport. The hub-location problem (HLP) optimizes intermediary nodes, their locations, and spoke assignments to minimize network costs. This paper addresses a special variant of HLP called the uncapacitated single allocation hub-location problem (USAHLP). A meta-heuristic algorithm, the multi-start local search (MSLS), is proposed to reliably solve large instances. Given the NP-hardness of USAHLP, MSLS uses a two-level local search, with the second level focusing on the best solutions from the first. Enhancements include three hub location structures, a non-hub reallocation operator, and greedy random restarts. These features ensure MSLS achieves near-optimal solutions and high reliability. The algorithm's performance is compared against CPLEX, GVNS, and eight state-of-the-art algorithms. Computational experiments conducted on USAHLP benchmark instances from the AP dataset demonstrate that the proposed MSLS consistently achieves superior solution quality and high reliability in a tolerable time-frame compared to existing approaches.

Keywords

Main Subjects