Planning for uncertainty is crucial for finding good, stable solutions. However, it is often impractical to incorporate stochastic elements into a large production system. Our paper tackles this issue in the context of the Technician Routing and Scheduling Problem (TRSP). We develop a set of techniques, based on phase-type distributions, to quickly and accurately evaluate risks caused by stochastic service durations. Our framework also supports hard time-windows and time-dependent travel times. We construct a new set of test instances derived from historical data. These instances demonstrate the importance of considering stochasticity and traffic in technician scheduling. We perform an extensive computational analysis over these instances. The experiments show that our approach works well in real-world scenarios and can scale to problem sizes of practical interest.
Microsoft Research, March 2020