The Workforce Routing and Scheduling Problem: solving real-world Instances - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2019

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

Gabriel Volte
  • Function : Author
  • PersonId : 1051351
Chloé Desdouits

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.
Fichier principal
Vignette du fichier
INOC2019 60-65.pdf (721.18 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-02193442 , version 1 (24-07-2019)

Licence

Attribution - NonCommercial - NoDerivatives

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook X LinkedIn More