A queueing-based approach for integrated routing and appointment scheduling

European Journal of Operational Research, vol. 318, pp. 534–548

Abstract

This paper aims to address the integrated routing and appointment scheduling (RAS) problem for a single service provider. The RAS problem is an operational challenge faced by operators that provide services requiring home attendance, such as grocery delivery, home healthcare, or maintenance services. While considering the inherently random nature of service and travel times, the goal is to minimize a weighted sum of the operator’s travel times and idle time, and the client’s waiting times. To handle the complex search space of routing and appointment scheduling decisions, we propose a queueing-based approach to effectively deal with the appointment scheduling decisions. We use two well-known approximations from queueing theory: first, we use an approach based on phase-type distributions to accurately approximate the objective function, and second, we use an heavy-traffic approximation to derive an efficient procedure to obtain good appointment schedules. Combining these two approaches results in a fast and sufficiently accurate hybrid approximation, thus essentially reducing RAS to a routing problem. Moreover, we propose the use of a simple yet effective large neighborhood search metaheuristic to explore the space of routing decisions. The effectiveness of our proposed methodology is tested on benchmark instances with up to 40 clients, demonstrating an efficient and accurate methodology for integrated routing and appointment scheduling.

Authors 4

1. René Bekker corresponding

   Vrije Universiteit Amsterdam

   Affiliation as printed

   Department of Mathematics, Vrije Universiteit, De Boelelaan 1111, 1081 HV Amsterdam, The Netherlands

2. Bharti Bharti

   University of Amsterdam

   Affiliation as printed

   Korteweg–de Vries Institute for Mathematics, University of Amsterdam, Science Park 904, 1098 XH Amsterdam, The Netherlands

3. Leon Lan

   Vrije Universiteit Amsterdam

   Affiliation as printed

   Department of Mathematics, Vrije Universiteit, De Boelelaan 1111, 1081 HV Amsterdam, The Netherlands

4. Michel Mandjes Aachen Mathematical Institute

   Leiden University · University of Amsterdam

   Affiliation as printed

   Amsterdam Business School, Faculty of Economics and Business, University of Amsterdam, Amsterdam, The Netherlands

   Korteweg–de Vries Institute for Mathematics, University of Amsterdam, Science Park 904, 1098 XH Amsterdam, The Netherlands

   Mathematical Institute, Leiden University, The Netherlands