Extended decomposition for mixed integer programming to solve a workforce scheduling and routing problem
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 tha...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Book Section |
| Published: |
Springer
2015
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/31298/ |
| _version_ | 1848794171084636160 |
|---|---|
| author | Laesanklang, Wasakorn Pinheiro, Rodrigo Lankaites Algethami, Haneen Landa-Silva, Dario |
| author2 | Werra, Dominique de |
| author_facet | Werra, Dominique de Laesanklang, Wasakorn Pinheiro, Rodrigo Lankaites Algethami, Haneen Landa-Silva, Dario |
| author_sort | Laesanklang, Wasakorn |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T19:11:57Z |
| format | Book Section |
| id | nottingham-31298 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:11:57Z |
| publishDate | 2015 |
| publisher | Springer |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-312982020-05-04T17:26:49Z https://eprints.nottingham.ac.uk/31298/ Extended decomposition for mixed integer programming to solve a workforce scheduling and routing problem Laesanklang, Wasakorn Pinheiro, Rodrigo Lankaites Algethami, Haneen Landa-Silva, Dario 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. Springer Werra, Dominique de Parlier, Greg H. Vitoriano, Begoña 2015-12-15 Book Section PeerReviewed Laesanklang, Wasakorn, Pinheiro, Rodrigo Lankaites, Algethami, Haneen and Landa-Silva, Dario (2015) Extended decomposition for mixed integer programming to solve a workforce scheduling and routing problem. In: Operations research and enterprise systems: 4th International Conference, ICORES 2015, Lisbon, Portugal, January 10-12, 2015: revised selected papers. Communications in computer and information science (577). Springer, Cham, pp. 191-211. ISBN 9783319276793 personnel scheduling vehicle routing exact algorithms mathematical programming genetic algorithms http://link.springer.com/chapter/10.1007%2F978-3-319-27680-9_12 doi:10.1007/978-3-319-27680-9_12 doi:10.1007/978-3-319-27680-9_12 |
| spellingShingle | personnel scheduling vehicle routing exact algorithms mathematical programming genetic algorithms Laesanklang, Wasakorn Pinheiro, Rodrigo Lankaites Algethami, Haneen Landa-Silva, Dario Extended decomposition for mixed integer programming to solve a workforce scheduling and routing problem |
| title | Extended decomposition for mixed integer programming to solve a workforce scheduling and routing problem |
| title_full | Extended decomposition for mixed integer programming to solve a workforce scheduling and routing problem |
| title_fullStr | Extended decomposition for mixed integer programming to solve a workforce scheduling and routing problem |
| title_full_unstemmed | Extended decomposition for mixed integer programming to solve a workforce scheduling and routing problem |
| title_short | Extended decomposition for mixed integer programming to solve a workforce scheduling and routing problem |
| title_sort | extended decomposition for mixed integer programming to solve a workforce scheduling and routing problem |
| topic | personnel scheduling vehicle routing exact algorithms mathematical programming genetic algorithms |
| url | https://eprints.nottingham.ac.uk/31298/ https://eprints.nottingham.ac.uk/31298/ https://eprints.nottingham.ac.uk/31298/ |