Program > By author > Nicod Jean-Marc

Biosolver: a VRPTW solver for the nurses tour scheduling problem with hard time constraints
Stéphane Chrétien  1, 2@  , Julien Coupey  3, *@  , Jean-Marc Nicod  4@  , Christophe Varnier  4@  
1 : Laboratoire de Mathématiques  (LM-Besançon)  -  Website
CNRS : UMR6623, Université de Franche-Comté
UFR Sciences et techniques 16 route de Gray 25 030 Besançon cedex -  France
2 : National Physical Laboratory  (NPL)  -  Website
Hampton Road Teddington Middlesex TW11 0LW -  United Kingdom
3 : FEMTO-ST Institute  -  Website
CNRS : UMR6174, Université de Technologie de Belfort-Montbeliard, Ecole Nationale Supérieure de Mécanique et des Microtechniques, Université de Franche-Comté
32 avenue de l'Observatoire - 25044 BESANCON -  France
4 : Département Automatique et Systèmes Micro-Macatroniques  (FEMTO-ST/AS2M)  -  Website
Université Technologique Belfort-Montbéliard, Ecole Nationale Supérieure de Mécanique et des Microtechniques, Université de Franche-Comté, CNRS : UMR6174
24, rue Alain Savary 25000 - BESANCON -  France
* : Corresponding author

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.


Online user: 1