吳仍裕，周 強(qiáng)，于海龍，王亞沙

（1.深圳市急救中心，廣東 深圳 518000；2.北京大學(xué) 信息科學(xué)技術(shù)學(xué)院，北京 100871；3.北京大學(xué) 軟件工程國(guó)家工程研究中心，北京 100871；4.北京大學(xué) 高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，北京 100871）

0 概述

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

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

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

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

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

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

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

1 強(qiáng)化學(xué)習(xí)

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

在MDP 中，智能體以試錯(cuò)的方式與環(huán)境進(jìn)行交互，在每個(gè)時(shí)間步中，智能體觀測(cè)到環(huán)境狀態(tài)并產(chǎn)生一個(gè)動(dòng)作，之后環(huán)境將會(huì)轉(zhuǎn)移到下一個(gè)狀態(tài)。在這期間，智能體收到一個(gè)獎(jiǎng)勵(lì)，這個(gè)獎(jiǎng)勵(lì)作為指導(dǎo)信號(hào)評(píng)估當(dāng)前動(dòng)作的好壞。因此，強(qiáng)化學(xué)習(xí)是通過(guò)最大化長(zhǎng)期獎(jiǎng)勵(lì)來(lái)學(xué)習(xí)環(huán)境狀態(tài)到動(dòng)作的映射關(guān)系。

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

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

2 調(diào)度算法

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

2.1 強(qiáng)化學(xué)習(xí)建模

強(qiáng)化學(xué)習(xí)的關(guān)鍵是將急救車調(diào)度問(wèn)題進(jìn)行形式化建模。在強(qiáng)化學(xué)習(xí)建模過(guò)程中需要對(duì)狀態(tài)、動(dòng)作、獎(jiǎng)勵(lì)、狀態(tài)轉(zhuǎn)移這4 個(gè)主要組件進(jìn)行定義。

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

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

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

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

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

圖1 強(qiáng)化學(xué)習(xí)模型整體架構(gòu)Fig.1 Overall framework of reinforcement learning model

2.2 評(píng)分網(wǎng)絡(luò)

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

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

對(duì)于強(qiáng)化學(xué)習(xí)中的策略梯度算法，目標(biāo)函數(shù)如式（2）所示：

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

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

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

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

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

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

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

算法1 表示在PPO 算法中急救車調(diào)度算法的訓(xùn)練流程。

算法1調(diào)度算法訓(xùn)練流程

2.4 急救車動(dòng)態(tài)調(diào)度算法

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

本文構(gòu)建一個(gè)基于強(qiáng)化學(xué)習(xí)的急救車調(diào)度算法。當(dāng)有急救車請(qǐng)求調(diào)度時(shí)，該調(diào)度算法首先觀測(cè)環(huán)境的狀態(tài)，包括所有急救站的動(dòng)態(tài)因素，通過(guò)Actor 網(wǎng)絡(luò)生成該急救車調(diào)往各個(gè)急救站的概率。在測(cè)試階段，該調(diào)度算法會(huì)選擇概率最高的急救站作為急救車被調(diào)往的站點(diǎn)。算法2 表示急救車動(dòng)態(tài)調(diào)度算法運(yùn)行的整體流程。

算法2急救車動(dòng)態(tài)調(diào)度算法運(yùn)行流程

3 實(shí)驗(yàn)與結(jié)果分析

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

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

3.2 模擬器設(shè)計(jì)

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

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

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

3.3 實(shí)驗(yàn)設(shè)置

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

本文采用平均到達(dá)時(shí)間和平均到達(dá)比例來(lái)評(píng)估急救車的調(diào)度問(wèn)題。平均到達(dá)時(shí)間是指急救車從派遣至到達(dá)現(xiàn)場(chǎng)的平均時(shí)間，如式（10）所示：

平均到達(dá)比例是在時(shí)間閾值內(nèi)（10 min）到達(dá)現(xiàn)場(chǎng)的急救車比例，如式（11）所示：

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

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

3.4 結(jié)果分析

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

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

表2 不同算法的平均到達(dá)時(shí)間對(duì)比Table 2 Average arrival time comparison among different algorithms min

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

表3 不同算法的平均到達(dá)比例對(duì)比Table 3 Average arrival proportion comparison among different algorithms %

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

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

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

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

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

4 結(jié)束語(yǔ)

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