TY - GEN
T1 - Extended decomposition for mixed integer programming to solve a workforce scheduling and routing problem
AU - Laesanklang, Wasakorn
AU - Pinheiro, Rodrigo Lankaites
AU - Algethami, Haneen
AU - Landa-Silva, Dario
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - 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.
AB - 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.
KW - Genetic algorithm
KW - Mixed integer programming
KW - Problem decomposition
KW - Routing problem
KW - Workforce scheduling
UR - http://www.scopus.com/inward/record.url?scp=84952051197&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-27680-9_12
DO - 10.1007/978-3-319-27680-9_12
M3 - Conference contribution
AN - SCOPUS:84952051197
SN - 9783319276793
T3 - Communications in Computer and Information Science
SP - 191
EP - 211
BT - Operations Research and Enterprise Systems - 4th International Conference, ICORES 2015, Revised Selected Papers
A2 - de Werra, Dominique
A2 - Vitoriano, Begoña
A2 - Parlier, Greg H.
PB - Springer Verlag
T2 - 4th International Conference on Operations Research and Enterprise Systems, ICORES 2015
Y2 - 10 January 2015 through 12 January 2015
ER -