A Real-Time Heuristic for Large-Scale Workforce Task Assignment, Multi-Vehicle Routing, and Scheduling With Time-Dependent Profits

Abstract

This paper presents a mixed-integer linear programming formulation for a dynamic and heterogeneous multi-depot vehicle routing problem with time windows, which accounts for the following complexities: customers profitability and deadlines, skills requirements, shifting technician availability, flexible and partial scheduling, multi-day planning. Building on a gossip-based strategy, we propose a heuristic that: 1) assigns tasks to technicians based on skills compatibility and expected profitability; 2) plans near-optimal routes within shift and time constraints; 3) continuously updates assignments and routes in real-time (within minutes), to absorb stochastic delays, unforeseen impediments, and dynamically generated tasks; 4) maintains private the real-time geolocation of the technicians; 5) is parallelizable in the sense that it can run simultaneously on multiple processors to speed up the execution. This paper is inspired by the real case study of DEDEM S.p.A., an international company that manages hundreds of technicians charged with refurbishing and repairing thousands of photo-booth machines spread across a wide geographic area, whose objective is to maximize the net profit by balancing per-task revenue against travel and labor costs. The performance of the proposed heuristic is demonstrated through numerical simulations over both synthetic data and real operational data provided by DEDEM S.p.A., saving up to 40% of profit loss and increasing up to 100% the net profit by efficiently handling stochastic delays. Note to Practitioners—This work is motivated by the operational challenges involved in managing a nationwide workforce responsible for carrying out tasks distributed across the country. Traditional scheduling methods typically rely on static, centralized optimization or simple proximity-based assignment, often resulting in suboptimal solutions with imbalanced workloads and poor adaptability to real-time disruptions. We provide a real-time, parallelizable algorithm that assigns and schedules tasks based on their profitability and deadlines, on technician availability, and on skill compatibility, while dynamically adjusting routes and schedules in response to delays or new task requests, maintaining private the technicians geolocation. Empirical validation using real company data demonstrates an overall increase in the net profit and the number of completed tasks when employing the proposed heuristic, preserving service quality under uncertainty. The algorithm is computationally tractable for practical problem sizes as each technician only needs to coordinate with nearby colleagues, enabling scalability to hundreds of workers and thousands of tasks and more. Companies can autonomously integrate this low-cost algorithm with their existing workforce management systems as a decision-support tool, especially when privacy concerns prevent continuous location tracking of technicians.