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

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

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

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

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

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

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

本文的主要貢獻(xiàn)包括3個方面：

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

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

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

1 相關(guān)工作

1.1 車隊(duì)管理

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

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

1.2 深度強(qiáng)化學(xué)習(xí)

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

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

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

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

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

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

Table 1 Summary of Notation

2.1 問題敘述

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

定義3.

調(diào)度中心

.

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

.

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

.

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

.

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

.

(1)

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

.

2.2 框架總覽

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

G

={

g

,

g

,…,

g

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

T

={

t

,

t

,…,

t

||}

.

如圖1所示，車隊(duì)管理模塊跟蹤網(wǎng)約車的實(shí)時位置，以獲取下一個時間片網(wǎng)約車供應(yīng)量，而請求預(yù)測模塊則根據(jù)歷史的請求時空分布，預(yù)測未來的網(wǎng)約車需求分布.供需感知的深度強(qiáng)化學(xué)習(xí)調(diào)度策略將供需結(jié)合起來，以確定空閑網(wǎng)約車的調(diào)度動作，然后網(wǎng)約車將會朝著調(diào)度終點(diǎn)巡航.對于收到的新請求，調(diào)度中心分配最近的空閑網(wǎng)約車為其服務(wù).當(dāng)網(wǎng)約車被分配給一個請求后，它會首先沿著最短路徑前往請求的起點(diǎn)去接乘客，然后駛向請求的終點(diǎn)以完成服務(wù).如果一個請求在其最長等待時間內(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)格劃分空間對動作空間進(jìn)行離散化.如圖2所示，將空閑網(wǎng)約車調(diào)度到目標(biā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

包括當(dāng)前區(qū)域的

k

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

.

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

s

，動作空間

A

也是不同的

.

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

.

3) 獎勵

r

.

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

(4)

其中,

d

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

d

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

.

式(4)計(jì)算的獎勵

r

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

.

注意到較大的

r

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

.

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

.

4) 回合

.

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

.

因此，時間

t

在22∶00之后的狀態(tài)為終止?fàn)顟B(tài)

.

5) 策略

π

(

a

|

s

)

.

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

A

的概率分布的映射

.

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

.

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

π

，以最大化預(yù)期獎勵

.

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

Q

(

s

,

a

)

.

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

s

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

a

，并且之后按照策略

π

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

Q

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

(5)

其中,

t

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

γ

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

.

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

.

在時刻

t

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

s

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

.

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

.

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

r

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

s

′

.

3 供需感知的深度強(qiáng)化學(xué)習(xí)

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

3.1 動作空間的確定

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

A

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

.

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

.

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

.

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

.

在下一個時間片中預(yù)測請求數(shù)量最多的少數(shù)網(wǎng)格(紐約為5個網(wǎng)格，?？跒?個網(wǎng)格)，因?yàn)榇蠖鄶?shù)請求都出現(xiàn)在這些網(wǎng)格中

.

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

A

中移除無效的動作

.

這是因?yàn)椋绻?dāng)前網(wǎng)格的供需差大于調(diào)度目標(biāo)網(wǎng)格的供需差，停留在當(dāng)前網(wǎng)格更可能獲得更高的獎勵，并且可以減少調(diào)度開銷

.

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

.

對于

A

中的每個網(wǎng)格

g

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

ρ

：

(6)

最后，從動作空間

A

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

.

3.2 AC模型

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

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

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

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

(7)

(8)

θ

←

θ

+

α

?

L

(

θ

),

(9)

其中，

α

是critic網(wǎng)絡(luò)的學(xué)習(xí)率

.

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

s

，輸出為常量

V

(

s

;

θ

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

.

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

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

A

(

s

,

a

)=

td

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

J

(

θ

)=?log

π

(

a

|

s

)

A

(

s

,

a

),

(10)

其中，

θ

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

.

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

θ

更新為

θ

←

θ

+

α

?

J

(

θ

),

(11)

其中，

α

是actor網(wǎng)絡(luò)的學(xué)習(xí)率

.

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

s

，輸出為數(shù)組

Q

(

s

;

a

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

.

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

① 初始化記憶庫

M

的容量為

N

；

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

θ

為隨機(jī)值；④ 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 動作采樣策略

在當(dāng)前狀態(tài)

s

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

Q

(

s

,

a

)從

A

中選擇一個動作

.

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

ε

-貪婪”策略會以1-

ε

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

.

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

Q

(

s

,

a

)對可行性動作進(jìn)行采樣

.

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

Q

(

s

,

a

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

.

具體地，第

i

個動作被采樣的概率計(jì)算為

(12)

其中,

p

>0是

A

中第

i

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

τ

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

τ

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

.

對于優(yōu)先級

p

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

.

其中

p

=

Q

(

s

,

a

)，它表示從

A

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

.

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

.

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

A

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

.

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

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

.

對于調(diào)度位置

l

∈

a

.g

，令

x

(

l

)和

y

(

l

)分別為

l

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

l

處的供需分配不匹配度計(jì)算為

(13)

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

a

.g

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

.

當(dāng)目的網(wǎng)格中沒有空閑網(wǎng)約車時，選擇該網(wǎng)格中心作為調(diào)度目的地，因?yàn)樗鼙ＷC與網(wǎng)格中的其他位置距離不會過遠(yuǎn)

.

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

.

算法2.

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

s

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

a

.

① 計(jì)算源動作價值

Q

(

s

,

a

),?

i

=1,2,…,|

G

|；② 初始化動作空間

A

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

A

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

G

|的數(shù)組

F

，并設(shè)置

F

=1,?

a

∈

A

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

Q

(

s

,

a

)×

F

對動作

a

∈

A

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

a

；⑦ return

a

.

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

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

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

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

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

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

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

Table 2 Dataset Statistics

4.2 對比算法與度量標(biāo)準(zhǔn)

通過實(shí)驗(yàn)對比以下6種算法的效果：

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

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

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

4) Q-learing. 標(biāo)準(zhǔn)表格式的Q-learning學(xué)習(xí)一個含有“

ε

-貪婪”策略的

q

表

.

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

ε

=0

.

1

.

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

ε

-貪婪”策略選取

Q

(

s

,

a

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

ε

=0

.

1

.

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

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

1) 拒絕率(reject rate,

RR

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

CT

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

WT

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

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

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

t

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

N

=100 000，采樣的批量大小

b

=64，critic中目標(biāo)網(wǎng)絡(luò)更新的周期

B

=1 000，折扣因子

γ

=0

.

9，學(xué)習(xí)率

α

=0

.

001，

α

=0.000 5.

為了驗(yàn)證方法的魯棒性，在不同網(wǎng)約車數(shù)量下進(jìn)行對比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表3所示，其中每種度量標(biāo)準(zhǔn)的最佳結(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ù)量越多，可以服務(wù)越多請求，這樣拒絕率(

RR

)、平均巡航時間(

CT

)以及平均等待時間(

WT

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

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

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

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

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

4.4 動作采樣策略的討論

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

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

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

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

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

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

2) 相比于變體V1，變體V2達(dá)到更好的效果.這是因?yàn)榛谂判虻膬?yōu)先級對異常值不敏感，具有更好的魯棒性，因此其更加有效，并選取其作為默認(rèn)的采樣策略優(yōu)先級.

5 結(jié) 論

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

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

作者貢獻(xiàn)聲明

：鄭渤龍?zhí)岢隽怂惴ㄋ悸泛蛯?shí)驗(yàn)方案；明嶺峰和胡琦負(fù)責(zé)完成實(shí)驗(yàn)并撰寫論文；方一向、鄭凱和李國徽提出指導(dǎo)意見并修改論文.