Résumé
We propose an efficient method to solve a workforce routing and scheduling problem with working constraints, and a bounded execution time limit. This problem combines two fundamental problems in operations research: routing and scheduling. In such a context, we develop a column generation algorithm, as a set partitioning problem with side constraints, within a branch-and-price framework. The pricing sub-problem is an elementary shortest path with resource constraints modeled with constraint programming. In our branch-and-price framework, we first solve our problem using branch-and-price and a branch-and-bound strategy is proposed on the last restricted master problem, in order to obtain a feasible solution when the time limit is almost reached. However, we show that the developed method leads to better solutions than using constraint programming or large neighborhood search methods. We show the relevance of our method with various-size real instances.