Skip to main content
SpringerLink
Log in

A hybrid artificial bee colony algorithm for the p-median problem with positive/negative weights

  • Application Article
  • Published:
OPSEARCH Aims and scope Submit manuscript

Abstract

In the classical p-median problem, the objective is to find a set Y of p vertices on an undirected graph \(G=(V,E)\) in such a way that \( Y \subseteq V\) and the sum of distances from all the vertices to their respective closest vertices in Y is minimized. In this paper, we have considered the weighted case where every vertex in G has either a positive or a negative weight under two different objective functions, viz. the sum of the minimum weighted distances and the sum of the weighted minimum distances. In this paper, we have proposed a hybrid artificial bee colony (ABC) algorithm for the positive/negative weighted p-median problem where each solution generated by ABC algorithm is improved by an interchange based randomized local search. In addition, an interchange based exhaustive local search is applied on some of the best solutions obtained after the execution of ABC algorithm in a bid to further improve their quality. We have compared our approach with the state-of-the-art approaches available in the literature on the standard benchmark instances. Computational results demonstrate the effectiveness of our approach.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. http://www.brunel.ac.uk/~mastjjb/jeb/info.html

References

  1. Alp, O., Erkut, E., Drezner, Z.: An efficient genetic algorithm for the p-median problem. Ann. Oper. Res. 122(1–4), 21–42 (2003)

    Article  Google Scholar 

  2. Banda, J., Singh, A.: A hybrid artificial bee colony algorithm for the terminal assignment problem. In: Swarm, Evolutionary, and Memetic Computing, vol 8947 of Lecture Notes in Computer Science, pp. 134–144. Springer (2015)

  3. Basti, M., Sevkli, M.: An artificial bee colony algorithm for the p-median facility location problem. Int. J. Metaheuristics 4(1), 91–113 (2015)

    Article  Google Scholar 

  4. Bozkaya, B., Zhang, J., Erkut, E.: An efficient genetic algorithm for the p-median problem. In: Facility Locations: Applications and Theory, Chap. 6, pp. 179–205. Springer, New York (2002)

  5. Burkard, R.E., Çela, E., Dollani, H.: 2-medians in trees with pos/neg weights. Discrete Appl. Math. 105(13), 51–71 (2000)

    Article  Google Scholar 

  6. Burkard, R., Fathali, J.: A polynomial method for the pos/neg weighted 3-median problem on a tree. Math. Methods Oper. Res. 65(2), 229–238 (2007)

    Article  Google Scholar 

  7. Burkard, R., Krarup, J.: A linear algorithm for the pos/neg-weighted 1-median problem on a cactus. Computing 60(3), 193–215 (1998)

    Article  Google Scholar 

  8. Cappanera, P.: A survey on obnoxious facility location problems, Technical Report TR-99-11, Departmento di Informatica, Universita di Pisa (1999)

  9. Carrizosa, E., Plastria, F.: Location of semi-obnoxious facilities. Stud. Locat. Anal. 12(1999), 1–27 (1999)

    Google Scholar 

  10. Chaurasia, S.N., Singh, A.: A hybrid swarm intelligence approach to the registration area planning problem. Inf. Sci. 302, 50–69 (2015)

    Article  Google Scholar 

  11. Chiyoshi, F., Galvao, R.D.: A statistical analysis of simulated annealing applied to the p-median problem. Ann. Oper. Res. 96, 61–74 (2000)

    Article  Google Scholar 

  12. Dai, Z., Cheung, T.-Y.: A new heuristic approach for the p-median problem. J. Oper. Res. Soc. 48(9), 950–960 (1997)

    Article  Google Scholar 

  13. Densham, P.J., Rushton, G.: A more efficient heuristic for solving large p-median problems. Pap. Reg. Sci. 71(3), 307–329 (1992)

    Article  Google Scholar 

  14. Dibble, C., Densham, P.J.: Generating interestingalternatives in gis and sdss using genetic algorithms. In: Proceedings of 1993 GIS/LIS Symposium. University of Nebraska, Lincoln (1993)

  15. Fathali, J.: A genetic algorithm for the p-median problem with pos/neg weights. Appl. Math. Comput. 183(2), 1071–1083 (2006)

    Google Scholar 

  16. Fathali, J., Kakhki, H., Burkard, R.: An ant colony algorithm for the pos/neg weighted p-median problem. Cent. Eur. J. Oper. Res. 14(3), 229–246 (2006)

    Article  Google Scholar 

  17. Fathali, J., Kakhki, H.T.: Solving the p-median problem with pos/neg weights by variable neighborhood search and some results for special cases. Eur. J. Oper. Res. 170(2), 440–462 (2006)

    Article  Google Scholar 

  18. Goldberg, D.E., Deb, K.: A comparative analysis of selection schemes used in genetic algorithms. In: Foundations of Gentic Algorithms, pp. 69–93. Morgan Kaufmann (1990)

  19. Hansen, P., Mladenović, N.: Variable neighborhood search for the p-median. Locat. Sci. 5(4), 207–226 (1997)

    Article  Google Scholar 

  20. Hosage, C., Goodchild, M.: Discrete space location-allocation solutions from genetic algorithms. Ann. Oper. Res. 6(2), 35–46 (1986)

    Article  Google Scholar 

  21. Karaboga, D.: An idea based on honey bee swarm for numerical optimization. In: Technical report-TR06. Erciyes University, Engineering Faculty, Computer Engineering Department, Turkey (2005)

  22. Karaboga, D., Gorkemli, B., Ozturk, C., Karaboga, N.: A comprehensive survey: artificial bee colony (ABC) algorithm and applications. Artif. Intell. Rev. 42(1), 21–57 (2014)

    Article  Google Scholar 

  23. Karaboga, D., Akay, B.: A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J. Glob. Optim. 39(3), 459–471 (2007)

    Article  Google Scholar 

  24. Karaboga, D., Akay, B.: On the performance of artificial bee colony (ABC) algorithm. Appl. Soft Comput. 8(1), 687–697 (2008)

    Article  Google Scholar 

  25. Karaboga, D., Akay, B.: A comparative study of artificial bee colony algorithm. Appl. Math. Comput. 214(1), 108–132 (2009)

    Google Scholar 

  26. Kariv, O., Hakimi, S.L.: An algorithmic approach to network location problems II: the p-medians. SIAM J. Appl. Math. 37(3), 539–560 (1979)

    Article  Google Scholar 

  27. Kuehn, A.A., Hamburger, M.J.: A heuristic program for locating warehouses. Manag. Sci. 9(4), 643–666 (1963)

    Article  Google Scholar 

  28. 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)

    Article  Google Scholar 

  29. Özçakir, N., Basti, M.: Particle swarm otimization algorithm approach for solving p-median facility location selection problem. Istanb. Univ. Fac. Manag. J. 41, 241–257 (2012)

    Google Scholar 

  30. Pan, Q.-K., Tasgetiren, M.F., Suganthan, P., Chua, T.: A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem. Inf. Sci. 181(12), 2455–2468 (2011)

    Article  Google Scholar 

  31. Perez, J.M., Garcia, J.R., Moreno, M.: A parallel genetic algorithm for the discrete p-median problem. Stud. Locat. Anal. 7, 131–141 (1994)

    Google Scholar 

  32. Plastria, F.: Optimal location of undesirable facilities: an overview. Belg. J. Oper. Res. Stat. Comput. Sci. 36, 109–127 (1996)

    Google Scholar 

  33. Resende, M.G., Werneck, R.F.: A hybrid heuristic for the p-median problem. J. Heuristics 10(1), 59–88 (2004)

    Article  Google Scholar 

  34. Resende, M.G.C., Werneck, R.F.: A fast swap-based local search procedure for location problems. Ann. Oper. Res. 150(1), 205–230 (2007)

    Article  Google Scholar 

  35. Rolland, E., Schilling, D.A., Current, J.R.: An efficient tabu search procedure for the p-median problem. Eur. J. Oper. Res. 96(2), 329–342 (1997)

    Article  Google Scholar 

  36. Rosing, K., ReVelle, C., Schilling, D.: A gamma heuristic for the p-median problem. Eur. J. Oper. Res. 117(3), 522–532 (1999)

    Article  Google Scholar 

  37. Sevkli, M., Mamedsaidov, R., Camci, F.: A novel discrete particle swarm optimization for p-median problem. J. King Saud Univ. Eng. Sci. 26, 11–19 (2014)

    Google Scholar 

  38. Singh, A.: An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem. Appl. Soft Comput. 9(2), 625–631 (2009)

    Article  Google Scholar 

  39. Singh, A., Sundar, S.: An artificial bee colony algorithm for the minimum routing cost spanning tree problem. Soft Comput. 15(12), 2489–2499 (2011)

    Article  Google Scholar 

  40. Teitz, M.B., Bart, P.: Heuristic methods for estimating the generalized vertex median of a weighted graph. Oper. Res. 16, 955–961 (1968)

    Article  Google Scholar 

  41. Venkatesh, P., Singh, A.: Two metaheuristic approaches for the multiple traveling salesperson problem. Appl. Soft Comput. 26, 74–89 (2015)

    Article  Google Scholar 

  42. Whitaker, R.: A fast algorithm for the greedy interchange of large-scale clustering and median location prolems. INFOR 21, 95–108 (1983)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer and Information Sciences, University of Hyderabad, Hyderabad, 500 046, India

    B. Jayalakshmi & Alok Singh

Authors
  1. B. Jayalakshmi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alok Singh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Alok Singh.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jayalakshmi, B., Singh, A. A hybrid artificial bee colony algorithm for the p-median problem with positive/negative weights. OPSEARCH 54, 67–93 (2017). https://doi.org/10.1007/s12597-016-0271-8

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12597-016-0271-8

Keywords

Search

Navigation