Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
The Journal of Supercomputing
Erschienen in: The Journal of Supercomputing 10/2017

16.03.2017

A GPU-based genetic algorithm for the p-median problem

verfasst von: Bader F. AlBdaiwi, Hosam M. F. AboElFotoh

Erschienen in: The Journal of Supercomputing | Ausgabe 10/2017

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The p-median problem is a well-known NP-hard problem. Many heuristics have been proposed in the literature for this problem. In this paper, we exploit a GPGPU parallel computing platform to present a new genetic algorithm implemented in CUDA and based on a pseudo-Boolean formulation of the p-median problem. We have tested the effectiveness of our algorithm using a Tesla K40 (2880 CUDA cores) on 290 different benchmark instances obtained from OR-Library, discrete location problems benchmark library, and benchmarks introduced in recent publications. The algorithm succeeded in finding optimal solutions for all instances except for two OR-library instances, namely pmed 30 and pmed 40, where better than 99.9% approximations were obtained.
Vorheriger Artikel Dependability enhancing mechanisms for integrated clinical environments
Nächster Artikel Dynamic bidding in spot market for profit maximization in the public cloud

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Fußnoten
1
We shall use distance and cost interchangeably.
 
Literatur
1.
2.
3.
NVIDIA (2015) CURAND Library. Programming guide. PG-05328-050_v7.5. NVIDIA
4.
5.
AlBdaiwi BF, Goldengorin B, Sierksma G (2009) Equivalent instances of the simple plant location problem. Comput Math Appl 57(5):812–820MathSciNetCrossRefMATH
6.
7.
Bargos FF, de Queiroz Lamas W, Bargos DC, Neto MB, Pardal PCPM (2016) Location problem method applied to sugar and ethanol mills location optimization. Renew Sustain Energy Rev 65:274–282CrossRef
8.
9.
Biesinger B, Hu B, Raidl G (2015) A hybrid genetic algorithm with solution archive for the discrete (r|p)-centroid problem. J Heuristics 21(3):391–431CrossRefMATH
10.
Bozkaya B, Zhang J, Erkut E (2002) An efficient genetic algorithm for the p-median problem. Facil Locat Appl Theory 29: 179–205
11.
Daskin MS, Maass KL (2015) The p-median problem. In: Laporte G, Nickel S, da Gama FS (eds) Location science, chapter 2. Springer, Berlin, pp 21–45
12.
Drezner Z, Brimberg J, Mladenović N, Salhi S (2015) New heuristic algorithms for solving the planar p-median problem. Comput Oper Res 62:296–304MathSciNetCrossRefMATH
13.
El-Mihoub TA, Hopgood AA, Nolle L, Battersby A (2006) Hybrid genetic algorithms: a review. Eng Lett 13(2):124–137
14.
Farahani RZ, Hekmatfar M, Arabani AB, Nikbakhsh E (2013) Hub location problems: a review of models, classification, solution techniques, and applications. Comput Ind Eng 64(4):1096–1109CrossRef
15.
Goldengorin B, Kocheturov A, Pardalos PM (2014) A Pseudo-Boolean approach to the market graph analysis by means of the p-median model. In: Clusters, orders, and trees: methods and applications. Springer, pp 77–89
16.
Goldengorin B, Krushinsky D, Pardalos P (2013) Cell formation in industrial engineering, theory, algorithms and experiments. Springer, BerlinCrossRefMATH
17.
18.
Hammer PL (1968) Plant location-a pseudo-Boolean approach. Isr J Technol 6(5):330–332MATH
19.
HP Inc. (2015) QuickSpecs. HP Z820 workstation. c04111526-DA-14264-Worldwide-Version 48. HP Inc., USA
20.
Jaillet P, Song G, Yu G (1996) Airline network design and hub location problems. Locat Sci 4(3):195–212CrossRefMATH
21.
Jaramillo JH, Bhadury J, Batta R (2002) On the use of genetic algorithms to solve location problems. Comput Oper Res 29(6):761–779MathSciNetCrossRefMATH
22.
23.
Kariv O, Hakimi S (1979) An algorithmic approach to network location problems. II: The p-medians. SIAM J Appl Math 37(3):539–560MathSciNetCrossRefMATH
24.
Kazakovtsev LA, Orlov V, Stupina AA, Kazakovtsev V (2015) Modified genetic algorithm with greedy heuristic for continuous and discrete p-median problems. Facta Univ Ser Math Inform 30(1):89–106
25.
26.
Lim G, Ma L (2013) GPU-based parallel vertex substitution algorithm for the p-median problem. Comput Ind Eng 64(1):381–388CrossRef
27.
Ma L, Lim G (2011) GPU-based parallel computational algorithms for solving p-median problem. In: IIE Annual Conference. Proceedings. Institute of Industrial Engineers-Publisher, p 1
28.
29.
Mitchell M (1998) An introduction to genetic algorithms. MIT Press, CambridgeMATH
30.
Mladenović N, Brimberg J, Hansen P, Moreno-Pérez JA (2007) The p-median problem: a survey of metaheuristic approaches. Eur J Oper Res 179(3):927–939MathSciNetCrossRefMATH
31.
NVIDIA (2013) Tesla K40 active accelerator. Board specification. BD-06949-001_v03. NVIDIA
32.
Rebreyend P, Lemarchand L, Euler R (2015) A computational comparison of different algorithms for very large p-median problems. In: 15th European Conference on Evolutionary Computation in Combinatorial Optimization. Springer, pp 13–24
33.
34.
Ren Y, Awasthi A (2015) Investigating metaheuristics applications for capacitated location allocation problem on logistics networks. In: Chaos modeling and control systems design. Springer, pp 213–238
35.
Resende MGC, Werneck RF (2004) A hybrid heuristic for thep-median problem. J Heuristics 10(1):59–88CrossRefMATH
36.
Stanimirović Z (2012) A genetic algorithm approach for the capacitated single allocation p-hub median problem. Comput Inform 29(1):117–132MATH
37.
Todosijević R, Urošević D, Mladenović N, Hanafi S (2015) A general variable neighborhood search for solving the uncapacitated r-allocation p-hub median problem. Optim Lett 23: 1–13
Metadaten
Titel
A GPU-based genetic algorithm for the p-median problem
verfasst von
Bader F. AlBdaiwi
Hosam M. F. AboElFotoh
Publikationsdatum
16.03.2017
Verlag
Springer US
Erschienen in
The Journal of Supercomputing / Ausgabe 10/2017
Print ISSN: 0920-8542
Elektronische ISSN: 1573-0484
DOI
https://doi.org/10.1007/s11227-017-2006-x

Weitere Artikel der Ausgabe 10/2017

The Journal of Supercomputing 10/2017 Zur Ausgabe

OriginalPaper

A game theoretic-based distributed detection method for VM-to-hypervisor attacks in cloud environment

OriginalPaper

CLUS_GPU-BLASTP: accelerated protein sequence alignment using GPU-enabled cluster

Erratum

Erratum to: A dynamic VM consolidation technique for QoS and energy consumption in cloud environment

OriginalPaper

Cross-group secret sharing scheme for secure usage of cloud storage over different providers and regions

OriginalPaper

An iso-time scaling method for big data tasks executing on parallel computing systems

OriginalPaper

Dependability enhancing mechanisms for integrated clinical environments