EUVIMEDEUVIMED entdecken
Open Access · CC BY-NC-SA 4.0

Improved starting solutions for the planar p-median problem

Jack Brimberg, Zvi Drezner

Yugoslav Journal of Operations Research · 2021 · 31 (1) · 45-64

DOI: 10.2298/yjor200315008b ↗

Kurz gefasst

Fachartikel in der Zeitschrift Yugoslav Journal of Operations Research, 2021. Verfasst von Jack Brimberg und 1 weiteren Autor:innen. Die Arbeit wurde bisher 9-mal zitiert (Crossref). Der Volltext ist frei zugänglich (Open Access, CC BY-NC-SA 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In this paper we present two new approaches for finding good starting solutions to the planar p-median problem. Both methods rely on a discrete approximation of the continuous model that restricts the facility locations to the given set of demand points. The first method adapts the first phase of a greedy random construction algorithm proposed for the minimum sum of squares clustering problem. The second one implements a simple descent procedure based on vertex exchange. The resulting solution is then used as a starting point in a local search heuristic that iterates between the well-known Cooper?s alternating locate-allocate method and a transfer follow-up step with a new and more effective selection rule. Extensive computational experiments show that (1) using good starting solutions can significantly improve the performance of local search, and (2) using a hybrid algorithm that combines good starting solutions with a \deep" local search can be an effective strategy for solving a diversity of planar p-median problems.

Zitieren

APA

Brimberg, J., & Drezner, Z. (2021). Improved starting solutions for the planar p-median problem. Yugoslav Journal of Operations Research, 31(1), 45-64. https://doi.org/10.2298/yjor200315008b

Vancouver

Brimberg J, Drezner Z. Improved starting solutions for the planar p-median problem. Yugoslav Journal of Operations Research. 2021;31(1):45-64. doi:10.2298/yjor200315008b

BibTeX
@article{Brimberg2021,
  author = {Brimberg, Jack and Drezner, Zvi},
  title = {Improved starting solutions for the planar p-median problem},
  journal = {Yugoslav Journal of Operations Research},
  year = {2021},
  volume = {31},
  number = {1},
  pages = {45--64},
  doi = {10.2298/yjor200315008b}
}
Kostenlos starten →