TY - GEN
T1 - An investigation of heuristic decomposition to tackle workforce scheduling and routing with time-dependent activities constraints
AU - Laesanklang, Wasakorn
AU - Landa-Silva, Dario
AU - Castillo-Salazar, J. Arturo
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017
Y1 - 2017
N2 - This paper presents an investigation into the application of heuristic decomposition and mixed-integer programming to tackle workforce scheduling and routing problems (WSRP) that involve timedependent activities constraints. These constraints refer to time-wise dependencies between activities. The decomposition method investigated here is called repeated decomposition with conflict repair (RDCR) and it consists of repeatedly applying a phase of problem decomposition and sub-problem solving, followed by a phase dedicated to conflict repair. In order to deal with the time-dependent activities constraints, the problem decomposition puts all activities associated to the same location and their dependent activities in the same sub-problem. This is to guarantee the satisfaction of time-dependent activities constraints as each subproblem is solved exactly with an exact solver. Once the assignments are made, the time windows of dependent activities are fixed even if those activities are subject to the repair phase. The paper presents an experimental study to assess the performance of the decomposition method when compared to a tailored greedy heuristic. Results show that the proposed RDCR is an effective approach to harness the power of mixed integer programming solvers to tackle the difficult and highly constrained WSRP in practical computational time. Also, an analysis is conducted in order to understand how the performance of the different solution methods (the decomposition, the tailored heuristic and the MIP solver) is affected by the size of the problem instances and other features of the problem. The paper concludes by making some recommendations on the type of method that could be more suitable for different problem sizes.
AB - This paper presents an investigation into the application of heuristic decomposition and mixed-integer programming to tackle workforce scheduling and routing problems (WSRP) that involve timedependent activities constraints. These constraints refer to time-wise dependencies between activities. The decomposition method investigated here is called repeated decomposition with conflict repair (RDCR) and it consists of repeatedly applying a phase of problem decomposition and sub-problem solving, followed by a phase dedicated to conflict repair. In order to deal with the time-dependent activities constraints, the problem decomposition puts all activities associated to the same location and their dependent activities in the same sub-problem. This is to guarantee the satisfaction of time-dependent activities constraints as each subproblem is solved exactly with an exact solver. Once the assignments are made, the time windows of dependent activities are fixed even if those activities are subject to the repair phase. The paper presents an experimental study to assess the performance of the decomposition method when compared to a tailored greedy heuristic. Results show that the proposed RDCR is an effective approach to harness the power of mixed integer programming solvers to tackle the difficult and highly constrained WSRP in practical computational time. Also, an analysis is conducted in order to understand how the performance of the different solution methods (the decomposition, the tailored heuristic and the MIP solver) is affected by the size of the problem instances and other features of the problem. The paper concludes by making some recommendations on the type of method that could be more suitable for different problem sizes.
KW - Mixed integer programming
KW - Problem decomposition
KW - Timedependent activities constraints
KW - Workforce scheduling and routing problem
UR - http://www.scopus.com/inward/record.url?scp=85013498401&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-53982-9_14
DO - 10.1007/978-3-319-53982-9_14
M3 - Conference contribution
AN - SCOPUS:85013498401
SN - 9783319539812
T3 - Communications in Computer and Information Science
SP - 239
EP - 260
BT - Operations Research and Enterprise Systems - 5th International Conference, ICORES 2016, Revised Selected Papers
A2 - Vitoriano, Begona
A2 - Parlier, Greg H.
PB - Springer Verlag
T2 - 5th International Conference on Operations Research and Enterprise Systems, ICORES 2016
Y2 - 23 February 2016 through 25 February 2016
ER -