基于深度強化學習的深圳市急救車調度算法

吳仍裕，周 強，于海龍，王亞沙

（1.深圳市急救中心，廣東 深圳 518000；2.北京大學 信息科學技術學院，北京 100871；3.北京大學 軟件工程國家工程研究中心，北京 100871；4.北京大學 高可信軟件技術教育部重點實驗室，北京 100871）

0 概述

在擁有1 300 萬人口的深圳市，每年有20 余萬名市民因突發事故或疾病，需要急救車將他們運送至醫院，其人數占深圳市總人口的2%［1］。在城市的院前急救中，急救中心派遣急救車將患者及時地送到醫院，對于患者的生命安全具有重要意義。統計數據表明，急救反應時間超過5 min 的患者死亡概率為1.58%，而低于5 min 的患者死亡概率為0.51%［2］。因此，急救車盡早到達現場能夠有效保障患者的生命安全。

目前，中國大部分城市的院前急救模式是患者撥打120 急救電話后，急救中心派遣離事發地點最近急救站的急救車前往現場，負責將患者送至醫院，之后急救車將返回到歸屬的急救站。但是在急救資源有限的情況下，無法保證每一個急救需求都能夠從離事發地點最近的急救站派遣急救車。

為縮短整體的急救反應時間，研究人員專注于急救車靜態分配策略的研究，將急救車分配問題建模成靜態的優化問題［3-4］。這類方法通常使用整數線性規劃模型求解最大化急救覆蓋范圍的急救車分配方案，為每輛急救車分配一個基站，在急救車執行完任務后返回自己的基站。但是，在急救系統中，無論是急救資源還是外部環境都是動態變化的，靜態分配策略無法充分利用這些動態信息。研究人員對急救車動態調度策略進行研究［5-7］。急救車的動態調度策略［8］是指急救車執行完任務后，通過重新調度到合適的急救站，為服務未來的急救請求做好準備，從而達到縮短整體急救反應時間的目的。在急救車動態調度中，調度策略的制定需要實時考慮環境的多種動態因素，例如，急救站附近的急救需求數量、急救站當前擁有的急救車數量、其他正在執行任務的急救車狀態等，這些動態因素對于調度策略的制定至關重要。

現有的調度策略研究通常基于專家知識設計特定的規則和指標［6-8］，將少數幾種動態因素相結合。但是這種方式需要同時考慮多種因素，如果僅考慮少數幾種動態因素，模型難以全面捕捉急救環境的變化情況，無法優化調度效果。

強化學習能夠解決序列決策問題，在共享單車重定位［9］、網約車派單［10-12］等類似調度問題上取得了良好的效果。網約車派單［13-14］與急救車調度都屬于車輛調度問題，在優化目標中都需要考慮長遠收益。但是，網約車派單問題是將短時間內接收到的大量乘客訂單與平臺司機進行匹配，本質上屬于二部圖的匹配問題。文獻［10-12］通過強化學習司機和訂單之間的匹配價值，在派單階段利用二部圖匹配算法實現最大權匹配。文獻［13-14］將短時間內大量司機的派單視作多智能體問題，通過多智能體強化學習實現司機間的協作，使得平臺整體收益最大化。而急救車調度問題是處理單一急救車的調度，難點在于急救環境的動態性和復雜性。此外，急救車調度是院前急救領域的重要問題，需要貼合真實環境設計方案，才能更好地保障人民的生命安全。

雖然強化學習可以用于解決網約車派單的調度問題，但是在急救車調度領域上的應用是非常少的，僅文獻［5］提出一種基于強化學習的急救車動態調度模型。該模型利用神經網絡融合環境中的動態因素，并建立強化學習框架，得到合適的急救車調度策略。然而，該模型對急救環境進行較強的假設和簡化，無法直接應用于深圳急救的真實環境，其原因為僅基于道路限速值估計急救車的行駛速度，未考慮道路擁堵的現象。深圳是我國一線城市，道路擁堵頻繁發生，需根據道路擁堵情況規劃急救車路徑。該模型對急救車行為做了較大簡化，例如，認為總是距離患者最近的急救車出車，并到達現場后，立刻將患者送往距離最近的醫院。然而，從深圳和急救的歷史數據可以看出，在很多情況下急救車到達現場后需要先對患者進行現場處置，并可能根據病情，將患者送至有救治能力且距離較近的醫院。此外，文獻［5］利 用REINFORCE 算法［15］優化策略函數，REINFORCE 是一種策略梯度算法［16］，使用蒙特卡洛法估計期望收益，但是存在訓練速度慢、方差大、樣本利用率低的問題。

本文提出基于深度強化學習的急救車調度算法。利用多層感知機將急救站的動態信息映射為各急救站的評分，同時將急救車動態調度建模成馬爾科夫決策過程，使用強化學習中演員-評論家（Actor-Critic）框架［16］下的近端策略優化（Proximal Policy Optimization，PPO）算法［17］學習評分網絡的參數。通過考慮急救環境因素、道路交通因素和急救車行為模式因素，建立較真實的模擬器環境。

1 強化學習

強化學習是機器學習的一種范式，通過智能體與環境進行不斷交互，以學習策略，使得累積期望收益最大化。強化學習組件包括S，A，P，R，γ五個要素。S是環境的狀態，A是智能體的動作，P是環境狀態的轉移概率矩陣，R是環境提供的獎勵，γ是折扣因子。在強化學習中，馬爾科夫決策過程（Markov Decision Process，MDP）是序列決策的一種數學模型，假設環境的狀態具有馬爾科夫性質。馬爾科夫性質是指在給定環境當前和過去的狀態下，未來環境狀態的條件概率分布僅依賴于當前環境狀態。本文利用S（t）表示環境的狀態，則馬爾科夫性質的表示如式（1）所示：

在MDP 中，智能體以試錯的方式與環境進行交互，在每個時間步中，智能體觀測到環境狀態并產生一個動作，之后環境將會轉移到下一個狀態。在這期間，智能體收到一個獎勵，這個獎勵作為指導信號評估當前動作的好壞。因此，強化學習是通過最大化長期獎勵來學習環境狀態到動作的映射關系。

強化學習和神經網絡的結合開始于20 世紀90 年代［18-19］。近年來，隨著計算力的提升和深度學習的發展，結合深度學習與強化學習的深度強化學習成為研究熱點。深度強化學習融合強化學習的決策能力和深度學習的表示能力，在很多序列決策問題中取得了巨大的進展，如AlphaGo［20］、網絡對戰游戲［21-22］、車輛調度問題等［5，9-10］。

受此啟發，基于急救車調度模型的特點，本文使用強化學習中的策略梯度框架，通過深度神經網絡對環境狀態進行表征，使用PPO 算法學習網絡參數。

2 調度算法

本文將急救車調度問題形式化成MDP，使用強化學習框架選擇合適的調度策略。本文網絡結構的主體部分稱為評分網絡，使用多層感知機表示，用于綜合急救站的多種動態因素，以評估急救車調度到該急救站的概率。為優化評分網絡參數，本文使用PPO 強化學習框架，以試錯的學習方式更新網絡參數。

2.1 強化學習建模

強化學習的關鍵是將急救車調度問題進行形式化建模。在強化學習建模過程中需要對狀態、動作、獎勵、狀態轉移這4 個主要組件進行定義。

1）狀態，指外部環境的狀態。在急救車調度過程中，環境是完全可觀測的，因此智能體觀測到的環境狀態等同于環境的實際狀態。本文將狀態定義為與急救車調度有關的環境信息，包括急救站附近的急救需求數量、急救站當前擁有的急救車數量、被調度車輛到達該急救站所需時間以及其他正在執行任務的急救車到達該急救站所需時間這4 種動態因素。

2）動作，指智能體執行的動作。在急救車調度問題中，本文將動作定義為調度到哪一個急救站，因此動作空間的大小等同于急救站的數目N。at表示t時刻智能體執行的動作，則at∈(1,2,…,N)。

3）獎勵，指智能體執行動作后收到的獎勵。R(st,at)表示智能體在狀態st下執行動作at，當環境從狀態st轉換成st+1后智能體接收到的獎勵。本文將R(st,at)定義為在時間閾值（10 min）內到達現場的急救車數目。例如，在t～(t+1)時刻內，整個系統共有5 輛急救車到達事發現場，其中有3 輛急救車花費的時間小于10 min，則獎勵值就是3。

4）狀態轉移，指環境狀態的轉移。當急救車執行完任務等待重新調度時，智能體從環境中觀測到狀態st，并隨之產生一個動作at，將該急救車調度到某個急救站。此后智能體處于空轉的狀態，直到有新的急救車執行完任務等待調度。此時環境狀態轉成st+1，并被智能體觀測到。環境狀態的轉移是一個隨機性事件，在兩次狀態之間的時間間隔是不固定的，但是這并不影響系統的馬爾科夫性質，因此強化學習算法仍然可以工作。

強化學習模型的整體架構如圖1 所示。首先智能體觀測環境狀態，即各個急救站的動態因素，并將其輸入到Actor 的評分網絡中以得到各個急救站的分數。智能體基于急救站的分數選擇急救車調度的站點，并執行相應動作。環境在轉移到下一個狀態前，將獎勵反饋給智能體，該獎勵作為學習信號，送入Critic 網絡中計算時序差分損失（TD error），使得智能體能夠不斷更新Actor 和Critic 網絡的參數。

圖1 強化學習模型整體架構Fig.1 Overall framework of reinforcement learning model

2.2 評分網絡

評分網絡用于表征環境狀態，將每個急救站的動態信息映射為一個得分，該得分決定了被調度急救車前往該急救站的概率。本文使用多層感知機作為評分網絡結構，以接收到急救站4 種動態信息作為輸入，包括急救站附近的急救需求數量、急救站當前擁有的急救車數量、被調度車輛到達該急救站所需時間以及其他正在執行任務的急救車到達該急救站所需時間，最后輸出急救站的得分。所有急救站的得分經過Softmax 函數后獲得急救車調度到每個急救站的概率。

2.3 PPO 參數優化

對于強化學習中的策略梯度算法，目標函數如式（2）所示：

其中：V(s)為狀態值函數，表征當前狀態的期望收益。使用蒙特卡洛法對序列進行估計，但是會產生較大的估計方差，且更新參數的效率較低。針對該問題，在演員-評論家框架中引入Critic 網絡對V(s)進行估計，使得每步動作執行后都能夠得到當前狀態期望收益的反饋，以減小估計方差，從而提高更新效率和樣本利用率。

PPO 算法在演員-評論家框架下，待優化的策略函數（即演員-評論家框架下Actor 網絡）是πθ，而與環境交互采樣的策略是πθ′。針對采樣得到的數據分布和待優化策略下狀態分布失配的問題，在目標函數中引入重要性采樣進行優化，如式（3）和式（4）所示：

重要性采樣是一種對原始分布期望的無偏差估計方法，如果引入的提議分布與原始分布差異較大，會產生較大的估計方差。因此，在PPO 算法中設計一種權重修剪機制，將重要性權重限制在[1-ε,1+ε]內，其中ε是超參數。此時，PPO 算法的優化目標表示如式（5）和式（6）所示：

clip(rt(θ),1-ε,1+ε)函數將重要性權重rt(θ)限制在[1-ε,1+ε]的范圍內，簡稱為clip(ε)。

本文使用PPO 算法優化評分網絡的參數，以學習調度的策略。在圖1 的Actor 網絡中基于評分網絡生成各個急救站的評分，經過Softmax 函數得到急救車被調度到各個急救站的概率。Critic 網絡和評分網絡具有相同的網絡結構，僅輸出層不同，本文使用φ表示Critic 網絡的參數。在訓練期間，Critic 網絡將接收的環境狀態作為輸入，估計當前狀態下執行動作a的期望收益Aφ(s,a)，根據環境反饋的獎勵R計算時序差分損失δ，如式（7）所示：

時序差分損失δ用于更新Actor 網絡的參數，網絡參數如式（8）所示：

Critic 網絡參數基于均方誤差損失函數進行更新，均方誤差損失函數如式（9）所示：

算法1 表示在PPO 算法中急救車調度算法的訓練流程。

算法1調度算法訓練流程

2.4 急救車動態調度算法

本文基于PPO 算法框架學習Actor 網絡πθ(s,a)的參數θ，以得到急救車調往各個急救站的概率。在調度模型的訓練階段，基于各個急救站的概率確定急救車調往哪個急救站。這種隨機性的策略有助于強化學習模型跳出局部最優。但是在測試階段運行該急救車調度算法時，不適合繼續采取這樣的隨機性策略，因此，在測試階段，調度算法會選擇概率最高的急救站作為調度的站點。

本文構建一個基于強化學習的急救車調度算法。當有急救車請求調度時，該調度算法首先觀測環境的狀態，包括所有急救站的動態因素，通過Actor 網絡生成該急救車調往各個急救站的概率。在測試階段，該調度算法會選擇概率最高的急救站作為急救車被調往的站點。算法2 表示急救車動態調度算法運行的整體流程。

算法2急救車動態調度算法運行流程

3 實驗與結果分析

3.1 數據集

本文使用深圳市的真實數據集對模型進行訓練、測試和驗證。數據集包括深圳市的急救電話數據、急救患者數據、急救站數據、醫院數據、道路網絡數據和速度數據。急救電話數據包含深圳市120 急救電話記錄，每條記錄均包括時間信息和事發地點。時間跨度從2019 年9月1日到2019 年10 月31日。其中9 月份的有效記錄共有16 278 條，10 月份的有效記錄共有15 327 條，平均每天約有518 條有效急救電話請求。本文以9 月份的急救電話數據作為訓練數據，將10 月份的急救電話數據作為測試數據。急救患者數據包括每條急救記錄中患者的基本信息、救治情況等內容。急救站數據包括深圳市急救站的地理位置信息。醫院數據包括深圳市醫院的地理位置信息。道路網絡數據和速度數據包括深圳市路網信息和道路速度信息。

3.2 模擬器設計

本文基于上述數據集，構建一個較真實的模擬器。模擬器的作用是模擬真實情況下急救系統的運行狀況，需要實時生成急救請求，并模擬派遣急救車接送患者至醫院，最后根據調度算法重新調度執行完任務的急救車。

本文在模擬器中考慮了城市的道路網絡數據和道路擁塞程度，基于城市的道路擁塞程度對急救車進行路徑規劃和時間估計，通過考慮不同道路的擁塞程度對急救反應時間的影響，以減小在仿真環境和真實環境中對路上時間估計的偏差。

本文基于對急救患者數據的觀察，發現真實情況下急救車到達現場后，出于多種原因患者可能被當場救治。因此，在本文的模擬器中急救車被派往現場后，以概率的方式選擇將患者送往醫院或停留在原地。此外，本文觀察到患者被送往的醫院通常不是距離最近的，存在一定的隨機性。因此，在本文的模擬器中根據距離獲得急救車前往各個醫院的概率。本文綜合考慮急救車的這些行為模式，能夠增強模擬器的真實性，使得算法適用于真實場景并進行落地部署。

3.3 實驗設置

為評估基于強化學習的急救車調度算法，本文選用以下6 種算法作為基準算法：1）Fixed 算法，目前深圳市使用的急救車分配策略，基于貪心算法計算得到不同的車輛數；2）MEXCLP 算法［3］，是一種經典的靜態分配模型，通過最大化急救站的覆蓋范圍，為每輛急救車選取一個基站，優化過程使用整數線性規劃求解；3）DSM算法［4］，是一種經典基于覆蓋的靜態分配模型，將雙重覆蓋作為優化目標；4）Random 算法，是一種隨機的動態調度策略，將急救車重新調度到一個隨機的急救站；5）Nearest算法，是一種基于貪心算法的動態調度策略，將急救車重新調度到距離最近的急救站；6）Least算法，另一種基于貪心算法的動態調度策略，將急救車重新調度到車輛數目最少的急救站。

本文采用平均到達時間和平均到達比例來評估急救車的調度問題。平均到達時間是指急救車從派遣至到達現場的平均時間，如式（10）所示：

平均到達比例是在時間閾值內（10 min）到達現場的急救車比例，如式（11）所示：

本文深度強化學習模型的代碼在PyTorch 框架下實現，Actor 和Critic 網絡使用相同的網絡結構，采用三層的多層感知機，僅輸出層不同，以Relu 作為激活函數。本文算法的超參數設置如表1 所示。

表1 本文算法的超參數設置Table 1 Hyperparameter settings of the proposed algorithm

3.4 結果分析

目前，深圳市實際部署的急救車數量是108 輛。深圳市作為中國的一線城市，急救資源相對充足，但是很多經濟欠發達地區的急救資源可能相對緊缺。因此，本文在實驗中還探究了在其他急救車數量的情況下，特別是急救車數量較少時的實驗結果。

在不同的急救車數量下不同算法平均到達時間對比如表2 所示。當急救車數量為108 輛時，即目前深圳市的急救車實際數目，本文算法的平均到達時間是12.63 min，而Fixed 算法的平均到達時間是13.93 min。相比Fixed 算法，本文算法的平均到達時間縮短約80 s，性能提升了約10%。相比基準算法中MEXCLP，本文算法的平均時間縮短約40 s。

表2 不同算法的平均到達時間對比Table 2 Average arrival time comparison among different algorithms min

在不同急救車數量下不同算法的平均到達比例對比如表3 所示。在108 輛急救車配置的條件下，Fixed算法和本文算法的平均到達比例分別為32.3%和36.5%，相比基準算法Least，本文算法提高了1.1 個百分點。此外，當急救車輛數目較少時，本文算法的優勢更為顯著，其原因為靜態調度策略在急救車數量較少時容易出現一些花費時間特別長的極端情況，基于貪心算法的動態調度策略則難以捕捉多種動態信息，而基于強化學習的調度策略能夠捕捉到環境的動態變化。這也說明在急救資源緊缺的城市中部署本文急救車調度算法，在資源受限情況下能夠有效提高院前急救效率。

表3 不同算法的平均到達比例對比Table 3 Average arrival proportion comparison among different algorithms %

在院前急救領域較為重視盲點的情況。本文將盲點定義為急救車到達現場的路程距離超過3 000 m。當急救車數量為108 輛時，不同算法的盲點和距離情況如表4 所示。

表4 不同算法的盲點和平均距離Table 4 Blind spots and average distances of different algorithms

從表4 可以看出，本文算法的平均距離在3 100 m左右，而最優的基準算法的平均距離約為3 300 m，說明強化學習模型能夠隱式地預估未來的急救需求，預先將急救車調度到可能有需求的急救站，從而在急救事件發生時能夠從最近的急救站派遣車輛。本文算法將盲點比例控制在36%，同樣優于其他基準算法。

本文算法的盲點可視化分析如圖2 所示（彩色效果見《計算機工程》官網HTML 版）。圖2（a）表示本文算法在運行過程中盲點分布熱力圖，可以看出：盲點的分布與急救電話的分布整體上較為一致。在局部地區盲點分布情況和急救電話分布情況存在顯著的差異。圖2（b）和圖2（c）分別表示急救電話和盲點在深圳市龍崗區龍城廣場附近的分布情況。區域A 中的急救電話需求較多，但在區域B 中的盲點分布較少。區域C 和區域D 的情況則恰好相反。這說明盲點的產生不僅受急救電話數量的影響，同時也與其他因素有關，例如交通狀況、急救資源分配情況等。

圖2 本文算法的盲點可視化分析Fig.2 Blind spot visual analysis of the proposed algorithm

4 結束語

針對急救環境的動態性和復雜性，本文提出一種急救車動態調度算法。將多層感知機作為評分網絡用于綜合急救站的多種動態因素，以評估急救車調度到該急救站的概率。在PPO 強化學習框架下，采用試錯的學習方式優化評分網絡參數。實驗結果表明，本文算法的平均達到時間和平均到達比例分別為12.63 min 和36.5%，與Fixed、DSM、MEXCLP 等算法相比，能夠有效提高數據的利用率，并且具有較優的魯棒性。下一步將利用圖神經網絡對不同時刻的交通資源進行編碼，并把急救車的行為模式與交通資源引入到環境狀態中，進一步縮短院前急救反應時間。