An efficient evolutionary algorithm for locating long-term care facilities

Abstract

This paper deals with a variant of a discrete location problem of establishing long-term care facilities in a given network. The objective is to determine optimal locations for these facilities in order to minimize the maximum number of assigned patients to a single facility. We propose an efficient evolutionary approach (EA) for solving this problem, based on binary encoding, appropriate objective function and standard genetic operators. Unfeasible individuals in the population are corrected to be feasible, while applied EA strategies keep the feasibility of individuals and preserve the diversity of genetic material. The algorithm is benchmarked on a real-life test instance with 33 nodes and the obtained results are compared with the existing ones from the literature. The EA is additionally tested on new problem instances derived from the standard ORLIB AP hub data set with up to 400 potential locations. For the first time in the literature we report verified optimal solutions for most of the tested problem instances with up to 80 nodes obtained by the standard optimization tool CPLEX. Exhaustive computational experiments show that the EA approach quickly returns all optimal solutions for smaller problem instances, while large-scale instances are solved in a relatively short CPU time. The results obtained on the test problems of practical sizes clearly indicate the potential of the proposed evolutionary-based method for solving this problem and similar discrete location problems.