Integrated Vehicle Routing and Monte Carlo Scheduling Approach for the Home Service Assignment, Routing, and Scheduling Problem
This work addresses operational efficiency for home service management companies by optimizing routing and scheduling under uncertainty, representing an incremental improvement with specific algorithmic enhancements.
The paper tackles the Home Service Assignment, Routing, and Scheduling Problem (H-SARA) by developing a two-stage approach that integrates vehicle routing with Monte Carlo scheduling to handle stochastic travel times, service durations, and customer cancellations, and introduces a Route Fracture Metaheuristic to iteratively improve solutions.
We formulate and solve the H-SARA Problem, a Vehicle Routing and Appointment Scheduling Problem motivated by home services management. We assume that travel times, service durations, and customer cancellations are stochastic. We use a two-stage process that first generates teams and routes using a VRP Solver with optional extensions and then uses an MC Scheduler that determines expected arrival times by teams at customers. We further introduce two different models of cancellation and their associated impacts on routing and scheduling. Finally, we introduce the Route Fracture Metaheuristic that iteratively improves an H-SARA solution by replacing the worst-performing teams. We present insights into the problem and a series of numerical experiments that illustrate properties of the optimal routing, scheduling, and the impact of the Route Fracture Metaheuristic for both models of cancellation.