Home service routing and appointment scheduling with stochastic service times

Yang Zhan, Zizhuo Wang, Guohua Wan

Research output: Contribution to journalArticlepeer-review

30 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)98-110
Number of pages13
JournalEuropean Journal of Operational Research
Issue number1
StatePublished - Jan 1 2021
Externally publishedYes

Bibliographical note

Funding Information:
This research is supported in part by NSF of China (Grants 71520107003, 71931008, 71125003, and 71421002 ).

Publisher Copyright:
© 2020 Elsevier B.V.


  • Appointment scheduling
  • Home services
  • OR in service industries
  • Stochastic optimization
  • Traveling salesman problem


Dive into the research topics of 'Home service routing and appointment scheduling with stochastic service times'. Together they form a unique fingerprint.

Cite this