Skip to Main content Skip to Navigation
Conference papers

The Workforce Routing and Scheduling Problem: solving real-world Instances

Gabriel Volte 1 Chloé Desdouits Rodolphe Giroudeau 1
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download
Contributor : Isabelle Gouat <>
Submitted on : Wednesday, July 24, 2019 - 2:45:35 PM
Last modification on : Thursday, July 25, 2019 - 1:30:24 PM


INOC2019 60-65.pdf
Files produced by the author(s)


Distributed under a Creative Commons Attribution - NonCommercial - NoDerivatives 4.0 International License




Gabriel Volte, Chloé Desdouits, Rodolphe Giroudeau. The Workforce Routing and Scheduling Problem: solving real-world Instances. INOC: International Network Optimization Conference, Jun 2019, Avignon, France. pp.60-65, ⟨10.5441/002/inoc.2019.12⟩. ⟨lirmm-02193442⟩



Record views


Files downloads