基于聯(lián)合Q 值分解的強(qiáng)化學(xué)習(xí)網(wǎng)約車訂單派送

黃曉輝，張雄，楊凱銘，熊李艷

（華東交通大學(xué)信息工程學(xué)院，南昌 330013）

0 概述

隨著移動互聯(lián)網(wǎng)技術(shù)的發(fā)展以及智能手機(jī)的普及，依托移動互聯(lián)網(wǎng)平臺的共享經(jīng)濟(jì)在各個行業(yè)逐漸涌現(xiàn)，并對人們的生活方式產(chǎn)生較大的影響。在交通出行領(lǐng)域，研究人員提出基于網(wǎng)約車平臺的多種新型出行方式。文獻(xiàn)［1］介紹網(wǎng)約車平臺通過整合乘客與網(wǎng)約車之間的供需信息使其相匹配。網(wǎng)約車平臺可以提高當(dāng)前的交通效率，當(dāng)乘客用智能手機(jī)設(shè)置目的地時，平臺可自動采用智能方法匹配可用車輛。由于訂單派送結(jié)果直接影響平臺收入及乘客舒適度，因此訂單派送問題也可以類比為PDP（Pickup and Delivery Problem）問題，其關(guān)鍵是將訂單與可用車輛進(jìn)行合理匹配。因此，通過合適的匹配方法來派送訂單，使車輛的總行駛距離和用戶的等待時間最小化，并增加司機(jī)的收入。

高效的訂單派送和空間擴(kuò)展性是構(gòu)建智能派單系統(tǒng)的關(guān)鍵。如果一輛汽車?yán)@道去接送客戶，并且在接送過程中，司機(jī)還需考慮堵車問題，用戶的總出行時間就會延長。文獻(xiàn)［2］根據(jù)出行路徑，將網(wǎng)約車與訂單進(jìn)行匹配，利用強(qiáng)化學(xué)習(xí)對司機(jī)的出行路徑進(jìn)行決策，同時，通過訓(xùn)練歷史出行路徑，提高出行效率，增加司機(jī)收益。但是該方法存在一定的局限性，在訓(xùn)練歷史出行路徑數(shù)據(jù)時僅考慮網(wǎng)約車到乘客初始位置的狀態(tài)，因乘客出行會改變駕駛員的位置，導(dǎo)致網(wǎng)約車司機(jī)的未來收益減少。對于空間擴(kuò)展性，文獻(xiàn)［3］提出基于深度強(qiáng)化學(xué)習(xí)的網(wǎng)約車重定位原理，提前將網(wǎng)約車進(jìn)行需求調(diào)度，考慮到一次性優(yōu)化整個網(wǎng)約車平臺的復(fù)雜性以及不同規(guī)模城市之間供需情況的差異，通常會劃分自然地理邊界來解決訂單派送問題。由于每個城市具有不同的規(guī)模和交通模式，因此在網(wǎng)約車平臺上為每個城市構(gòu)建新的模型。

本文結(jié)合深度神經(jīng)網(wǎng)絡(luò)與多智能體強(qiáng)化學(xué)習(xí)（MARL），在基于聯(lián)合Q值函數(shù)分解的框架VFD 下，提出兩種方法ODDRL 與LF-ODDRL，使乘客整體等待時間最小化。通過將訂單派送建模為分布式?jīng)Q策問題，具有集中訓(xùn)練、分散執(zhí)行策略的優(yōu)點(diǎn)，同時設(shè)計基于動作搜索的損失函數(shù)，將訂單高效地與網(wǎng)約車司機(jī)相匹配，提高模型在不同規(guī)模網(wǎng)格上的可擴(kuò)展性。

1 相關(guān)工作

1.1 基于組合優(yōu)化的PDP 方法

網(wǎng)約車訂單派送體系結(jié)構(gòu)如圖1 所示。車輛與訂單的合理匹配是網(wǎng)約車平臺中的一項(xiàng)重要決策任務(wù)。文獻(xiàn)［4］考慮為每個訂單找到最近司機(jī)。文獻(xiàn)［5］通過網(wǎng)約車平臺給司機(jī)發(fā)送虛擬訂單，使網(wǎng)約車提前調(diào)度到未來乘客可能多的地方，滿足更多乘客的需求，提高司機(jī)收益。文獻(xiàn)［6］使用人工編寫的函數(shù)來估計出行時間和用戶等待時間。文獻(xiàn)［7］提出新型雙特征協(xié)同轉(zhuǎn)換器，通過新的循環(huán)位置編碼方法嵌入車輛位置特征，使用Transform 設(shè)計有效的車輛路徑解決方案。文獻(xiàn)［8］提出基于自注意力機(jī)制的深層架構(gòu)，并將其作為策略網(wǎng)絡(luò)來引導(dǎo)下一個動作的選擇，解決旅行商路徑最短問題。文獻(xiàn)［9］提出基于集中組合優(yōu)化的新模型，該模型在短時間內(nèi)將訂單并發(fā)匹配多個車輛。但是上述方法大多需要計算所有可用的車輛派送訂單，并對每個城市構(gòu)建新的模型，難以用于大規(guī)模的網(wǎng)約車訂單派送，擴(kuò)展性較差。

圖1 網(wǎng)約車訂單派送體系結(jié)構(gòu)Fig.1 Structure of online car-hailing order dispatch system

1.2 基于強(qiáng)化學(xué)習(xí)的PDP 方法

文獻(xiàn)［10］描述了PDP 問題如何從一個組合優(yōu)化方法發(fā)展到一個包含半馬爾可夫決策過程（Markov Decision Process，MDP）模型的深度強(qiáng)化學(xué)習(xí)方法。文獻(xiàn)［11］將神經(jīng)網(wǎng)絡(luò)與異構(gòu)注意力機(jī)制相結(jié)合，增強(qiáng)深度強(qiáng)化學(xué)習(xí)中的策略，側(cè)重關(guān)注乘客的上車位置，該策略期望尋找網(wǎng)約車訂單派送問題中的最優(yōu)解。文獻(xiàn)［12］利用model-free 強(qiáng)化學(xué)習(xí)來解決最優(yōu)解問題，通過與復(fù)雜環(huán)境交互來學(xué)習(xí)策略。文獻(xiàn)［13］將某一個區(qū)域的司機(jī)視為具有相同狀態(tài)的智能體，簡化了大規(guī)模訂單派送場景中的隨機(jī)供需動態(tài)。文獻(xiàn)［14］考慮對異構(gòu)車隊約束的車輛選擇解碼器和基于路由結(jié)構(gòu)的節(jié)點(diǎn)選擇解碼器，通過在每一步自動選擇車輛和節(jié)點(diǎn)來構(gòu)建解決策略，使得車輛的總行駛時間最小化。文獻(xiàn)［15］通過深度強(qiáng)化學(xué)習(xí)理論對智能體的路徑規(guī)劃策略進(jìn)行改進(jìn)，文獻(xiàn)［16］基于知識遷移學(xué)習(xí)方法，通過深度神經(jīng)網(wǎng)絡(luò)估計駕駛員的狀態(tài)動作值函數(shù)，利用訓(xùn)練歷史數(shù)據(jù)來達(dá)到跨多個城市的模型遷移目的。文獻(xiàn)［17］提出一種新的方法，將多智能體強(qiáng)化學(xué)習(xí)轉(zhuǎn)化為兩個智能體不斷交互的過程，使其在大規(guī)模智能體中更好地學(xué)習(xí)策略。文獻(xiàn)［18］基于獨(dú)立DQN 的方法學(xué)習(xí)分散的價值函數(shù)。文獻(xiàn)［19］基于深度價值網(wǎng)絡(luò)的批量訓(xùn)練方法來學(xué)習(xí)時空狀態(tài)值函數(shù)，通過基于價值的策略搜索，將規(guī)劃和引導(dǎo)與價值網(wǎng)絡(luò)相結(jié)合，按需生成最優(yōu)的重新定位行動。

在上述方法的基礎(chǔ)上，本文基于VFD 框架來解決訂單派送問題，VFD 框架由聯(lián)合動作價值網(wǎng)絡(luò)、獨(dú)立動作價值網(wǎng)絡(luò)、狀態(tài)價值網(wǎng)絡(luò)組成，并且為每個神經(jīng)網(wǎng)絡(luò)定義合適的損失函數(shù)，實(shí)現(xiàn)集中訓(xùn)練和分散執(zhí)行的優(yōu)勢策略［20］。

2 問題陳述

針對在線網(wǎng)約車平臺管理大量PDP 問題，本文對空閑車輛和訂單進(jìn)行高效匹配。PDP 問題屬于經(jīng)典網(wǎng)約車管理問題的一個變種［21］。網(wǎng)約車訂單派送示意圖如圖2 所示。本文使用四邊形網(wǎng)格表示地圖，地圖中的節(jié)點(diǎn)對應(yīng)不同路網(wǎng)的交叉點(diǎn)，它們之間的邊對應(yīng)于不同的道路。車輛和訂單隨機(jī)出現(xiàn)在每個網(wǎng)格上，每條道路上都有相應(yīng)的成本，該成本對應(yīng)一輛車穿過道路的時間。成本包括不同交通條件在內(nèi)的因素，如天氣、節(jié)假日等，由環(huán)境決定，不能人為的定義。

圖2 網(wǎng)約車訂單派送示意圖Fig.2 Schematic diagram of online car-hailing order dispatch

本文將網(wǎng)約車訂單派送問題建模成MDP。智能體是從駕駛員的角度定義。完整的行程轉(zhuǎn)換包括訂單派送、訂單接受和完成。網(wǎng)約車平臺對空閑司機(jī)進(jìn)行訂單派送，司機(jī)接受訂單并前往乘客初始位置，把乘客帶到目的地，完成訂單。司機(jī)在行程轉(zhuǎn)換中立即獲得獎勵，即路費(fèi)。本文把司機(jī)的一次閑置運(yùn)動視為一次零獎勵運(yùn)動，定義MDP 的關(guān)鍵要素G=(N，S，A，P，R，γ)，分別表示車輛的數(shù)量、狀態(tài)集合、聯(lián)合動作空間、狀態(tài)轉(zhuǎn)移概率、獎勵函數(shù)、折扣因子。

1）狀態(tài)St。狀態(tài)輸入表示為一個三元素元組，即S=(l，t，1)元組中的元素，分別表示車輛的起始經(jīng)緯度、時間、接單成功。

2）動作at。對司機(jī)的一段特定行程進(jìn)行分配，它簡單由行程起始地點(diǎn)和下車時間定義。設(shè)當(dāng)前S0=(l0，t0，0)為分配行程時司機(jī)位置、時間和車輛空閑，S1=(l1，t1，1)為上車地點(diǎn)、時間和接單成功。因此，動作a=(l，t)。所有符合條件動作的空間用A表示。

3）獎勵r。獎勵函數(shù)在強(qiáng)化學(xué)習(xí)中非常重要，它在很大程度上決定了優(yōu)化的方向。網(wǎng)約車通過接受訂單到將乘客送到目的地完成訂單，從而獲得獎勵。本文設(shè)計一個與每個訂單的花費(fèi)成比例的獎勵函數(shù)，在每個單位時間步長中即時獎勵序列的總和表示為Rt=rt+1+γrt+2+…+

4）動作價值函數(shù)Q(s，a)。司機(jī)采取動作時將獲得累計獎勵，直到一個時間步長結(jié)束。Q(s，a)=

5）策略π(a|s)。π(a|s)是一個將狀態(tài)映射到動作空間或特定動作上的分布策略。學(xué)習(xí)型Q(s，a)的貪婪策略由π(s)=argmaxQ(s，a)得出。

6）狀態(tài)值函數(shù)V(s)。如果司機(jī)從開始遵循策略，將獲得預(yù)期累計獎勵，直到時間步長結(jié)束。策略π假設(shè)使用了Q函數(shù)的貪心策略，狀態(tài)值V(s)=

3 基于聯(lián)合Q 值分解框架

網(wǎng)約車平臺要實(shí)現(xiàn)高效的訂單匹配，需要對外部環(huán)境有一個基本認(rèn)識，主要包括訂單的位置信息、時間等，綜合考慮車輛當(dāng)前狀態(tài)的即時獎勵和下一個狀態(tài)的長期價值，通過最優(yōu)策略函數(shù)選擇最佳動作。VFD 架構(gòu)的核心思想是將原有的聯(lián)合動作值函數(shù)轉(zhuǎn)化為擁有最優(yōu)動作的新函數(shù)。在t時刻，某區(qū)域的車輛最優(yōu)聯(lián)合動作相當(dāng)于每輛車的最優(yōu)動作集合，在集中訓(xùn)練階段易于因式分解的分布式?jīng)Q策任務(wù)的執(zhí)行。

對于聯(lián)合動作價值函數(shù)Qj：SN×AN→R，其中a∈AN是一個歷史聯(lián)合動作，如式（1）所示：

3.1 整體結(jié)構(gòu)

VFD 框架克服現(xiàn)有方法中聯(lián)合動作值函數(shù)分解的可加性和單調(diào)性的約束，能夠分解所有可分解的任務(wù)。聯(lián)合Q值分解函數(shù)的框架如圖3 所示，該框架由3 個獨(dú)立的網(wǎng)絡(luò)構(gòu)成：1）獨(dú)立動作價值網(wǎng)絡(luò)，主要是通過神經(jīng)網(wǎng)絡(luò)獲得在t時刻某區(qū)域內(nèi)每輛車的動作值Qi(si，ai)；2）聯(lián)合動作價值網(wǎng)絡(luò)，主要是通過隱藏特征得到在t時刻某區(qū)域內(nèi)車輛的聯(lián)合動作值Qj(s，a)；3）狀態(tài)價值網(wǎng)絡(luò)，用于彌補(bǔ)聯(lián)合動作價值網(wǎng)絡(luò)學(xué)習(xí)到的動作值Qj(s，a)，并與通過獨(dú)立動作價值網(wǎng)絡(luò)得到所有車輛動作值之和Q'j(s，a)的差距。通過對3 個神經(jīng)網(wǎng)絡(luò)進(jìn)行集中訓(xùn)練，每輛車在分散執(zhí)行期間使用自己因式分解的獨(dú)立價值函數(shù)Qi采取動作。

圖3 聯(lián)合Q 值函數(shù)分解的框架Fig.3 Framework of joint Q-value function decomposition

3.1.1 獨(dú)立動作價值網(wǎng)絡(luò)

對于每輛車，獨(dú)立動作價值網(wǎng)絡(luò)根據(jù)其自身的歷史觀察si輸入，并將產(chǎn)生的動作值Qi=(si，ai)作為輸出。通過計算給定的動作值來確定動作，如式（2）所示：

其中：Q'j為所有車輛的動作值之和；Qi(si，ai)為每輛車的動作值。

3.1.2 聯(lián)合動作價值網(wǎng)絡(luò)

聯(lián)合動作價值網(wǎng)絡(luò)的Qj值用于近似所有車輛的動作值之和，將車輛所選動作作為輸入，生成所選動作的Q值并作為輸出。為了提高網(wǎng)絡(luò)的可擴(kuò)展性和訓(xùn)練效率，聯(lián)合動作價值網(wǎng)絡(luò)的設(shè)計是通過所有車輛獨(dú)立動作價值網(wǎng)絡(luò)確定的動作來更新聯(lián)合動作價值網(wǎng)絡(luò)。聯(lián)合動作空間N是復(fù)雜的，隨著車輛數(shù)的增加，尋找最優(yōu)動作能提高復(fù)雜度，而獨(dú)立動作價值網(wǎng)絡(luò)通過線性時間的個體最優(yōu)動作的分散策略，獲得最優(yōu)動作。聯(lián)合動作價值網(wǎng)絡(luò)共享獨(dú)立動作價值網(wǎng)絡(luò)的底層參數(shù)，并且結(jié)合獨(dú)立動作價值網(wǎng)絡(luò)的隱藏特征這些共享的參數(shù)可用于擴(kuò)展訓(xùn)練。

3.1.3 狀態(tài)價值網(wǎng)絡(luò)

狀態(tài)價值網(wǎng)絡(luò)通過計算標(biāo)量狀態(tài)值Vj，用于彌補(bǔ)與真實(shí)學(xué)習(xí)到的Qj(s，a)之間的差距，如果沒有狀態(tài)價值網(wǎng)絡(luò)，部分可觀測性將限制Q'j的復(fù)雜性，狀態(tài)值與給定狀態(tài)s的選定動作無關(guān)。因此，狀態(tài)價值網(wǎng)絡(luò)不利于動作的選擇，而是用于計算式（3）和式（4）的損失值。與聯(lián)合動作價值網(wǎng)絡(luò)相同，使用單個網(wǎng)絡(luò)的組合隱藏特征作為狀態(tài)價值網(wǎng)絡(luò)的輸入，以提高空間擴(kuò)展性。

定理1聯(lián)合動作價值函數(shù)Qj(s，a)被Qi(si，ai)分解，如式（3）和式（4）所示：

3.2 損失函數(shù)

集中訓(xùn)練有2 個主要目標(biāo)：訓(xùn)練聯(lián)合動作價值函數(shù)，計算真正的動作價值；轉(zhuǎn)化后的動作價值函數(shù)Qj應(yīng)近似聯(lián)合動作價值函數(shù)，它們的最優(yōu)動作是等價的。本文使用DDQN 方法來更新網(wǎng)絡(luò)［22］，設(shè)計全局損失函數(shù)，將3 個損失函數(shù)加權(quán)組合，如式（5）所示：

其中：r表示在智能體觀測環(huán)境執(zhí)行動作a后，狀態(tài)s轉(zhuǎn)換到下一狀態(tài)s'所獲得獎勵；Ltd表示估算實(shí)際動作價值的損失函數(shù)，通過學(xué)習(xí)Qj使誤差最小化；Lnopt和Lopt表示滿足式（3）和式（4）的因式分解損失函數(shù)，Lnopt的作用是驗(yàn)證在樣本中選擇的動作是否滿足式（4），則進(jìn)一步確認(rèn)Lopt得到的最優(yōu)局部動作是否滿足式（3）。因此，本文通過定義損失函數(shù)來實(shí)現(xiàn)式（3）和式（4），根據(jù)網(wǎng)絡(luò)對樣本中所采取的動作是否滿足式（3）或式（4），但是這樣驗(yàn)證式（3）和式（4）所得到的動作將需要過多的樣本。由于在訓(xùn)練中很少采取最優(yōu)動作，因此本文VFD 框架的目標(biāo)是學(xué)習(xí)Q'j和Vj對給定的Qj進(jìn)行因式分解，在使用Lnopt和Lopt進(jìn)行學(xué)習(xí)時，通過修正Qj使學(xué)習(xí)更加穩(wěn)定。λopt和λnopt是2 個損失的權(quán)重常數(shù)，損失函數(shù)如式（6）～式（8）所示：

在上述3 個損失函數(shù)中，Ltd使用標(biāo)準(zhǔn)時序差分TD-error 來更新需學(xué)習(xí)的聯(lián)合動作值Qj(s，a)，Lopt和Lnopt通過Qj(s，a)來引導(dǎo)獨(dú)立動作值之和(s，a)與標(biāo)量狀態(tài)值Vj(s)的更新。

根據(jù)式（4），在ODDRL 中通過獨(dú)立動作價值函數(shù)Qi和狀態(tài)價值函數(shù)Vj來更新聯(lián)合動作值Qi，導(dǎo)致神經(jīng)網(wǎng)絡(luò)無法準(zhǔn)確地構(gòu)建Qi因式分解函數(shù)。式（4）條件可能會影響非最優(yōu)動作，從而降低訓(xùn)練過程的穩(wěn)定性或收斂速度。在此基礎(chǔ)上，本文提出另一種方法LF-ODDRL，如定理2 所示。

ODDRL 算法流程如下：

算法1ODDRL 算法

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

4.1 模擬平臺

與有監(jiān)督學(xué)習(xí)問題相比，多智能體強(qiáng)化學(xué)習(xí)的交互性給訓(xùn)練和評估帶來更多的困難。常見的解決方案是建立環(huán)境模擬器［23-24］。模擬器作為多智能體強(qiáng)化學(xué)習(xí)方法的訓(xùn)練環(huán)境，以及它們的評估器，是整個訓(xùn)練和學(xué)習(xí)的基礎(chǔ)。文獻(xiàn)［25］通過訓(xùn)練真實(shí)的歷史數(shù)據(jù)產(chǎn)生模擬訂單。在本文實(shí)驗(yàn)中，使用文獻(xiàn)［26］的模擬平臺模擬訂單的生成，實(shí)現(xiàn)分配訂單的過程。根據(jù)每輛網(wǎng)約車在平臺上第一次的位置和時間進(jìn)行初始化，駕駛員隨后的動作由模擬器決定，如進(jìn)行空閑移動或者離線/在線操作。模擬器經(jīng)過仔細(xì)校準(zhǔn)，對比模擬數(shù)據(jù)與真實(shí)數(shù)據(jù)，使兩者的誤差在允許范圍內(nèi)。

在基于網(wǎng)格模擬器中，將城市定義為圖2 所示的一張四邊形網(wǎng)格的地圖。在每個時間步，模擬器提供一個環(huán)境、一組空閑車輛和可用的訂單。所有模擬訂單與真實(shí)訂單都具有相同的屬性。為了提高模擬器的效率，每個乘客通過相同的網(wǎng)絡(luò)同時計算動作值。因此，這個網(wǎng)絡(luò)的輸出是一個矩陣，其行表示乘客，其列表示每個乘客可以匹配的車輛。（i，j）的矩陣值是第i名乘客和第j輛車匹配的動作值，每個乘客與列表中Q值最大的車配對，使得獎勵最大化，并且乘客的等待時間最小化。模擬器訓(xùn)練過程示意圖如圖4 所示。

圖4 模擬器訓(xùn)練過程示意圖Fig.4 Schematic diagram of simulator training process

4.2 實(shí)驗(yàn)結(jié)果

為了分析方法的性能，本文采用Random、Greedy、DQN 和QMIX 作為基線方法。

1）Random：模擬沒有任何訂單派送的場景，只在每個時間步長隨機(jī)分配閑置訂單，并隨機(jī)派送給網(wǎng)約車。

2）Greedy：貪婪方法被作為基線方法，并將其與各種強(qiáng)化學(xué)習(xí)方法進(jìn)行對比。貪婪方法遵循先到先得（FCFS）策略。因此，較早要求用車的乘客會獲得更高的優(yōu)先權(quán)。每個乘客根據(jù)距離（曼哈頓距離）配對到一輛車。

3）DQN：文獻(xiàn)［27］提出一種基于Q 學(xué)習(xí)網(wǎng)絡(luò)的動作價值函數(shù)近似方法，該網(wǎng)絡(luò)的參數(shù)化是由一個具有4 個隱層的多層感知機(jī)（MLP）組成，隱層之間采用ReLU 激活函數(shù)激活，并對Q 網(wǎng)絡(luò)的最終線性輸出進(jìn)行轉(zhuǎn)換，使得車輛與環(huán)境之間進(jìn)行局部交互，從而捕獲全局的動態(tài)需求與供應(yīng)變化關(guān)系。

4）QMIX：考慮了全局狀態(tài)，將聯(lián)合動作價值網(wǎng)絡(luò)函數(shù)分解為獨(dú)立價值函數(shù)并進(jìn)行分散執(zhí)行［28］，使聯(lián)合動作值最大化的聯(lián)合動作等于使獨(dú)立動作值最大化的一組動作。全局狀態(tài)動作值允許每輛車貪婪地選擇與它們獨(dú)立動作值相關(guān)的動作。

為了測試ODDRL 和LF-ODDRL 方法在訂單派送中的有效性和魯棒性，本文在不同的網(wǎng)格、乘客數(shù)量和車輛數(shù)的情況下進(jìn)行3 組實(shí)驗(yàn)，所提方法在整體上都優(yōu)于其他方法。如QMIX 方法能夠分解聯(lián)合動作價值函數(shù)，確保全局最優(yōu)動作和局部最優(yōu)動作的一致性，使得動作值最大化，但是通過神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)全局與局部之間的關(guān)系，確保全局動作值與局部動作值的單調(diào)性，僅解決了小部分可分解任務(wù)的問題。因此，該方法存在一定的局限性問題。本文方法克服了聯(lián)合動作值分解可加性和單調(diào)性的約束，以確保聯(lián)合動作和獨(dú)立動作是相同的，從而提高學(xué)習(xí)效率和擴(kuò)展性。

本文將網(wǎng)約車和乘客數(shù)量設(shè)置為固定的，在100×100 的網(wǎng)格上，使用把所有乘客送達(dá)目的地所持續(xù)的總時間作為評判指標(biāo)，6 種方法的總時間對比如表1 所示。P和C分別表示在固定人車網(wǎng)格中每回合初始的乘客數(shù)量和車輛數(shù)量，當(dāng)P=7，C=2 時，ODDRL 和LF-ODDRL 兩種方法相對于QMIX 接送乘客持續(xù)總時間分別減少了6%和18%，當(dāng)有大量車輛和乘客時，如P=25，C=20，持續(xù)總時間分別減少了10%和18%。實(shí)驗(yàn)結(jié)果表明，本文方法能有效解決網(wǎng)約車不足和充分問題。

表1 在100×100 網(wǎng)格上不同方法接送乘客的總時間對比Table 1 Total time for picking up passengers comparison among different methods on 100×100 grid

為進(jìn)一步衡量方法的可伸縮性，在10×10 和500×500 網(wǎng)格上，不同方法接送乘客持續(xù)總時間隨網(wǎng)約車和乘客數(shù)量的變化曲線分別如圖5 和圖6 所示。其中Random、Greedy、DQN 方法都是針對單個智能體，并沒有聯(lián)合所有智能體集中訓(xùn)練和分散執(zhí)行的策略，因此，其結(jié)果并不理想。QMIX 方法雖然考慮集中訓(xùn)練和分散執(zhí)行的策略，但是需聯(lián)合動作值和獨(dú)立動作值呈現(xiàn)單調(diào)性，阻礙了對非單調(diào)性結(jié)構(gòu)動作值函數(shù)的學(xué)習(xí)。而本文方法卻彌補(bǔ)了這些缺點(diǎn)，不僅聯(lián)合車輛共同學(xué)習(xí)，還針對不同規(guī)模的網(wǎng)格構(gòu)建ReLU 激活函數(shù)和訓(xùn)練訂單派送的策略Q 網(wǎng)絡(luò)，并且設(shè)計新的損失函數(shù)來縮小(s，a)與Qj(s，a)的差距。實(shí)驗(yàn)結(jié)果表明，ODDRL與LF-ODDRL 都優(yōu)于其他4 種基線方法，說明本文方法具有較優(yōu)的擴(kuò)展性。

圖5 在10×10 網(wǎng)格上不同方法接送乘客的總時間對比Fig.5 Total time for picking up passengers comparison among different methods on 10×10 grid

圖6 在500×500 網(wǎng)格上不同方法接送乘客的總時間對比Fig.6 Total time for picking up passengers comparison among different methods on 500×500 grid

在10×10 和500×500 的網(wǎng)格上，本文給網(wǎng)約車和乘客數(shù)量分別設(shè)置域值，并進(jìn)行訓(xùn)練和測試，接送乘客所持續(xù)的總時間如表2 所示。在500×500 的網(wǎng)格上，當(dāng)最大乘客數(shù)和車輛數(shù)都為20 時，ODDRL 與LF-ODDRL 相對于QMIX 接送乘客所持續(xù)的總時間分別減少了2%和12%，說明VFD 在應(yīng)對可變的乘客數(shù)和車輛數(shù)時，具有更強(qiáng)的學(xué)習(xí)能力，以更好適應(yīng)可變的環(huán)境。

表2 不同方法接送乘客的總時間對比Table 2 Total time for picking up passenges comparison among different methods

為驗(yàn)證本文設(shè)計動作搜索損失函數(shù)的有效性，本文在10×10 網(wǎng)格P=7，C=2 的條件下進(jìn)行實(shí)驗(yàn)。不同方法的損失值對比如圖7 所示。本文設(shè)計的損失函數(shù)是從當(dāng)前的Q 網(wǎng)絡(luò)中找出最大Q值對應(yīng)的動作，利用這個選擇的動作在目標(biāo)網(wǎng)絡(luò)中計算目標(biāo)Q值。從圖7 可以看出，LF-ODDRL 的收斂速度和效果都優(yōu)于ODDRL 方法。

圖7 不同方法的損失值對比Fig.7 Loss values comparison among different methods

5 結(jié)束語

本文基于VFD 框架提出多智能體強(qiáng)化學(xué)習(xí)方法ODDRL 和LF-ODDRL，用于解決PDP 問題。將訂單派送建模為一個分布式?jīng)Q策問題，把初始的聯(lián)合動作值函數(shù)分解為多個獨(dú)立的值函數(shù)，使聯(lián)合動作值函數(shù)中的動作與獨(dú)立動作值函數(shù)中的動作相一致。將每輛車以分布式的方式執(zhí)行動作，通過集中訓(xùn)練和分散執(zhí)行的方式確定車輛與訂單之間的最佳匹配關(guān)系，達(dá)到優(yōu)化平臺長期運(yùn)作效率的目的，同時最大程度縮短接送時間，提高乘客舒適度。實(shí)驗(yàn)結(jié)果表明，相比Random、Greedy、DQN 等方法，ODDRL 和LF-ODDRL 能夠有效縮短接送時間，在不同規(guī)模網(wǎng)格上具有較優(yōu)的擴(kuò)展性。后續(xù)將原始車輛GPS 數(shù)據(jù)與乘客的個人偏好及其目的地距離相結(jié)合，最大化縮短接送時間，從而提高乘客和司機(jī)的出行效率。