基于深度強化學習的網(wǎng)約車動態(tài)路徑規(guī)劃

鄭渤龍 明嶺峰 胡 琦 方一向 鄭 凱 李國徽

1(華中科技大學計算機科學與技術(shù)學院 武漢 430074) 2(香港中文大學(深圳)數(shù)據(jù)科學學院 廣東深圳 518172) 3(電子科技大學計算機科學與工程學院 成都 610054)

網(wǎng)約車平臺，如滴滴出行和優(yōu)步等，允許用戶在手機app或小程序上發(fā)起打車請求，由平臺通過智能算法將請求與空閑的網(wǎng)約車進行匹配，在近年來得到了快速發(fā)展.一方面，與傳統(tǒng)的司機在街道上尋找乘客的模式相比，網(wǎng)約車平臺有效地減少了網(wǎng)約車的空駛時間，提升了司機的收益，并大大減少了乘客打不到車的情況，提高了城市交通系統(tǒng)的運行效率.另一方面，這些網(wǎng)約車平臺積累了大量的包含乘客的出行模式等信息的數(shù)據(jù)，例如軌跡數(shù)據(jù)和訂單數(shù)據(jù)，這些數(shù)據(jù)可以進一步用于交通領(lǐng)域的許多應用，如需求預測、訂單分派和車隊管理.

作為網(wǎng)約車平臺的核心模塊，網(wǎng)約車路徑規(guī)劃需要管理城市中的所有網(wǎng)約車，為空閑網(wǎng)約車指派巡航路線，將其調(diào)度到潛在的乘客位置，同時又要協(xié)調(diào)各輛網(wǎng)約車，防止其相互之間競爭乘客，以充分利用有限的網(wǎng)約車資源，平衡網(wǎng)約車的供應與乘客的打車需求之間的差距.然而，現(xiàn)實情況是，盡管在需求端每天有數(shù)萬請求通過網(wǎng)約車平臺進行處理，但仍然有許多的打車請求由于附近沒有空閑網(wǎng)約車而未能及時處理，或是需要等待很長的時間才能打到車.而在供應端，依然有相當一部分的網(wǎng)約車無法接到乘客，需要空駛很長一段時間才能找到合適的乘客.這種供需不平衡的現(xiàn)象在大城市中每天都在發(fā)生，這既降低了平臺的收益，也影響了用戶的體驗，并進一步導致了交通擁堵和資源浪費.因此，有效的網(wǎng)約車路徑規(guī)劃對網(wǎng)約車平臺有著重要的意義.

制定有效的網(wǎng)約車路徑規(guī)劃策略主要存在3項挑戰(zhàn)：1)需要對動態(tài)變化的供需分布進行建模，以準確預測每個區(qū)域?qū)W(wǎng)約車資源的需求；2)需要防止空閑網(wǎng)約車聚集在熱門區(qū)域，而導致這些區(qū)域出現(xiàn)運力過剩，而其他區(qū)域又運力不足的情況；3)需要考慮處于偏僻區(qū)域的網(wǎng)約車，讓其能更快駛離當前區(qū)域，從而減少無效的巡航時間.

現(xiàn)有方法通過對歷史網(wǎng)約車數(shù)據(jù)進行建模來解決上述挑戰(zhàn).RHC通過構(gòu)建供需模型調(diào)度網(wǎng)約車以應對靜態(tài)交通環(huán)境.深度強化學習(deep reinforce-ment learning, DRL)算法可以處理動態(tài)的交通環(huán)境，具有更好的性能.但是DRL算法在建模時面臨著簡化設定的問題，例如，大多數(shù)DRL算法都假設所有空閑網(wǎng)約車同時進行調(diào)度，并且假設網(wǎng)約車能夠在下一時間片到達調(diào)度終點，而這在實際交通環(huán)境中是不可能的.而本文的調(diào)度策略會在網(wǎng)約車空閑時立即對其進行路徑規(guī)劃，不存在不合理的假設，更貼近真實的交通環(huán)境.

相比基于值函數(shù)的算法(如deep Q-network, DQN)，actor-critic采用策略梯度的算法可以在連續(xù)動作空間或高維動作空間中選取合適的動作，而這是基于值函數(shù)的算法無法做到的；相比單純策略梯度的算法，actor-critic采用類似DQN的策略評估算法，可以進行單步更新而不是回合更新，比單純策略梯度的算法更有效.因此，本文基于actor-critic的算法，提出了一種供需感知的深度強化學習算法，用于網(wǎng)約車調(diào)度.首先，通過定義智能體、狀態(tài)、動作和獎勵，將網(wǎng)約車路徑規(guī)劃問題轉(zhuǎn)化為一個Markov決策過程(Markov decision process, MDP).然后，設計了一個具有動作采樣策略的執(zhí)行者-評論者(actor-critic with action sampling policy, AS-AC)網(wǎng)絡結(jié)構(gòu)，以學習最佳的調(diào)度策略.

本文的主要貢獻包括3個方面：

1) 提出了一個基于實時供需狀態(tài)的動態(tài)網(wǎng)約車路徑規(guī)劃框架，實現(xiàn)高效的大規(guī)模空閑網(wǎng)約車調(diào)度，通過包含實時的供需信息來適應動態(tài)變化的環(huán)境.

2) 設計了一種帶有動作采樣的AS-AC算法來選擇可行的動作，增加了動作選擇的隨機性，從而有效地防止競爭.

3) 使用真實的網(wǎng)約車訂單數(shù)據(jù)進行了大量實驗，實驗結(jié)果表明提出的方法相比對比方法有著更低的請求拒絕率.

1 相關(guān)工作

1.1 車隊管理

車隊管理是網(wǎng)約車平臺的一項主要決策任務，它包括確定車隊的規(guī)模和配置、車隊分配、車輛路線規(guī)劃等，這些都廣泛應用于交通運輸中.其中網(wǎng)約車路徑規(guī)劃是車隊管理問題的核心任務，許多研究致力于有效地解決此問題或其變體，例如車輛路由問題(vehicle routing problem, VRP)、最小車隊問題(minimum fleet problem, MFP)和乘車問題.大多數(shù)方法首先將這些問題轉(zhuǎn)換成經(jīng)典的圖論問題，然后采用組合優(yōu)化的方法去求解.例如，Vazifeh等人將最小車隊問題建模為二部圖上的最大匹配問題，然后采用Hopcroft-Karp算法確定服務所有訂單所需的最小車隊的規(guī)模.

隨著網(wǎng)約車服務的普及，調(diào)度城市中的空閑網(wǎng)約車以平衡不同位置的供需成為一個新的研究熱點.許多工作對城市中的網(wǎng)約車供需進行建模，調(diào)度空閑網(wǎng)約車來平衡供需，以最大程度地減少乘客的等待時間和網(wǎng)約車的空駛時間.例如，文獻[18]將網(wǎng)約車調(diào)度任務建模為最小費用流(minimum cost flow, MCF)問題，并使用組合優(yōu)化的方法對其進行求解.后退水平控制模型根據(jù)供需模型和網(wǎng)約車的實時位置來調(diào)度網(wǎng)約車，以減少網(wǎng)約車空駛的距離.然而，這些基于模型的方法局限于預先確定的供需模型，因此難以適應車輛狀態(tài)和出行請求都在不斷變化的真實交通環(huán)境.

1.2 深度強化學習

深度強化學習將具有強大感知力的深度學習方法和具有優(yōu)秀決策力的強化學習方法相結(jié)合，通過試錯的方式來學習智能體在觀測狀態(tài)下應采取的最佳動作.DRL利用神經(jīng)網(wǎng)絡來估計狀態(tài)動作值，并通過更新網(wǎng)絡參數(shù)來學習最佳行為策略，已經(jīng)在許多具有挑戰(zhàn)性的領(lǐng)域取得了突破性的進展，例如，圍棋、電子游戲和自動駕駛.然而，主流的深度強化學習算法，如DQN和Reinforce主要適用于低維度且樣本容易獲取的任務，而在高維和非靜態(tài)的動作空間中表現(xiàn)不佳.本文通過實時的供需估計和巧妙的采樣策略，運用深度強化學習算法來解決網(wǎng)約車路徑規(guī)劃問題.

1.3 基于深度強化學習的網(wǎng)約車路徑規(guī)劃

由于網(wǎng)約車路徑規(guī)劃這一決策任務可以很自然地建模為Markov決策問題，許多最近的研究都致力利用深度強化學習設計模型無關(guān)的方法來調(diào)度網(wǎng)約車.這些方法可以分為基于值函數(shù)的方法(如DQN)和基于策略梯度方法(如A3C).基于值函數(shù)的方法主要使用DQN來估計動作的價值，通過神經(jīng)網(wǎng)絡計算出動作價值，然后選擇價值最大的動作.例如，MOVI通過卷積神經(jīng)網(wǎng)絡(convolutional neural network, CNN)來提取供需分布特征并采用分布式的DQN策略學習單獨的車輛的最優(yōu)調(diào)度動作.COX采用聚類算法將路網(wǎng)劃分為許多用于網(wǎng)約車調(diào)度的區(qū)域，再通過環(huán)境感知的需求預測模型和實時的網(wǎng)約車狀態(tài)來計算區(qū)域級別的供需，最后將這些供需信息加入到狀態(tài)中，提高DQN的表現(xiàn).與基于值函數(shù)的方法不同，策略梯度方法用神經(jīng)網(wǎng)絡來近似策略，采用梯度上升法來尋找最優(yōu)策略.例如，CoRide將訂單調(diào)度和車隊管理概述為部分可觀測Markov決策問題(partially observable Markov decision process, POMDP)，然后采用深度確定性策略梯度(deep deterministic policy gradient, DDPG)算法來學習訂單匹配和車隊管理的最優(yōu)策略，以最大化累積司機收入(accumulated driver income, ADI)和訂單應答率(order response rate, ORR).文獻[11]在求解動作空間時考慮了地理環(huán)境和協(xié)作環(huán)境，消除了無效的網(wǎng)格從而減小了動作空間，并提出contextual actor-critic多智能體強化學習算法用于網(wǎng)約車學習行為策略.

盡管這些方法相比基于模型的方法有著更強大的能力以適應復雜動態(tài)的交通環(huán)境，它們?nèi)匀皇芟抻诓滑F(xiàn)實的問題設定.例如，大多數(shù)方法要求所有的網(wǎng)約車在每個時間片同時進行調(diào)度決策，并要求網(wǎng)約車能在下一時間片到達調(diào)度終點，這在現(xiàn)實的動態(tài)交通場景中很難保證.此外，只把鄰居網(wǎng)格作為動作空間會使得處于偏僻區(qū)域的網(wǎng)約車很難盡快駛離這些區(qū)域.與現(xiàn)有的方法不同，本文不對所有的網(wǎng)約車進行統(tǒng)一調(diào)度，而是將每一輛網(wǎng)約車看作單獨的同質(zhì)智能體，共享網(wǎng)絡參數(shù)和調(diào)度策略，當一輛網(wǎng)約車變?yōu)榭臻e狀態(tài)時立即對其進行調(diào)度.此外，提出的供需感知的強化學習方法采用變化的動作空間來代替靜態(tài)的動作空間，在以鄰近網(wǎng)格作為可行調(diào)度動作的基礎(chǔ)上加上了全局熱門區(qū)域，并采用動作過濾和采樣來平衡全局供需分布.本文的框架在網(wǎng)約車變?yōu)榭臻e時就為其分配搜索路線，并激勵網(wǎng)約車在其到達調(diào)度終點前盡快被分配請求，更接近真實的交通場景.

2 網(wǎng)約車路徑規(guī)劃問題

本節(jié)將介紹網(wǎng)約車路徑規(guī)劃問題的背景，包括問題設置、問題定義和框架概述，并將該問題描述為一個Markov決策過程.表1總結(jié)了本文常用的符號.

Table 1 Summary of Notation

2.1 問題敘述

網(wǎng)約車路徑規(guī)劃問題由空間中的一組網(wǎng)約車車隊、流形式的請求和一個管理所有網(wǎng)約車的調(diào)度中心所組成.

定義3.

調(diào)度中心

.

調(diào)度中心包括3個模塊：車隊管理模塊、請求預測模塊和調(diào)度策略模塊

.

車隊管理模塊跟蹤每輛網(wǎng)約車的實時位置和占用狀態(tài)，并更新供應分布

.

請求預測模塊根據(jù)歷史訂單信息預測未來的乘客請求分布

.

調(diào)度策略模塊基于供需分布將空閑的網(wǎng)約車調(diào)度到未來請求可能出現(xiàn)的位置

.

(1)

給定一組網(wǎng)約車和一個乘客請求流，調(diào)度中心需要為空閑網(wǎng)約車規(guī)劃巡航路線以使得其能夠盡快服務潛在的請求，從而最小化請求拒絕率

.

2.2 框架總覽

ST-GCSL模型將請求預測問題建模為圖節(jié)點預測問題，采用圖神經(jīng)網(wǎng)絡技術(shù)，同時提取短期與長期時空依賴關(guān)系，具有很高的預測精度.因此，在框架中，使用ST-GCSL作為請求預測模型.具體而言，使用Uber H3庫將城市路網(wǎng)劃分為一組六邊形網(wǎng)格

G

={

g

,

g

,…,

g

||}；將一天劃分為一個時間片序列，表示為

T

={

t

,

t

,…,

t

||}

.

如圖1所示，車隊管理模塊跟蹤網(wǎng)約車的實時位置，以獲取下一個時間片網(wǎng)約車供應量，而請求預測模塊則根據(jù)歷史的請求時空分布，預測未來的網(wǎng)約車需求分布.供需感知的深度強化學習調(diào)度策略將供需結(jié)合起來，以確定空閑網(wǎng)約車的調(diào)度動作，然后網(wǎng)約車將會朝著調(diào)度終點巡航.對于收到的新請求，調(diào)度中心分配最近的空閑網(wǎng)約車為其服務.當網(wǎng)約車被分配給一個請求后，它會首先沿著最短路徑前往請求的起點去接乘客，然后駛向請求的終點以完成服務.如果一個請求在其最長等待時間內(nèi)都沒有被分配給網(wǎng)約車，則該請求將被拒絕.

Fig. 1 Interaction between taxis and passengers with the dispatching center圖1 網(wǎng)約車、乘客在調(diào)度中心下的交互

2.3 Markov決策過程的構(gòu)建

本文將網(wǎng)約車路徑規(guī)劃問題建模為Markov決策過程(MDP).具體地，將網(wǎng)約車視為與外部環(huán)境交互的智能體，并將每次路線規(guī)劃看作是一次決策.采用六邊形網(wǎng)格劃分空間對動作空間進行離散化.如圖2所示，將空閑網(wǎng)約車調(diào)度到目標網(wǎng)格視為是一個動作.

Fig. 2 An example of MDP formulation圖2 一個MDP敘述的例子

MDP包含狀態(tài)、動作、獎勵、回合、策略和狀態(tài)-動作價值函數(shù)6個關(guān)鍵元素.

(2)

(3)

2) 動作

a

∈

A.

動作

a

=〈

g

〉是指將空閑網(wǎng)約車派往某個特定的目的網(wǎng)格

g

.

所有可行的動作組成了動作空間，用

A

表示

.A

包括當前區(qū)域的

k

-階鄰居區(qū)域中需求與供應之差大于當前區(qū)域的所有區(qū)域和全局的熱門區(qū)域

.

因此對于不同的供需狀態(tài)

s

，動作空間

A

也是不同的

.

值得注意的是，由于網(wǎng)約車在調(diào)度的執(zhí)行過程中也可以接單，因此其并不一定能到達調(diào)度終點(中途被分配給請求)

.

3) 獎勵

r

.

使用文獻[8]中有效行駛比作為即時獎勵，其定義為：

(4)

其中,

d

為調(diào)度過程的持續(xù)時間，該過程從網(wǎng)約車空閑開始到乘客下車結(jié)束；設

d

為調(diào)度過程中乘客乘坐網(wǎng)約車的持續(xù)時間

.

式(4)計算的獎勵

r

考慮服務請求的收入和空閑巡航的成本

.

注意到較大的

r

表示網(wǎng)約車在短時間閑置后迅速分配給乘客，因此獲得的獎勵很高

.

如果網(wǎng)約車到達調(diào)度目的地時未分配任何請求，則獎勵為0

.

4) 回合

.

在該問題設定中，一個回合是從8∶00到22∶00的繁忙時段

.

因此，時間

t

在22∶00之后的狀態(tài)為終止狀態(tài)

.

5) 策略

π

(

a

|

s

)

.

策略函數(shù)表示從狀態(tài)到可行動作

A

的概率分布的映射

.

對于確定性的策略，輸出是一個特定的動作

.

通過深入的與環(huán)境進行交互，代理旨在學習到一個最優(yōu)的策略

π

，以最大化預期獎勵

.

6) 狀態(tài)-動作價值函數(shù)

Q

(

s

,

a

)

.

狀態(tài)-動作價值函數(shù)是司機從狀態(tài)

s

開始，執(zhí)行調(diào)度動作

a

，并且之后按照策略

π

執(zhí)行調(diào)度動作，直到回合結(jié)束能得到的獎勵和的期望，由于使用有效性行駛比作為獎勵，因此

Q

表示的是預期累積有效行駛比，定義為

(5)

其中,

t

表示當前時間片，考慮到短期的獎勵的影響更大，估值也更準，這里加入?yún)?shù)

γ

作為未來獎勵的折扣因子，以對長期的獎勵進行衰減

.

更具體地，在圖2中給出了上述MDP概述的一個例子

.

在時刻

t

，一輛處于狀態(tài)

s

的空閑車輛被指派了一條從網(wǎng)格0到網(wǎng)格17的搜索路線，執(zhí)行前往網(wǎng)格17的動作

.

當它行駛到網(wǎng)格6時，在網(wǎng)格16出現(xiàn)一個請求并且這輛車被分配給了這個請求

.

因此它前往該請求的位置去接乘客，然后駛向位于網(wǎng)格12的訂單終點，獲得對應的獎勵

r

，并到達下一狀態(tài)

s

′

.

3 供需感知的深度強化學習

本節(jié)介紹一種供需感知的深度強化學習算法，稱為AS-AC算法.

3.1 動作空間的確定

首先，通過考慮以下2種類型的網(wǎng)格來初始化可行動作空間

A

：1) 地理鄰居網(wǎng)格

.

為了確保合理的調(diào)度距離，選擇當前網(wǎng)格的鄰居網(wǎng)格

.

具體來說，在實驗中選擇了紐約數(shù)據(jù)集的三階鄰域和海口數(shù)據(jù)集的二階鄰域內(nèi)的網(wǎng)格

.

2) 全局熱門網(wǎng)格

.

在下一個時間片中預測請求數(shù)量最多的少數(shù)網(wǎng)格(紐約為5個網(wǎng)格，海口為3個網(wǎng)格)，因為大多數(shù)請求都出現(xiàn)在這些網(wǎng)格中

.

為了減少計算開銷，需要從初始動作空間

A

中移除無效的動作

.

這是因為，如果當前網(wǎng)格的供需差大于調(diào)度目標網(wǎng)格的供需差，停留在當前網(wǎng)格更可能獲得更高的獎勵，并且可以減少調(diào)度開銷

.

因此，可以從動作空間中刪除這些調(diào)度動作

.

對于

A

中的每個網(wǎng)格

g

，首先根據(jù)式(2)(3)分別計算供應和需求，然后通過如式(6)計算供需差

ρ

：

(6)

最后，從動作空間

A

中移除供需差小于網(wǎng)約車當前網(wǎng)格的動作

.

3.2 AC模型

actor-critic(AC)算法結(jié)合了基于值函數(shù)的方法與基于策略梯度方法的優(yōu)勢，避免了低維度動作空間的限定，可擴展性更強.因此，使用AC模型學習得到空閑網(wǎng)約車的最佳調(diào)度策略，它通過調(diào)整策略網(wǎng)絡的權(quán)重來適應動態(tài)變化的環(huán)境.不同于DQN采用價值函數(shù)來制訂策略，AC采用一個叫做actor的策略網(wǎng)絡來直接近似策略，用于選擇動作，用一個稱為critic的價值網(wǎng)絡來評估所選擇的動作.相比基于值函數(shù)的方法，它不僅能夠?qū)崿F(xiàn)更穩(wěn)定的學習過程，還適用于高維度或連續(xù)的動作空間.

本文采用了2種技術(shù)來提升網(wǎng)絡的性能：1)對于critic網(wǎng)絡，類似DQN，采用原始和目標2個相同的價值網(wǎng)絡來實現(xiàn)周期穩(wěn)定更新；2)通過嵌入地理鄰居和供需差來過濾無效動作使得能夠調(diào)整策略以適應動態(tài)變化的動作空間.

出臺《松江區(qū)關(guān)于推進公共圖書館總分館制建設管理暫行辦法》，整合區(qū)內(nèi)公共閱讀資源，實行總館主導下的統(tǒng)一文獻資源目錄、統(tǒng)一編目、統(tǒng)一配送、通借通還和人員培訓。總館對分館加強業(yè)務指導，分館按照總館服務標準，對轄區(qū)內(nèi)基層服務點實施業(yè)務考核、績效管理、采編目錄等方面的統(tǒng)一管理。制定《松江區(qū)公共圖書館服務規(guī)范》，規(guī)范服務項目，完善內(nèi)部制度，以區(qū)級公共文化“服務規(guī)范”，提升全區(qū)公共圖書館行業(yè)服務水平。

采用小批量反向傳播算法訓練網(wǎng)絡，對于critic價值網(wǎng)絡，如圖3所示，根據(jù)貝爾曼方程得到時序差分誤差，以此平方作為損失函數(shù)：

(7)

(8)

θ

←

θ

+

α

?

L

(

θ

),

(9)

其中，

α

是critic網(wǎng)絡的學習率

.

價值網(wǎng)絡的輸入為智能體的當前狀態(tài)

s

，輸出為常量

V

(

s

;

θ

)表示當前狀態(tài)價值

.

Fig. 3 The structure of critic network圖3 Critic價值網(wǎng)絡結(jié)構(gòu)

對于actor策略網(wǎng)絡，如圖4所示，采用第3.3節(jié)提到的動作采樣策略替換傳統(tǒng)actor網(wǎng)絡最后的softmax層.為了減小動作選擇的方差，引入了一個優(yōu)勢函數(shù)來代替critic網(wǎng)絡中的原始回報，以衡量選取的動作值與所有動作平均值的好壞，用時序差分來近似優(yōu)勢函數(shù)，即：

A

(

s

,

a

)=

td

，那么策略網(wǎng)絡的梯度為?

J

(

θ

)=?log

π

(

a

|

s

)

A

(

s

,

a

),

(10)

其中，

θ

是策略網(wǎng)絡參數(shù)

.

根據(jù)計算得到的策略梯度，策略網(wǎng)絡參數(shù)

θ

更新為

θ

←

θ

+

α

?

J

(

θ

),

(11)

其中，

α

是actor網(wǎng)絡的學習率

.

策略網(wǎng)絡的輸入為智能體的當前狀態(tài)

s

，輸出為數(shù)組

Q

(

s

;

a

)表示當前狀態(tài)下執(zhí)行所有動作對應的狀態(tài)價值函數(shù)

.

Fig. 4 The structure of Actor network圖4 Actor策略網(wǎng)絡結(jié)構(gòu)

① 初始化記憶庫

M

的容量為

N

；

③ 初始化actor網(wǎng)絡參數(shù)

θ

為隨機值；④ for

m

=1 to

max

-

episodes

do⑤ 重置所有網(wǎng)約車為初始狀態(tài)

s

；⑥ for

t

=1 to |

T

| do⑦ 對每輛空閑網(wǎng)約車生成并存儲狀態(tài)轉(zhuǎn)移元組(

s

,

a

,

r

,

s

+1)到

M

；

⑧ end for

3.3 動作采樣策略

在當前狀態(tài)

s

下，為了得到具體的動作，基于狀態(tài)-動作價值函數(shù)

Q

(

s

,

a

)從

A

中選擇一個動作

.

然而，傳統(tǒng)的“

ε

-貪婪”策略會以1-

ε

的概率選擇價值最大的動作，導致大部分空閑出租車都前往熱門區(qū)域，造成“羊群效應”，無法很好地對網(wǎng)約車進行協(xié)調(diào)

.

為了實現(xiàn)網(wǎng)約車之間的協(xié)調(diào)，采取了動作優(yōu)先級采樣策略，與文獻[38]中基于時序差分誤差的經(jīng)驗優(yōu)先級采樣策略不同，依據(jù)動作價值函數(shù)

Q

(

s

,

a

)對可行性動作進行采樣

.

具體而言，對動作價值函數(shù)

Q

(

s

,

a

)做類似softmax處理，以確保動作被采樣的概率與動作價值是單調(diào)遞增的關(guān)系，同時確保最小價值的動作被采樣的概率非零

.

具體地，第

i

個動作被采樣的概率計算為

(12)

其中,

p

>0是

A

中第

i

個動作的優(yōu)先級，而

τ

是確定使用多少優(yōu)先級的參數(shù)，當

τ

=0時，對應于統(tǒng)一隨機采樣

.

對于優(yōu)先級

p

，有如下2種變體：1) 比例優(yōu)先級

.

其中

p

=

Q

(

s

,

a

)，它表示從

A

中根據(jù)狀態(tài)價值成比例的采樣動作

.

值得注意的是，由于基于排序的優(yōu)先級對異常值不敏感，具有更好的魯棒性，因此實驗中默認選擇其來制訂采樣策略，與對比方法進行比較，并且在實驗中比較這2種變體

.

最終，根據(jù)動作采樣策略從

A

中采樣得到調(diào)度動作

.

3.4 調(diào)度地點確定

為了實現(xiàn)更加細粒度的供需平衡，使用文獻[16]中供需分布不匹配度來確定每個空閑網(wǎng)約車的具體調(diào)度位置

.

對于調(diào)度位置

l

∈

a

.g

，令

x

(

l

)和

y

(

l

)分別為

l

處空閑網(wǎng)約車的數(shù)量和預測請求數(shù)量，則

l

處的供需分配不匹配度計算為

(13)

對于每次調(diào)度，從目的網(wǎng)格

a

.g

中貪婪地選擇需求供應不匹配最小的位置作為調(diào)度目的地，然后網(wǎng)約車沿著最短路徑前往目的地

.

當目的網(wǎng)格中沒有空閑網(wǎng)約車時，選擇該網(wǎng)格中心作為調(diào)度目的地，因為它能保證與網(wǎng)格中的其他位置距離不會過遠

.

算法2中詳細地介紹了AS-AC的執(zhí)行過程

.

算法2.

AS-AC算法.輸入：當前狀態(tài)

s

；輸出：一個調(diào)度動作

a

.

① 計算源動作價值

Q

(

s

,

a

),?

i

=1,2,…,|

G

|；② 初始化動作空間

A

為地理鄰居和全局熱門網(wǎng)格；③ 從

A

移除無效的動作；④ 初始化大小為|

G

|的數(shù)組

F

，并設置

F

=1,?

a

∈

A

；⑤ 通過狀態(tài)-動作價值

Q

(

s

,

a

)×

F

對動作

a

∈

A

進行排序，并計算對應優(yōu)先級；⑥ 根據(jù)式(12)采樣一個動作

a

；⑦ return

a

.

4 實驗與結(jié)果

解決交通問題的強化學習方法通常需要一個動態(tài)模擬環(huán)境用于訓練模型和評估算法，采用并拓展了車隊管理模擬器COMSET，以訓練并評估調(diào)度策略.實驗用Java實現(xiàn)調(diào)度策略和所有的對比方法，使用Python3.6和Tensorflow1.15.0來構(gòu)建并訓練模型，其中網(wǎng)絡模型在一臺裝配有Nvidia Tesla P100 GPU和16 G內(nèi)存的機器上訓練.

4.1 環(huán)境模擬器與數(shù)據(jù)集

基于真實數(shù)據(jù)集，采用并拓展了能夠模擬外部環(huán)境的COMSET模擬器訓練DRL模型.該模擬器是對網(wǎng)約車平臺如何管理網(wǎng)約車和處理乘客請求的整個過程進行建模.具體而言，在模擬開始時，根據(jù)輸入的OSM JSON文件創(chuàng)建一個地圖，并通過輸入邊界多邊形對其進行裁剪.乘客請求從歷史訂單數(shù)據(jù)中讀取，每一個請求對應一個歷史訂單記錄，只保留上下車位置均在邊界多邊形范圍內(nèi)的請求，并按照上車時間的先后順序以流的形式進入系統(tǒng). 固定數(shù)量的網(wǎng)約車被部署在地圖上的隨機位置，并按照調(diào)度策略給出的搜索路線進行巡航.當請求進入系統(tǒng)后，控制中心為其分配最近的空閑網(wǎng)約車；網(wǎng)約車接受請求，前往請求起點接乘客，再將其送到請求終點，期間車輛都沿著最短路徑行駛.更重要的，模擬器會通過歷史訂單數(shù)據(jù)校正每條路段的旅行速度，因此COMSET產(chǎn)生的平均旅行時間與真實數(shù)據(jù)基本一致.

本文采用紐約和海口2個真實網(wǎng)約車數(shù)據(jù)集評估模型，有關(guān)數(shù)據(jù)集的信息統(tǒng)計在表2中，值得注意的是每條訂單記錄包含起點與終點信息、訂單類型、旅行時間、乘客數(shù)量等信息.

1) 紐約數(shù)據(jù)集.紐約黃色網(wǎng)約車訂單數(shù)據(jù)包括了2016年1月到6月中上車和下車點均在紐約市的網(wǎng)約車訂單，而路網(wǎng)數(shù)據(jù)來源于OpenStreetMap，其中包含了4 360個節(jié)點和9 542條邊.選取2016年6月1日至21日數(shù)據(jù)用于訓練模型，6月22日至28日數(shù)據(jù)用評估模型.

2) 海口數(shù)據(jù)集.海口數(shù)據(jù)來源于海口市2017年5月到10月的網(wǎng)約車訂單記錄，路網(wǎng)包含3 298個節(jié)點和8 034條邊.選取2017年10月1日至21日數(shù)據(jù)用于訓練，10月22日至28日數(shù)據(jù)用于評估模型.

Table 2 Dataset Statistics

4.2 對比算法與度量標準

通過實驗對比以下6種算法的效果：

1) RD.從路網(wǎng)中隨機選取一個節(jié)點作為目的地，選取從當前位置到目的地的最短路徑作為搜索路線.

2) MCF-FM. MCF-FM根據(jù)權(quán)重采樣的方法選擇調(diào)度終點，并在每個時間片中對空閑司機進行統(tǒng)一調(diào)度.

3) FMU. FMU根據(jù)動態(tài)的節(jié)點權(quán)重進行采樣，并為等待中的請求增加額外的權(quán)重.

4) Q-learing. 標準表格式的Q-learning學習一個含有“

ε

-貪婪”策略的

q

表

.

實驗中，狀態(tài)簡化為只包含智能體的位置和時間，并設置

ε

=0

.

1

.

5) DQN. 狀態(tài)、動作和獎勵定義與本文一樣，采取“

ε

-貪婪”策略選取

Q

(

s

,

a

)值最大的動作作為調(diào)度目的地，實驗中

ε

=0

.

1

.

6) AS-AC. 本文提出的具有動作采樣策略的供需感知的執(zhí)行者-評論者方法.

為了評估上述算法，統(tǒng)一采用3種度量標準：

1) 拒絕率(reject rate,

RR

)，指被拒絕的請求數(shù)占請求總數(shù)的比例，它在所有度量標準中具有最高的優(yōu)先級；2) 巡航時間(cruising time,

CT

)，指網(wǎng)約車從空閑狀態(tài)到乘客上車的平均時間，由總的空閑行駛時間除以接收的請求數(shù)量得到；3) 等待時間(waiting time,

WT

)，指乘客從發(fā)出請求到司機到達上車點的平均等待時間，由總的等待時間除以請求數(shù)量.

4.3 實驗參數(shù)與結(jié)果對比

由表2可知，紐約數(shù)據(jù)集的規(guī)模比海口數(shù)據(jù)集大很多，如果對海口數(shù)據(jù)集采用和紐約數(shù)據(jù)集相同的劃分粒度，則每個分區(qū)的數(shù)據(jù)將十分稀疏.為了避免這一問題，根據(jù)數(shù)據(jù)集的規(guī)模調(diào)整時空劃分的粒度.具體而言，在紐約和海口數(shù)據(jù)集上設定時間片長度分別為5 min和10 min；采用Uber H3庫將紐約和海口路網(wǎng)分別劃分為99和30個網(wǎng)格.每個請求的最大生命周期

t

=5 min，即乘客最多等待5 min，如果5 min內(nèi)沒有司機接單，則該請求被視為拒絕，并從系統(tǒng)中移除.對于提出的方法，其設定的參數(shù)如下：actor與critic網(wǎng)絡(如圖3、圖4)均采用3層全連接層，每層包含128個隱藏單元，并采用ReLU激活函數(shù).記憶庫容量

N

=100 000，采樣的批量大小

b

=64，critic中目標網(wǎng)絡更新的周期

B

=1 000，折扣因子

γ

=0

.

9，學習率

α

=0

.

001，

α

=0.000 5.

為了驗證方法的魯棒性，在不同網(wǎng)約車數(shù)量下進行對比實驗，實驗結(jié)果如表3所示，其中每種度量標準的最佳結(jié)果用粗體表示.

Table 3 The Results on Two Real-World Datasets

續(xù)表3

Fig. 5 Comparison of variants on New York dataset圖5 2種變體在紐約數(shù)據(jù)集上的比較

一般而言，網(wǎng)約車數(shù)量越多，可以服務越多請求，這樣拒絕率(

RR

)、平均巡航時間(

CT

)以及平均等待時間(

WT

)都會降低.更具體些，可以從表3中得出以下4點結(jié)論：

1) MCF-FM和FMU相比于隨機調(diào)度策略RD在所有的度量標準上都有很大的提升.這是因為MCF-FM和FMU均根據(jù)歷史訂單數(shù)據(jù)為節(jié)點分配合理的權(quán)重，直觀上，熱門區(qū)域具有較高的權(quán)重，再根據(jù)權(quán)重采樣可以很好地平衡供應與需求.

2) 基于歷史數(shù)據(jù)學習動作價值函數(shù)的Q-learning相比于RD也有所提升，但其提升的程度沒有MCF-FM與FMU大，這是因為Q-learning的性能受限于確定性的狀態(tài)空間，而由于交通環(huán)境的復雜性，實際產(chǎn)生的狀態(tài)是無窮多的，所以表格式方法無法對其完整建模.

3) 雖然標準DQN算法也可以實現(xiàn)不錯的效果，但是其采用的“ε-策略”會貪婪地調(diào)度車輛前往價值高的區(qū)域，這會導致大部分車輛前往熱區(qū)，造成“羊群效應”，而在其他區(qū)域因車輛少而乘客請求得到不到服務，直至拒絕.所以其提升效果也受限.

4) 除了在網(wǎng)約車數(shù)量為1 000的海口數(shù)據(jù)集上，提出的AS-AC算法在所有度量標準上均實現(xiàn)了最佳的效果，提升程度最大.相比于MCF-FM,FMU和DQN等已有最佳方法，在不同數(shù)據(jù)集、不同網(wǎng)約車數(shù)量的情況下，AS-AC算法可以在拒絕率上最高提升0.3個百分點，巡航時間上減少0.1～4.6 s，乘客等待時間減少1.8～4.1 s.由于每天都有百萬級別的訂單產(chǎn)生，所以每一點提升都會帶來巨大效益，可以大大減少能源消耗，減少交通擁堵現(xiàn)象，提升用戶體驗，提高平臺收益.

4.4 動作采樣策略的討論

表3的實驗結(jié)果表明了3.3節(jié)提出動作采樣策略的有效性.同時，針對3.3節(jié)中提到的2種采樣優(yōu)先級變體，本節(jié)進行對比實驗，以驗證排序優(yōu)先級的優(yōu)越性.其中：

1) 采用比例優(yōu)先級的AS-AC記為V1;

2) 采用排序優(yōu)先級的AS-AC記為V2.

為了方便比較，將2個變體相對DQN的提升程度作為實驗結(jié)果，如圖5和圖6所示.可以觀察到：

Fig. 6 Comparison of variants on Haikou dataset圖6 2種變體在海口數(shù)據(jù)集上的比較

1) 總體來說，對于每種變體，相比于DQN的提升程度隨網(wǎng)約車數(shù)量的增加而增大，比如，在紐約數(shù)據(jù)集上，當車輛數(shù)量為3 000時，DQN的拒絕率為11.799%，而V1與V2相比于DQN分別提升0.453%和0.448%；當車輛數(shù)量增加到4 000時，DQN的拒絕率為2.485%，而V1與V2相比于DQN分別提升1.323%和1.383%.由此可以看出隨著車輛數(shù)的增加，2種變體能更好實現(xiàn)車輛之間的協(xié)調(diào)；

2) 相比于變體V1，變體V2達到更好的效果.這是因為基于排序的優(yōu)先級對異常值不敏感，具有更好的魯棒性，因此其更加有效，并選取其作為默認的采樣策略優(yōu)先級.

5 結(jié) 論

本文提出了一種基于供需感知的深度強化學習模型用于網(wǎng)約車調(diào)度.該模型通過定義合適的智能體、狀態(tài)、動作和獎勵，將網(wǎng)約車路徑規(guī)劃問題轉(zhuǎn)化為Markov決策過程，然后提出了一個具有動作采樣策略的執(zhí)行者-評論者網(wǎng)絡結(jié)構(gòu)(AS-AC)，以學習最佳的空閑網(wǎng)約車調(diào)度策略.實驗結(jié)果表明，本文提出的供需感知的深度強化學習方法在不同數(shù)據(jù)集上均取得了比對比方法更好的表現(xiàn)，驗證了執(zhí)行者-評論者網(wǎng)絡在協(xié)調(diào)網(wǎng)約車上的有效性，此外，通過對不同的動作采樣策略進行對比試驗，證明基于排序優(yōu)先級的采樣策略比采用比例優(yōu)先級的采樣策略效果更優(yōu).

在下一步工作中，可以采用多智能體強化學習的方法，以及考慮更復雜的實時路況信息，讓模型學到更優(yōu)的調(diào)度策略，以更好地平衡城市中的供需分布.

作者貢獻聲明

：鄭渤龍?zhí)岢隽怂惴ㄋ悸泛蛯嶒灧桨福幻鲙X峰和胡琦負責完成實驗并撰寫論文；方一向、鄭凱和李國徽提出指導意見并修改論文.