A general variable neighborhood search for solving the uncapacitated single allocation p-hub median problem |
| |
Authors: | Aleksandar Ili? Dragan Uroševi? Jack Brimberg Nenad Mladenovi? |
| |
Institution: | 1. Faculty of Sciences and Mathematics, University of Niš, Serbia;2. Mathematical Institute, Serbian Academy of Science, 11000 Belgrade, Serbia;3. Department of Mathematics and Computer Science, Royal Military College of Canada, Kingston, Canada;4. School of Mathematics, Brunel University – West London, United Kingdom |
| |
Abstract: | 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. |
| |
Keywords: | Variable neighborhood search Nested variable neighborhood descent Discrete location p-Hub median |
本文献已被 ScienceDirect 等数据库收录! |
|