Authors: Ratli, Mustapha
Urošević, Dragan 
El Cadi, Abdessamad Ait
Brimberg, Jack
Mladenović, Nenad 
Todosijević, Raca 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: An efficient heuristic for a hub location routing problem
Journal: Optimization Letters
Issue Date: 28-Nov-2020
Rank: M22
ISSN: 1862-4472
DOI: 10.1007/s11590-020-01675-z
This paper examines a new model for hub location known as the hub location routing problem. The problem shares similarities with the well studied uncapacitated single allocation p-hub median problem except that the hubs are now connected to each other by a cyclical path (or tour) known as the global route, each cluster of non-hub nodes and assigned hub is also connected by a single tour known as a local route, and the length of the local routes is constrained to a maximum number of nodes. Thus, aside from the normal tasks of hub selection and allocation of non-hub nodes, up to p + 1 travelling salesman problems need to be solved. A heuristic based on the general variable neighborhood search framework is proposed here to solve this very complicated problem. The improvement phase of the algorithm uses a sequential variable neighborhood descent with multiple neighborhoods required to suit the complex nature of the problem. A best sequencing of the neighborhoods is established through empirical testing. The perturbation phase known as the shaking procedure also uses a well-structured selection of neighborhoods in order to effectively diversify the search to different regions of the solution space. Extensive computational testing shows that the new heuristic significantly outperforms the state-of-the-art. Out of 912 test instances from the literature, we are able to obtain 691 new best known solutions. Not only are the improvements in objective values quite impressive, but also these new solutions are obtained in a small fraction of the time required by the competing algorithms.
Keywords: General variable neighborhood search | Heuristics | Hub location-routing problem | p-hub
Publisher: Springer Link

Show full item record


checked on May 19, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.