Back

G-2009-84

A General Variable Neighborhood Search for Solving the Uncapacitated Single Allocation p-Hub Median Problem

, , , and

BibTeX reference

We present a new general variable neighborhood search approach for the uncapacitated single allocation p-hub median problem in networks. This NP-hard problem is concerned with locating hub facilities in order to minimize the traffic between all origin-destination pairs. We use three neighborhoods and efficiently update data structures for calculating new total flow in the network. In addition to the usual sequential strategy, a new nested strategy is proposed in designing a deterministic variable neighborhood descent local search. Our experimentation shows that general variable neighborhood search based heuristics outperform the best-known heuristics in terms of solution quality and computational effort. Moreover, we improve the best-known objective values for some large Australia Post and PlanetLab instances. Results with the new nested variable neighborhood descent show the best performance in solving very large test instances.

, 24 pages

Research Axis

Research applications

Publication

Variable neighborhood search for solving the uncapacitated single allocation p-hub median problem
, , , and
European Journal of Operational Research, 206, 289–300, 2010 BibTeX reference