Skip to Main content Skip to Navigation
Journal articles

A basic variable neighborhood search heuristic for the uncapacitated multiple allocation p-hub center problem

Abstract : The uncapacitated multiple allocation p-hub center problem (UMApHCP) consists of choosing p hub locations from a set of nodes with pairwise traffic demands in order to route the traffic between the origin-destination pairs such that the maximum cost between origin-destination pairs is minimum. It is assumed that transportation between non-hub nodes is possible only via chosen hub nodes. In this paper we propose a basic variable neighborhood search (VNS) heuristic for solving this NP hard problem. In addition we apply two mathematical formulations of the UMApHCP in order to detect limitations of the current state-of-the-art solver used for this problem. The heuristics are tested on benchmark instances for p-hub problems. The obtained results reveal the superiority of the proposed basic VNS over the state-of-the-art as well as over a multi-start local search heuristic developed by us in this paper.
Document type :
Journal articles
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03576814
Contributor : Julie Cagniard Connect in order to contact the contributor
Submitted on : Wednesday, February 16, 2022 - 12:04:30 PM
Last modification on : Monday, May 9, 2022 - 10:21:44 AM

Identifiers

Collections

Citation

Jack Brimberg, Nenad Mladenovic, Raca Todosijević, Dragan Urošević. A basic variable neighborhood search heuristic for the uncapacitated multiple allocation p-hub center problem. Optimization Letters, Springer Verlag, 2017, 11 (2), pp.313-327. ⟨10.1007/s11590-015-0973-5⟩. ⟨hal-03576814⟩

Share

Metrics

Record views

3