AN EFFICIENT EVOLUTIONARY ALGORITHM FOR LOCATING LONG-TERM CARE FACILITIES

  • Zorica Stanimirovic Assistant Professor at Faculty of Mathematics, University of Belgrade
  • Miroslav Maric Assistant Professor at Faculty of Mathematics, University of Belgrade
  • Srdjan Bozovic MFC-Mikrokomerc, Zaplanjska 86, 11000 Belgrade, Serbia
  • Predrag Stanojevic PhD student at Faculty of Mathematics, University of Belgrade
Keywords: Evolutionary algorithms, Long-term care facility, Facility location problem, Discrete optimization

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.

DOI: http://dx.doi.org/10.5755/j01.itc.41.1.1115

Author Biographies

Zorica Stanimirovic, Assistant Professor at Faculty of Mathematics, University of Belgrade

Assistant Professor at the Department for Numerical Mathematics and Optimization, Faculty of Mathematics, University of Belgrade

Vice-Dean for Science and Research

 

Miroslav Maric, Assistant Professor at Faculty of Mathematics, University of Belgrade
Assistant Professor at the Department for Computer Science and Informatics, Faculty of Mathematics, University of Belgrade
Srdjan Bozovic, MFC-Mikrokomerc, Zaplanjska 86, 11000 Belgrade, Serbia
Microsoft MVP, MFC-Mikrokomerc,  Belgrade, Serbia
Predrag Stanojevic, PhD student at Faculty of Mathematics, University of Belgrade
PhD student at the Department for Computer Science and Informatics, Faculty of Mathematics, University of Belgrade
Published
2012-04-09
Section
Articles