Decomposition techniques with mixed integer programming and heuristics for home healthcare planning
We tackle home healthcare planning scenarios in the UK using decomposition methods that incorporate mixed integer programming solvers and heuristics. Home healthcare planning is a difficult problem that integrates aspects from scheduling and routing. Solving real-world size instances of these proble...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Published: |
Springer
2017
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/37904/ |
| _version_ | 1848795557399625728 |
|---|---|
| author | Laesanklang, Wasakorn Landa-Silva, Dario |
| author_facet | Laesanklang, Wasakorn Landa-Silva, Dario |
| author_sort | Laesanklang, Wasakorn |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | We tackle home healthcare planning scenarios in the UK using decomposition methods that incorporate mixed integer programming solvers and heuristics. Home healthcare planning is a difficult problem that integrates aspects from scheduling and routing. Solving real-world size instances of these problems still presents a significant challenge to modern exact optimization solvers. Nevertheless, we propose decomposition techniques to harness the power of such solvers while still offering a practical approach to produce high-quality solutions to real-world problem instances. We first decompose the problem into several smaller sub-problems. Next, mixed integer programming and/or heuristics are used to tackle the sub-problems. Finally, the sub-problem solutions are combined into a single valid solution for the whole problem. The different decomposition methods differ in the way in which subproblems are generated and the way in which conflicting assignments are tackled (i.e. avoided or repaired). We present the results obtained by the proposed decomposition methods and compare them to solutions obtained with other methods. In addition, we conduct a study that reveals how the different steps in the proposed method contribute to those results. The main contribution of this paper is a better understanding of effective ways to combine mixed integer programming within effective decomposition methods to solve real-world instances of home healthcare planning problems in practical computation time. |
| first_indexed | 2025-11-14T19:33:59Z |
| format | Article |
| id | nottingham-37904 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T19:33:59Z |
| publishDate | 2017 |
| publisher | Springer |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-379042020-05-04T19:09:53Z https://eprints.nottingham.ac.uk/37904/ Decomposition techniques with mixed integer programming and heuristics for home healthcare planning Laesanklang, Wasakorn Landa-Silva, Dario We tackle home healthcare planning scenarios in the UK using decomposition methods that incorporate mixed integer programming solvers and heuristics. Home healthcare planning is a difficult problem that integrates aspects from scheduling and routing. Solving real-world size instances of these problems still presents a significant challenge to modern exact optimization solvers. Nevertheless, we propose decomposition techniques to harness the power of such solvers while still offering a practical approach to produce high-quality solutions to real-world problem instances. We first decompose the problem into several smaller sub-problems. Next, mixed integer programming and/or heuristics are used to tackle the sub-problems. Finally, the sub-problem solutions are combined into a single valid solution for the whole problem. The different decomposition methods differ in the way in which subproblems are generated and the way in which conflicting assignments are tackled (i.e. avoided or repaired). We present the results obtained by the proposed decomposition methods and compare them to solutions obtained with other methods. In addition, we conduct a study that reveals how the different steps in the proposed method contribute to those results. The main contribution of this paper is a better understanding of effective ways to combine mixed integer programming within effective decomposition methods to solve real-world instances of home healthcare planning problems in practical computation time. Springer 2017-09-30 Article PeerReviewed Laesanklang, Wasakorn and Landa-Silva, Dario (2017) Decomposition techniques with mixed integer programming and heuristics for home healthcare planning. Annals of Operations Research, 256 (1). pp. 93-127. ISSN 1572-9338 Home healthcare planning; workforce scheduling and routing; mixed integer programming; problem decomposition; heuristic decomposition http://link.springer.com/article/10.1007%2Fs10479-016-2352-8 doi:10.1007/s10479-016-2352-8 doi:10.1007/s10479-016-2352-8 |
| spellingShingle | Home healthcare planning; workforce scheduling and routing; mixed integer programming; problem decomposition; heuristic decomposition Laesanklang, Wasakorn Landa-Silva, Dario Decomposition techniques with mixed integer programming and heuristics for home healthcare planning |
| title | Decomposition techniques with mixed integer programming and heuristics for home healthcare planning |
| title_full | Decomposition techniques with mixed integer programming and heuristics for home healthcare planning |
| title_fullStr | Decomposition techniques with mixed integer programming and heuristics for home healthcare planning |
| title_full_unstemmed | Decomposition techniques with mixed integer programming and heuristics for home healthcare planning |
| title_short | Decomposition techniques with mixed integer programming and heuristics for home healthcare planning |
| title_sort | decomposition techniques with mixed integer programming and heuristics for home healthcare planning |
| topic | Home healthcare planning; workforce scheduling and routing; mixed integer programming; problem decomposition; heuristic decomposition |
| url | https://eprints.nottingham.ac.uk/37904/ https://eprints.nottingham.ac.uk/37904/ https://eprints.nottingham.ac.uk/37904/ |