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.