The technician routing and scheduling problem with skills and time-sensitive returns under uncertainty

We study the scheduling and routing of technician teams with the objective of maximizing the overall benefit of services provided while satisfying operational constraints on skills, workloads, routing, and working hours. The problem is motivated by a real-world collaboration with Hydro-Québec, where large-scale field operations require daily technician dispatching under tight time, skill, and uncertainty considerations. The problem is formulated over a finite multi-period planning horizon, differentiating between prioritized and optional customer visits and incorporating diminishing service benefits over time. Technician skill heterogeneity, vehicle capacity limits, and travel and service times are explicitly modeled, with stochastic extensions capturing uncertainty through chance constraints. As the main methodological contribution, we develop a tailored Logic-Based Benders Decomposition (LBBD) algorithm that decomposes the problem into an assignment-based master problem and routing feasibility subproblems. Routing feasibility is verified via dedicated TSP solvers in deterministic settings and conic-quadratic formulations under uncertainty, enabling scalability without sacrificing solution quality. To further assess incumbent quality, we also develop an Adaptive Large Neighborhood Search (ALNS) benchmark tailored to the same multi-period, hybrid-skill, chance-constrained setting. Extensive computational experiments on 210 benchmark instances demonstrate that the proposed LBBD substantially outperforms a Branch-and-Cut benchmark. LBBD solves 202 instances to optimality, compared to 161 for Branch-and-Cut, achieves significantly lower average optimality gaps (13.2% versus 28.2%, over unsolved instances), and reduced average computation time (1616 s versus 2493 s). The ALNS benchmark rapidly generates feasible schedules but exhibits an average gap of 5.47% relative to the LBBD incumbents, reinforcing the advantage of LBBD in solution quality, especially for medium and large instances. A real-world case study with 200 customers over a multi-period horizon confirms the practical applicability of the approach. The results show that LBBD produces robust and operationally viable schedules under uncertainty while maintaining high service coverage and improved workforce utilization with moderate computational effort.