A bi-objective home care routing and scheduling problem considering patient preference and soft temporal dependency constraints. (March 2023) - Oladzad-Abbasabady, Nastaran; Tavakkoli-Moghaddam, Reza; Mohammadi, Mehrdad; Vahedi-Nouri, Behdin
Abstract: 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). Highlights: Presenting a bi-objective mixed-integer programming model for a home health care routing and scheduling problem. Applying patient availability and all types of temporal dependencies in the form of soft constraints. Considering uncovered visits, patient preference, qualification level of caregivers, and hard and soft time windows. Adapting an iterated local search (ILS) algorithm to cope with the complexity of the large-sized instances. Comparing the results obtained by the ILS algorithm with the non-dominated sorting genetic algorithm. Conducting numerical experiments to evaluate the efficiency of the proposed approach. Graphical abstract: