Toward a Reference Experimental Benchmark for Solving Hub Location Problems

Sebastian Wandelt (), Weibin Dai (), Jun Zhang () and Xiaoqian Sun ()
Additional contact information
Sebastian Wandelt: National Key Laboratory of Communication Navigation and Surveillance/Air Traffic Management, School of Electronic and Information Engineering, Beihang University, 100191 Beijing, China
Weibin Dai: National Key Laboratory of Communication Navigation and Surveillance/Air Traffic Management, School of Electronic and Information Engineering, Beihang University, 100191 Beijing, China
Jun Zhang: National Key Laboratory of Communication Navigation and Surveillance/Air Traffic Management, School of Electronic and Information Engineering, Beihang University, 100191 Beijing, China
Xiaoqian Sun: National Key Laboratory of Communication Navigation and Surveillance/Air Traffic Management, School of Electronic and Information Engineering, Beihang University, 100191 Beijing, China

Transportation Science, 2022, vol. 56, issue 2, 543-564

Abstract: Our study provides an experimental benchmark for state-of-the-art solution algorithms with hub location problems. Such problems are fundamental optimization problems in location science with widespread application areas, such as transportation, telecommunications, economics, and geography. Given they combine aspects of facility location and quadratic assignment problems, the majority of hub location problems are NP-hard and, accordingly, several solution techniques have been proposed for solving these problems. In this study, we report on the results of a large benchmark and reproduction effort to investigate 12 fundamental hub location problems that combine single or multiple allocation, a p-hub median objective or fixed hub set-up costs, capacitated or uncapacitated hubs, and complete or incomplete networks. We implemented four standard exact algorithms on these 12 problems as proposed in the literature. Algorithms are evaluated on subsets of three standard data sets in the field (CAB, TR, and AP); we computed more than 5,000 optimal solutions for these data sets. We report comparisons of solution techniques regarding wall clock time, convergence speed, memory use, and the impact of data features. In addition, we identify patterns in optimal solutions across these 12 problems, extracting insights regarding solution similarity, hub set candidates, and economies of scale. All results and programs are being made available to the public for free academic use.

Keywords: hub location problems; solution techniques; experimental benchmark (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2021.1094 (application/pdf)

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:inm:ortrsc:v:56:y:2022:i:2:p:543-564

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().