A decomposition approach for the periodic consistent vehicle routeing problem with an application in the cleaning sector

Abstract

This study is inspired by a challenging logistic problem encountered in the cleaning service sector. The company wishes to solve the consistent vehicle routeing problem over a three-month planning horizon. The company has a heterogeneous vehicle fleet to guarantee multiple frequencies of visits to its customers. The objective is to minimise the number of vehicles used and the total distance travelled. This problem is a generalisation of the periodic vehicle routeing problem. We decompose the problem into two sub-problems, namely, the planning and routeing optimisation sub-problems. We construct a mathematical model for the former and a large neighbourhood search for the latter. We evaluate the performance of our approach using the results of the industrial partner and instances from the literature on problems that are closely related to our case study. Our approach is found to be effective and robust. Our results outperform the existing company's plan in terms of solution quality, and staff convenience, and speed. We also discovered new best solutions on some of the instances from the literature.

Keywords:

• Routing
• driver consistency
• mixed-integer linear programming
• large neighbourhood search
• Decomposition methods

Acknowledgments

This paper is an extension of the preliminary study conducted by Messaoudi, Oulamara, and Rahmani (2019), we are grateful to the authors of Messaoudi, Oulamara, and Rahmani (2019), for providing us with the material (instances and results) of their study and allowing the successful completion of this publication. We are also grateful to the authors of Rodríguez-Martín, Salazar-González, and Yaman (2019) for providing us with detailed results of all instances and to the referees for their interesting comments that improved both the content as well as the presentation of the paper.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

The data used in the industrial instance is the property of the company, and is only available on request due to privacy restrictions.

Additional information

Notes on contributors

Bilal Messaoudi

Bilal Messaoudi is an optimisation scientist at Antsway with over six years of experience in Operations Research. He received a Ph.D. degree in Computer Science from Universitè de Lorraine, in the year of 2020. His main focus is on design and implementation of algorithms applied to real-world problems. He currently heads up optimisation engine development in Antsroute, a web-based vehicle routeing software.

Ammar Oulamara

Ammar Oulamara is a professor in Computer Science at the University of Lorraine. He received M.Sc. in Computer Science from National Polytechnic Institute of Grenoble, a Ph.D. in Computer Science from Joseph Fourier University, Grenoble, in 2001, and Habilitation in Computer Science from the National Polytechnic Institute of Lorraine, Nancy, in 2009. His research interests lie mainly in production scheduling and logistics, combinatorial optimisation, methods applied to manufacturing systems. He has published papers in many Operational Research and Industrial Engineering journals.

Said Salhi

Said Salhi is Emeritus Professor in Operational Research/Management Science at the Kent Business School (UK) where he was full professor for 16 years until January 2021. He is currently Editor in Chief for the Journal of the Operational Research Society (JORS). He was Head of the Management Science Group for over 8 years (2008-May 2017), founder and designer of the MSc in Logistics & Supply Chain Management. He was also the Director of the Centre on Logistics and Heuristic Optimisation (CLHO), which he founded in 2008, till January 2021. Prior to his appointment to Kent in 2005, Said was at the University of Birmingham in the School of Mathematics for 15 years and in his later years he acted as the Head of the Management Mathematics Group. Pr Salhi has edited 11 special issues including the recent OR handbook 'The Palgrave Handbook of Operations Research' published in Summer 2022 and authored a book on 'Heuristic Search: The Emerging Science of Problem Solving” (2017). He published over 130 papers in academic journals (excluding edited proceedings and book chapters). Pr. Salhi is a fellow of the OR Society (FORS), the IMA (FIMA), and CILT (FCILT), and an Executive member of NATCOR and a member of COPIOR. He has also been an associate editor of the IMA Journal of Management Mathematics since 2004 and sits in several editorial boards.