A tabu search heuristic for the uncapacitated single allocation p-hub maximal covering problem

Marcos Roberto Silva and Claudio B. Cunha

European Journal of Operational Research, 2017, vol. 262, issue 3, 954-965

Abstract: This paper describes a tabu search (TS) heuristic for the uncapacitated single allocation p-hub maximal covering problem. The objective is to determine the best location for p hubs and the assignment of each of the spokes to a single hub such that the total demand between pairs of nodes within a given coverage distance is maximized. We consider all nodes as possible candidates for establishing hub facilities, what increases the complexity of the problem. Based on the mathematical programming formulation proposed by Peker and Kara (2015) we also report, for the first time, the optimal solutions for instances with up to 50 nodes from the AP (Australian Post) benchmark dataset, as well as the complete set of results for the CAB (Civil Aeronautics Board) dataset, including some heretofore yet unpublished results. The computational experiments have also demonstrated that our TS heuristic is efficient, leading to improved solutions in shorter CPU times when compared to previously published results, as well as for new derived instances with tigher coverage. It was also able to solve, for the first time, all instances of the AP data set, with up to 200 nodes, as well as new instances with tighter coverage parameters, thus evidencing it capacity to solve effectively large, realistic-sized instances of the problem.

Keywords: Location; Hub-and-spoke network; Hub covering problem; Tabu search (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221717302977
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:262:y:2017:i:3:p:954-965

DOI: 10.1016/j.ejor.2017.03.066

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().