Home service routing and appointment scheduling with stochastic service times

Motivated by the practices of home services, we consider an integrated routing and appointment scheduling problem with stochastic service times. Given a set of customers with known locations and random service times, the professional operator has to visit each customer location exactly once to provide the services. The problem is to determine the visit route of the operator and the appointment times for the customers so as to minimize the total costs of traveling and idling of the operator, and waiting of customers. Given a finite support of random service times, we develop a mixed-integer program model for the problem. Practical-sized instances of the problem are very difficult to solve in a reasonable time with just standard techniques. We exploit several structural properties of the model and develop an L-shaped method to efficiently solve the problem. Specifically, we strengthen the formulation and introduce valid inequalities to speed up the solution process. We also propose an easy-to-implement heuristic algorithm that allows for effectively solving problem instances with large size. The effectiveness and efficiency of the proposed methods are demonstrated through computational experiments with randomly generated problem instances.