  In the Home Service Assignment, Routing, and Appointment scheduling (H-SARA)
problem, a set of homogeneous service teams must visit a set of customers. The
home service provider needs to decide how many teams to hire (i.e., sizing
problem), how to assign service teams to customers (i.e., assignment problem),
how to route service teams (i.e., vehicle routing problem),and how to schedule
the appointment times for the customers (i.e., appointment scheduling problem)
such that the total cost is minimized. To tackle the H-SARA problem, we propose
an efficient solution method that comprises two stages. In the first stage, we
present a column generation algorithm to solve the sizing, assignment, and
routing problem. The algorithm is enhanced by a high-quality initial solution
which is found using the route-first cluster-second principle and a
polynomial-time 2-approximation algorithm. In the second stage, due to the
stochastic nature of travel time, service time, and cancellation, we propose a
simulation-driven approach to decide the appointment times such that a desired
on-time arrival probability is achieved. To ensure the suitability of the
simulation model, we discuss the characterization of the stochastic parameters.
The proposed ideas can be embedded in different solution schemes, including a
fast heuristic method that finds good solutions within seconds or a more
elaborate algorithm to find near-optimal solutions at the expense of longer
computational time. At last, we provide a high-level flexible decision support
tool implemented in AIMMS.
