張建同 何鈺林

摘 要：共享單車在為城市出行帶來(lái)便利的同時(shí)，也面臨著資源分布不平衡問(wèn)題。針對(duì)單車分布動(dòng)態(tài)變化環(huán)境下的共享單車重置問(wèn)題，提出基于強(qiáng)化學(xué)習(xí)的實(shí)時(shí)調(diào)度策略結(jié)構(gòu)。構(gòu)建了面向強(qiáng)化學(xué)習(xí)的共享單車重置問(wèn)題模型，利用深度確定性策略梯度算法（DDPG）進(jìn)行求解，以獲得實(shí)時(shí)調(diào)度策略。基于實(shí)際單車分布數(shù)據(jù)，構(gòu)建了調(diào)度過(guò)程中的環(huán)境交互模擬器。最后，利用強(qiáng)化學(xué)習(xí)在模擬器中進(jìn)行大規(guī)模數(shù)據(jù)實(shí)驗(yàn)，結(jié)果表明算法得到的調(diào)度策略能提高系統(tǒng)表現(xiàn)，并且效果好于已有方法。

關(guān)鍵詞：共享單車重置問(wèn)題;深度強(qiáng)化學(xué)習(xí);摩拜單車

中圖分類號(hào)：F 57

文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1005-9679（2021）02-0081-06

Abstract：While bikes sharing bring convenience to urban travel， they also face the problem of unbalanced distribution of shared bike resources. A real-time scheduling strategy structure based on reinforcement learning was proposed to solve the repositioning problem of shared bikes under dynamic change of bicycle distribution. In this paper， a model of the bike repositioning problem for reinforcement learning is built， which is solved by deep deterministic strategy gradient （DDPG） to obtain real-time scheduling strategy. Based on the actual distribution data of shared bikes， an environmental interaction simulator is constructed for the scheduling process. A large-scale data experiment using reinforcement learning is carried out in the simulator. The experiment results show that the reposi tioning strategy obtained by the algorithm can significantly improve the performance of the system， and the algorithm performance is better than other existing methods.

Key words：bike repositioning problem; deep reinforcement learning; Mobike

共享單車作為一種便捷、環(huán)保的出行方式，近年來(lái)在國(guó)內(nèi)大部分城市都已經(jīng)普及，有效地解決了城市公共交通的“最后一公里”問(wèn)題。但龐大的共享單車系統(tǒng)在運(yùn)營(yíng)管理上也面臨諸多問(wèn)題，其中一個(gè)主要問(wèn)題就是共享單車在時(shí)空上分布不平衡，導(dǎo)致有些地方單車短缺，無(wú)法滿足用戶需求，而同時(shí)在某些地方單車數(shù)量過(guò)多，不僅浪費(fèi)資源，同時(shí)給城市管理帶來(lái)了許多麻煩。

針對(duì)共享單車分布不平衡現(xiàn)象，許多學(xué)者圍繞共享單車重置問(wèn)題（Bike Repositioning Problem，BRP）展開了研究。從調(diào)度主體的角度，共享單車重置問(wèn)題可以分為基于用戶的重置問(wèn)題（User-Based BRP）和基于運(yùn)營(yíng)商的重置問(wèn)題（Operator-Based BRP）?；谟脩舻闹刂猛ㄟ^(guò)引導(dǎo)用戶用車和還車行為實(shí)現(xiàn)系統(tǒng)單車再平衡，一般通過(guò)動(dòng)態(tài)定價(jià)或者對(duì)于在指定站點(diǎn)用車與還車行為給予獎(jiǎng)勵(lì)的方式實(shí)現(xiàn)?；谶\(yùn)營(yíng)商的重置一般是由運(yùn)營(yíng)商派遣調(diào)度卡車，在單車較多的站點(diǎn)取車，往單車較少的站點(diǎn)放車，實(shí)現(xiàn)單車數(shù)量再平衡。

基于運(yùn)營(yíng)商的重置問(wèn)題可以分為靜態(tài)重置問(wèn)題（Static-BRP，SBRP）和動(dòng)態(tài)重置問(wèn)題（Dynamic-BRP，DBRP）。SBRP會(huì)忽略單車數(shù)量和需求的變化，適合夜間調(diào)度。對(duì)于共享單車重置問(wèn)題研究更多針對(duì)的是傳統(tǒng)的有樁單車系統(tǒng)。Chemla等首次建立有樁共享單車的靜態(tài)完全再平衡模型，允許車輛對(duì)站點(diǎn)多次訪問(wèn)，并將站點(diǎn)作為臨時(shí)存儲(chǔ)點(diǎn)，結(jié)合分支定界與禁忌搜索算法進(jìn)行求解。Bulhes等建立了多車型且允許重復(fù)訪問(wèn)站點(diǎn)的混合整數(shù)規(guī)劃模型，并應(yīng)用分支剪界算法框架，提出基于迭代局部搜索的啟發(fā)式算法進(jìn)行求解。隨著近年來(lái)無(wú)樁式自由浮動(dòng)共享單車的發(fā)展普及，學(xué)者也開始關(guān)注相關(guān)的再平衡問(wèn)題。Pal等對(duì)有停車位的FFBS的SBRP進(jìn)行研究，將停在停車位外的單車回收重置于停車位。

靜態(tài)重置問(wèn)題研究的是夜間調(diào)度，將單車分布視為靜態(tài)不變的，而單車不平衡現(xiàn)象更多會(huì)出現(xiàn)在日間用戶頻繁使用單車進(jìn)行轉(zhuǎn)移的情況下。動(dòng)態(tài)重置問(wèn)題會(huì)考慮單車數(shù)量和需求的時(shí)變特征，更符合目前實(shí)際重置需求。對(duì)于有樁單車的動(dòng)態(tài)重置問(wèn)題，Shui等采用滾動(dòng)周期法將動(dòng)態(tài)重置問(wèn)題分解為多個(gè)階段靜態(tài)重置問(wèn)題進(jìn)行分階段求解。Zhang等用再平衡車輛的到達(dá)時(shí)間將整個(gè)動(dòng)態(tài)再平衡過(guò)程分解為兩個(gè)子時(shí)段，預(yù)測(cè)每個(gè)子時(shí)段內(nèi)的用戶不滿意度，與車輛路徑結(jié)合產(chǎn)生非線性時(shí)空網(wǎng)絡(luò)流量模型進(jìn)行求解。徐國(guó)勛等同樣將動(dòng)態(tài)調(diào)度時(shí)間劃分為多個(gè)靜態(tài)時(shí)間段，同時(shí)考慮多類型共享單車的重置問(wèn)題。Caggiani等針對(duì)無(wú)樁式自由浮動(dòng)共享單車的動(dòng)態(tài)重置進(jìn)行研究，通過(guò)定時(shí)執(zhí)行靜態(tài)調(diào)度策略，實(shí)現(xiàn)動(dòng)態(tài)調(diào)度。

通過(guò)劃分時(shí)間段進(jìn)行動(dòng)態(tài)重置的方法能實(shí)現(xiàn)各個(gè)時(shí)間段的重置效果最優(yōu)，但學(xué)者并沒有針對(duì)如何更好劃分時(shí)間段進(jìn)行研究;另一方面，各個(gè)時(shí)間段的重置效果最優(yōu)不代表從長(zhǎng)期角度也能達(dá)到調(diào)度效果最優(yōu)，這是因?yàn)橐粋€(gè)時(shí)間段內(nèi)的重置即從單車較多的節(jié)點(diǎn)取車往單車較少的節(jié)點(diǎn)放車，而被取車的節(jié)點(diǎn)在未來(lái)時(shí)間段可能出現(xiàn)缺車，而當(dāng)前取車操作會(huì)加劇未來(lái)的缺車程度，從而加劇未來(lái)的系統(tǒng)不平衡度與增加調(diào)度成本。本文從相對(duì)較長(zhǎng)的調(diào)度周期入手，研究在調(diào)度周期內(nèi)的連續(xù)決策而非分階段決策，應(yīng)用強(qiáng)化學(xué)習(xí)（Reinforcement learning， RL）的方法對(duì)重置問(wèn)題進(jìn)行求解，實(shí)現(xiàn)實(shí)時(shí)動(dòng)態(tài)決策。

1 共享單車重置問(wèn)題

共享單車重置問(wèn)題研究的是如何從單車較多的節(jié)點(diǎn)取車，往單車較少的節(jié)點(diǎn)放車，以實(shí)現(xiàn)共享單車資源再平衡，同時(shí)實(shí)現(xiàn)重置成本最低。

在無(wú)樁的自由浮動(dòng)共享單車系統(tǒng)中，雖然沒有固定的停放站點(diǎn)，但用戶會(huì)自發(fā)地將共享單車停放在某些聚集度高的區(qū)域，如地鐵站出入口等，同時(shí)附近的用戶也會(huì)自發(fā)地到這些地點(diǎn)使用單車。本文將這些地點(diǎn)作為重置的節(jié)點(diǎn)，以這些節(jié)點(diǎn)覆蓋的周圍區(qū)域?yàn)榉秶?jì)算節(jié)點(diǎn)的單車數(shù)量，調(diào)度車會(huì)在這些調(diào)度節(jié)點(diǎn)集中回收與投放單車。設(shè)系統(tǒng)中有n個(gè)節(jié)點(diǎn)1，2，…，n，節(jié)點(diǎn)i在時(shí)間t的共享單車數(shù)量記為numi（t）。當(dāng)節(jié)點(diǎn)單車數(shù)量較少時(shí)，用戶會(huì)因?yàn)閷ふ覇诬嚨臅r(shí)間成本較高而放棄使用單車，使得用戶滿意度下降;而當(dāng)節(jié)點(diǎn)單車數(shù)量較多時(shí)，便會(huì)引起道路堵塞、亂停亂放等問(wèn)題，不利于城市管理，所以應(yīng)將節(jié)點(diǎn)單車數(shù)量控制在一定范圍內(nèi)。設(shè)節(jié)點(diǎn)i在時(shí)間t的理想共享單車數(shù)量范圍為[σdi（t），σui（t）]。當(dāng)節(jié)點(diǎn)單車數(shù)量numi（t）<σdi（t）時(shí)，節(jié)點(diǎn)單車數(shù)量不足，需要投放單車，缺少單車數(shù)量為qdi（t）=σdi（t）-numi（t）;當(dāng)節(jié)點(diǎn)單車數(shù)量numi（t）>σui（t）時(shí)，節(jié)點(diǎn)單車數(shù)量過(guò)多，需要回收單車，多余的單車數(shù)量為qpi（t）=numi（t）-σui（t）。

在動(dòng)態(tài)重置問(wèn)題中，由于用戶的使用，共享單車分布時(shí)刻在動(dòng)態(tài)變化中，調(diào)度車需要根據(jù)共享單車的實(shí)時(shí)分布情況進(jìn)行連續(xù)決策，在強(qiáng)化學(xué)習(xí)中以馬爾科夫決策過(guò)程（MDP）來(lái)形式化描述這種連續(xù)決策過(guò)程，即在每次決策時(shí)，只考慮當(dāng)前的狀態(tài)，不考慮先前狀態(tài)。強(qiáng)化學(xué)習(xí)通過(guò)智能體與環(huán)境進(jìn)行交互來(lái)實(shí)現(xiàn)連續(xù)決策。在共享單車重置問(wèn)題中，智能體可以作為調(diào)度車的抽象理解，本文研究在單調(diào)度車條件下的動(dòng)態(tài)調(diào)度，使用單智能體強(qiáng)化學(xué)習(xí)進(jìn)行求解。

強(qiáng)化學(xué)習(xí)中馬爾科夫決策過(guò)程可由五元組{S，A，R，P，γ}表示，其中S表示環(huán)境的狀態(tài)空間，A表示動(dòng)作空間，R表示智能體執(zhí)行動(dòng)作后環(huán)境狀態(tài)改變得到的相應(yīng)獎(jiǎng)勵(lì)值，P表示狀態(tài)轉(zhuǎn)移概率矩陣，γ表示未來(lái)獎(jiǎng)勵(lì)值在當(dāng)期的折扣率。智能體基于環(huán)境狀態(tài)，根據(jù)相應(yīng)策略執(zhí)行相應(yīng)的動(dòng)作并作用于環(huán)境，環(huán)境的狀態(tài)將會(huì)發(fā)生改變轉(zhuǎn)移到下一狀態(tài)，同時(shí)智能體獲得相應(yīng)行為的獎(jiǎng)勵(lì)，智能體以最大化累計(jì)獎(jiǎng)勵(lì)為目標(biāo)不斷學(xué)習(xí)，從而學(xué)得最優(yōu)策略。根據(jù)狀態(tài)轉(zhuǎn)移概率是否已知，強(qiáng)化學(xué)習(xí)可以分為基于模型的強(qiáng)化學(xué)習(xí)與不基于模型的強(qiáng)化學(xué)習(xí)，在共享單車重置問(wèn)題中狀態(tài)轉(zhuǎn)移概率無(wú)法提前獲得，所以本文使用不基于模型的方法。其他元素定義如下：

（1） 狀態(tài)空間

在各個(gè)時(shí)間均具有一個(gè)全局狀態(tài)st∈S，狀態(tài)信息包含各個(gè)節(jié)點(diǎn)共享單車數(shù)量，調(diào)度車當(dāng)前所在節(jié)點(diǎn)及調(diào)度車裝載單車數(shù)量：

其中，pl為一個(gè)n維向量，表示調(diào)度車所在節(jié)點(diǎn)及裝載共享單車的數(shù)量，當(dāng)調(diào)度車在節(jié)點(diǎn)i且當(dāng)前裝載單車數(shù)量為l時(shí)，向量pl的第i-1維表示為l，其他維元素為0。

（2） 動(dòng)作空間

每次決策考慮調(diào)度車在未來(lái)一個(gè)小時(shí)會(huì)執(zhí)行的動(dòng)作，包括調(diào)度車下一個(gè)訪問(wèn)的節(jié)點(diǎn)，訪問(wèn)節(jié)點(diǎn)的時(shí)間，以及實(shí)際調(diào)度的數(shù)量：

其中，p表示調(diào)度車下一個(gè)訪問(wèn)的節(jié)點(diǎn)，使用獨(dú)熱編碼表示。τ表示訪問(wèn)下一個(gè)節(jié)點(diǎn)距離現(xiàn)在的時(shí)間長(zhǎng)度，時(shí)間粒度為分鐘，τ的取值范圍為[0，60]。在實(shí)際調(diào)度中要考慮調(diào)度車行駛時(shí)間，所以到達(dá)下一個(gè)節(jié)點(diǎn)的時(shí)間為t′=t+max（τ，d（i，j）/v），其中i和j分別表示當(dāng)前所在節(jié)點(diǎn)與下一個(gè)訪問(wèn)節(jié)點(diǎn)，d（i，j）表示兩個(gè)節(jié)點(diǎn)間的距離，v表示調(diào)度車平均行駛速度。q表示調(diào)度車在下一個(gè)節(jié)點(diǎn)調(diào)度單車的數(shù)量，q>0表示從節(jié)點(diǎn)取車，q<0表示往節(jié)點(diǎn)投車，在實(shí)施調(diào)度操作時(shí)需要考慮調(diào)度車裝載量、剩余容量、節(jié)點(diǎn)擁有單車數(shù)量，所以實(shí)際調(diào)度數(shù)量為：

其中，C為調(diào)度車容量，L為調(diào)度車裝載的共享單車數(shù)量。

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

智能體在當(dāng)前系統(tǒng)狀態(tài)執(zhí)行動(dòng)作后使得系統(tǒng)狀態(tài)發(fā)生變化，產(chǎn)生獎(jiǎng)勵(lì)，以引導(dǎo)智能體選擇更優(yōu)動(dòng)作。在本文中，設(shè)定重置目標(biāo)為在調(diào)度周期內(nèi)，系統(tǒng)缺少的單車數(shù)量與多余的數(shù)量最小化，同時(shí)調(diào)度成本最小化。設(shè)智能體在時(shí)間t基于系統(tǒng)狀態(tài)st執(zhí)行動(dòng)作at，調(diào)度車從節(jié)點(diǎn)i在時(shí)間t′到達(dá)節(jié)點(diǎn)j進(jìn)行調(diào)度，而取/放每輛單車時(shí)間都設(shè)為l，調(diào)度車在時(shí)間t″=t′+q′×l完成取/放車操作。由于只有j受到調(diào)度操作的影響，所以獎(jiǎng)勵(lì)計(jì)算為

式（4）中包含三項(xiàng)，分別計(jì)算在時(shí)間t″調(diào)度完成后，在t″之后的時(shí)間[t″，Te]（Te為調(diào)度周期終止時(shí)間）在節(jié)點(diǎn)j的累計(jì)多余單車數(shù)量的減少量、累計(jì)缺少單車數(shù)量的減少量、調(diào)度車行駛距離，w1、w2、w3分別代表三項(xiàng)的權(quán)重。

基于以上強(qiáng)化學(xué)習(xí)的共享單車重置問(wèn)題定義，該問(wèn)題可以被認(rèn)為是一輛調(diào)度車智能體在動(dòng)態(tài)變化的共享單車系統(tǒng)中，獲得環(huán)境狀態(tài)信息后，執(zhí)行調(diào)度動(dòng)作與環(huán)境交互，環(huán)境收到動(dòng)作影響并返回對(duì)智能體的獎(jiǎng)勵(lì)和下一個(gè)狀態(tài)信息，從而構(gòu)成一個(gè)完整的強(qiáng)化學(xué)習(xí)迭代過(guò)程。

2 基于深度強(qiáng)化學(xué)習(xí)的共享單車重置

強(qiáng)化學(xué)習(xí)可分為基于價(jià)值（value-based）的方法和基于策略（policy-based）的方法，還有將基于價(jià)值與基于策略相結(jié)合的方法。基于價(jià)值的方法根據(jù)動(dòng)作價(jià)值來(lái)選擇執(zhí)行的動(dòng)作，動(dòng)作價(jià)值函數(shù)公式為

這里T表示時(shí)間步，在時(shí)間步T的環(huán)境狀態(tài)sT下，執(zhí)行動(dòng)作aT后時(shí)間步轉(zhuǎn)移到T+1，系統(tǒng)狀態(tài)變成sT+1。根據(jù)Bellman方程可以轉(zhuǎn)化為遞推公式：

在迭代過(guò)程中，智能體根據(jù)價(jià)值函數(shù)利用ε-貪婪的方法選擇動(dòng)作。價(jià)值函數(shù)更新方法有蒙特卡洛法與時(shí)序差分法，其中時(shí)序差分法價(jià)值函數(shù)更新公式為

其中，α為步長(zhǎng)因子?；趦r(jià)值的強(qiáng)化學(xué)習(xí)需要利用Q值表記錄每個(gè)狀態(tài)下每個(gè)動(dòng)作的價(jià)值，當(dāng)狀態(tài)較多時(shí)，將需要維持一個(gè)非常大的Q值表，內(nèi)存資源可能沒法滿足。一個(gè)可行的解決方法是近似地計(jì)算Q值，而放棄維護(hù)完整的Q值表。利用深度學(xué)習(xí)的方法，使用神經(jīng)網(wǎng)絡(luò)近似計(jì)算價(jià)值的方法，即深度強(qiáng)化學(xué)習(xí)。深度強(qiáng)化學(xué)習(xí)需要維護(hù)一個(gè)經(jīng)驗(yàn)回放集合，保存智能體在探索過(guò)程中的經(jīng)驗(yàn){sT，aT，rT，sT+1}，作為神經(jīng)網(wǎng)絡(luò)訓(xùn)練集?；趦r(jià)值的強(qiáng)化學(xué)習(xí)算法有Q學(xué)習(xí)（Q-Learning），深度Q網(wǎng)絡(luò)（DQN）等。

基于價(jià)值的方法有其局限性：只適用于離散動(dòng)作，無(wú)法處理如時(shí)間、數(shù)量等連續(xù)動(dòng)作，且對(duì)于受限狀態(tài)下的問(wèn)題處理能力不足，無(wú)法解決隨機(jī)策略問(wèn)題?；诓呗缘姆椒芨行У亟鉀Q上述問(wèn)題?；诓呗缘姆椒ㄍ瑯邮褂蒙疃葘W(xué)習(xí)的方法近似計(jì)算策略函數(shù)π（s，a），即在狀態(tài)s選擇動(dòng)作a的概率，在迭代過(guò)程中通過(guò)基于蒙特卡羅法的策略梯度的方法優(yōu)化近似策略函數(shù)，但該方法需要完全的序列樣本才能做算法迭代，同時(shí)需要使用獎(jiǎng)勵(lì)的期望值來(lái)計(jì)算狀態(tài)價(jià)值，會(huì)導(dǎo)致行為有較多的變異性，參數(shù)更新的方向可能不是策略梯度的最優(yōu)方向。將基于價(jià)值與基于策略的方法相結(jié)合，可以充分發(fā)揮兩者的優(yōu)點(diǎn)，避免其缺點(diǎn)。將基于價(jià)值與基于策略的方法相結(jié)合的算法有Actor-Critic、A3C、DDPG等。

本文利用DDPG（Deep Deterministic Policy Gradient）求解共享單車重置問(wèn)題。DDPG基于確定性策略，即相同的策略，在同一個(gè)狀態(tài)下，采取的動(dòng)作不是基于概率分布的，而是唯一確定的，則策略變成π（s）=a。DDPG包含4個(gè)神經(jīng)網(wǎng)絡(luò)：

1. Actor當(dāng)前網(wǎng)絡(luò)：網(wǎng)絡(luò)參數(shù)為θ，負(fù)責(zé)根據(jù)當(dāng)前狀態(tài)s選擇當(dāng)前動(dòng)作a，與環(huán)境交互生成新狀態(tài)s′，得到獎(jiǎng)勵(lì)r。

2. Actor目標(biāo)網(wǎng)絡(luò)：網(wǎng)絡(luò)參數(shù)為θ′，負(fù)責(zé)根據(jù)新狀態(tài)s′選擇新動(dòng)作a′，參數(shù)θ′定期從θ復(fù)制。

3. Critic當(dāng)前網(wǎng)絡(luò)：網(wǎng)絡(luò)參數(shù)為ω，負(fù)責(zé)計(jì)算在當(dāng)前狀態(tài)s執(zhí)行動(dòng)作a產(chǎn)生的價(jià)值Q（s，a，ω）。

4. Critic目標(biāo)網(wǎng)絡(luò)：網(wǎng)絡(luò)參數(shù)為ω′，負(fù)責(zé)計(jì)算在新狀態(tài)s′執(zhí)行新動(dòng)作a′產(chǎn)生的價(jià)值Q（s′，a′，ω′），參數(shù)ω′定期從ω復(fù)制。

應(yīng)用于共享單車重置問(wèn)題的DDPG算法流程如下：

輸入：Actor當(dāng)前網(wǎng)絡(luò)，Actor目標(biāo)網(wǎng)絡(luò)，Critic當(dāng)前網(wǎng)絡(luò)，Critic目標(biāo)網(wǎng)絡(luò)，參數(shù)分別為θ，θ′，ω，ω′;衰減因子γ;軟更新系數(shù)μ;批量梯度下降樣本數(shù)m;目標(biāo)網(wǎng)絡(luò)參數(shù)更新頻率η;對(duì)動(dòng)作產(chǎn)生擾動(dòng)概率p0;重置計(jì)算周期[Ts，Te];最大迭代次數(shù)T。

輸出：Actor當(dāng)前網(wǎng)絡(luò)參數(shù)θ;Critic當(dāng)前網(wǎng)絡(luò)參數(shù)ω。

1） 隨機(jī)初始化θ，ω，θ=θ′，ω=ω′，當(dāng)前迭代輪次i=1;

2） 初始化狀態(tài)s為初始狀態(tài);

3） 向Actor當(dāng)前網(wǎng)絡(luò)輸入狀態(tài)s，得到動(dòng)作a={p，τ，q};

4） 產(chǎn)生隨機(jī)數(shù)，如果小于概率p0，對(duì)動(dòng)作進(jìn)行隨機(jī)擾動(dòng)，得到新動(dòng)作a′={p′，τ′，q′};

5） 執(zhí)行動(dòng)作a，得到新狀態(tài)s′，獎(jiǎng)勵(lì)r;

6） 如果狀態(tài)s′的時(shí)間t′

7） 將經(jīng)驗(yàn){s，a，r，s′，done}存入檢驗(yàn)回放集合D;

8） 令s=s′;

12） 如果η|i，則更新Critic目標(biāo)網(wǎng)絡(luò)和Actor目標(biāo)網(wǎng)絡(luò)參數(shù)：

13） 如果s′是終止?fàn)顟B(tài)，當(dāng)前輪次迭代結(jié)束，否則轉(zhuǎn)到步驟3）;

14） 如果i=T，則結(jié)束迭代，否則令i=i+1，轉(zhuǎn)到步驟2）。

算法中，4個(gè)網(wǎng)絡(luò)均選用全連接BP神經(jīng)網(wǎng)絡(luò)進(jìn)行計(jì)算。為了避免算法過(guò)早收斂、陷入局部最優(yōu)，在迭代過(guò)程中對(duì)動(dòng)作進(jìn)行隨機(jī)擾動(dòng)，增加學(xué)習(xí)覆蓋率。設(shè)定擾動(dòng)概率p0，在每輪迭代中產(chǎn)生隨機(jī)數(shù)，如果小于概率p0，則隨機(jī)選擇一個(gè)原來(lái)目標(biāo)節(jié)點(diǎn)p的鄰域節(jié)點(diǎn)p′作為新目標(biāo)節(jié)點(diǎn)，對(duì)τ，q分別加一個(gè)隨機(jī)數(shù)，得到τ′，q′，同時(shí)τ′，q′應(yīng)分布控制在其定義范圍之內(nèi)，從而得到新動(dòng)作a′={p′，τ′，q′}。調(diào)度的效果以三個(gè)指標(biāo)進(jìn)行衡量：所有節(jié)點(diǎn)在調(diào)度周期內(nèi)累積短缺共享單車數(shù)量減少比例RL、累積多余共享單車數(shù)量減少比例RO、總調(diào)度路徑長(zhǎng)度RC，其中RL與RO計(jì)算如下：

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

3.1 數(shù)據(jù)概述與環(huán)境模擬器構(gòu)造

本研究使用的數(shù)據(jù)來(lái)源于爬蟲爬取的上海某區(qū)域摩拜單車分布數(shù)據(jù)，爬蟲每10分鐘爬取一次，記錄研究區(qū)域內(nèi)停放的共享單車的編號(hào)、停放的經(jīng)緯度位置以及爬蟲爬取時(shí)間?；诠蚕韱诬嚪植紨?shù)據(jù)，利用基于密度聚類的方法發(fā)現(xiàn)6個(gè)高密度點(diǎn)作為調(diào)度節(jié)點(diǎn)，利用Voronoi圖劃分節(jié)點(diǎn)覆蓋區(qū)域，以覆蓋區(qū)域內(nèi)單車數(shù)量表述節(jié)點(diǎn)單車數(shù)量。由于共享單車數(shù)量以天為單位周期性變化，選取一天作為調(diào)度周期，各節(jié)點(diǎn)共享單車數(shù)量在一天內(nèi)的變化如圖1所示，其中包含3個(gè)日間數(shù)量增加節(jié)點(diǎn)與3個(gè)日間數(shù)量減少節(jié)點(diǎn)。由于數(shù)據(jù)每10分鐘收集一次，所以將調(diào)度周期離散化為時(shí)間點(diǎn)，時(shí)間點(diǎn)的間隔為10分鐘，長(zhǎng)度為一天的調(diào)度周期共包含144個(gè)時(shí)間點(diǎn)，記為t1，t2，L，t144。

基于調(diào)度周期各時(shí)間點(diǎn)的各節(jié)點(diǎn)單車數(shù)量，構(gòu)建調(diào)度過(guò)程中共享單車數(shù)量變化模擬器。在調(diào)度過(guò)程中，調(diào)度車在節(jié)點(diǎn)進(jìn)行取車或者放車操作，在此之后的時(shí)間該節(jié)點(diǎn)的共享單車數(shù)量都會(huì)發(fā)生改變，這種改變既包含當(dāng)前調(diào)度行為的改變，又包含用戶使用量的變化。在數(shù)據(jù)中共享單車的數(shù)量變化由用戶實(shí)際使用歸還單車行為引起，但數(shù)據(jù)并不能反映實(shí)際用戶需求，特別是在單車數(shù)量較少時(shí)，用戶可能無(wú)法在可接受的時(shí)間內(nèi)獲得共享單車，而選擇其他交通方式。當(dāng)調(diào)度車往節(jié)點(diǎn)投放共享單車時(shí)，節(jié)點(diǎn)的用戶使用數(shù)量可能會(huì)增加，節(jié)點(diǎn)單車數(shù)量越少增加越明顯;當(dāng)調(diào)度車從節(jié)點(diǎn)回收共享單車時(shí)，節(jié)點(diǎn)的用戶使用量可能會(huì)減少，節(jié)點(diǎn)單車數(shù)量越少減少越明顯。設(shè)在時(shí)間ti，i∈{1，L，144}，在節(jié)點(diǎn)j回收/投放單車數(shù)量q，節(jié)點(diǎn)j在ti的單車數(shù)量變?yōu)閚um′j（ti）=numi（tj）-q，而在此后的時(shí)間，單車數(shù)量變?yōu)?/p>

3.2 調(diào)度結(jié)果分析

設(shè)置調(diào)度車默認(rèn)容量C=50，平均行駛速度為500m/min。設(shè)置DDPG中衰減因子γ=0.9，軟更新系數(shù)μ=0.01，批量梯度下降樣本數(shù)m=64，目標(biāo)網(wǎng)絡(luò)參數(shù)更新頻率η=100，對(duì)動(dòng)作產(chǎn)生擾動(dòng)概率p0=0.4×0.9i，其中i為迭代次數(shù)，最大迭代次數(shù)T=2000。基于模擬器利用強(qiáng)化學(xué)習(xí)進(jìn)行調(diào)度，調(diào)度時(shí)間為4：00-20：00，得到的調(diào)度方案為（3， 4：00， 15）→（1， 8：00， 30）→（6， 9：00， -28）→（3， 9：50， -17），三元組三個(gè)元素分別表示調(diào)度節(jié)點(diǎn)編號(hào)、調(diào)度時(shí)間與調(diào)度單車數(shù)量。調(diào)度結(jié)果如圖2與表1中DDPG所示。實(shí)驗(yàn)結(jié)果顯示調(diào)度完成后所有節(jié)點(diǎn)在調(diào)度周期內(nèi)累積短缺共享單車數(shù)量減少了14%，累積多余共享單車數(shù)量減少了29%，總調(diào)度路徑長(zhǎng)度為6.3km?？梢缘玫浇Y(jié)論，使用強(qiáng)化學(xué)習(xí)方法能得到有效的實(shí)時(shí)動(dòng)態(tài)調(diào)度方案，使得共享單車系統(tǒng)運(yùn)營(yíng)效率得到提高。

為了驗(yàn)證強(qiáng)化學(xué)習(xí)算法解決動(dòng)態(tài)共享單車重置問(wèn)題的優(yōu)勢(shì)，將算法與傳統(tǒng)劃分為多階段靜態(tài)重置問(wèn)題的方法對(duì)比，每個(gè)階段的靜態(tài)重置問(wèn)題視為單商品取送貨問(wèn)題，每個(gè)階段以階段起始時(shí)間的共享單車分布情況計(jì)算節(jié)點(diǎn)調(diào)度需求。對(duì)比以1小時(shí)與2小時(shí)為固定長(zhǎng)度劃分時(shí)間段的方法，兩種方法得到的調(diào)度結(jié)果如表1中MSSBRP_1與MSSBRP_2所示。從實(shí)驗(yàn)結(jié)果可以看出，DDPG的強(qiáng)化學(xué)習(xí)方法相對(duì)于劃分為多階段靜態(tài)重置問(wèn)題的方法在減少累積短缺共享單車數(shù)量、減少累積多余共享單車數(shù)量與調(diào)度路徑長(zhǎng)度三個(gè)指標(biāo)上表現(xiàn)更好。

4 結(jié)論

共享單車數(shù)量具有時(shí)變性的特點(diǎn)，動(dòng)態(tài)的單車調(diào)度策略更能滿足實(shí)際的共享單車重置要求。本文提出利用強(qiáng)化學(xué)習(xí)方法解決實(shí)時(shí)動(dòng)態(tài)的共享單車重置問(wèn)題，并創(chuàng)造性地提出適用于強(qiáng)化學(xué)習(xí)的共享單車重置問(wèn)題建模方法?；谂老x爬取的共享單車現(xiàn)實(shí)使用情況數(shù)據(jù)，構(gòu)造了調(diào)度過(guò)程中系統(tǒng)環(huán)境變化模擬器，并利用強(qiáng)化學(xué)習(xí)方法進(jìn)行模擬調(diào)度。結(jié)果顯示，調(diào)度完成后，系統(tǒng)累計(jì)缺少單車數(shù)量減少14%，累計(jì)多余單車數(shù)量減少29%。同時(shí)對(duì)比傳統(tǒng)將動(dòng)態(tài)問(wèn)題劃分為多階段靜態(tài)問(wèn)題的方法，強(qiáng)化學(xué)習(xí)方法無(wú)論在調(diào)度效果還是在調(diào)度成本方面，都有更好的表現(xiàn)。在未來(lái)的研究中可以對(duì)模型進(jìn)行擴(kuò)展，考慮多車輛調(diào)度、允許在節(jié)點(diǎn)暫存單車、故障單車回收等情況。

參考文獻(xiàn)：

[1] CAGGIANI L， CAMPOREALE R， OTTOMANELLI M， et al. A modeling framework for the dynamic management of free-floating bike-sharing systems[J]. Transportation Research， 2018， 87：159-182.

[2] CHEMLA D， MEUNIER F， CALVO R W. Bike sharing systems：solving the static rebalancing problem[J]. Discrete Optim，2013， 10：120–146.

[3] PFROMMER J， WARRINGTON J， SCHIDBACH G， et al. Dynamic vehicle redistribution and online price incentives in shared mobility systems[J]. IEEE Transactions on Intelligent Transportation Systems， 2014， 15（4）：1567-1578.

[4] FRICKER C， GAST N. Incentives and redistribution in homogeneous bike-sharing systems with stations of finite capacity[J]. EURO Journal on Transportation and Logistics， 2014.

[5] BULHES T， SUBRAMANIAN A， ERDOGAN G， et al. The static bike relocation problem with multiple vehicles and visits[J]. European Journal of Operational Research， 2018， 264（2）：508-523.

[6] PAL A， ZHANG Y. Free-floating bike sharing：solving real-life large-scale static rebalancing problems[J]. Transportation Research Part C-Emerging Technologies， 2017， 80：92-116.

[7] SHUI C S， SZETO W Y. Dynamic green bike repositioning problem：a hybrid rolling horizon artificial bee colony algorithm approach[J]. Transportation Research， 2018， 60：119-136.

[8] ZHANG D， YU C H， DESAI J， et al. A time-space network flow approach to dynamic repositioning in bicycle sharing systems[J]. Transportation Research Part D：Methodological， 2017， 103：188-207.

[9] 徐國(guó)勛， 張偉亮， 李妍峰. 共享單車調(diào)配路線優(yōu)化問(wèn)題研究[J]. 工業(yè)工程與管理， 2019， 1（11）：45-57.

[10] LILLICRAP， TIMOTHY H， JONATHAN P， et al. Continuous control with deep reinforcement learning[J]. Computing Research Repository， 2015.

[11] HERNNDEZ-PREZ H， SALAZAR-GONZLEZ J J. The One-Commodity Pickup-and-Delivery Travelling Salesman Problem[C]. Lecture Notes in Computer Science， 2003.