A variable neighbourhood search for the workforce scheduling and routing problem

Pinheiro, Rodrigo Lankaites; Landa-Silva, Dario; Atkin, Jason

Abstract

The workforce scheduling and routing problem (WSRP) is a combinatorial optimisation problem where a set of workers must perform visits to geographically scattered locations. We present a Variable Neighbourhood Search (VNS) metaheuristic algorithm to tackle this problem, incorporating two novel heuristics tailored to the problem-domain. The first heuristic restricts the search space using a priority list of candidate workers and the second heuristic seeks to reduce the violation of specific soft constraints. We also present two greedy constructive heuristics to give the VNS a good starting point. We show that the use of domain-knowledge in the design of the algorithm can provide substantial improvements in the quality of solutions. The proposed VNS provides the first benchmark results for the set of real-world WSRP scenarios considered.

Citation

Pinheiro, R. L., Landa-Silva, D., & Atkin, J. (2015, December). A variable neighbourhood search for the workforce scheduling and routing problem. Presented at 7th World Congress on Nature and Biologically Inspired Computing (NaBIC2015), Pietermaritzburg, South Africa

• Presentation Conference Type: Edited Proceedings
• Conference Name: 7th World Congress on Nature and Biologically Inspired Computing (NaBIC2015)
• Start Date: Dec 1, 2015
• End Date: Dec 3, 2015
• Online Publication Date: Nov 18, 2015
• Publication Date: Dec 2, 2015
• Deposit Date: Jan 21, 2016
• Publisher: Springer Verlag
• Peer Reviewed: Peer Reviewed
• Issue: 419
• Pages: 247–259
• Series Title: Advances in intelligent systems and computing
• Series ISSN: 2194-5365
• Book Title: Advances in nature and biologically inspired computing: proceedings of the 7th World Congress on Nature and Biologically Inspired Computing, NaBIC2015, in Pietermaritzburg, South Africa, held December 01-03, 2015
• ISBN: 9783319273990
• DOI: https://doi.org/10.1007/978-3-319-27400-3_22
• Keywords: personnel scheduling, variable neighbourhood search, heuristics metaheuristics, vehicle routing
• Public URL: https://nottingham-repository.worktribe.com/output/766305
• Publisher URL: http://link.springer.com/chapter/10.1007/978-3-319-27400-3_22