A bi-objective home care routing and scheduling problem considering patient preference and soft temporal dependency constraints

A Home Health Care Routing and Scheduling Problem (HHCRSP) is one of the most practical branches in Home Health Care (HHC) optimization. The main focus of this study is to investigate an HHCRSP with both soft and Hard Time Windows (HTWs) associated with caregivers and patients, respectively. Furthermore, five different types of soft temporal dependency constraints are considered, which specify different relations amongst the starting time of dependent visits. Accordingly, a bi-objective Mixed-Integer Programming (MIP) model is devised to incorporate staff rostering, vehicle routing, and scheduling simultaneously. This model aims at minimizing the system’s total cost while maximizing the total satisfaction of patient preference. Since the problem is NP-hard, Iterated Local Search (ILS) is applied to solve large-sized problems in high frequencies and within reasonable computational time. Computational results on some real-world-inspired benchmark instances highlight the overall efficiency of the employed algorithm compared to the Non-dominated Sorting Genetic Algorithm (NSGA-II).