張建同 何鈺林

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

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

中圖分類號：F 57

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

文章編號：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)保的出行方式，近年來在國內(nèi)大部分城市都已經(jīng)普及，有效地解決了城市公共交通的“最后一公里”問題。但龐大的共享單車系統(tǒng)在運(yùn)營管理上也面臨諸多問題，其中一個主要問題就是共享單車在時空上分布不平衡，導(dǎo)致有些地方單車短缺，無法滿足用戶需求，而同時在某些地方單車數(shù)量過多，不僅浪費(fèi)資源，同時給城市管理帶來了許多麻煩。

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

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

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

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

1 共享單車重置問題

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

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

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

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

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

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

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

（2） 動作空間

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

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

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

（3） 獎勵

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

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

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

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

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

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

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

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

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

本文利用DDPG（Deep Deterministic Policy Gradient）求解共享單車重置問題。DDPG基于確定性策略，即相同的策略，在同一個狀態(tài)下，采取的動作不是基于概率分布的，而是唯一確定的，則策略變成π（s）=a。DDPG包含4個神經(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)前動作a，與環(huán)境交互生成新狀態(tài)s′，得到獎勵r。

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

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

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

應(yīng)用于共享單車重置問題的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ù)更新頻率η;對動作產(chǎn)生擾動概率p0;重置計算周期[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，得到動作a={p，τ，q};

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

5） 執(zhí)行動作a，得到新狀態(tài)s′，獎勵r;

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

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

3 實驗結(jié)果與分析

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

本研究使用的數(shù)據(jù)來源于爬蟲爬取的上海某區(qū)域摩拜單車分布數(shù)據(jù)，爬蟲每10分鐘爬取一次，記錄研究區(qū)域內(nèi)停放的共享單車的編號、停放的經(jīng)緯度位置以及爬蟲爬取時間?；诠蚕韱诬嚪植紨?shù)據(jù)，利用基于密度聚類的方法發(fā)現(xiàn)6個高密度點(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個日間數(shù)量增加節(jié)點(diǎn)與3個日間數(shù)量減少節(jié)點(diǎn)。由于數(shù)據(jù)每10分鐘收集一次，所以將調(diào)度周期離散化為時間點(diǎn)，時間點(diǎn)的間隔為10分鐘，長度為一天的調(diào)度周期共包含144個時間點(diǎn)，記為t1，t2，L，t144。

基于調(diào)度周期各時間點(diǎn)的各節(jié)點(diǎn)單車數(shù)量，構(gòu)建調(diào)度過程中共享單車數(shù)量變化模擬器。在調(diào)度過程中，調(diào)度車在節(jié)點(diǎn)進(jìn)行取車或者放車操作，在此之后的時間該節(jié)點(diǎn)的共享單車數(shù)量都會發(fā)生改變，這種改變既包含當(dāng)前調(diào)度行為的改變，又包含用戶使用量的變化。在數(shù)據(jù)中共享單車的數(shù)量變化由用戶實際使用歸還單車行為引起，但數(shù)據(jù)并不能反映實際用戶需求，特別是在單車數(shù)量較少時，用戶可能無法在可接受的時間內(nèi)獲得共享單車，而選擇其他交通方式。當(dāng)調(diào)度車往節(jié)點(diǎn)投放共享單車時，節(jié)點(diǎn)的用戶使用數(shù)量可能會增加，節(jié)點(diǎn)單車數(shù)量越少增加越明顯;當(dāng)調(diào)度車從節(jié)點(diǎn)回收共享單車時，節(jié)點(diǎn)的用戶使用量可能會減少，節(jié)點(diǎn)單車數(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ù)量變?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，對動作產(chǎn)生擾動概率p0=0.4×0.9i，其中i為迭代次數(shù)，最大迭代次數(shù)T=2000。基于模擬器利用強(qiáng)化學(xué)習(xí)進(jìn)行調(diào)度，調(diào)度時間為4：00-20：00，得到的調(diào)度方案為（3， 4：00， 15）→（1， 8：00， 30）→（6， 9：00， -28）→（3， 9：50， -17），三元組三個元素分別表示調(diào)度節(jié)點(diǎn)編號、調(diào)度時間與調(diào)度單車數(shù)量。調(diào)度結(jié)果如圖2與表1中DDPG所示。實驗結(jié)果顯示調(diào)度完成后所有節(jié)點(diǎn)在調(diào)度周期內(nèi)累積短缺共享單車數(shù)量減少了14%，累積多余共享單車數(shù)量減少了29%，總調(diào)度路徑長度為6.3km。可以得到結(jié)論，使用強(qiáng)化學(xué)習(xí)方法能得到有效的實時動態(tài)調(diào)度方案，使得共享單車系統(tǒng)運(yùn)營效率得到提高。

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

4 結(jié)論

共享單車數(shù)量具有時變性的特點(diǎn)，動態(tài)的單車調(diào)度策略更能滿足實際的共享單車重置要求。本文提出利用強(qiáng)化學(xué)習(xí)方法解決實時動態(tài)的共享單車重置問題，并創(chuàng)造性地提出適用于強(qiáng)化學(xué)習(xí)的共享單車重置問題建模方法?；谂老x爬取的共享單車現(xiàn)實使用情況數(shù)據(jù)，構(gòu)造了調(diào)度過程中系統(tǒng)環(huán)境變化模擬器，并利用強(qiáng)化學(xué)習(xí)方法進(jìn)行模擬調(diào)度。結(jié)果顯示，調(diào)度完成后，系統(tǒng)累計缺少單車數(shù)量減少14%，累計多余單車數(shù)量減少29%。同時對比傳統(tǒng)將動態(tài)問題劃分為多階段靜態(tài)問題的方法，強(qiáng)化學(xué)習(xí)方法無論在調(diào)度效果還是在調(diào)度成本方面，都有更好的表現(xiàn)。在未來的研究中可以對模型進(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] 徐國勛， 張偉亮， 李妍峰. 共享單車調(diào)配路線優(yōu)化問題研究[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.