Skip to main content

Research Repository

Advanced Search

Extended decomposition for mixed integer programming to solve a workforce scheduling and routing problem

Laesanklang, Wasakorn; Pinheiro, Rodrigo Lankaites; Algethami, Haneen; Landa-Silva, Dario

Authors

Wasakorn Laesanklang

Rodrigo Lankaites Pinheiro

Haneen Algethami

Profile Image

DARIO LANDA SILVA DARIO.LANDASILVA@NOTTINGHAM.AC.UK
Professor of Computational Optimisation



Contributors

Dominique de Werra
Editor

Greg H. Parlier
Editor

Bego�a Vitoriano
Editor

Abstract

© Springer International Publishing Switzerland 2015. We propose an approach based on mixed integer programming (MIP) with decomposition to solve a workforce scheduling and routing problem, in which a set of workers should be assigned to tasks that are distributed across different geographical locations. We present a mixed integer programming model that incorporates important real-world features of the problem such as defined geographical regions and flexibility in the workers’ availability. We decompose the problem based on geographical areas. The quality of the overall solution is affected by the ordering in which the sub-problems are tackled. Hence, we investigate different ordering strategies to solve the sub-problems. We also use a procedure to have additional workforce from neighbouring regions and this helps to improve results in some instances. We also developed a genetic algorithm to compare the results produced by the decomposition methods. Our experimental results show that although the decomposition method does not always outperform the genetic algorithm, it finds high quality solutions in practical computational times using an exact optimization method.

Citation

Laesanklang, W., Pinheiro, R. L., Algethami, H., & Landa-Silva, D. (2015). Extended decomposition for mixed integer programming to solve a workforce scheduling and routing problem. In D. D. Werra, G. H. Parlier, & B. Vitoriano (Eds.), Operations research and enterprise systems: 4th International Conference, ICORES 2015, Lisbon, Portugal, January 10-12, 2015: revised selected papers (191–211). https://doi.org/10.1007/978-3-319-27680-9_12

Conference Name 4th International Conference, ICORES 2015
Conference Location Lisbon, Portugal
Start Date Jan 10, 2015
End Date Jan 12, 2015
Online Publication Date Dec 14, 2015
Publication Date Dec 16, 2015
Deposit Date Jan 21, 2016
Publicly Available Date Mar 29, 2024
Publisher Springer Verlag
Peer Reviewed Peer Reviewed
Issue 577
Pages 191–211
Series Title Communications in computer and information science
Series ISSN 1865-0937
Book Title Operations research and enterprise systems: 4th International Conference, ICORES 2015, Lisbon, Portugal, January 10-12, 2015: revised selected papers
ISBN 9783319276793
DOI https://doi.org/10.1007/978-3-319-27680-9_12
Keywords personnel scheduling, vehicle routing, exact algorithms, mathematical programming, genetic algorithms
Public URL https://nottingham-repository.worktribe.com/output/769320
Publisher URL http://link.springer.com/chapter/10.1007%2F978-3-319-27680-9_12