A constraint-programming based decomposition method for the Generalised Workforce Scheduling and Routing Problem (GWSRP)

Abstract

This paper deals with the Generalised Workforce Scheduling and Routing Problem (GWSRP) where 9 temporal constraints ensuring visit dependencies are all together taken into account and where customer and worker’s quality of service are taken into consideration. A Constraint-Programming based Decomposition Method (CPDM) is proposed, firstly based on a relaxation of coordination constraints and a column generation, and secondly with an iterative insertion of coordination constraint by constraint programming solver. Numerical experiments are achieved on huge instances derived from WSRP benchmark instances with up to 177 customers, 59 vehicles and coordination constraints. The CPDM is able to find nearly optimal solution for medium-size instances and find high-quality solution for huge-size instances whereas CPLEX solver applied to a mixed integer linear model is not able to give a solution in this case.

KEYWORDS:

• WSRP
• dynamic programming
• constraint programming
• column generation
• temporal dependencies

Acknowledgements

Special thanks to S. Affifi who provided us with constant support and help for the Bredström and Rönnqvis’s instances.

Disclosure statement

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

Additional information

Funding

This work was carried out and funded within the framework of the European Regional Development Fund and other European programs.

Notes on contributors

E. Bourreau

Eric Bourreau is an assistant professor in Computer Science at the University of Montpellier. He is member of the LIRMM laboratory in the optimisation team MAORE and his main research contributions are in the field of Operation Research mainly solved by Constraint Programming.

T. Garaix

Thierry Garaix is an assistant professor at the Health Care Engineering Center at Mines St-Etienne (France) since 2011. He is member of the LIMOS UMR CNRS 6158 from 2013. His main research contributions are in the field of operation research applied to health care systems.

M. Gondran

Matthieu Gondran is an engineer and defended his PhD in 2018 at the University of Clermont-Ferrand. His PhD focuses in routing and scheduling problems, tackled by metaheuristics, linear programming and constraints programming.

P. Lacomme

Philippe Lacomme is an assistant professor at the University of Clermont-Ferrand. He is engineer in informatics and defends his PhD in 1993 and his HdR in 2006. He is co-author of more than 40 publications in journal and co-author of 9 books.

N. Tchernev

Nikolay Tchernev is a professor of Industrial Engineering and Supply chain at IAE Clermont Ferrand, School of Management, University of Clermont Auvergne. He received his Ph.D. degree in computer science in 1997 from University of Blaise Pascal and defended his Habilitation to manage research in 2009. He is the author of more than 130 publications including books, book chapters, research papers and scientific communications.