×

zbMATH — the first resource for mathematics

A general variable neighborhood search for solving the uncapacitated single allocation \(p\)-hub median problem. (English) Zbl 1188.90142
Summary: 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.

MSC:
90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming
Software:
PlanetLab
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alumur, S.; Kara, B.Y., Network hub location problems: the state of the art, European journal of operational research, 190, 1-21, (2008) · Zbl 1146.90455
[2] Banerjee, S., Griffin, T.G., Pias, M., 2004. The interdomain connectivity of PlanetLab nodes. In: Barakat, C., Pratt, I. (Eds.), Proceedings of the 5th International Workshop on Passive and Active Network Measurement.
[3] Campbell, J.F., 1991. Hub location problems and the p-hub median problem, Center for Business and Industrial Studies Working Paper 91-06-21, University of Missouri-St. Louis, St. Louis.
[4] Ernst, A.T.; Krishnamoorthy, M., Efficient algorithms for the uncapacitated single allocation p-hub Median problem, Location science, 4, 130-154, (1996) · Zbl 0927.90065
[5] Ernst, A.T.; Krishnamoorthy, M., An exact solution approach based on shortest-paths for p-hub Median problems, Informs journal on computing, 10, 149-162, (1998) · Zbl 1034.90505
[6] Hansen, P.; Mladenović, N., Developments of variable neighborhood search, (), 415-440 · Zbl 1017.90130
[7] Hansen, P.; Mladenović, N., Variable neighborhood search: principles and applications, European journal of operational research, 130, 449-467, (2001) · Zbl 0981.90063
[8] Hansen, P.; Mladenović, N., Variable neighborhood search, (), 145-184 · Zbl 1102.90371
[9] Hansen, P.; Mladenović, N.; Pérez, J.A.M., Variable neighborhood search, European journal of operational research, 191, 593-595, (2008)
[10] Hansen, P.; Mladenović, N.; Moreno-Perez, J.A., Variable neighborhood search: methods and applications, 4or, 6, 319-360, (2008) · Zbl 1179.90332
[11] Klincewicz, J.G., Heuristics for the p-hub location problem, European journal of operational research, 53, 25-37, (1991) · Zbl 0726.90042
[12] Klincewicz, J.G., Avoiding local optima in the p-hub location problem using tabu search and GRASP, Annals of operations research, 40, 283-302, (1992) · Zbl 0784.90044
[13] Kratica, J.; Stanimirović, Z.; Tošić, D.; Filipović, V., Two genetic algorithms for solving the uncapaciated single allocation p-hub problem, European journal of operational research, 182, 15-28, (2007) · Zbl 1128.90038
[14] Kratica, J., Kojić, J., Tošić, D., Filipović, V., Dugošija, Dj., 2009. Two hybrid genetic algorithms for solving the super-peer selection problem, WSC2008 Conference, Advances in Soft Computing, Springer Verlag.
[15] Love, R.F., Morris, J.G., Wesolowsky, G. 1996. Facility Location: Models and Methods, vol. 7. Publications in Operations Research, New York.
[16] Meyer, T.; Ernst, A.T.; Krishnamoorthy, M., A 2-phase algorithm for solving the single allocation p-hub center problem, Computers and operations research, 36, 3143-3151, (2009) · Zbl 1176.90360
[17] Mladenović, N.; Hansen, P., Variable neighborhood search, Computers and operations research, 24, 1097-1100, (1997) · Zbl 0889.90119
[18] O’Kelly, M., A quadratic integer program for the location of interacting hub facilities, European journal of operational research, 32, 393-404, (1987) · Zbl 0627.90030
[19] Pérez-Pérez, M.; Almeida-Rodríguez, F.; Moreno-Vega, J.M., On the use of the path relinking for the p-hub Median problem, Lecture notes in computer science, 3004, 155-164, (2004) · Zbl 1177.90251
[20] Pérez-Pérez, M.; Almeida-Rodríguez, F.; Moreno-Vega, J.M., A hybrid VNS-path relinking for the p-hub Median problem, IMA journal of management mathematics, 18, 157-171, (2007) · Zbl 1177.90252
[21] Skorin-Kapov, D.; Skorin-Kapov, J., On tabu search for the location of interacting hub facilities, European journal of operational research, 73, 502-509, (1994) · Zbl 0806.90075
[22] Wolf, S., Merz, P., 2007. Evolutionary local search for the super-peer selection problem and the p-hub median problem. In: Bartz-Beielstein et al. (Eds.), Proceedings of the 4th International Workshop on Hybrid Metaheuristcs - HM2007, Lecture Notes in Computer Science, Springer, p. 1-15.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.