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.     

A scatter search methodology for the nurse rostering problem

The benefits of automating the nurse scheduling process in hospitals include reducing the planning workload and associated costs and being able to create higher quality and more flexible schedules. This has become more important recently in order to retain nurses and to attract more people into the profession. Better quality rosters also reduce fatigue and stress due to overwork and poor scheduling and help to maximise the use of leisure time by satisfying more requests. A more contented workforce will lead to higher productivity, increased quality of patient service and a better level of healthcare. This paper presents a scatter search approach for the problem of automatically creating nurse rosters. Scatter search is an evolutionary algorithm, which has been successfully applied across a number of problem domains. To adapt and apply scatter search to nurse rostering, it was necessary to develop novel implementations of some of scatter search's subroutines. The algorithm was then tested on publicly available real-world benchmark instances and compared against previously published approaches. The results show the proposed algorithm is a robust and effective method on a wide variety of real-world instances.     

A decomposition approach for the integrated vehicle-crew-roster problem with days-off pattern

The integrated vehicle-crew-roster problem with days-off pattern aims to simultaneously determine minimum cost vehicle and daily crew schedules that cover all timetabled trips and a minimum cost roster covering all daily crew duties according to a pre-defined days-off pattern. This problem is formulated as a new integer linear programming model and is solved by a heuristic approach based on Benders decomposition that iterates between the solution of an integrated vehicle-crew scheduling problem and the solution of a rostering problem. Computational experience with data from two bus companies in Portugal and data from benchmark vehicle scheduling instances shows the ability of the approach for producing a variety of solutions within reasonable computing times as well as the advantages of integrating the three problems.     

A new model for the asymmetric vehicle routing problem with simultaneous pickup and deliveries

The asymmetric vehicle routing problem with simultaneous pickup and deliveries is considered. This paper develops four new classes of valid inequalities for the problem. We generalize the idea of a no-good cut. Together, these help us solve 45-node randomly generated problem instances more efficiently. We report results on a set of benchmark instances in literature. In this set, we are able to show an order of magnitude improvement in computational times over currently published results in literature.     

Solving a nurse scheduling problem with knapsacks,networks and tabu search

This paper illustrates how a modern heuristic and two classical integer programming models have been combined to provide a solution to a nurse rostering problem at a major UK hospital. Neither a heuristic nor an exact approach based on a standard IP package was able to meet all the practical requirements. This was overcome by using a variant of tabu search as the core method, but applying knapsack and network flow models in pre- and post-processing phases. The result is a successful software tool that frees senior nursing staff from a time consuming administrative task.     

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 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.     

A matheuristic approach for solving a home health care problem

We deal with a Home Health Care Problem (HHCP) which objective consists in constructing the optimal routes and rosters for the health care staffs. The challenge lies in combining aspects of vehicle routing and staff rostering which are two well known hard combinatorial optimization problems. To solve this problem, we initially propose an integer linear programming formulation (ILP) and we tested this model on small instances. To deal with larger instances we develop a matheuristic based on the decomposition of the ILP formulation into two problems. The first one is a set partitioning like problem and it represents the rostering part. The second problem consists in the routing part. This latter is equivalent to a Multi-depot Traveling Salesman Problem with Time Windows (MTSPTW).     

Efficient heuristics for the rectilinear distance capacitated multi-facility Weber problem

In this paper, we consider the capacitated multi-facility Weber problem with rectilinear distance. This problem is concerned with locating m capacitated facilities in the Euclidean plane to satisfy the demand of n customers with the minimum total transportation cost. The demand and location of each customer are known a priori and the transportation cost between customers and facilities is proportional to the rectilinear distance separating them. We first give a new mixed integer linear programming formulation of the problem by making use of a well-known necessary condition for the optimal facility locations. We then propose new heuristic solution methods based on this formulation. Computational results on benchmark instances indicate that the new methods can provide very good solutions within a reasonable amount of computation time.     

The balanced academic curriculum problem revisited

The Balanced Academic Curriculum Problem (BACP) consists in assigning courses to teaching terms satisfying prerequisites and balancing the credit course load within each term. The BACP is part of the CSPLib with three benchmark instances, but its formulation is simpler than the problem solved in practice by universities. In this article, we introduce a generalized version of the problem that takes different curricula and professor preferences into account, and we provide a set of real-life problem instances arisen at University of Udine. Since the existing formulation based on a min–max objective function does not balance effectively the credit load for the new instances, we also propose alternative objective functions. Whereas all the CSPLib instances are efficiently solved with Integer Linear Programming (ILP) state-of-the-art solvers, our new set of real-life instances turns out to be much more challenging and still intractable for ILP solvers. Therefore, we have designed, implemented, and analyzed heuristics based on local search. We have collected computational results on all the new instances with the proposed approaches and assessed the quality of solutions with respect to the lower bounds found by ILP on a relaxed and decomposed problem. Results show that a selected heuristic finds solutions of quality at 9%–60% distance from the lower bound. We make all data publicly available, in order to stimulate further research on this problem.     

Branch-and-cut algorithms for the split delivery vehicle routing problem

In this paper we present two exact branch-and-cut algorithms for the Split Delivery Vehicle Routing Problem (SDVRP) based on two relaxed formulations that provide lower bounds to the optimum. Procedures to obtain feasible solutions to the SDVRP from a feasible solution to the relaxed formulations are presented. Computational results are presented for 4 classes of benchmark instances. The new approach is able to prove the optimality of 17 new instances. In particular, the branch-and-cut algorithm based on the first relaxed formulation is able to solve most of the instances with up to 50 customers and two instances with 75 and 100 customers.     

A combined local search and integer programming approach to the traveling tournament problem

The traveling tournament problem is a well-known combinatorial optimization problem with direct applications to sport leagues scheduling, that sparked intensive algorithmic research over the last decade. With the Challenge Traveling Tournament Instances as an established benchmark, the most successful approaches to the problem use meta-heuristics like tabu search or simulated annealing, partially heavily parallelized. Integer programming based methods on the other hand are hardly able to tackle larger benchmark instances. In this work we present a hybrid approach that draws on the power of commercial integer programming solvers as well as the speed of local search heuristics. Our proposed method feeds the solution of one algorithm phase to the other one, until no further improvements can be made. The applicability of this method is demonstrated experimentally on the galaxy instance set, resulting in currently best known solutions for most of the considered instances.     

A systematic two phase approach for the nurse rostering problem

Nurse rostering is an NP-hard combinatorial problem which makes it extremely difficult to efficiently solve real life problems due to their size and complexity. Usually real problem instances have complicated work rules related to safety and quality of service issues in addition to rules about quality of life of the personnel. For the aforementioned reasons computer supported scheduling and rescheduling for the particular problem is indispensable. The specifications of the problem addressed were defined by the First International Nurse Rostering Competition (INRC2010) sponsored by the leading conference in the Automated Timetabling domain, PATAT-2010. Since the competition imposed quality and time constraint requirements, the problem instances were partitioned into sub-problems of manageable computational size and were then solved sequentially using Integer Mathematical Programming. A two phase strategy was implemented where in the first phase the workload for each nurse and for each day of the week was decided while in the second phase the specific daily shifts were assigned. In addition, local optimization techniques for searching across combinations of nurses’ partial schedules were also applied. This sequence is repeated several times depending on the available computational time. The results of our approach and the submitted software produced excellent solutions for both the known and the hidden problem instances, which in respect gave our team the first position in all tracks of the INRC-2010 competition.     

A branch-and-price approach to the feeder network design problem

In this paper we consider the problem of designing a container liner shipping feeder network. The designer has to choose which port to serve during many rotations that start and end at a central hub. Many operational characteristics are considered, such as variable leg-by-leg speeds and cargo transit times. Realistic instances are generated from the LinerLib benchmark suite. The problem is solved with a branch-and-price algorithm, which can solve most instances to optimality within one hour. The results also provide insights on the cost structure and desirable features of optimal routes. These insights were obtained by means of an analysis where scenarios are generated varying internal and external conditions, such as fuel costs and port demands.     

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.     

Local search neighbourhoods for dealing with a novel nurse rostering model

A novel nurse rostering model is developed to represent real world problem instances more accurately. The proposed model is generic in the sense that it allows modelling of essentially different problem instances. Novel local search neighbourhoods are implemented to take advantage of the problem properties represented by the model. These neighbourhoods are used in a variable neighbourhood search and in an adaptive large neighbourhood search algorithm. The performance of the solution method is evaluated empirically on real world data. The proposed model is open to further extensions for covering personnel planning problems in different sectors and countries.     

An exact solution framework for the minimum cost dominating tree problem

The minimum cost dominating tree problem is a recently introduced NP-hard problem, which consists of finding a tree of minimal cost in a given graph, such that for every node of the graph, the node or one of its neighbours is in the tree. We present an exact solution framework combining a primal–dual heuristic with a branch-and-cut approach based on a transformation of the problem into a Steiner arborescence problem with an additional constraint. The effectiveness of our approach is evaluated on testbeds proposed in literature containing instances with up to 500 nodes. Our framework manages to solve all but four instances from literature to proven optimality within 3 h (most of them in a few seconds). We provide optimal solution values for 69 instances from literature for which the optimal solution was previously unknown.     

A combinatorial algorithm for the TDMA message scheduling problem

In this paper, we introduce a combinatorial algorithm for the message scheduling problem on Time Division Multiple Access (TDMA) networks. In TDMA networks, time is divided in to slots in which messages are scheduled. The frame length is defined as the total number of slots required for all stations to broadcast without message collisions. The objective is to provide a broadcast schedule of minimum frame length which also provides the maximum throughput. This problem is known to be -hard, thus efficient heuristics are needed to provide solutions to real-world instances. We present a two-phase algorithm which exploits the combinatorial structure of the problem in order to provide high quality solutions. The first phase finds a feasible frame length in which the throughput is maximized in phase two. Computational results are provided and compared with other heuristics in the literature as well as to the optimal solutions found using a commercial integer programming solver. Experiments on 63 benchmark instances show that the proposed method is able to provide optimal frame lengths for all cases with near optimal throughput.