Program > By author > Chrétien Stéphane

In the nurses tour scheduling problem, many blood samples are collected at the patients' respective locations. This problem is difficult because of the hard timing constraints which have to be imposed in order to route the samples to the laboratory before they get too corrupted for any reliable medical diagnosis. To comply with the ISO 15189 norm, those constraints imply a drastic need to monitor the return and travel times of the collected samples. Moreover, many laboratories have recently undertaken a significant grouping of their collection activities. As a result, the nurses tour scheduling problem is now often a large scale combinatorial optimization problem.

The Biosolver project aims at proposing a tool to provide reliable solutions to the VRPTW (Vehicle Routing Problem with Time Windows) variant resulting from our model of the nurses tour scheduling problem. The additional constraints applying on return and travel times have a strong impact on the characteristic features of the solutions -- often requiring multi-trips -- and are especially challenging for validity concerns.

Our strategy uses a refined tuning of Solomons heuristics and a stochastic search based on Metropolis-Hastings' algorithm. The solver handles actual road topography and is used in production on a daily basis, providing solutions roughly improving by 30% over human-planned travel times. Our approach enjoys fast convergence with low variance in the solution quality, a crucial aspect for industrial use. Finally, performance is shown to compare well on usual VRPTW benchmarks although the approach is not specifically taylored for these problems.