Genetic based discrete particle swarm optimization for elderly day care center timetabling

Lin, M.Y. and Chin, K.S. and Tsui, K.L. and Wong, T.C. (2016) Genetic based discrete particle swarm optimization for elderly day care center timetabling. Computers & Operations Research, 65. pp. 125-138. ISSN 0305-0548 (https://doi.org/10.1016/j.cor.2015.07.010)

[thumbnail of Lin-etal-COR-2016-Genetic-based-discrete-particle-swarm-optimization-for-elderly-day-care-center]
Preview
Text. Filename: Lin_etal_COR_2016_Genetic_based_discrete_particle_swarm_optimization_for_elderly_day_care_center.pdf
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo

Download (1MB)| Preview

Abstract

The timetabling problem of local Elderly Day Care Centers (EDCCs) is formulated into a weighted maximum constraint satisfaction problem (Max-CSP) in this study. The EDCC timetabling problem is a multi-dimensional assignment problem, where users (elderly) are required to perform activities that require different venues and timeslots, depending on operational constraints. These constraints are categorized into two: hard constraints, which must be fulfilled strictly, and soft constraints, which may be violated but with a penalty. Numerous methods have been successfully applied to the weighted Max-CSP; these methods include exact algorithms based on branch and bound techniques, and approximation methods based on repair heuristics, such as the min-conflict heuristic. This study aims to explore the potential of evolutionary algorithms by proposing a genetic-based discrete particle swarm optimization (GDPSO) to solve the EDCC timetabling problem. The proposed method is compared with the min-conflict random-walk algorithm (MCRW), Tabu search (TS), standard particle swarm optimization (SPSO), and a guided genetic algorithm (GGA). Computational evidence shows that GDPSO significantly outperforms the other algorithms in terms of solution quality and efficiency.