Home Health Care Routing and Scheduling Problem with Genetic Algorithms

The Home Health Care Routing and Scheduling Problem (HHCRSP) is an NP-hard optimization problem that involves planning the routes and schedules of caregivers who provide in-home medical services. Despite the extensive use of metaheuristics in related routing problems, the HHCRSP has received limited attention, with only one known Genetic Algorithm (GA) and its variants reported in the literature. This thesis addresses this gap by proposing a novel GA and, for the first time, a Tabu Search (TS) approach for the HHCRSP. The GA incorporates and evaluates the Best-Cost Route Crossover (BCRC) operator—originally designed for vehicle routing problems. In addition, an enhanced version of the BCRC, the Best-Cost Route Crossover with Incremental Swap Optimization (BCRCS), is introduced in this thesis, alongside a route-based encoding scheme that eliminates the need for decoding. Experiments on benchmark instances demonstrate that the proposed methods outperform existing GA-based approaches and achieve competitive results compared to other metaheuristics. Notably, the BCRCSGA with Local Search (BCRCSGA-LS) produced new best-known solutions and superior average performance. These findings expand the limited metaheuristic research on the HHCRSP and provide a solid foundation for future exploration of more efficient and scalable optimization strategies.

Name thesis:degree_name

M.Sc. Computer Science

Level thesis:degree_level

Master

Discipline thesis:degree_discipline

Faculty of Mathematics and Science

Department dc:contributor.department

Department of Computer Science

Grantor dc:publisher

Brock University

Year dc:date.issued

2026

Author dc:creator

• Eshun, Michael

• Home Healthcare
• Genetic Algorithms
• Best-Cost Route Crossover
• Home Healthcare Routing and Scheduling Problem
• Routing and Scheduling Problem

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/10464/19869

OAI identifier oai:identifier

oai:brocku.scholaris.ca:10464/19869