Portal de Periódicos da CAPES

A Variable Neighbourhood Search for the Workforce Scheduling and Routing Problem

2015; Springer Nature; Linguagem: Inglês

10.1007/978-3-319-27400-3_22

2194-5357

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

Scheduling and Optimization Algorithms

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.