An investigation of heuristic decomposition to tackle workforce scheduling and routing with time-dependent activities constraints
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 d...
| Main Authors: | , , |
|---|---|
| Format: | Book Section |
| Published: |
Springer
2017
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/41537/ |
| _version_ | 1848796297656532992 |
|---|---|
| author | Laesanklang, Wasakorn Landa-Silva, Dario Castillo-Salazar, J. Arturo |
| author_facet | Laesanklang, Wasakorn Landa-Silva, Dario Castillo-Salazar, J. Arturo |
| author_sort | Laesanklang, Wasakorn |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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 con ict repair (RDCR) and it consists of repeatedly applying a phase of problem decomposition and sub-problem solving, followed by a phase dedicated to con ict 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 sub-problem 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 diffcult 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 accected 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. |
| first_indexed | 2025-11-14T19:45:45Z |
| format | Book Section |
| id | nottingham-41537 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:45:45Z |
| publishDate | 2017 |
| publisher | Springer |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-415372020-05-04T18:34:40Z https://eprints.nottingham.ac.uk/41537/ An investigation of heuristic decomposition to tackle workforce scheduling and routing with time-dependent activities constraints Laesanklang, Wasakorn Landa-Silva, Dario Castillo-Salazar, J. Arturo 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 con ict repair (RDCR) and it consists of repeatedly applying a phase of problem decomposition and sub-problem solving, followed by a phase dedicated to con ict 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 sub-problem 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 diffcult 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 accected 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. Springer 2017-02-15 Book Section PeerReviewed Laesanklang, Wasakorn, Landa-Silva, Dario and Castillo-Salazar, J. Arturo (2017) An investigation of heuristic decomposition to tackle workforce scheduling and routing with time-dependent activities constraints. In: Operations research and enterprise systems. Communications in Computer and Information Science (695). Springer, Cham, pp. 239-260. ISBN 9783319539829 workforce scheduling and routing problem time-dependent activities constraints mixed integer programming problem decomposition https://link.springer.com/chapter/10.1007/978-3-319-53982-9_14 doi:10.1007/978-3-319-53982-9 doi:10.1007/978-3-319-53982-9 |
| spellingShingle | workforce scheduling and routing problem time-dependent activities constraints mixed integer programming problem decomposition Laesanklang, Wasakorn Landa-Silva, Dario Castillo-Salazar, J. Arturo An investigation of heuristic decomposition to tackle workforce scheduling and routing with time-dependent activities constraints |
| title | An investigation of heuristic decomposition to tackle workforce scheduling and routing with time-dependent activities constraints |
| title_full | An investigation of heuristic decomposition to tackle workforce scheduling and routing with time-dependent activities constraints |
| title_fullStr | An investigation of heuristic decomposition to tackle workforce scheduling and routing with time-dependent activities constraints |
| title_full_unstemmed | An investigation of heuristic decomposition to tackle workforce scheduling and routing with time-dependent activities constraints |
| title_short | An investigation of heuristic decomposition to tackle workforce scheduling and routing with time-dependent activities constraints |
| title_sort | investigation of heuristic decomposition to tackle workforce scheduling and routing with time-dependent activities constraints |
| topic | workforce scheduling and routing problem time-dependent activities constraints mixed integer programming problem decomposition |
| url | https://eprints.nottingham.ac.uk/41537/ https://eprints.nottingham.ac.uk/41537/ https://eprints.nottingham.ac.uk/41537/ |