A matheuristic for the home healthcare routing and scheduling problem with ferry-dependent travel times

Home healthcare in coastal regions of Norway presents unique operational challenges, as caregivers must combine road driving with scheduled ferry trips to reach certain patients. Unlike conventional time-dependent travel, fixed ferry timetables impose strict synchronization requirements, where a missed departure may lead to prolonged idle times, cascading delays, or even unserved patients. Despite its practical significance, this integration of driving and ferry transportation has not been examined in the home healthcare routing and scheduling literature, leaving a gap between research and practice. To address this gap, we formulate a mixed-integer linear programming model that incorporates patient and caregiver time windows, skill matching requirements, and synchronization constraints, including those induced by ferry-dependent travel. Given the complexity of the problem, we propose a two-phase matheuristic. Phase I constructs a feasible solution through a sequential graph expansion strategy that employs either classical or weighted proximity search, while Phase II refines this solution using the same search method. Computational tests on 20 realistic instances derived from two Norwegian healthcare centers demonstrate that the proposed method with weighted proximity search outperforms direct model solving and the classical proximity search in terms of feasibility, optimality, and solution quality. In particular, the method solves instances with up to 30 patients (50 visits) to proven optimality and identifies high-quality feasible solutions for instances with up to 80 patients (135 visits) within a 3600-second time limit. • First study integrating ferry timetables into home healthcare routing and scheduling. • MILP model that considers time windows, skill matching, and synchronization constraints. • Two-phase matheuristic using sequential graph expansion and weighted proximity search. • Outperforms direct solving and classical proximity search on realistic Norwegian instances. • Solves up to 30 patients optimally, and 80 patients with high-quality feasible solutions.