Abstract
In this paper, we propose a new method for solving large scale \(p\)-median problem instances based on real data. We compare different approaches in terms of runtime, memory footprint and quality of solutions obtained. In order to test the different methods on real data, we introduce a new benchmark for the \(p\)-median problem based on real Swedish data. Because of the size of the problem addressed, up to 1938 candidate nodes, a number of algorithms, both exact and heuristic, are considered. We also propose an improved hybrid version of a genetic algorithm called impGA. Experiments show that impGA behaves as well as other methods for the standard set of medium-size problems taken from Beasley’s benchmark, but produces comparatively good results in terms of quality, runtime and memory footprint on our specific benchmark based on real Swedish data.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
We thank C. Cleraux for providing us the code.
References
Al-Khedhairi, A.: Simulated annealing metaheuristic for solving \(p\)-median problem. Int. J. Contemp. Math. Sci. 3(25–28), 1357–1365 (2008)
Alp, O., Erkut, E., Drezner, Z.: An efficient genetic algorithm for the p-median problem. Ann. Oper. Res. 122(1–4), 21–42 (2003)
Ashayeri, J., Heuts, R., Tammel, B.: A modified simple heuristic for the p-median problem, with facilities design applications. Robot. Comput. Integr. Manufact. 21(4–5), 451–464 (2005)
Avella, P., Boccia, M., Salerno, S., Vasilyev, I.: An aggregation heuristic for large scale p-median problem. Comput. Oper. Res. 39(7), 1625–1632 (2012)
Avella, P., Sassano, A., Vasil’ev, I.: Computational study of large-scale p-median problems. Math. Program. 109(1), 89–114 (2007)
Barahona, F., Anbil, R.: The volume algorithm: producing primal solutions with a subgradient method. Math. Program. 87(3), 385–399 (2000)
Beasley, J.E.: OR-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11), 1069–1072 (1990)
Cantú-Paz, E.: A survey of parallel genetic algorithms. Calculateurs Parallèles, Réseaux et Systèmes Répartis 10, 141–171 (1998)
Carling, K., Han, M., Håkansson, J.: Does Euclidean distance work well when the p-median model is applied in rural areas? Ann. Oper. Res. 201(1), 83–97 (2012)
Cleraux, C., Bourges, P.: Relaxation Lagrangienne et le problème du p-médian. Master’s thesis, Institut Supérieur d’informatique, de modélisation et de leurs applications, Campus de Clermont-Ferrand/Les Cézeaux, BP 10125, 63173 Aubière CEDEX, France (2009)
Correa, E., Steiner, M., Freitas, A.A., Carieri, C.: A genetic algorithm for the P-median problem. In: Proceedings of 2001 Genetic and Evolutionary Computation Conference (GECCO-2001), pp. 1268–1275 (2001)
Corrêa, R., Ferreira, A., Rebreyend, P.: Scheduling multiprocessor tasks with genetic algorithms. IEEE Trans. Parallel Distrib. Syst. 10(8), 825–837 (1999)
CPlex online reference manual
Gay, J.: Résolution du Problème du p-médian, Application à la Restructuration de Bases de Données Semi-Structurées. Ph.D. thesis, Université Blaise-Pascal, Clermont-II (2011)
Hakimi, S.L.: Optimum locations of switching centers and the absolute centers and medians of a graph. Oper. Res. 12(3), 450–459 (1964)
Kariv, O., Hakimi, L.: An algorithmic approach to network location problems. SIAM J. Appl. Math. 37(3), 539–560 (1979)
Lim, G.J., Ma, L.: Gpu-based parallel vertex substitution algorithm for the p-median problem. Comput. Ind. Eng. 64(1), 381–388 (2013)
Lim, G.J., Reese, J., Holder, A.: Fast and robust techniques for the Euclidean p-median problem with uniform weights. Comput. Ind. Eng. 57(3), 896–905 (2009)
Meng, X., Rebreyend, P.: From the road network database to a graph for localization purposes. Technical report 2014:09, Dalarna University, Statistics (2014)
Mladenoviç, N., Brimberg, J., Hansen, P., Moreno-Pérez, J.A.: The p-median problem: a survey of metaheuristic approaches. Eur. J. Oper. Res. 179(3), 927–939 (2007)
Rebreyend, P., Han, M., Håkansson, J.: How do different algorithms work when applied on the different road networks when optimal location of facilities is searched for in rural areas? In: Huang, Z., Liu, C., He, J., Huang, G. (eds.) WISE Workshops 2013. LNCS, vol. 8182, pp. 284–291. Springer, Heidelberg (2014)
Reese, J.: Solution methods for the p-median problem: an annotated bibliography. Networks 48(3), 125–142 (2006)
ReVelle, C.S., Swain, R.W.: Central facilities location. Geogr. Anal. 2(1), 30–42 (1970)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Rebreyend, P., Lemarchand, L., Euler, R. (2015). A Computational Comparison of Different Algorithms for Very Large \(p\)-median Problems. In: Ochoa, G., Chicano, F. (eds) Evolutionary Computation in Combinatorial Optimization. EvoCOP 2015. Lecture Notes in Computer Science(), vol 9026. Springer, Cham. https://doi.org/10.1007/978-3-319-16468-7_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-16468-7_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-16467-0
Online ISBN: 978-3-319-16468-7
eBook Packages: Computer ScienceComputer Science (R0)