Lusby Richard Martin, Schwierz Martin, Range Troels Martin, Larsen Jesper
Department of Engineering Management, Produktionstorvet, Technical University of Denmark, Kongens Lyngby 2800, Denmark.
AMCS Denmark A/S, Hejrevej 34D, Copenhagen 2400, Denmark.
Artif Intell Med. 2016 Nov;74:21-31. doi: 10.1016/j.artmed.2016.10.002. Epub 2016 Nov 16.
The aim of this paper is to provide an improved method for solving the so-called dynamic patient admission scheduling (DPAS) problem. This is a complex scheduling problem that involves assigning a set of patients to hospital beds over a given time horizon in such a way that several quality measures reflecting patient comfort and treatment efficiency are maximized. Consideration must be given to uncertainty in the length of stays of patients as well as the possibility of emergency patients.
We develop an adaptive large neighborhood search (ALNS) procedure to solve the problem. This procedure utilizes a Simulated Annealing framework.
We thoroughly test the performance of the proposed ALNS approach on a set of 450 publicly available problem instances. A comparison with the current state-of-the-art indicates that the proposed methodology provides solutions that are of comparable quality for small and medium sized instances (up to 1000 patients); the two approaches provide solutions that differ in quality by approximately 1% on average. The ALNS procedure does, however, provide solutions in a much shorter time frame. On larger instances (between 1000-4000 patients) the improvement in solution quality by the ALNS procedure is substantial, approximately 3-14% on average, and as much as 22% on a single instance. The time taken to find such results is, however, in the worst case, a factor 12 longer on average than the time limit which is granted to the current state-of-the-art.
The proposed ALNS procedure is an efficient and flexible method for solving the DPAS problem.
本文旨在提供一种改进方法，以解决所谓的动态患者入院调度（DPAS）问题。这是一个复杂的调度问题，涉及在给定的时间范围内将一组患者分配到医院病床，使得反映患者舒适度和治疗效率的多个质量指标最大化。必须考虑患者住院时间的不确定性以及急诊患者的可能性。
我们开发了一种自适应大邻域搜索（ALNS）程序来解决该问题。此程序利用模拟退火框架。
我们在一组450个公开可用的问题实例上全面测试了所提出的ALNS方法的性能。与当前的先进方法相比，结果表明，对于中小型实例（最多1000名患者），所提出的方法提供的解决方案质量相当；两种方法提供的解决方案质量平均相差约1%。然而，ALNS程序确实能在更短的时间内提供解决方案。对于较大的实例（1000 - 4000名患者），ALNS程序在解决方案质量上有显著提高，平均约为3 - 14%，在单个实例上高达22%。然而，找到这些结果所需的时间在最坏情况下平均比当前先进方法的时间限制长12倍。
所提出的ALNS程序是解决DPAS问题的一种有效且灵活的方法。
