干擾管理在護工調(diào)度與路徑規(guī)劃的應用綜述

黃錦昌

隨著人口老齡化加深，居家養(yǎng)老醫(yī)護資源緊缺，不確定性因素對居家養(yǎng)老服務質(zhì)量的影響越來越明顯。在對居家養(yǎng)老護工調(diào)度與路徑規(guī)劃問題的相關研究進行評述的基礎上，著重討論了干擾管理方法在該問題中的應用價值和研究情況，為后續(xù)研究提供文獻基礎。

隨著我國老齡化程度的不斷加深，積極應對人口老齡化已經(jīng)上升為國家戰(zhàn)略。國家發(fā)改委近期表示，預計“十四五”我國將進入中度老齡化階段?？梢灶A見的是，在未來幾年，作為“以居家為基礎、社區(qū)為依托、機構為補充、醫(yī)養(yǎng)相結合”的養(yǎng)老服務體系的基礎，居家養(yǎng)老服務需求將會持續(xù)穩(wěn)步上升。本文提到的居家養(yǎng)老服務是指政府和社會力量依托社區(qū)，為居家的老年人提供生活照料、家政服務、康復護理和精神慰藉等方面服務的一種服務形式。

由于居家養(yǎng)老服務需要護理人員上門提供服務，但居家養(yǎng)老醫(yī)護資源緊缺的現(xiàn)狀仍沒有得到很好的解決，居家養(yǎng)老服務機構存在著護工能力未被充分利用、客戶服務要求不能被滿足等問題。另外，在居家養(yǎng)老服務機構日常運營中，管理者通常為護理人員分配好了客戶以及設計了對應的訪問路線。但在實際執(zhí)行中，可能會發(fā)生各種突發(fā)事件（如道路阻塞等），導致客戶不能服務或延遲服務，使得原計劃不可行。而干擾管理就是研究如何處理干擾，使得其對系統(tǒng)的副作用最小化。因此將干擾管理思想應用于居家養(yǎng)老護工調(diào)度與路徑規(guī)劃問題中，有利于在干擾發(fā)生時及時合理調(diào)整原計劃，為居家養(yǎng)老服務機構提供科學的護工調(diào)度決策方案，使干擾帶來的副作用最小化，提高服務的效率與滿意度。

對居家養(yǎng)老護工調(diào)度與路徑規(guī)劃問題（Home Care Scheduling and Routing Problem，HCSRP）的研究早期以確定性情況為主，后來才逐漸增加考慮不確定的因素，因此本文雖然主要探討干擾管理在HCSRP問題的應用，但仍將從確定性和非確定性兩種情況進行討論。

確定情況下的HCSRP研究現(xiàn)狀

HCSRP問題是在中期（如一周）或短期（如一天）的計劃期內(nèi)考慮的，因此本小節(jié)將從這兩個方面闡述。

Begur等（1997）關注每周5天的護士排班問題，并開發(fā)了一個基于一些簡單啟發(fā)式算法的空間決策支持系統(tǒng)來解決這個問題。Nickel等（2012）使用不同的元啟發(fā)式算法（如自適應大鄰域搜索和禁忌搜索）結合約束規(guī)劃的方法來解決每周HCSRP問題，該問題將提供服務的護士人數(shù)最小化作為目標函數(shù)的一部分。An等（2012）研究了不同患者的就診間隔可能出現(xiàn)不同的HCSRP，并提出了兩階段啟發(fā)式方法求解問題。Bard等（2014）和Shao等（2012）設計了一個順序貪婪隨機自適應搜索程序（GRASP）、一個并行GRASP和一個分支定價集合分割算法來解決每周護理人員的路徑和調(diào)度問題。Trautsamwieser等（2014）考慮額外的工作時間規(guī)定（如休息時間、每天的最大工作時間等），并將護士每日以及每周的休息時間轉(zhuǎn)化為每周HCSRP問題，提出了一種分支定價切割求解方法，以便變鄰域搜索（VNS）算法的解為上界精確求解問題。Cappanera等（2015）使用模式建模設備來聯(lián)合協(xié)調(diào)分配、調(diào)度和路由決策。在他們的問題所考慮的計劃范圍內(nèi)，最多可以為每個患者分配給定數(shù)量的操作員。該方法通過分析三種模式生成策略來生成模式集，利用商業(yè)優(yōu)化軟件求解由模式集構造的整數(shù)線性規(guī)劃模型。Maya Duque等（2015）將每周HCSRP制定為一個雙目標（即最大化服務水平和最小化旅行距離）數(shù)學程序，該程序基于集合分割公式，并設計了一個兩階段的解決方法來有效地解決問題。Liu等（2014）提出了一種可行和不可行局部搜索的禁忌搜索啟發(fā)式算法，用于家庭健康護理問題中的周期性車輛路徑問題。

上述論文研究中期計劃周期中的HCSRP，而以下論文則考慮短期計劃周期中的HCSRP。Bertels等（2006）應用禁忌搜索啟發(fā)式算法、模擬退火啟發(fā)式算法和約束規(guī)劃，為護士找到一個可行的工作計劃，該計劃滿足關于居家護理的各種硬約束和軟約束以及各種偏好約束。他們考慮了病人對特定護士的偏好以及護士對特定病人的偏好。同時，他們?yōu)閷嶋H應用開發(fā)了優(yōu)化軟件PARPAP。Eveborn等（2006）提出了一種重復匹配算法，將約束和軟目標納入HCSRP，以求出護理人員的上門服務計劃。他們定義了客戶的偏好護工。此外，他們還開發(fā)了一個決策支持系統(tǒng)LAPS CARE來幫助調(diào)度人員。Akjiratikarl等（2007）設計了粒子群優(yōu)化算法來解決日常HCSRP問題。Rasmussen等（2012）使用分支定價算法求解HCSRP，其中包含軟偏好約束（即將護工就診偏好的最大化作為目標函數(shù)的一部分）和服務開始時間之間的時間依賴性。此外，他們使用聚類技術來加速分支定價算法。Mankowska等（2014）提出了一種自適應變鄰域搜索算法來解決考慮相互依賴服務和護工病人匹配性的HCSRP問題。Du等（2017）在考慮患者優(yōu)先級和時間窗的情況下，提出了遺傳算法求解HCSRP問題。Liu等（2017）構建了考慮午休需求和護工病人匹配性的HCSRP模型，并開發(fā)了一個分支定價算法來精確解決問題。

考慮不確定性因素的HCSRP研究現(xiàn)狀

由于服務過程中的不確定因素會大大提高護工調(diào)度的難度和降低計劃執(zhí)行的可行性，對時效性要求較高的服務內(nèi)容（如胰島素注射等）影響極大。同時，護理資源越發(fā)緊缺，近年來越來越多的文獻開始研究如何處理HCSRP問題中的不確定因素。Yuan等（2015）設計了一個針對隨機服務時間和技能需求的HCSRP的分支定價算法。R.J.Kuo等（2016）研究在不斷接收訂單的情況下，考慮模糊服務時長、動態(tài)客戶地點等因素，上門服務公司如何決定服務的順序，以最大化服務客戶的數(shù)量和最小化客戶的等待時間的問題，并設計在蟻群算法（ACO）上改進的蟻群系統(tǒng)（ACS）算法求解問題。Cappanera P等（2017）首次將魯棒框架應用于居家護理問題，其考慮了需求不確定（包括增加和取消）的情況，提出用非標準基數(shù)約束魯棒方法建立模型。Shi Y等（2018）在HCSRP問題中首個同時考慮取送生物樣本以及不確定旅行和服務時間，其以最小化總成本為目標函數(shù)，建立帶資源約束的隨機規(guī)劃模型。Restrepo M I等（2019）首次提出集成人員配置和調(diào)度決策的優(yōu)化方法，使用上下文無關文法建立長期調(diào)度時間表，以應對不確定需求。其提出兩階段隨機規(guī)劃模型：第一階段決策對應于地理區(qū)域護理人員的配置和日程安排；第二階段的決定涉及臨時將護工重新分配到鄰近地區(qū)，聯(lián)系護工在休息日工作，以及允許需求不足和過度覆蓋。Shi Y等（2019）考慮不確定旅行時間和服務時間，從魯棒優(yōu)化角度研究HCSRP問題，并分別設計模擬退火算法、可變鄰域搜索算法、禁忌搜索算法求解問題。Du G等（2019）研究突發(fā)事件下的實時HHC護理人員調(diào)度問題，考慮時間窗約束、多個護理人員、多服務類型，以最小化所有醫(yī)務人員的總周轉(zhuǎn)時間和患者的總體滿意度差值為目標，提出改進的模因算法求解問題。Demirbilek M等（2019）研究單計劃周期新病人需求按指數(shù)分布隨機到達的情況，以最大化計劃周期內(nèi)病人的服務次數(shù)為目標，提出基于場景的算法（SBA）求解問題。

目前在居家養(yǎng)老調(diào)度領域考慮不確定性的研究中，很少有文獻使用干擾管理的方法。干擾管理是一種實時處理干擾或意外事件的方法，它已被廣泛用于解決各種優(yōu)化問題。Wang等（2012）提出了利用干擾恢復模型對帶時間窗的VRP問題進行建模，并設計了一種嵌套劃分方法進行求解。Kiefer等（2016）針對公共交通系統(tǒng)的嚴重故障，構建了一個混合整數(shù)規(guī)劃模型，并用商業(yè)優(yōu)化軟件CPLEX進行了求解。Zhang等（2016）研究了泊位計劃恢復問題，并使用基于詞典優(yōu)化的方法來解決該問題。Dollevoet等（2017）提出了一個迭代框架，用于重新安排與鐵路干擾管理相關的時間表、機車車輛和乘務員。Marla等（2017）提出了綜合飛機和乘客恢復的精確和近似模型，以及權衡延誤和燃油消耗的飛行計劃。Wu等（2017）采用整數(shù)規(guī)劃迭代不動點的方法來獲得可行的飛行路線，以重新分配飛機的飛行路線來應對一架飛機的停飛。Yuan B等（2017）對護工實時調(diào)度過程中出現(xiàn)的意外事件（包括客戶新需求、客戶服務取消、客戶時間窗改變）進行了干擾管理，以最小化對病人、護工、護理企業(yè)的偏離為目標函數(shù)建立模型，并使用基于成本記錄機制的禁忌搜索算法求解模型。

結 語

目前在居家養(yǎng)老調(diào)度領域的研究主要以國外發(fā)達國家為主，國內(nèi)的研究近年才逐漸增多，主要因為國外現(xiàn)代養(yǎng)老服務市場發(fā)展較早，且更早更嚴重的社會老齡化問題都迫使其進行更多更深入的研究，這也為我國提供了寶貴的發(fā)展經(jīng)驗。針對HCSRP問題中的不確定因素，學者們提出了隨機規(guī)劃模型、魯棒優(yōu)化模型等解決方法，但這些方法要么不能實時處理突發(fā)事件，要么在處理突發(fā)事件的時候?qū)υ媱澑膭舆^大，相當于拋棄原來的計劃又重新做了另外一個。干擾管理方法的應用可以有效避免以上問題，獲得令人滿意的計劃，其對于HCSRP復雜的系統(tǒng)調(diào)整問題具有很強的適應性。

（華南理工大學）

參考文獻：

[1]資元星. 區(qū)分任務緊急性的居家養(yǎng)老預約調(diào)度與路徑規(guī)劃問題研究[D].廣州：華南理工大學， 2019.

[2]胡祥培， 丁秋雷， 張漪，等. 干擾管理研究評述[J]. 管理科學， 2007.

[3]Cappanera P ， Scutella M G， Nervi F， et al. Demand uncertainty in Robust Home Care Optimization[J]. Omega-international Journal of Management Science， 2017： 95-110.

[4]Restrepo M I， Rousseau L， Vallee J， et al. Home Healthcare Integrated Staffing and Scheduling[J]. Omega-international Journal of Management Science， 2019.

[5]Shi Y， Boudouh T， Grunder O. A robust optimization for a home health care routing and scheduling problem with consideration of uncertain travel and service times[J]. Transportation Research Part E： Logistics and Transportation Review， 2019， 128： 52-95.