A 2-phase algorithm for solving the single allocation p-hub center problem

Meyer, T, Ernst, A and Krishnamoorthy, M 2009, 'A 2-phase algorithm for solving the single allocation p-hub center problem', Computers & Operations Research, vol. 36, no. 12, pp. 3143-3151.


Document type: Journal Article
Collection: Journal Articles

Title A 2-phase algorithm for solving the single allocation p-hub center problem
Author(s) Meyer, T
Ernst, A
Krishnamoorthy, M
Year 2009
Journal name Computers & Operations Research
Volume number 36
Issue number 12
Start page 3143
End page 3151
Total pages 9
Publisher Pergamon-Elsevier Science
Abstract The single allocation p-hub center problem is an NP-hard location-allocation problem which consists of locating hub facilities in a network and allocating non-hub nodes to hub nodes such that the maximum distance/cost between origin-destination pairs is minimized. In this paper we present an exact 2-phase algorithm where in the first phase we compute a set of potential optimal hub combinations using a shortest path based branch and bound. This is followed by an allocation phase using a reduced sized formulation which returns the optimal solution. In order to get a good upper bound for the branch and bound we developed a heuristic for the single allocation p-hub center problem based on an ant colony optimization approach. Numerical results on benchmark instances show that the new solution approach is superior over traditional MIP-solver like CPLEX. As a result we are able to provide new optimal solutions for larger problems than those reported previously in literature. We are able to solve problems consisting of up to 400 nodes in reasonable time. To the best of our knowledge these are the largest problems solved in the literature to date.
Subject Applied Mathematics not elsewhere classified
Keyword(s) Ant colony optimization
branch and bound
hub location
DOI - identifier 10.1016/j.cor.2008.07.011
Copyright notice © 2008 Elsevier Ltd. All rights reserved.
ISSN 0305-0548
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 44 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 44 times in Scopus Article | Citations
Altmetric details:
Access Statistics: 244 Abstract Views  -  Detailed Statistics
Created: Thu, 15 Jan 2015, 13:42:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us