Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
An Importance Sampling Approach to the Estimation of Algorithm Performance in Automated Algorithm Design Read chapter Read first chapter

2017 | OriginalPaper | Chapter

A New Local Search for the p-Center Problem Based on the Critical Vertex Concept

Authors : Daniele Ferone, Paola Festa, Antonio Napoletano, Mauricio G. C. Resende

Published in: Learning and Intelligent Optimization

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

For the p-center problem, we propose a new smart local search based on the critical vertex concept and embed it in a GRASP framework. Experimental results attest the robustness of the proposed search procedure and confirm that for benchmark instances it converges to optimal or near/optimal solutions faster than the best known state-of-the-art local search.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter A GRASP for the Minimum Cost SAT Problem
next chapter An Iterated Local Search Framework with Adaptive Operator Selection for Nurse Rostering
Literature
1.
2.
Coffin, M., Saltzman, M.: Statistical analysis of computational tests of algorithms and heuristics. INFORMS J. Comput. 12(1), 24–44 (2000)CrossRefMATH
3.
Daskin, M.: Network and Discrete Location: Models, Algorithms, and Applications. Wiley, New York (1995)CrossRefMATH
4.
Davidović, T., Ramljak, D., Šelmić, M., Teodorović, D.: Bee colony optimization for the \(p\)-center problem. Comput. Oper. Res. 38(10), 1367–1376 (2011)CrossRefMATHMathSciNet
5.
6.
Feo, T., Resende, M.: A probabilistic heuristic for a computationally difficult set covering problem. Oper. Res. Lett. 8, 67–71 (1989)CrossRefMATHMathSciNet
7.
8.
Festa, P., Resende, M.: GRASP: an annotated bibliography. In: Ribeiro, C., Hansen, P. (eds.) Essays and Surveys on Metaheuristics, pp. 325–367. Kluwer Academic Publishers, London (2002)CrossRef
9.
10.
11.
Goldengorin, B., Kocheturov, A., Pardalos, P.M.: A pseudo-boolean approach to the market graph analysis by means of the p-median model. In: Aleskerov, F., Goldengorin, B., Pardalos, P.M. (eds.) Clusters, Orders, and Trees: Methods and Applications. SOIA, vol. 92, pp. 77–89. Springer, New York (2014). doi:10.​1007/​978-1-4939-0742-7_​5
12.
Goldengorin, B., Krushinsky, D., Pardalos, P.M.: Application of the PMP to cell formation in group technology. In: Goldengorin, B., Krushinsky, D., Pardalos, P.M. (eds.) Cell Formation in Industrial Engineering. SOIA, vol. 79, pp. 75–99. Springer, New York (2013). doi:10.​1007/​978-1-4614-8002-0_​3 CrossRef
13.
Hakimi, S.: Optimum locations of switching centers and the absolute centers and medians of a graph. Oper. Res. 12(3), 450–459 (1964)CrossRefMATH
14.
Hansen, P., Mladenović, N.: Variable neighborhood search for the \(p\)-median. Locat. Sci. 5(4), 207–226 (1997)CrossRefMATH
15.
16.
Kariv, O., Hakimi, S.: An algorithmic approach to network location problems. Part I: the \(p\)-centers. SIAM J. Appl. Math. 37(3), 513–538 (1979)CrossRefMATHMathSciNet
17.
Kariv, O., Hakimi, S.: An algorithmic approach to network location problems. Part II: the \(p\)-medians. SIAM J. Appl. Math. 37(3), 539–560 (1979)CrossRefMATHMathSciNet
18.
19.
Matsumoto, M., Nishimura, T.: Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8(1), 3–30 (1998)CrossRefMATH
20.
21.
Mladenović, N., Labbé, M., Hansen, P.: Solving the \(p\)-center problem with Tabu Search and variable neighborhood search. Networks 42(April), 48–64 (2003)CrossRefMATHMathSciNet
22.
Mladenovic, N., Urosevic, D., Prez-Brito, D., Garca-Gonzlez, C.G.: Variable neighbourhood search for bandwidth reduction. Eur. J. Oper. Res. 200(1), 14–27 (2010)CrossRefMathSciNet
23.
Pardo, E.G., Mladenovi, N., Pantrigo, J.J., Duarte, A.: Variable formulation search for the cutwidth minimization problem. Appl. Soft Comput. 13(5), 2242–2252 (2013)CrossRef
24.
25.
Resende, M., Werneck, R.: A hybrid heuristic for the \(p\)-median problem. J. Heuristics 10(1), 59–88 (2004)CrossRefMATH
26.
Salhi, S., Al-Khedhairi, A.: Integrating heuristic information into exact methods: the case of the vertex p-centre problem. J. Oper. Res. Soc. 61(11), 1619–1631 (2010)CrossRefMATH
27.
Wilcoxon, F.: Individual comparisons by ranking methods. Biom. Bull. 1(6), 80–83 (1945)CrossRef
Metadata
Title
A New Local Search for the p-Center Problem Based on the Critical Vertex Concept
Authors
Daniele Ferone
Paola Festa
Antonio Napoletano
Mauricio G. C. Resende
Copyright Year
2017
Book
Learning and Intelligent Optimization

Print ISBN: 978-3-319-69403-0

Electronic ISBN: 978-3-319-69404-7

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-69404-7_6

Premium Partner

    Image Credits