Home service routing and appointment scheduling with stochastic service times

Yang Zhan, Zizhuo Wang and Guohua Wan

European Journal of Operational Research, 2021, vol. 288, issue 1, 98-110

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.

Keywords: OR in service industries; Home services; Traveling salesman problem; Appointment scheduling; Stochastic optimization (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720304835
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:288:y:2021:i:1:p:98-110

DOI: 10.1016/j.ejor.2020.05.037

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().