A Genetic Algorithm for the Uncapacitated Facility Location Problem

The uncapacitated Facility Location Problem (FLP) is an NP-hard graph problem. A set of coordinate points are given on a Euclidean plane and treated as endpoints or “clients”. The goal is to place n number of facilities on the graph such that the distance between all clients each one’s closest facility is cost-minimized. The uncapacitated version of the problem assumes all facilities have infinite resources for their clients, and therefore additional costs do not need to be factored in.

A genetic algorithm (GA) metaheuristic has been created and refined with utilization of the “Wisdom of the Crowds” (WOC) phenomenon to offer a sufficiently ideal solution (but not necessarily the best possible solution). The method of generation data sets, details of the algorithm, and information about the graphical user interface (GUI) are explained. Resultant performances of various tests are analyzed to draw a conclusion about the purpose and effectiveness of this hybrid approach and provide the insight of potential applications.