An optimization framework for a dynamic multi-skill workforce scheduling and routing problem with time windows, synchronization constraints, and anticipated tasks

This article addresses the dynamic multi-skill workforce scheduling and routing problem with time windows and synchronization constraints (DWSRP-TW-SC) inherent in the on-demand home services sector. In this problem, new service requests (tasks) emerge in real-time, necessitating a constant reevaluation of service team task plans. This process must account for fixed portions of the plan, team-task skill compatibility, task priorities, and synchronization when task demands exceed a team’s capabilities. To address this problem, we introduce a real-time optimization framework triggered upon the arrival of new tasks or the elapse of a set time. This framework redesigns the routes of teams with the goal of minimizing the cumulative weighted throughput time for all tasks and incorporates task anticipation by reserving time slots for predicted future tasks. These anticipated tasks are introduced into the optimization as low-priority “ghost” tasks based on synthetic forecasts. For the route redesign phase of this framework, we develop both a mathematical model and an Adaptive Large Neighborhood Search (ALNS) algorithm. While we do not develop or train a specific learning algorithm, the framework is designed to be modular and compatible with any forecasting tool, allowing users to integrate models suited to their operational context. Instead, we evaluate the impact of anticipation performance on solution quality through controlled experiments. A comprehensive computational study assesses the performance of the proposed ALNS-based reoptimization framework and examines the effects of reoptimization strategies, frozen period lengths, and varying degrees of dynamism. Our findings offer practical insights and solutions for effective dynamic and anticipatory workforce management in on-demand home services.