An analysis of generalised heuristics for vehicle routing and personnel rostering problems

Abstract

The present study investigates the performance of heuristics while solving problems with routing and rostering characteristics. The target problems include scheduling and routing home care, security and maintenance personnel. In analysing the behaviour of the heuristics and determining the requirements for solving the aforementioned problems, the winning hyper-heuristic from the first International Cross-domain Heuristic Search Challenge (CHeSC 2011) is employed. The completely new application of a hyper-heuristic as an analysis tool offers promising perspectives for supporting dedicated heuristic development. The experimental results reveal that different low-level heuristics perform better on different problems and that their performance varies during a search process. The following characteristics affect the performance of the heuristics: the planning horizon, the number of activities and lastly the number of resources. The body of this paper details both these characteristics and also discusses the required features for embedding in an algorithm to solve problems particularly with a vehicle routing component.

Keywords:

• hyper-heuristic
• home care scheduling
• security personnel routing and rostering
• maintenance personnel scheduling

Acknowledgements

This research was carried out within the IWT 090549 project.