Home service routing and appointment scheduling with stochastic service times

Yang Zhan, Zizhuo Wang, Guohua Wan

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume288
Issue number1
DOIs
StateAccepted/In press - 2020

Keywords

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

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

Cite this