A study of deterministic capacitated facility location problems : models and solution methods

Abstract

Facility Location Problems have been widely used throughout the years for dealing with allocations of shelters, hospitals and healthcare centers, as well as disaster response facilities when natural disasters occur. In this dissertation, deterministic Capacitated Facility Location Problems (CFLPs) are studied in detail. Four mathematical models with known and constant parameters are developed; the Minisum (k-Median) Multi-Source and Single-Source models, and the Minimax (k-Center) Multi-Source and Single-Source models. The minisum models minimize the transportation and opening costs of a system comprising of k facilities, whereas the minimax models minimize the worst performance of the system. A number of problem instances of varying complexities are considered in this study and the Branch-and-Cut exact method is used to obtain optimal solutions, where possible. However, as the problem instance size increases, Branch-and-Cut tends to be inefficient as it takes significantly longer computational times to find optimal solutions since the CFLP is an NP-hard problem. Hence, heuristic methods are applied to the minimax models and the Genetic Algorithm meta-heuristic is applied to the minisum models, so that relatively fast but significantly good solutions are achieved. The results obtained indicate that the heuristics and meta-heuristics developed are able to yield optimal or close-to-optimal solutions for the majority of the instances considered, and sometimes even produce significantly better results than Branch-and-Cut in considerably less computational time.