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 metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02193442
Contributor : Isabelle Gouat <>
Submitted on : Wednesday, July 24, 2019 - 2:45:35 PM
Last modification on : Thursday, July 25, 2019 - 1:30:24 PM

File

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

Licence


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

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

65

Files downloads

49