貪心算法在智能導檢中的應用研究

付 冰，周作建，張維芯

（1.南京中醫藥大學人工智能與信息技術學院，江蘇 南京 210023；2.江蘇省中醫院信息數據中心，江蘇 南京 210004）

0 引言

隨著醫學模式向預防為主的健康管理方向轉移，人們愈發重視早期篩查慢性病，全社會強調為實施健康中國落實以預防為主的發展戰略，將中心由“治已病”向“治未病”轉變，加強疾病預防和健康促進研究［1-2］。隨著2020 年全球新型冠狀病毒疫情爆發，人們更加重視大健康產業，同時在人口老齡化趨勢下，體檢需求日益增加，驅動健康體檢行業規模迅速擴容［3-4］。

體檢需求日益增加使健康產業蓬勃發展，隨著體檢中心客戶人數劇增，體檢排隊時間大大增加，而候診時間是客戶評價滿意度的主要指標之一［5-6］。楊一帆［7］運用排隊論建立了病患等待時間的區間估計模型。李凌洋等［8］通過引入M/M/c/∞/∞/FCFS 排隊模型，構建基于排隊論的醫院收費窗口設置優化模型，以患者最少等待時間和最低經營成本為目標設置窗口。Kaungu 等［9］采用多通道排隊方法M1/M2/S/n/FCFS 開發模型，該模型提供了多種性能指標優化系統。以上學者都是通過增加服務窗口數量的方式緩解排隊壓力，但隨之增加了運營商服務成本［10］，并且存在服務資源浪費的情況［11］。因此需要合理的動態規劃項目順序方案。魏偉等［12-13］基于篩選路徑選擇策略，實驗結果顯示LTP 策略在考慮正在接受服務人數、排隊等待人數等病人實時狀態時效果最好。梁月等［14-15］在此研究基礎上將人數進一步規劃為時間，基于排隊論理論設計了4 種排隊方案，并進行動態規劃仿真實驗，實驗結果顯示在不同排隊策略影響下，排隊時間及逗留時間不同。通過對比分析表明，綜合考慮排隊等待時間、服務時間等因素的方案最優。劉路［16］提出了實時通知策略，依據當前時間結點優先安排完成時間最早的檢查，并進行動態規劃檢查路徑。陳家偉［17］以最短行進時間為目標，結合TSP 模型構建問題的整數規劃模型，并利用混合粒子群算法進行求解。

目前智能導檢路徑規劃研究仍處于早期階段，眾學者將重心放在規劃服務窗口上，而對健康體檢的路徑選擇策略及規劃待檢項目整體順序方向的研究較少。研究表明，通過調整客戶檢查順序的路徑選擇策略可有效縮短排隊時間［12］，本文對上述學者的路徑選擇策略進行改進，最終設置了考慮服務時間、排隊時間和路程時間的路徑規劃策略，同時考慮客戶預測待檢行程方案，為體檢排隊的智能化、自動化研究提供新的思路。

1 相關知識

1.1 插值擬合

插值是離散函數逼近的重要方法之一，可通過函數在有限個點處的取值情況，估算函數在其他點處的近似值［18］，用來填充圖像變換時像素間的空隙。最小二乘法通過最小化誤差的平方和尋找數據的最佳函數匹配，使擬合數據與實際數據之間的SSE 為最小值。計算方式如式（1）所示：

其中，ω=[ω1,ω2,…,ωn]T為待定參數，為了尋找函數f(x,ω)的參數ω的最優估計值，對給定m組觀測數據求解目標函數。

擬合優度是一種統計方法，基于所得觀測值作出預測［19］。度量擬合優度的統計量為R-square（R2）及SSE。具體公式如下：

其中，R-square 是衡量整體擬合度的重要指標，當值越接近1 時，擬合程度越好；SSE 數值越小則代表擬合程度越好。

1.2 貪心算法

貪心算法是一種能夠得到某種衡量方式下最優解的分級處理方法，采用自頂向下、以迭代方式進行貪心選擇，每次貪心選擇便會將問題簡化為規模更小的子問題［20］。算法思路為建立數學模型描述問題，并將求解問題分為若干個子問題，先取得子問題的局部最優解，然后將子問題的局部最優解合成為原問題的一個解。因此，貪心算法能夠篩選出當前的最優解，并未考慮整體最優性，所取得的僅是在某種意義上的局部最優解。但貪心算法的計算過程更為迅速、簡便［20-21］，并且局部最優解的計算結果與整體最優解的求解結果較為接近。袁絳書等［22］利用貪心算法構建景區路徑規劃模型，依托游客對各景點的個性化選擇，考慮游客景點偏好、金錢預算、精力等多重約束條件，以此規劃游客最滿意的路線。王翔［23］基于貪心算法不斷推算局部最優解，對采礦進行動態規劃，選取多重規劃狀態下的路徑方案進行對比，最終取得最優策略。蔡文潔等［24］將貪心算法與隨機算法相結合，快速取得不同情況下初始排班表的最優解，以滿足個性化需求。

2 基于貪心算法的智能導檢模型

2.1 導檢問題描述

體檢中心設有若干檢查項目，相同檢查項目時間大致恒定。以體檢客戶角度出發，由于客戶可個性化選擇體檢套餐，不同項目的等待時間和服務時間均存在差異。具體問題描述如下：①體檢客戶到達體檢中心的時間隨機；②體檢客戶檢查的項目具有多樣性；③不同項目的服務時間存在差異；④不同科室服務臺數量不同；⑤不同科室之間的距離不同。綜上所述，體檢中心需為體檢客戶預先分配合理的檢查順序，使體檢客戶逗留的時間最短。

2.2 智能導檢模型構建

步驟1：采用MATLAB 的griddata 函數模擬體檢中心的排隊狀態，通過圖1-圖2 形象的表示不同科室在不同時間節點的人數密度和時間密度。其中，橫坐標分別表示眼科、心電圖室、婦科、外科（女）、口腔科、耳鼻喉科、內科、外科（男）、血液科、彩超甲狀腺、彩超肝膽胰脾雙腎前列腺、胸部正位片DR 室、胸部CT。縱坐標為7：30-11：30，間隔30min 進行統計的時間點信息，豎坐標為當前時間某一科室的等待人數，圖2 豎坐標為當前時間某一科室總體的等待時間。

Fig.1 Griddata v4 interpolated waiting number圖1 griddatav4 插值等待人數

Fig.2 Griddata v4 interpolation waiting time圖2 griddata v4 插值等待時間

步驟2：通過最小二乘法進行數據擬合，構建體檢項目到達率φi(t)與時間t的函數關系。由表1 可見，數據擬合的SSE 值分別為5.115、0.787 8、4.541、1.304 等，R-square 值分別為0.979 6、0.996 7、0.898 6、0.996 4 等，表明該方法取得了較好的擬合效果。

Table1 Evaluation index of goodness of fit表1 擬合優度評價指標

步驟3：根據式（6）計算當前隊列中待檢人數。其中，Pi(k-1 )為上一時間段剩余的待檢人數為時間區間為［k-1,n］時的到檢人數，Mi為服務時間。

步驟4：計算d(i,j)表示科室i到科室j 行走的距離，如式（7）所示。其中，科室i的坐標為Ci(ai,bi)。

步驟5：計算待檢項目中服務時間、排隊時間和路程時間三者的總時間，計算公式如式（8）。

步驟6：采用貪心算法在時間t時對TTi(t)進行全局比較，選擇min（TTi(t)）為局部最優解，然后重新計算時間點，不斷合成待檢項目局部最優解后形成體檢路徑。

3 實驗結果與分析

3.1 數據來源

數據來源于江蘇省中醫院體檢中心，選取2021 年3 月份13 個科室全部的體檢數據，以30min 為間隔統計體檢中心客戶的到達情況，過濾掉不完整、無意義的數據后，最終選擇29 126 條數據作為研究對象。如表2 可見，13 個科室分別為眼科、心電圖室、婦科等。時間按照“7：30-8：00”“8：00-8：30”“8：30-9：00”等區域進行劃分，為了便于統計分別賦值為1-8。

Table 2 Experimental data structure表2 實驗數據結構

3.2 結果分析

如表3 所示，將擬合的函數采用貪心算法構建智能導檢模型，根據不同初始數據，以體檢客戶個性化選擇為基礎，加入體檢項目服務時間的各異性因素，并考慮顧客切換不同項目時所消耗的時間成本，將不同科室之間距離量化為時間。

如圖3 所示，通過對體檢客戶個性化設置到達時間及服務套餐，應用貪心算法自頂向下以迭代方式相繼進行貪心選擇，最終預測體檢項目順序及計算總體等待時間，獲得體檢客戶的路徑狀態。由表4 可見，當預設體檢客戶A體檢的時間為9：24，選擇套餐一（女）項目分別為A1、A2、A3、A4、A5、A6、A7、A9、A10，通過智能導檢模型規劃體檢順序及預測體檢時間，可預測其逗留時間為120.56min。

Table 3 Distance time between departments表3 各科室之間距離時間

Table 4 Sequence planning of item A of health checkers表4 體檢客戶A 項目順序規劃

Fig.3 Sequence path diagram of physical examination items圖3 體檢項目順序路徑

將提出的SQJI 路徑選擇策略與SQI、SQA、QI、QA、SI 和SQJA 路徑選擇策略進行對比分析。其中，SQI 與SQA 分別表示為以體檢服務時間與排隊時間之和最小值或最大值作為評價標準；QI 與QA 分別表示為以排隊時間最小值或最大值作為評價標準；SI 表示以服務時間的最小值作為評價標準；SQJI 與SQJA 則分別表示以服務時間、排隊時間及路程時間之和最小值或最大值作為評價標準。對比結果如圖4 所示，實驗證明SQJI 路徑選擇策略可有效減少客戶逗留時間。如表5 可見，在1-5 及1-8 時間區間SQJI 優越性更強，客戶逗留的時間最少。

Table 5 Comparison between 1-5 and 1-8 time intervals表5 1-5 與1-8 時間區間對比

Fig.4 Comparison of experimental results of different path selection strategies圖4 不同路徑選擇策略模型實驗結果對比

4 總結

目前關于多檢查科室組成的多服務臺排隊問題的研究仍然較少，當前優化排隊時間的主流方式為合理規劃服務窗口的數量，具有一定的局限性。因此，本文提出基于貪心算法的智能導檢路徑優化模型，以規劃客戶體檢項目順序。在考慮服務時間、排隊等待時間的基礎上增加了科室距離因素，將距離信息量轉化為時間信息，利用貪心算法尋找最優解并采用分級處理方法構建最優體檢路徑。本文方法在一定程度上彌補了部分中小型體檢中心無法合理規劃服務臺數量的局限性，將路徑選擇策略與貪心算法相結合，預測體檢路徑及等待時間，并顯示各時間節點的信息量。下一步將考慮加入跨區域因素，綜合考慮科室的地理區域，以提升模型的實用性。