Solving the home service assignment, routing, and appointment scheduling (H-SARA) problem with uncertainties

Syu Ning Johnn, Yiran Zhu, Andrés Miniguano–Trujillo, Akshay GupteDROPS (Schloss Dagstuhl – Leibniz Center for Informatics) 2021 · DOI

TL;DR

This paper tackles the complex Home Service Assignment, Routing, and Appointment Scheduling (H-SARA) problem, which involves deciding how many service teams to deploy, assigning them to customers, planning their routes, and scheduling appointments, all while dealing with uncertainties like variable service times and customer cancellations. The authors propose a novel two-stage heuristic that dynamically updates plans as new information becomes available, offering a practical and efficient solution for real-world home service operations.

What Problem Does This Paper Address?

The home service industry, encompassing everything from healthcare to appliance repair, faces a significant operational challenge: efficiently managing service delivery to customers spread across a geographical area. This involves a multi-layered decision-making process:

  • Fleet-sizing: How many service teams (vehicles) are needed?
  • Assignment: Which team serves which customer?
  • Routing: What is the optimal path for each team?
  • Scheduling: When should each service appointment occur?

This is further complicated by inherent uncertainties:

  • Service duration: How long will each service actually take?
  • Travel time: How long will it take to get between locations?
  • Customer cancellations: Customers might cancel their appointments at the last minute.

The paper refers to this integrated problem as the Home Service Assignment, Routing, and Appointment scheduling (H-SARA) problem. Existing approaches often tackle these components in isolation or struggle with the combined stochasticity, leading to suboptimal or infeasible plans. The authors aim to develop a robust system that can handle these uncertainties and provide high-quality, timely solutions.

Methods

The paper introduces a multi-faceted approach:

  • Stochastic Mixed-Integer Programming (MIP) Model: They first formulate the H-SARA problem as a stochastic MIP model. This model explicitly accounts for uncertainties in service duration, travel time, and customer cancellation rates. It's a "two-stage" model, meaning it makes initial decisions (first stage) and then has recourse actions to adjust based on revealed uncertainties (second stage).
  • Deterministic Model with Acceleration: For smaller instances, they derive a deterministic version of the problem and apply two acceleration techniques to solve it to optimality more efficiently.
  • Two-Stage Heuristic: For larger, more realistic instances, they develop a tailored two-stage heuristic. This heuristic mimics a real-world service process:
  • Stage 1 (Initial Planning): Based on estimated data and probabilistic cancellation rates, an initial plan is created, including fleet size, team assignments, routes, and broad appointment time windows. This stage uses an Adaptive Large Neighborhood Search (ALNS) meta-heuristic to improve initial routes and balance workloads.
  • Stage 2 (Tour Refinement): On the actual service day, after last-minute cancellations are known, the plan is refined. Routes are adjusted, and narrower appointment time windows are communicated to customers. ALNS is used again to optimize these refined tours.
  • ALNS Meta-Heuristic: The core of their heuristic approach is ALNS, a powerful optimization technique that iteratively improves solutions by "destroying" parts of a current solution and then "repairing" it. They detail various destroy and repair operators, as well as a roulette wheel selection mechanism for choosing operators.

Datasets

The paper does not explicitly mention using pre-existing real-world datasets. Instead, they generate simulated instances for their experiments. These instances are created based on parameters inspired by the AIMMS-MOPTA competition guidelines, including customer locations on a geometric grid, and distributions for travel times (log-normal), service times (gamma), and cancellation probabilities. They also describe a scenario generation procedure using Monte Carlo simulation and k-means clustering to create diverse sets of scenarios for evaluating their stochastic model.

Key Insights and Ideas

  • The Power of Two Stages: The most significant insight is the effectiveness of a two-stage approach. By making initial robust plans and then refining them with actual information (like cancellations), the system can achieve good solutions without needing perfect foresight. This mirrors real-world operational flexibility.
  • Uncertainty is the Norm, Not the Exception: The paper strongly emphasizes that ignoring uncertainties like customer cancellations leads to significantly worse outcomes. Their stochastic model and heuristic are designed precisely to mitigate these issues.
  • ALNS as a Workhorse: The Adaptive Large Neighborhood Search (ALNS) meta-heuristic proves to be a versatile and effective tool for both initial route generation and dynamic refinement, balancing workload and improving solution quality.
  • Appointment Windows Matter: Providing customers with appointment windows rather than fixed times is crucial for managing stochasticity and customer satisfaction, especially when plans are updated.
  • Trade-offs in Optimization: The paper highlights the inherent trade-offs, such as between fleet size and operational costs, and the cost of "imperfect information" (i.e., making decisions before all facts are known).

Key Results

  • Computational Efficiency: The two-stage heuristic significantly outperforms exact MIP solvers (CPLEX) in terms of computation time, especially for larger instances. For a 40-customer instance, the heuristic takes under 2 minutes, while the deterministic model takes ~19 minutes, and the stochastic model fails to terminate within 30 minutes. For 100-150 customers, exact methods are impractical, while the heuristic remains efficient.
  • Solution Quality: The heuristic provides competitive solutions, achieving results within 4% of CPLEX's optimal solutions on benchmark instances, despite the significant speedup.
  • Robustness: The two-stage heuristic demonstrates robustness by adapting to changing information (customer cancellations) and providing up-to-date decisions.
  • Cost Reduction: The proposed methods aim to reduce various costs, including travel, idling, waiting, and overtime, while balancing team workloads.
  • Deterministic vs. Stochastic: The deterministic model, even with acceleration, struggles with larger instances. The stochastic model is even more challenging. The heuristic offers a practical balance between performance and solution quality.

Limitations and Future Work

  • Heuristic Nature: While the heuristic is efficient and provides good quality solutions, it does not guarantee global optimality, unlike exact methods for smaller instances.
  • Data Overfitting: The authors acknowledge the potential for data over-fitting in their heuristic, as it relies on in-sample objective values from discretized scenarios. They address this by evaluating out-of-sample performance on a separate set of benchmark scenarios.
  • Scenario Generation: The quality of the heuristic's performance is dependent on the quality and diversity of the generated scenarios.
  • Future Work: The paper suggests exploring more advanced scenario generation techniques and potentially integrating more sophisticated local search operators within the ALNS framework. Further investigation into the impact of different parameter settings and the application of the framework to other similar service industries could also be valuable.

Summary updated

Abstract

The Home Service Assignment, Routing, and Appointment scheduling (H-SARA) problem integrates the strategic fleet-sizing, tactical assignment, operational vehicle routing and scheduling problems at different decision levels, with a single period planning horizon and uncertainty (stochasticity) from the service duration, travel time, and customer cancellation rate. We propose a stochastic mixed-integer linear programming model for the H-SARA problem. Additionally, a reduced deterministic version is introduced which allows to solve small-scale instances to optimality with two acceleration approaches. For larger instances, we develop a tailored two-stage decision support system that provides high-quality and in-time solutions based on information revealed at different stages. Our solution method aims to reduce various costs under stochasticity, to create reasonable routes with balanced workload and team-based customer service zones, and to increase customer satisfaction by introducing a two-stage appointment notification system updated at different time stages before the actual service. Our two-stage heuristic is competitive to CPLEX’s exact solution methods in providing time and cost-effective decisions and can update previously-made decisions based on an increased level of information. Results show that our two-stage heuristic is able to tackle reasonable-size instances and provides good-quality solutions using less time compared to the deterministic and stochastic models on the same set of simulated instances.
BibTeX
@inproceedings{johnn2021solving,
  author = {Syu Ning Johnn and Yiran Zhu and Andrés Miniguano–Trujillo and Akshay Gupte},
  title = {{Solving the home service assignment, routing, and appointment scheduling (H-SARA) problem with uncertainties}},
  booktitle = {DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)},
  year = {2021},
  doi = {10.4230/oasics.atmos.2021.4},
}
Figure