Progress control in iterated local search for nurse rostering

This paper describes an approach in which a local search technique is alternated with a process which ‘jumps’ to another point in the search space. After each ‘jump’ a (time-intensive) local search is used to obtain a new local optimum. The focus of the paper is in monitoring the progress of this technique on a set of real world nurse rostering problems. We propose a model for estimating the quality of this new local optimum. We can then decide whether to end the local search based on the predicted quality. The fact that we avoid searching these bad neighbourhoods enables us to reach better solutions in the same amount of time. We evaluate the approach on five highly constrained problems in nurse rostering. These problems represent complex and challenging real world rostering situations and the approach described here has been developed during a commercial implementation project by ORTEC bv.     

A hybrid heuristic ordering and variable neighbourhood search for the nurse rostering problem

This paper is concerned with the development of intelligent decision support methodologies for nurse rostering problems in large modern hospital environments. We present an approach which hybridises heuristic ordering with variable neighbourhood search. We show that the search can be extended and the solution quality can be significantly improved by the careful combination and repeated use of heuristic ordering, variable neighbourhood search and back-tracking. The amount of computational time that is allowed plays a significant role and we analyse and discuss this. The algorithms are evaluated against a commercial Genetic Algorithm on commercial data. We demonstrate that this methodology can significantly outperform the commercial algorithm. This paper is one of the few in the scientific nurse rostering literature which deal with commercial data and which compare against a commercially implemented algorithm.     

Selecting and weighting features using a genetic algorithm in a case-based reasoning approach to personnel rostering

Personnel rostering problems are highly constrained resource allocation problems. Human rostering experts have many years of experience in making rostering decisions which reflect their individual goals and objectives. We present a novel method for capturing nurse rostering decisions and adapting them to solve new problems using the Case-Based Reasoning (CBR) paradigm. This method stores examples of previously encountered constraint violations and the operations that were used to repair them. The violations are represented as vectors of feature values. We investigate the problem of selecting and weighting features so as to improve the performance of the case-based reasoning approach. A genetic algorithm is developed for off-line feature selection and weighting using the complex data types needed to represent real-world nurse rostering problems. This approach significantly improves the accuracy of the CBR method and reduces the number of features that need to be stored for each problem. The relative importance of different features is also determined, providing an insight into the nature of expert decision making in personnel rostering.     

A Flexible, Fast, and Optimal Modeling Approach Applied to Crew Rostering at London Underground

We present a general modeling approach to crew rostering and its application to computer-assisted generation of rotation-based rosters (or rotas) at the London Underground. Our goals were flexibility, speed, and optimality, and our approach is unique in that it achieves all three. Flexibility was important because requirements at the Underground are evolving and because specialized approaches in the literature did not meet our flexibility-implied need to use standard solvers. We decompose crew rostering into stages that can each be solved with a standard commercial MILP solver. Using a 167 MHz Sun UltraSparc 1 and CPLEX 4.0 MILP solver, we obtained high-quality rosters in runtimes ranging from a few seconds to a few minutes within 2% of optimality. Input data were takes from different depots with crew sizes ranging from 30–150 drivers, i.e., with number of duties ranging from about 200–1000. Using an argument based on decomposition and aggregation, we prove the optimality of our approach for the overall crew rostering problem.     

A hybrid model of integer programming and variable neighbourhood search for highly-constrained nurse rostering problems

This paper presents a hybrid multi-objective model that combines integer programming (IP) and variable neighbourhood search (VNS) to deal with highly-constrained nurse rostering problems in modern hospital environments. An IP is first used to solve the subproblem which includes the full set of hard constraints and a subset of soft constrains. A basic VNS then follows as a postprocessing procedure to further improve the IP’s resulting solutions. The satisfaction of the excluded constraints from the preceding IP model is the major focus of the VNS. Very promising results are reported compared with a commercial genetic algorithm and a hybrid VNS approach on real instances arising in a Dutch hospital. The comparison results demonstrate that our hybrid approach combines the advantages of both the IP and the VNS to beat other approaches in solving this type of problems. We also believe that the proposed methodology can be applied to other resource allocation problems with a large number of constraints.     

Branch-and-price for staff rostering: An efficient implementation using generic programming and nested column generation

We present a novel generic programming implementation of a column-generation algorithm for the generalized staff rostering problem. The problem is represented as a generalized set partitioning model, which is able to capture commonly occurring problem characteristics given in the literature. Columns of the set partitioning problem are generated dynamically by solving a pricing subproblem, and constraint branching in a branch-and-bound framework is used to enforce integrality. The pricing problem is formulated as a novel three-stage nested shortest path problem with resource constraints that exploits the inherent problem structure. A very efficient implementation of this pricing problem is achieved by using generic programming principles in which careful use of the C++ pre-processor allows the generator to be customized for the target problem at compile-time. As well as decreasing run times, this new approach creates a more flexible modeling framework that is well suited to handling the variety of problems found in staff rostering. Comparison with a more-standard run-time customization approach shows that speedups of around a factor of 20 are achieved using our new approach. The adaption to a new problem is simple and the implementation is automatically adjusted internally according to the new definition. We present results for three practical rostering problems. The approach captures all features of each problem and is able to provide high-quality solutions in less than 15 minutes. In two of the three instances, the optimal solution is found within this time frame.     

A Decision Support System for Crew Planning in Passenger Transportation Using a Flexible Branch-and-Price Algorithm

This paper discusses a decision support system for airline and railway crew planning. The system is a state-of-the-art branch-and-price solver that is used for crew scheduling and crew rostering. Since it is far from trivial to build such a system from the information provided in the existing literature, technical issues about the system and its implementation are covered in more detail. We also discuss several applications. In particular, we focus on a specific aircrew rostering application. The computational results contain an interesting comparison of results obtained with the approach in which crew scheduling is carried out before crew rostering, and an approach in which these two planning problems are solved in an integrated manner.     

A Neural Network Application in Personnel Scheduling

In this paper, we present and evaluate a neural network model for solving a typical personnel-scheduling problem, i.e. an airport ground staff rostering problem. Personnel scheduling problems are widely found in servicing and manufacturing industries. The inherent complexity of personnel scheduling problems has normally resulted in the development of integer programming-based models and various heuristic solution procedures. The neural network approach has been admitted as a promising alternative to solving a variety of combinatorial optimization problems. While few works relate neural network to applications of personnel scheduling problems, there is great theoretical and practical value in exploring the potential of this area. In this paper, we introduce a neural network model following a relatively new modeling approach to solve a real rostering case. We show how to convert a mixed integer programming formulation to a neural network model. We also provide the experiment results comparing the neural network method with three popular heuristics, i.e. simulated annealing, Tabu search and genetic algorithm. The computational study reveals some potential of neural networks in solving personnel scheduling problems.     

A Tabu-Search Hyperheuristic for Timetabling and Rostering

Hyperheuristics can be defined to be heuristics which choose between heuristics in order to solve a given optimisation problem. The main motivation behind the development of such approaches is the goal of developing automated scheduling methods which are not restricted to one problem. In this paper we report the investigation of a hyperheuristic approach and evaluate it on various instances of two distinct timetabling and rostering problems. In the framework of our hyperheuristic approach, heuristics compete using rules based on the principles of reinforcement learning. A tabu list of heuristics is also maintained which prevents certain heuristics from being chosen at certain times during the search. We demonstrate that this tabu-search hyperheuristic is an easily re-usable method which can produce solutions of at least acceptable quality across a variety of problems and instances. In effect the proposed method is capable of producing solutions that are competitive with those obtained using state-of-the-art problem-specific techniques for the problems studied here, but is fundamentally more general than those techniques.     

Metaheuristics approach for solving personalized crew rostering problem in public bus transit

The crew rostering problem in public bus transit aims at constructing personalized monthly schedules for all drivers. This problem is often formulated as a multi-objective optimization problem, since it considers the interests of both the management of bus companies and the drivers. Therefore, this paper attempts to solve the multi-objective crew rostering problem with the weighted sum of all objectives using ant colony optimization, simulated annealing, and tabu search methods. To the best of our knowledge, this is the first paper that attempts to solve the personalized crew rostering problem in public transit using different metaheuristics, especially the ant colony optimization. The developed algorithms are tested on numerical real-world instances, and the results are compared with ones solved by commercial solvers.     

A variable neighborhood search based matheuristic for nurse rostering problems

A practical nurse rostering problem, which arises at a ward of an Italian private hospital, is considered. In this problem, it is required each month to assign shifts to the nursing staff subject to various requirements. A matheuristic approach is introduced, based on a set of neighborhoods iteratively searched by a commercial integer programming solver within a defined global time limit, relying on a starting solution generated by the solver running on the general integer programming formulation of the problem. Generally speaking, a matheuristic algorithm is a heuristic algorithm that uses non trivial optimization and mathematical programming tools to explore the solutions space with the aim of analyzing large scale neighborhoods. Randomly generated instances, based on the considered nurse rostering problem, were solved and solutions computed by the proposed procedure are compared to the solutions achieved by pure solvers within the same time limit. The results show that the proposed solution approach outperforms the solvers in terms of solution quality. The proposed approach has also been tested on the well known Nurse Rostering Competition instances where several new best results were reached.     

Two-level decomposition algorithm for crew rostering problems with fair working condition

A typical railway crew scheduling problem consists of two phases: a crew pairing problem to determine a set of crew duties and a crew rostering problem. The crew rostering problem aims to find a set of rosters that forms workforce assignment of crew duties and rest periods satisfying several working regulations. In this paper, we present a two-level decomposition approach to solve railway crew rostering problem with the objective of fair working condition. To reduce computational efforts, the original problem is decomposed into the upper-level master problem and the lower-level subproblem. The subproblem can be further decomposed into several subproblems for each roster. These problems are iteratively solved by incorporating cuts into the master problem. We show that the relaxed problem of the master problem can be formulated as a uniform parallel machine scheduling problem to minimize makespan, which is NP-hard. An efficient branch-and-bound algorithm is applied to solve the master problem. Effective valid cuts are developed to reduce feasible search space to tighten the duality gap. Using data provided by the railway company, we demonstrate the effectiveness of the proposed method compared with that of constraint programming techniques for large-scale problems through computational experiments.     

New approaches to nurse rostering benchmark instances

This paper presents the results of developing a branch and price algorithm and an ejection chain method for nurse rostering problems. The approach is general enough to be able to apply it to a wide range of benchmark nurse rostering instances. The majority of the instances are real world applications. They have been collected from a variety of sources including industrial collaborators, other researchers and various publications. The results of entering these algorithms in the 2010 International Nurse Rostering Competition are also presented and discussed. In addition, incorporated within both algorithms is a dynamic programming method which we present. The algorithm contains a number of heuristics and other features which make it very effective on the broad rostering model introduced.     

An estimation of distribution algorithm with intelligent local search for rule-based nurse rostering

This paper proposes a new memetic evolutionary algorithm to achieve explicit learning in rule-based nurse rostering, which involves applying a set of heuristic rules for each nurse's assignment. The main framework of the algorithm is an estimation of distribution algorithm, in which an ant-miner methodology improves the individual solutions produced in each generation. Unlike our previous work (where learning is implicit), the learning in the memetic estimation of distribution algorithm is explicit, that is, we are able to identify building blocks directly. The overall approach learns by building a probabilistic model, that is, an estimation of the probability distribution of individual nurse–rule pairs that are used to construct schedules. The local search processor (ie the ant-miner) reinforces nurse–rule pairs that receive higher rewards. A challenging real-world nurse rostering problem is used as the test problem. Computational results show that the proposed approach outperforms most existing approaches. It is suggested that the learning methodologies suggested in this paper may be applied to other scheduling problems where schedules are built systematically according to specific rules.     

The nurse rostering problem: A critical appraisal of the problem structure

This paper is concerned with the problem of nurse rostering within hospitals. We analyse a class of four benchmark instances from the nurse rostering literature to provide insight into the nature of the problem. By highlighting the structure of the problem we are able to reduce the relevant solution space. A mixed integer linear programme is then able to find optimal solutions to all four instances of this class of benchmark problems, each within half an hour. Our second contribution is to extend current mathematical approaches to nurse rostering to take better account of the practical considerations. We provide a methodology for handling rostering constraints and preferences arising from the continuity from one scheduling period to the next.     

The roster quality staffing problem – A methodology for improving the roster quality by modifying the personnel structure

Quantitative decision support on personnel planning is often restricted to either rostering or staffing. There exist some approaches in which aspects at the staffing level and the rostering level are treated in a sequential way. Obviously, such practice risks producing suboptimal solutions at both decision levels. These arguments justify an integrated approach towards improving the overall quality of personnel planning. This contribution constitutes (1) the introduction of the roster quality staffing problem and (2) a three-step methodology that enables assessing the appropriateness of a personnel structure for achieving high quality rosters, while relying on an existing rostering algorithm. Based on the rostering assessment result, specific modifications to the personnel structure can be suggested at the staffing level. The approach is demonstrated by means of two different hospital cases, which have it that they are subject to complex rostering constraints. Experimental results show that the three-step methodology indeed points out alternative personnel structures that better comply with the rostering requirements. The roster analysis approach and the corresponding staffing recommendations integrate personnel planning needs at operational and tactical levels.     

Enhancing case-based reasoning for personnel rostering with selected tabu search concepts

In this paper, we investigate the advantages of using case-based reasoning (CBR) to solve personnel rostering problems. Constraints for personnel rostering problems are commonly categorized as either ‘hard’ or ‘soft’. Hard constraints are those that must be satisfied and a roster that violates none of these constraints is considered to be ‘feasible’. Soft constraints are more flexible and are often used to measure roster quality in terms of staff satisfaction. We introduce a method for repairing hard constraint violations using CBR. CBR is an artificial intelligence paradigm whereby new problems are solved by considering the solutions to previous similar problems. A history of hard constraint violations and their corresponding repairs, which is captured from human rostering experts, is stored and used to solve similar violations in new rosters. The soft constraints are not defined explicitly. Their treatment is captured implicitly during the repair of hard constraint violations. The knowledge in the case-base is combined with selected tabu search concepts in a hybrid meta-heuristic algorithm. Experiments on real-world data from a UK hospital are presented. The results show that CBR can guide a meta-heuristic algorithm towards feasible solutions with high staff satisfaction, without the need to explicitly define soft constraint objectives.