A Hyper-Heuristic Using GRASP with Path-Relinking: A Case Study of the Nurse Rostering Problem

Introduction

Hyper-heuristics aim to design general solving technologies for various problems by choosing existing heuristics (Burke, Hyde, Kendall, Ochoa, Ozcan, & Woodward, 2010). In contrast to meta-heuristics focused on the domain knowledge, hyper-heuristics tend to produce the High Level Heuristics (HLHs) for guiding the Low Level Heuristics (LLHs) (Burke, Hyde, Kendall, Ochoa, Ozcan, & Qu, 2010). The high level heuristics are referred to the heuristics designed by algorithm experts over the problem domains while the LLHs are referred to the heuristics designed by the problem domain experts. Since the domain knowledge is necessary for a particular problem and is hard to explore by an algorithm designer (Ochaoa, Qu, & Burke, 2009), the primary motivation behind the hyper-heuristics is to help the algorithm designers to jump out of the limit from the problem domain and to produce general approaches. Based on the ability of general problem solving, hyper-heuristics have been applied to many kinds of problems, especially NP-hard problems, such as the timetabling (Burke, McCollum, Meisels, Petrovic, & Qu, 2007; Qu & Burke, 2009), the cutting stock (Terashima-Martin, Moran-Saavedre, & Ross, 2005), the workforce scheduling (Remde, Cowling, Dahal, & Colledge, 2006; Remde, Dahal, Cowling, & Colledge, 2009) and the p-median (Ren, Jiang, Xuan, & Luo, 2010).

In general, the goal of a hyper-heuristic is to design HLH to find an optimal LLH sequence, which can generate optimal solutions to the problems. As one kind of heuristics, most of hyper-heuristics draw on the experiments from the existing meta-heuristics, e.g., a simulated annealing based hyper-heuristic (Dowsland, Soubeiga, & Burke, 2007) and a genetic algorithm based hyper-heuristic (Ross, Martin-Blazquez, Schulenburg, & Hart, 2003). However, the kinds of hyper-heuristics are much fewer than those of meta-heuristics. The insufficiency of hyper-heuristics has limited the development of hyper-heuristics (Burke, Hyde, Kendall, Ochoa, Ozcan, & Woodward, 2010).

Greedy Randomized Adaptive Search Procedure (GRASP) with path-relinking is one of the effective meta-heuristics for problem solving (Resende & Ribeiro, 2003). There is no hyper-heuristic based on GRASP with path-relinking. As a typical meta-heuristic, GRASP with path-relinking is an iterative procedure to find the optimal solution. GRASP with path-relinking consists of three phases, such as the construction phase, the local search phase, and the path-relinking phase.

Motivated by the success of this algorithm in meta-heuristics, we propose a Hyper-heuristic using GRASP with Path-Relinking (HyGrasPr) in this paper. Our algorithm, HyGrasPr, generates LLH sequences to produce solutions in an iterative procedure. In each iteration, HyGrasPr builds an initial LLH sequence and applies a local search operator to find a relatively good LLH sequence. To avoid to be trapped as a local optimal LLH sequence, the path-relinking strategy is applied to obtain potential good solutions. To show the experimental results of HyGrasPr, we take the nurse rostering problem as a case study. On this problem, an existing simulated annealing based hyper-heuristic (SAHH) is employed as an experiment baseline. The results indicate that HyGrasPr can achieve better solutions than SAHH within the same running time.

The rest of this paper is organized as follows. First, we give the background of our work. We then propose the details of our HyGrasPr and present the experiments results with a case study on the nurse rostering problem.