A Game-Theoretic Genetic Algorithm for the Competitive Facility Location Problem

Abstract:

We introduce a new evolutionary algorithm called the Game-Theoretic Genetic Algorithm (GTGA) for solving combinatorial optimization game theory problems where it is computationally infeasible to enumerate all decision options of the players involved in the game.  Although evolutionary algorithms are widely used in combinatorial optimization, their applications to game theory have been limited to a specific type of games.  The GTGA aims to handle different types of games using multiple populations and alternating fitness evaluation methods.  We demonstrate an application of the GTGA to the Competitive Maximal Covering Location Problem, which is typically modeled as a two-player Stackelberg game such that first one player and then the other locate a fixed number of facilities to capture a maximum amount of revenue in a region.  Computational experiments demonstrate that the GTGA can converge to Stackelberg, Nash, and minimax equilibria as well as outperform some existing approaches.

Short Bio:

Sadan Kulturel‐Konak is a Professor of Management Information Systems and the director of the Flemming Creativity, Entrepreneurship and Economic Development (CEED) Center at Penn State Berks.  She received her Ph.D.in Industrial and Systems Engineering from Auburn University, USA.  Her research interests are in modeling and optimization of complex systems and robustness under uncertainty with applications to facility layout, reliability, and scheduling.  She has published her research in numerous journals including IIE Transactions, OR Letters, INFORMS Journal on Computing, INFORMS Transactions on Education, International Journal of Production Research, European Journal of Operational Research, and Journal of Intelligent Manufacturing Computers.  She is a member of the Institute for Operations Research and the Management Sciences (INFORMS), the Institute of Industrial and Systems Engineers (IISE) and the American Society for Engineering Education (ASEE).  She is the past chair of the ASEE Middle Atlantic Section.  She has been a principal investigator in sponsored projects from National Science Foundation (NSF) and VentureWell.