Reactive tabu search and mixed-integer linear programming for multi-day assignment, scheduling, and routing problems of specialised education and home-care services

In this paper, we address the Multi-Day Assignment, Scheduling, and Routing Problem for Specialized Education and Home Care Services (SEHCS-MASRP), which involves heterogeneous employees and missions, posing a complex optimisation challenge. To tackle this, we propose a novel Mixed-Integer Linear Programming (MILP) model that considers employee qualifications, service requirements, scheduling constraints, routing decisions, and multiple objectives across the planning horizon. Additionally, we develop two metaheuristic approaches: a Reactive Tabu Search (RTS) algorithm incorporating either a Probabilistic Greedy Heuristic (PGH) or a Greedy Randomized Adaptive Search Procedure (GRASP) for initial solutions and a tailored genetic algorithm (GA). The three approaches aim to minimise wasted and overtime hours, total travel distances, and the number of assignments with an unsatisfied specialty while balancing wasted hours, overtime hours, and travel distances among the employees. Gurobi uses the proposed MILP model to find the optimal solutions, which are then compared with RTS and GA results across various instance sizes based on real-life SEHCS scenarios. Experimental results demonstrate the efficiency of MILP, RTS, and GA. MILP achieves proven optimal solutions for smaller to large instances. For huge instances, RTS generates high-quality solutions within reasonable computing times, outperforming GA performance. Notably, RTS consistently finds solutions within 5% of optimality for most instances.