Vehicle routing and scheduling problems with interdependent routes arise when some services must be performed by at least two vehicles and temporal synchronization is thus required between the starting times of these services. These problems are often coupled with time window constraints in order to model various real-world applications such as pickup and delivery with transfers, cross-docking and home care scheduling. Interdependent routes in these applications can lead to large idle times for some drivers, unnecessarily lengthening their working hours. To remedy this unfairness, it is necessary to balance the duration of the drivers' routes. However, quickly evaluating duration-based equity functions for interdependent vehicle routes with time windows poses a significant computational challenge, particularly when the departure time of routes is flexible. This paper introduces models and algorithms to compute two well-known equity functions in flexible departure time settings: min-max and range minimization. We explore the challenges and algorithmic complexities of evaluating these functions both from a theoretical and an experimental viewpoint. The results of this paper enable the development of new heuristic methods to balance the workload of interdependent vehicle routes with time windows.

The reach of an arc in a network can intuitively be described as an indication of the maximum length of the shortest paths of the digraph that pass through this arc. This concept captures the natural hierarchy of any type of network, in an accurate and comprehensive manner. Traditional reach approximation algorithms compute upper bounds to these reaches and require computation of a partial shortest path tree rooted in all vertices of the network. Tailored for route computation enhancement, these methods yield exact reaches in the low reach spectrum, whereas higher reaches are kept set to infinity.

This paper presents a variable depth search for the nurse rostering problem. The algorithm works by chaining together single neighbourhood swaps into more effective compound moves. It achieves this by using heuristics to decide whether to continue extending a chain and which candidates to examine as the next potential link in the chain. Because end users vary in how long they are willing to wait for solutions, a particular goal of this research was to create an algorithm that accepts a user specified computational time limit and uses it effectively. When compared against previously published approaches the results show that the algorithm is very competitive.

A hyper-heuristic performs search over a set of other search mechanisms. During the search, it does not require any problem-dependent data. This structure makes hyper-heuristics problem-independent indirect search mechanisms. In this study, we propose a learning strategy to explore elite heuristic subsets for different phases of a search. For that purpose, we apply a number of hyper-heuristics with the proposed approach to a set of home care scheduling problem instances. The results show that the learning strategy increases the performance of the different hyper-heuristics by excluding some heuristics from the heuristic set over the tested problem instances.

Users of hospital personnel planning software cope with the complex task of translating their needs into several constraints of a very different nature and with differing cost parameters. We present a multi criteria evolutionary approach, which overcomes some of the practical difficulties that personnel schedulers in hospitals often face.

When applying evolutionary algorithms to difficult real-world problems, the fitness function routinely needs evaluating for a very high number of intermediary cases. The paper is concerned with real-world nurse rostering problems with highly constrained resources. We consider a particular approach, which allows for a quick evaluation and is general enough to deal with other kinds of resource planning problems with time-related constraints. The model developed for this approach handles the constraints in a modular way and the addition of new constraints is relatively straightforward. Simple constraints (such as those affecting the personal wishes of employees) and global constraints (such as balancing the workload among people) can be formulated easily using this approach. Our approach can also handle very complex time-related constraints as well as conditions that are related to previously planned work. Moreover, it provides clear feedback about violation of constraints. The approach has been implemented successfully in a nurse rostering program entitled "Plane" which is used in hospitals all over Belgium. It can tackle a high number of specific and modifiable constraints of a very different nature. The benefits from this approach (in terms of software requirements) are small memory use and a computationally simple, single evaluation function allowing for the simultaneous rostering of several hospital wards at the same time.