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

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

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

0 概述

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

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

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

現(xiàn)有的調度策略研究通?；趯＜抑R設計特定的規(guī)則和指標［6-8］，將少數(shù)幾種動態(tài)因素相結合。但是這種方式需要同時考慮多種因素，如果僅考慮少數(shù)幾種動態(tài)因素，模型難以全面捕捉急救環(huán)境的變化情況，無法優(yōu)化調度效果。

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

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

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

1 強化學習

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

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

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

受此啟發(fā)，基于急救車調度模型的特點，本文使用強化學習中的策略梯度框架，通過深度神經網(wǎng)絡對環(huán)境狀態(tài)進行表征，使用PPO 算法學習網(wǎng)絡參數(shù)。

2 調度算法

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

2.1 強化學習建模

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

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

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

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

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

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

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

2.2 評分網(wǎng)絡

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

2.3 PPO 參數(shù)優(yōu)化

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

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

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

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

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

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

時序差分損失δ用于更新Actor 網(wǎng)絡的參數(shù)，網(wǎng)絡參數(shù)如式（8）所示：

Critic 網(wǎng)絡參數(shù)基于均方誤差損失函數(shù)進行更新，均方誤差損失函數(shù)如式（9）所示：

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

算法1調度算法訓練流程

2.4 急救車動態(tài)調度算法

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

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

算法2急救車動態(tài)調度算法運行流程

3 實驗與結果分析

3.1 數(shù)據(jù)集

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

3.2 模擬器設計

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

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

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

3.3 實驗設置

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

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

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

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

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

3.4 結果分析

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

在不同的急救車數(shù)量下不同算法平均到達時間對比如表2 所示。當急救車數(shù)量為108 輛時，即目前深圳市的急救車實際數(shù)目，本文算法的平均到達時間是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

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

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

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

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

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

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

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

4 結束語

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