Laesanklang Wasakorn, Landa-Silva Dario
ASAP Research Group, School of Computer Science, The University of Nottingham, Jubilee Campus, Wollaton Road, Nottingham, NG8 1BB UK.
Ann Oper Res. 2017;256(1):93-127. doi: 10.1007/s10479-016-2352-8. Epub 2016 Oct 24.
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 sub-problems 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.
我们运用结合了混合整数规划求解器和启发式算法的分解方法，来处理英国的家庭医疗保健规划场景。家庭医疗保健规划是一个难题，它整合了调度和路径规划等方面。对于现代精确优化求解器而言，解决这些问题的实际规模实例仍然是一项重大挑战。尽管如此，我们提出了分解技术，以利用此类求解器的强大功能，同时仍然提供一种实用的方法，为实际问题实例生成高质量的解决方案。我们首先将问题分解为几个较小的子问题。接下来，使用混合整数规划和/或启发式算法来处理这些子问题。最后，将子问题的解决方案组合成整个问题的一个有效解决方案。不同的分解方法在生成子问题的方式以及处理冲突任务分配的方式（即避免或修复）上有所不同。我们展示了所提出的分解方法获得的结果，并将其与其他方法获得的解决方案进行比较。此外，我们进行了一项研究，揭示了所提出方法中的不同步骤是如何对这些结果产生影响的。本文的主要贡献在于更好地理解了在有效分解方法中结合混合整数规划的有效方式，以便在实际计算时间内解决家庭医疗保健规划问题的实际实例。
