[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

An Efficient Neural Network Algorithm for the p-Median Problem

  • Conference paper
  • First Online:
Advances in Artificial Intelligence — IBERAMIA 2002 (IBERAMIA 2002)

Part of the book series: Lecture Notes in Computer Science ((LNAI,volume 2527))

Included in the following conference series:

Abstract

In this paper we present a neural network model and new formulation for the p-median problem. The effectiveness and efficiency of our algorithm under varying problem sizes are analyzed in comparison to conventional heuristic methods. The results for small-scale problems (less than 100 points) indicate that our implementation of algorithm is effective. Furthermore, we also have applied our algorithm to solve large-scale problems, demonstrating that a simple recurrent neural network, with an adapted formulation of the problem, can generate good solutions in a few seconds.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. E. Bartezzaghi, A. Colorni (1981), “A search tree algorithm for plant location problems”, European Journal of Operational Research 7, 371–379

    Article  MATH  MathSciNet  Google Scholar 

  2. M. J. Canós, C. Ivorra, V. Liern (1999), “An exact algorithm for the fuzzy problem pmediates”, European Journal of Operational Research 116, 80–86

    Article  MATH  Google Scholar 

  3. N. Christofides, J. E. Beasley (1982), “A tree search algorithm for the problem pmediates”, European Journal of Operational Research 10, 196–204

    Article  MATH  MathSciNet  Google Scholar 

  4. L. Cooper (1963), “Location-Allocation Problems”, Operations Research 11, 331–343

    MATH  MathSciNet  Google Scholar 

  5. E. Dominguez, J. Muñoz (2001), “Solving the m-median problem with a neural network”, Proc. of IX CAEPIA (Conference of the Spanish Associations for the Artificial Intelligence) Gijon, Spain

    Google Scholar 

  6. Zvi Drezner (ed.) (1995), “Facility location: To survey of applications and methods”, Springer

    Google Scholar 

  7. Zvi Drezner, Jeffery Guyse (1999), “Application of decision analysis to the Weber facility location problem”, European Journal of Operational Research 116, 69–79

    Article  MATH  Google Scholar 

  8. G. Galán Marín, J. Muñoz Pérez (1999), “A Net n-parallel Competitive Neuronal for Combinatory Optimization”, Proc. of VIII CAEPIA (Conference of the Spanish Asociations for the Artificial Intelligence) Murcia, Spain, vol. 1, 98–106

    Google Scholar 

  9. G. Galán Marín, J. Muñoz Pérez (1999), “A Design of a Neuronal Network for the resolution of the problem of the Four Colors”, Have Ibero-American of Artificial Intelligence 8, 6–17

    Google Scholar 

  10. G. Galán Marín, J. Muñoz Pérez (2000), “An improved Neural Network Algorithm for the Bipatite Subgraph Problem”, Proc. of International Conference on Computational Intelligence and Neuroscience, Atlantic City, NJ USES

    Google Scholar 

  11. G. Galán Marín, J. Muñoz Pérez (2000), “Finding Near-Maximum Cliques with Competitive Hopfield Networks”, Proc. of International ICSC Symposium on Neural Computation, Berlin, Germany

    Google Scholar 

  12. G. Galán Marín, J. Muñoz Pérez (2001), “Design and Analysis of Maximum Hopfield Networks”, IEEE Trans. On Neural Networks 12 (2), 329–339

    Article  Google Scholar 

  13. Roberto D. Galvao (1980), “A dual-bounded algorithm for the problem p-mediates”, Operations Research

    Google Scholar 

  14. M. R. Garey, D. S. Johnson (1979), “Computers and intractability: To guide to the theory of NP-completeness”, W.H. Freeman and Co., New York

    Google Scholar 

  15. S. L. Hakimi (1964), “Optimum locations of switching centers and absolute centers and medians of to graph”, Operations Research 12, 450–459

    MATH  Google Scholar 

  16. S. L. Hakimi (1965), “Optimum distribution of switching centers in to communication network and some related graph theoretic problems”, Operations Research 13, 462–475

    MATH  MathSciNet  Google Scholar 

  17. P. Hanjoul, D. Peeters (1985), “A comparison of two dual-based procedures for solving the p-median problem”, European Journal of Operational Research 20, 386–396

    Article  MathSciNet  Google Scholar 

  18. Pierre Hansen, Nenad Mladenovic, Eric Taillard (1998), “Heuristic solution of the multisource Weber problem ace to problem p-mediates”, Operations Research Letters 22, 55–62

    Article  MATH  MathSciNet  Google Scholar 

  19. J. J. Hopfield, D.W. Tank (1985), “Neural computation of decisions in optimization problems”, Biological Cybernetics 52, 141–152

    MATH  MathSciNet  Google Scholar 

  20. Michelle Hribar, Mark S. Daskin (1997), “A dynamic programming heuristic for the problem p-mediates”, European Journal of Operational Research 101, 499–508

    Article  MATH  Google Scholar 

  21. Kariv O. and Hakimi S. L. (1979) “An Algorithmic Approach to Network Location Problem. Part 2: The p-Median”. SIAM J. Appl. Math., Vol. 37, pp. 539–560.

    Article  MATH  MathSciNet  Google Scholar 

  22. Love, Robert F., Morris, James G. and Wesolowsky, George O. (1998) “Facilities Location Models & Methods”, North-Holland

    Google Scholar 

  23. S. Lozano, F. Guerrero, L. Onieva, J. Larrañeta (1998), “Kohonen maps for solving to class of location-allocation problems”, European Journal of Operational Research 108, 106–117

    Article  MATH  Google Scholar 

  24. Subhash C. Narula, Ugonnaya I. Ogbu, Haakon M. Samuelsson (1977), “An algorithm for the problem p-mediates”, Operations Research 25, 709–713

    MATH  MathSciNet  Google Scholar 

  25. M. Ohlemüller (1997), “Taboo search for large location-allocation problems”, Journal of the Operational Research Society 48, 745–750

    Article  MATH  Google Scholar 

  26. C. ReVelle, R. Swain (1970), “Central facilities location”, Geographical Analysis, 2, 30–42

    Article  Google Scholar 

  27. M. B. Teitz, P. Bart (1968), “Heuristic methods for estimating the generalized vertex median of a weighted graph”, Operations Research 16, 955–961

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, E.T.S.I. Informatica, University of Malaga, Campus de Teatinos s/n, 29071, Malaga, Spain

    Enrique Dominguez Merino & José Muñoz Perez

Authors
  1. Enrique Dominguez Merino
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. José Muñoz Perez
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Telefónica Investigación y Desarrollo, Emilio Vargas 6, 28043, Madrid, Spain

    Francisco J. Garijo

  2. Dpto. Lenguajes y Sistemas Informáticos, Universidad de Sevilla, ETS Ingeniería Informática, 41012, Seville, Spain

    José C. Riquelme  & Miguel Toro  & 

Rights and permissions

Reprints and permissions

Copyright information

© 2002 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Dominguez Merino, E., Muñoz Perez, J. (2002). An Efficient Neural Network Algorithm for the p-Median Problem. In: Garijo, F.J., Riquelme, J.C., Toro, M. (eds) Advances in Artificial Intelligence — IBERAMIA 2002. IBERAMIA 2002. Lecture Notes in Computer Science(), vol 2527. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36131-6_47

Download citation

  • DOI: https://doi.org/10.1007/3-540-36131-6_47

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-00131-7

  • Online ISBN: 978-3-540-36131-2

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation