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

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

7 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationOperations Research and Enterprise Systems - 4th International Conference, ICORES 2015, Revised Selected Papers
EditorsDominique de Werra, Begoña Vitoriano, Greg H. Parlier
PublisherSpringer Verlag
Pages191-211
Number of pages21
ISBN (Print)9783319276793
DOIs
Publication statusPublished - 2015
Externally publishedYes
Event4th International Conference on Operations Research and Enterprise Systems, ICORES 2015 - Lisbon, Portugal
Duration: 10 Jan 201512 Jan 2015

Publication series

NameCommunications in Computer and Information Science
Volume577
ISSN (Print)1865-0929

Conference

Conference4th International Conference on Operations Research and Enterprise Systems, ICORES 2015
Country/TerritoryPortugal
CityLisbon
Period10/01/1512/01/15

Keywords

  • Genetic algorithm
  • Mixed integer programming
  • Problem decomposition
  • Routing problem
  • Workforce scheduling

Fingerprint

Dive into the research topics of 'Extended decomposition for mixed integer programming to solve a workforce scheduling and routing problem'. Together they form a unique fingerprint.

Cite this