The Classical p-median Problem as a Surrogate Model in Hub Location

Jack Brimberg (), Raca Todosijević () and Dragan Uros̈ević ()
Additional contact information
Jack Brimberg: Royal Military College of Canada
Raca Todosijević: Univ. Polytechnique Hauts-de-France, LAMIH, CNRS, UMR 8201
Dragan Uros̈ević: Mathematical Institute of the Serbian Academy of Sciences and Arts

Networks and Spatial Economics, 2025, vol. 25, issue 2, No 6, 407-443

Abstract: Abstract This paper examines the use of the classical p-median problem as a surrogate (or approximate) model in hub location. The models presented here are derived from two extreme situations: (i) the hub network is super-efficient so that cost coefficient $$\alpha$$ α for hub to hub transfer tends to be close to 0; and (ii) the reverse where the hub sub-network is highly inefficient, so that $$\alpha$$ α tends to be unusually high. The performance of these approximate models is assessed on a group of test instances using different allocation strategies (single and multiple), uniform and non-uniform flows between nodes, and different values of $$\alpha$$ α . The group contains relatively small instances in order to allow optimal hub locations to be found most of the time by a general purpose MILP solver. A second group of larger instances is also tested, but in this case we use a state-of-the-art heuristic based on variable neighborhood search to find high quality solutions to one of the hub median problems under investigation. The obtained results confirm that the presented models are viable alternatives for finding good (sometimes even optimal) solutions to p-hub median problems. In some cases, where the MILP solver does not find an optimal solution for the given hub problem within the specified time-limit, better solutions are obtained with the basic p-median model in a small fraction of the time. We also introduce new cuts that can be added to the MILP formulations of p-hub median problems. These cuts take advantage of the observed ’proximity’ of the p-median nodes to the optimal hub nodes, and should be highly effective in finding optimal solutions or tight upper bounds. The effectiveness of the p-median solution as a starting solution in heuristics is also demonstrated.

Keywords: Location; p-median; Hub location; Surrogate models; q-cuts; q-optimality (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s11067-024-09633-3 Abstract (text/html)
Access to full text is restricted to subscribers.

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:kap:netspa:v:25:y:2025:i:2:d:10.1007_s11067-024-09633-3

Ordering information: This journal article can be ordered from
http://www.springer. ... ce/journal/11067/PS2

DOI: 10.1007/s11067-024-09633-3

Access Statistics for this article

Networks and Spatial Economics is currently edited by Terry L. Friesz

More articles in Networks and Spatial Economics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().