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

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

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

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

制定有效的網(wǎng)約車路徑規(guī)劃策略主要存在3項(xiàng)挑戰(zhàn)：1)需要對(duì)動(dòng)態(tài)變化的供需分布進(jìn)行建模，以準(zhǔn)確預(yù)測(cè)每個(gè)區(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ū)域，從而減少無效的巡航時(shí)間.

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

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

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

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

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

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

1 相關(guān)工作

1.1 車隊(duì)管理

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

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

深度強(qiáng)化學(xué)習(xí)將具有強(qiáng)大感知力的深度學(xué)習(xí)方法和具有優(yōu)秀決策力的強(qiáng)化學(xué)習(xí)方法相結(jié)合，通過試錯(cuò)的方式來學(xué)習(xí)智能體在觀測(cè)狀態(tài)下應(yīng)采取的最佳動(dòng)作.DRL利用神經(jīng)網(wǎng)絡(luò)來估計(jì)狀態(tài)動(dòng)作值，并通過更新網(wǎng)絡(luò)參數(shù)來學(xué)習(xí)最佳行為策略，已經(jīng)在許多具有挑戰(zhàn)性的領(lǐng)域取得了突破性的進(jìn)展，例如，圍棋、電子游戲和自動(dòng)駕駛.然而，主流的深度強(qiáng)化學(xué)習(xí)算法，如DQN和Reinforce主要適用于低維度且樣本容易獲取的任務(wù)，而在高維和非靜態(tài)的動(dòng)作空間中表現(xiàn)不佳.本文通過實(shí)時(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ì)動(dòng)作的價(jià)值，通過神經(jīng)網(wǎng)絡(luò)計(jì)算出動(dòng)作價(jià)值，然后選擇價(jià)值最大的動(dòng)作.例如，MOVI通過卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural network, CNN)來提取供需分布特征并采用分布式的DQN策略學(xué)習(xí)單獨(dú)的車輛的最優(yōu)調(diào)度動(dòng)作.COX采用聚類算法將路網(wǎng)劃分為許多用于網(wǎng)約車調(diào)度的區(qū)域，再通過環(huán)境感知的需求預(yù)測(cè)模型和實(shí)時(shí)的網(wǎng)約車狀態(tài)來計(jì)算區(qū)域級(jí)別的供需，最后將這些供需信息加入到狀態(tài)中，提高DQN的表現(xiàn).與基于值函數(shù)的方法不同，策略梯度方法用神經(jīng)網(wǎng)絡(luò)來近似策略，采用梯度上升法來尋找最優(yōu)策略.例如，CoRide將訂單調(diào)度和車隊(duì)管理概述為部分可觀測(cè)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]在求解動(dòng)作空間時(shí)考慮了地理環(huán)境和協(xié)作環(huán)境，消除了無效的網(wǎng)格從而減小了動(dòng)作空間，并提出contextual actor-critic多智能體強(qiáng)化學(xué)習(xí)算法用于網(wǎng)約車學(xué)習(xí)行為策略.

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

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

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

Table 1 Summary of Notation

2.1 問題敘述

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

定義3.

調(diào)度中心

.

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

.

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

.

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

.

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

.

(1)

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

.

2.2 框架總覽

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

G

={

g

,

g

,…,

g

||}；將一天劃分為一個(gè)時(shí)間片序列，表示為

T

={

t

,

t

,…,

t

||}

.

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

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

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

(2)

(3)

2) 動(dòng)作

a

∈

A.

動(dòng)作

a

=〈

g

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

g

.

所有可行的動(dòng)作組成了動(dòng)作空間，用

A

表示

.A

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

k

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

.

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

s

，動(dòng)作空間

A

也是不同的

.

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

.

3) 獎(jiǎng)勵(lì)

r

.

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

(4)

其中,

d

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

d

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

.

式(4)計(jì)算的獎(jiǎng)勵(lì)

r

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

.

注意到較大的

r

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

.

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

.

4) 回合

.

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

.

因此，時(shí)間

t

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

.

5) 策略

π

(

a

|

s

)

.

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

A

的概率分布的映射

.

對(duì)于確定性的策略，輸出是一個(gè)特定的動(dòng)作

.

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

π

，以最大化預(yù)期獎(jiǎng)勵(lì)

.

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

Q

(

s

,

a

)

.

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

s

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

a

，并且之后按照策略

π

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

Q

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

(5)

其中,

t

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

γ

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

.

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

.

在時(shí)刻

t

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

s

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

.

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

.

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

r

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

s

′

.

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

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

3.1 動(dòng)作空間的確定

首先，通過考慮以下2種類型的網(wǎng)格來初始化可行動(dò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)格

.

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

.

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

A

中移除無效的動(dòng)作

.

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

.

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

.

對(duì)于

A

中的每個(gè)網(wǎng)格

g

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

ρ

：

(6)

最后，從動(dòng)作空間

A

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

.

3.2 AC模型

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

本文采用了2種技術(shù)來提升網(wǎng)絡(luò)的性能：1)對(duì)于critic網(wǎng)絡(luò)，類似DQN，采用原始和目標(biāo)2個(gè)相同的價(jià)值網(wǎng)絡(luò)來實(shí)現(xiàn)周期穩(wěn)定更新；2)通過嵌入地理鄰居和供需差來過濾無效動(dòng)作使得能夠調(diào)整策略以適應(yīng)動(dòng)態(tài)變化的動(dò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)?？傪^對(duì)分館加強(qiáng)業(yè)務(wù)指導(dǎo)，分館按照總館服務(wù)標(biāo)準(zhǔn)，對(duì)轄區(qū)內(nèi)基層服務(wù)點(diǎn)實(shí)施業(yè)務(wù)考核、績效管理、采編目錄等方面的統(tǒng)一管理。制定《松江區(qū)公共圖書館服務(wù)規(guī)范》，規(guī)范服務(wù)項(xiàng)目，完善內(nèi)部制度，以區(qū)級(jí)公共文化“服務(wù)規(guī)范”，提升全區(qū)公共圖書館行業(yè)服務(wù)水平。

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

(7)

(8)

θ

←

θ

+

α

?

L

(

θ

),

(9)

其中，

α

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

.

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

s

，輸出為常量

V

(

s

;

θ

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

.

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

對(duì)于actor策略網(wǎng)絡(luò)，如圖4所示，采用第3.3節(jié)提到的動(dòng)作采樣策略替換傳統(tǒng)actor網(wǎng)絡(luò)最后的softmax層.為了減小動(dòng)作選擇的方差，引入了一個(gè)優(yōu)勢(shì)函數(shù)來代替critic網(wǎng)絡(luò)中的原始回報(bào)，以衡量選取的動(dòng)作值與所有動(dòng)作平均值的好壞，用時(shí)序差分來近似優(yōu)勢(shì)函數(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í)行所有動(dòng)作對(duì)應(yīng)的狀態(tài)價(jià)值函數(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⑦ 對(duì)每輛空閑網(wǎng)約車生成并存儲(chǔ)狀態(tài)轉(zhuǎn)移元組(

s

,

a

,

r

,

s

+1)到

M

；

⑧ end for

3.3 動(dòng)作采樣策略

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

s

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

Q

(

s

,

a

)從

A

中選擇一個(gè)動(dòng)作

.

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

ε

-貪婪”策略會(huì)以1-

ε

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

.

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

Q

(

s

,

a

)對(duì)可行性動(dòng)作進(jìn)行采樣

.

具體而言，對(duì)動(dòng)作價(jià)值函數(shù)

Q

(

s

,

a

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

.

具體地，第

i

個(gè)動(dòng)作被采樣的概率計(jì)算為

(12)

其中,

p

>0是

A

中第

i

個(gè)動(dòng)作的優(yōu)先級(jí)，而

τ

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

τ

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

.

對(duì)于優(yōu)先級(jí)

p

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

.

其中

p

=

Q

(

s

,

a

)，它表示從

A

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

.

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

.

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

A

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

.

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

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

.

對(duì)于調(diào)度位置

l

∈

a

.g

，令

x

(

l

)和

y

(

l

)分別為

l

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

l

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

(13)

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

a

.g

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

.

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

.

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

.

算法2.

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

s

；輸出：一個(gè)調(diào)度動(dòng)作

a

.

① 計(jì)算源動(dòng)作價(jià)值

Q

(

s

,

a

),?

i

=1,2,…,|

G

|；② 初始化動(dòng)作空間

A

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

A

移除無效的動(dòng)作；④ 初始化大小為|

G

|的數(shù)組

F

，并設(shè)置

F

=1,?

a

∈

A

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

Q

(

s

,

a

)×

F

對(duì)動(dòng)作

a

∈

A

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

a

；⑦ return

a

.

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

解決交通問題的強(qiáng)化學(xué)習(xí)方法通常需要一個(gè)動(dòng)態(tài)模擬環(huán)境用于訓(xùn)練模型和評(píng)估算法，采用并拓展了車隊(duì)管理模擬器COMSET，以訓(xùn)練并評(píng)估調(diào)度策略.實(shí)驗(yàn)用Java實(shí)現(xiàn)調(diào)度策略和所有的對(duì)比方法，使用Python3.6和Tensorflow1.15.0來構(gòu)建并訓(xùn)練模型，其中網(wǎng)絡(luò)模型在一臺(tái)裝配有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模型.該模擬器是對(duì)網(wǎng)約車平臺(tái)如何管理網(wǎng)約車和處理乘客請(qǐng)求的整個(gè)過程進(jìn)行建模.具體而言，在模擬開始時(shí)，根據(jù)輸入的OSM JSON文件創(chuàng)建一個(gè)地圖，并通過輸入邊界多邊形對(duì)其進(jìn)行裁剪.乘客請(qǐng)求從歷史訂單數(shù)據(jù)中讀取，每一個(gè)請(qǐng)求對(duì)應(yīng)一個(gè)歷史訂單記錄，只保留上下車位置均在邊界多邊形范圍內(nèi)的請(qǐng)求，并按照上車時(shí)間的先后順序以流的形式進(jìn)入系統(tǒng). 固定數(shù)量的網(wǎng)約車被部署在地圖上的隨機(jī)位置，并按照調(diào)度策略給出的搜索路線進(jìn)行巡航.當(dāng)請(qǐng)求進(jìn)入系統(tǒng)后，控制中心為其分配最近的空閑網(wǎng)約車；網(wǎng)約車接受請(qǐng)求，前往請(qǐng)求起點(diǎn)接乘客，再將其送到請(qǐng)求終點(diǎn)，期間車輛都沿著最短路徑行駛.更重要的，模擬器會(huì)通過歷史訂單數(shù)據(jù)校正每條路段的旅行速度，因此COMSET產(chǎn)生的平均旅行時(shí)間與真實(shí)數(shù)據(jù)基本一致.

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

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

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

Table 2 Dataset Statistics

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

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

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

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

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

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

ε

-貪婪”策略的

q

表

.

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

ε

=0

.

1

.

5) DQN. 狀態(tài)、動(dòng)作和獎(jiǎng)勵(lì)定義與本文一樣，采取“

ε

-貪婪”策略選取

Q

(

s

,

a

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

ε

=0

.

1

.

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

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

1) 拒絕率(reject rate,

RR

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

CT

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

WT

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

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

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

t

=5 min，即乘客最多等待5 min，如果5 min內(nèi)沒有司機(jī)接單，則該請(qǐng)求被視為拒絕，并從系統(tǒng)中移除.對(duì)于提出的方法，其設(shè)定的參數(shù)如下：actor與critic網(wǎng)絡(luò)(如圖3、圖4)均采用3層全連接層，每層包含128個(gè)隱藏單元，并采用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)行對(duì)比實(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ù)越多請(qǐng)求，這樣拒絕率(

RR

)、平均巡航時(shí)間(

CT

)以及平均等待時(shí)間(

WT

)都會(huì)降低.更具體些，可以從表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í)動(dòng)作價(jià)值函數(shù)的Q-learning相比于RD也有所提升，但其提升的程度沒有MCF-FM與FMU大，這是因?yàn)镼-learning的性能受限于確定性的狀態(tài)空間，而由于交通環(huán)境的復(fù)雜性，實(shí)際產(chǎn)生的狀態(tài)是無窮多的，所以表格式方法無法對(duì)其完整建模.

3) 雖然標(biāo)準(zhǔn)DQN算法也可以實(shí)現(xiàn)不錯(cuò)的效果，但是其采用的“ε-策略”會(huì)貪婪地調(diào)度車輛前往價(jià)值高的區(qū)域，這會(huì)導(dǎo)致大部分車輛前往熱區(qū)，造成“羊群效應(yīng)”，而在其他區(qū)域因車輛少而乘客請(qǐng)求得到不到服務(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個(gè)百分點(diǎn)，巡航時(shí)間上減少0.1～4.6 s，乘客等待時(shí)間減少1.8～4.1 s.由于每天都有百萬級(jí)別的訂單產(chǎn)生，所以每一點(diǎn)提升都會(huì)帶來巨大效益，可以大大減少能源消耗，減少交通擁堵現(xiàn)象，提升用戶體驗(yàn)，提高平臺(tái)收益.

4.4 動(dòng)作采樣策略的討論

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

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

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

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

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

1) 總體來說，對(duì)于每種變體，相比于DQN的提升程度隨網(wǎng)約車數(shù)量的增加而增大，比如，在紐約數(shù)據(jù)集上，當(dāng)車輛數(shù)量為3 000時(shí)，DQN的拒絕率為11.799%，而V1與V2相比于DQN分別提升0.453%和0.448%；當(dāng)車輛數(shù)量增加到4 000時(shí)，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)先級(jí)對(duì)異常值不敏感，具有更好的魯棒性，因此其更加有效，并選取其作為默認(rèn)的采樣策略優(yōu)先級(jí).

5 結(jié) 論

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

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

作者貢獻(xiàn)聲明

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