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:
Algorithm Portfolios for Noisy Optimization: Compare Solvers Early Read chapter Read first chapter

2014 | OriginalPaper | Chapter

An Evolutionary Algorithm for the Leader-Follower Facility Location Problem with Proportional Customer Behavior

Authors : Benjamin Biesinger, Bin Hu, Günther Raidl

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

The leader-follower facility location problem arises in the context of two non-cooperating companies, a leader and a follower, competing for market share from a given set of customers. In our work we assume that the firms place a given number of facilities on locations taken from a discrete set of possible points. The customers are assumed to split their demand inversely proportional to their distance to all opened facilities. In this work we present an evolutionary algorithm with an embedded tabu search to optimize the location selection for the leader. A complete solution archive is used to detect already visited candidate solutions and convert them into not yet considered ones. This avoids unnecessary time-consuming re-evaluations, reduces premature convergence and increases the population diversity at the same time. Results show significant advantages of our approach over an existing algorithm from the literature.

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 Two Look-Ahead Strategies for Local-Search Metaheuristics
next chapter Towards a Matheuristic Approach for the Berth Allocation Problem
Footnotes
Literature
1.
Alekseeva, E., Kochetov, Y.: Matheuristics and exact methods for the discrete (\(\mathit{r}|\mathit{p}\))-centroid problem. In: Talbi, E.-G., Brotcorne, L. (eds.) Metaheuristics for bi-level Optimization. SCI, vol. 482, pp. 189–220. Springer, Heidelberg (2013) CrossRef
2.
Alekseeva, E., Kochetova, N., Kochetov, Y., Plyasunov, A.: A hybrid memetic algorithm for the competitive P-median problem. In: Bakhtadze, N., Dolgui, A. (eds.) Information Control Problems in Manufacturing, vol. 13, pp. 1533–1537. International Federation of Automatic Control, Boston (2009)
3.
Alekseeva, E., Kochetova, N., Kochetov, Y., Plyasunov, A.: Heuristic and exact methods for the discrete (\(\mathit{r}|\mathit{p}\))-centroid problem. In: Cowling, P., Merz, P. (eds.) EvoCOP 2010. LNCS, vol. 6022, pp. 11–22. Springer, Heidelberg (2010) CrossRef
4.
Bhadury, J., Eiselt, H., Jaramillo, J.: An alternating heuristic for medianoid and centroid problems in the plane. Comput. Oper. Res. 30(4), 553–565 (2003)CrossRefMATH
5.
Fernández, J., Hendrix, E.M.: Recent insights in huff-like competitive facility location and design. Eur. J. Oper. Res. 227(3), 581–584 (2013)CrossRef
6.
Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York (1997)CrossRefMATH
7.
8.
9.
Hu, B., Raidl, G.: An evolutionary algorithm with solution archives and bounding extension for the generalized minimum spanning tree problem. In: Soule, T. (ed.) Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation (GECCO 2012), pp. 393–400. ACM Press, Philadelphia (2012)
10.
Kochetov, Y., Kochetova, N., Plyasunov, A.: A matheuristic for the leader-follower facility location and design problem. In: Lau, H., Van Hentenryck, P., Raidl, G. (eds.) Proceedings of the 10th Metaheuristics International Conference (MIC 2013), Singapore, pp. 32/1-32/3 (2013)
11.
Kress, D., Pesch, E.: \(( r| p)\)-centroid problems on networks with vertex and edge demand. Comput. Oper. Res. 39, 2954–2967 (2012)CrossRefMathSciNet
12.
Küçükaydin, H., Aras, N., Altınel, I.K.: Competitive facility location problem with attractiveness adjustment of the follower: a bilevel programming model and its solution. Eur. J. Oper. Res. 208(3), 206–220 (2011)CrossRefMATH
13.
Laporte, G., Benati, S.: Tabu Search Algorithms for the \((r|X_p)\)-medianoid and \((r|p)\)-centroid Problems. Location Sci. 2, 193–204 (1994)MATH
14.
Louis, S., Li, G.: Combining robot control strategies using genetic algorithms with memory. In: Angeline, P.J., McDonnell, J.R., Reynolds, R.G., Eberhart, R. (eds.) EP 1997. LNCS, vol. 1213, pp. 431–441. Springer, Heidelberg (1997) CrossRef
15.
Mauldin, M.: Maintaining diversity in genetic search. In: Brachman, R.J. (ed.) Proceedings of the National Conference on Artificial Intelligence (AAAI-84), Austin, Texas, USA, pp. 247–250 (1984)
16.
Raidl, G.R., Hu, B.: Enhancing genetic algorithms by a trie-based complete solution archive. In: Cowling, P., Merz, P. (eds.) EvoCOP 2010. LNCS, vol. 6022, pp. 239–251. Springer, Heidelberg (2010) CrossRef
17.
Roboredo, M., Pessoa, A.: A branch-and-cut algorithm for the discrete \((r|p)\)-centroid problem. Eur. J. Oper. Res. 224(1), 101–109 (2013)CrossRefMATHMathSciNet
18.
Ronald, S.: Preventing diversity loss in a routing genetic algorithm with hash tagging. Complex. Int. 2, 548–553 (1995)
19.
Saidani, N., Chu, F., Chen, H.: Competitive facility location and design with reactions of competitors already in the market. Eur. J. Oper. Res. 219(1), 9–17 (2012)CrossRefMATHMathSciNet
20.
Sáiz, M.E., Hendrix, E.M., Pelegrín, B.: On nash equilibria of a competitive location-design problem. Eur. J. Oper. Res. 210(3), 588–593 (2011)CrossRefMATH
21.
Suárez-Vega, R., Santos-Peñate, D., Pablo, D.G.: Competitive multifacility location on networks: the \((r| X_p)\)-medianoid problem. J. Reg. Sci. 44(3), 569–588 (2004)CrossRef
22.
Teitz, M.B., Bart, P.: Heuristic methods for estimating the generalized vertex median of a weighted graph. Oper. Res. 16(5), 955–961 (1968)CrossRefMATH
23.
Yuen, S.Y., Chow, C.K.: A non-revisiting genetic algorithm. In: Proceedings of the IEEE Congress on Evolutionary Computation, (CEC 2007), pp. 4583–4590. IEEE Press, Singapore (2007)
Metadata
Title
An Evolutionary Algorithm for the Leader-Follower Facility Location Problem with Proportional Customer Behavior
Authors
Benjamin Biesinger
Bin Hu
Günther Raidl
Copyright Year
2014
Book
Learning and Intelligent Optimization

Print ISBN: 978-3-319-09583-7

Electronic ISBN: 978-3-319-09584-4

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-3-319-09584-4_19

Premium Partner

    Image Credits