[Back]


Publications in Scientific Journals:

B. Biesinger, B. Hu, G. Raidl:
"A hybrid genetic algorithm with solution archive for the discrete (r|p)-centroid problem";
Journal of Heuristics, 21 (2015), 3; 391 - 431.



German abstract:
In this article we propose a hybrid genetic algorithm for the discrete(r/p)-centroid problem. We consider the competitive facility location problem where two non-cooperating companies enter a market sequentially and compete for market share. The rst decision maker, called the leader, wants to maximize his market share knowing that a follower will enter the same market.

Thus, for evaluating a leader's candidate solution, a corresponding follower's subproblem needs to be solved, and the overall problem therefore is a bi-level optimization problem. This problem is P2-hard, i.e., harder than any problem in NP. A heuristic approach is employed which is based on a genetic algorithm with tabu search as local improvement procedure and a complete solution archive. The archive is used to store and convert already visited solutions in
order to avoid costly unnecessary re-evaluations. Di erent solution evaluation methods are combined into an e ective multi-level evaluation scheme. The algorithm is tested on a well-known benchmark set as well as on larger newly created instances. For most of the instances we are able to outperform previous state-of-the-art heuristic approaches in solution quality and running time.

Keywords:
combinatorial optimization, competitive facility location, discrete ( r / p )-centroid problem, metaheuristics, solution archive, bi-level optimization


"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1007/s10732-015-9282-5



Related Projects:
Project Head Günther Raidl:
Lösungsarchive für Evolutionäre Kombinatorische Optimierung


Created from the Publication Database of the Vienna University of Technology.