基于深度強化學習的動態共享單車重置問題研究

張建同 何鈺林

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

關鍵詞：共享單車重置問題;深度強化學習;摩拜單車

中圖分類號：F 57

文獻標志碼：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

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

針對共享單車分布不平衡現象，許多學者圍繞共享單車重置問題（Bike Repositioning Problem，BRP）展開了研究。從調度主體的角度，共享單車重置問題可以分為基于用戶的重置問題（User-Based BRP）和基于運營商的重置問題（Operator-Based BRP）。基于用戶的重置通過引導用戶用車和還車行為實現系統單車再平衡，一般通過動態定價或者對于在指定站點用車與還車行為給予獎勵的方式實現。基于運營商的重置一般是由運營商派遣調度卡車，在單車較多的站點取車，往單車較少的站點放車，實現單車數量再平衡。

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

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

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

1 共享單車重置問題

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

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

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

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

（1） 狀態空間

在各個時間均具有一個全局狀態st∈S，狀態信息包含各個節點共享單車數量，調度車當前所在節點及調度車裝載單車數量：

其中，pl為一個n維向量，表示調度車所在節點及裝載共享單車的數量，當調度車在節點i且當前裝載單車數量為l時，向量pl的第i-1維表示為l，其他維元素為0。

（2） 動作空間

每次決策考慮調度車在未來一個小時會執行的動作，包括調度車下一個訪問的節點，訪問節點的時間，以及實際調度的數量：

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

其中，C為調度車容量，L為調度車裝載的共享單車數量。

（3） 獎勵

智能體在當前系統狀態執行動作后使得系統狀態發生變化，產生獎勵，以引導智能體選擇更優動作。在本文中，設定重置目標為在調度周期內，系統缺少的單車數量與多余的數量最小化，同時調度成本最小化。設智能體在時間t基于系統狀態st執行動作at，調度車從節點i在時間t′到達節點j進行調度，而取/放每輛單車時間都設為l，調度車在時間t″=t′+q′×l完成取/放車操作。由于只有j受到調度操作的影響，所以獎勵計算為

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

基于以上強化學習的共享單車重置問題定義，該問題可以被認為是一輛調度車智能體在動態變化的共享單車系統中，獲得環境狀態信息后，執行調度動作與環境交互，環境收到動作影響并返回對智能體的獎勵和下一個狀態信息，從而構成一個完整的強化學習迭代過程。

2 基于深度強化學習的共享單車重置

強化學習可分為基于價值（value-based）的方法和基于策略（policy-based）的方法，還有將基于價值與基于策略相結合的方法。基于價值的方法根據動作價值來選擇執行的動作，動作價值函數公式為

這里T表示時間步，在時間步T的環境狀態sT下，執行動作aT后時間步轉移到T+1，系統狀態變成sT+1。根據Bellman方程可以轉化為遞推公式：

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

其中，α為步長因子。基于價值的強化學習需要利用Q值表記錄每個狀態下每個動作的價值，當狀態較多時，將需要維持一個非常大的Q值表，內存資源可能沒法滿足。一個可行的解決方法是近似地計算Q值，而放棄維護完整的Q值表。利用深度學習的方法，使用神經網絡近似計算價值的方法，即深度強化學習。深度強化學習需要維護一個經驗回放集合，保存智能體在探索過程中的經驗{sT，aT，rT，sT+1}，作為神經網絡訓練集。基于價值的強化學習算法有Q學習（Q-Learning），深度Q網絡（DQN）等。

基于價值的方法有其局限性：只適用于離散動作，無法處理如時間、數量等連續動作，且對于受限狀態下的問題處理能力不足，無法解決隨機策略問題。基于策略的方法能更有效地解決上述問題。基于策略的方法同樣使用深度學習的方法近似計算策略函數π（s，a），即在狀態s選擇動作a的概率，在迭代過程中通過基于蒙特卡羅法的策略梯度的方法優化近似策略函數，但該方法需要完全的序列樣本才能做算法迭代，同時需要使用獎勵的期望值來計算狀態價值，會導致行為有較多的變異性，參數更新的方向可能不是策略梯度的最優方向。將基于價值與基于策略的方法相結合，可以充分發揮兩者的優點，避免其缺點。將基于價值與基于策略的方法相結合的算法有Actor-Critic、A3C、DDPG等。

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

1. Actor當前網絡：網絡參數為θ，負責根據當前狀態s選擇當前動作a，與環境交互生成新狀態s′，得到獎勵r。

2. Actor目標網絡：網絡參數為θ′，負責根據新狀態s′選擇新動作a′，參數θ′定期從θ復制。

3. Critic當前網絡：網絡參數為ω，負責計算在當前狀態s執行動作a產生的價值Q（s，a，ω）。

4. Critic目標網絡：網絡參數為ω′，負責計算在新狀態s′執行新動作a′產生的價值Q（s′，a′，ω′），參數ω′定期從ω復制。

應用于共享單車重置問題的DDPG算法流程如下：

輸入：Actor當前網絡，Actor目標網絡，Critic當前網絡，Critic目標網絡，參數分別為θ，θ′，ω，ω′;衰減因子γ;軟更新系數μ;批量梯度下降樣本數m;目標網絡參數更新頻率η;對動作產生擾動概率p0;重置計算周期[Ts，Te];最大迭代次數T。

輸出：Actor當前網絡參數θ;Critic當前網絡參數ω。

1） 隨機初始化θ，ω，θ=θ′，ω=ω′，當前迭代輪次i=1;

2） 初始化狀態s為初始狀態;

3） 向Actor當前網絡輸入狀態s，得到動作a={p，τ，q};

4） 產生隨機數，如果小于概率p0，對動作進行隨機擾動，得到新動作a′={p′，τ′，q′};

5） 執行動作a，得到新狀態s′，獎勵r;

6） 如果狀態s′的時間t′

7） 將經驗{s，a，r，s′，done}存入檢驗回放集合D;

8） 令s=s′;

12） 如果η|i，則更新Critic目標網絡和Actor目標網絡參數：

13） 如果s′是終止狀態，當前輪次迭代結束，否則轉到步驟3）;

14） 如果i=T，則結束迭代，否則令i=i+1，轉到步驟2）。

算法中，4個網絡均選用全連接BP神經網絡進行計算。為了避免算法過早收斂、陷入局部最優，在迭代過程中對動作進行隨機擾動，增加學習覆蓋率。設定擾動概率p0，在每輪迭代中產生隨機數，如果小于概率p0，則隨機選擇一個原來目標節點p的鄰域節點p′作為新目標節點，對τ，q分別加一個隨機數，得到τ′，q′，同時τ′，q′應分布控制在其定義范圍之內，從而得到新動作a′={p′，τ′，q′}。調度的效果以三個指標進行衡量：所有節點在調度周期內累積短缺共享單車數量減少比例RL、累積多余共享單車數量減少比例RO、總調度路徑長度RC，其中RL與RO計算如下：

3 實驗結果與分析

3.1 數據概述與環境模擬器構造

本研究使用的數據來源于爬蟲爬取的上海某區域摩拜單車分布數據，爬蟲每10分鐘爬取一次，記錄研究區域內停放的共享單車的編號、停放的經緯度位置以及爬蟲爬取時間。基于共享單車分布數據，利用基于密度聚類的方法發現6個高密度點作為調度節點，利用Voronoi圖劃分節點覆蓋區域，以覆蓋區域內單車數量表述節點單車數量。由于共享單車數量以天為單位周期性變化，選取一天作為調度周期，各節點共享單車數量在一天內的變化如圖1所示，其中包含3個日間數量增加節點與3個日間數量減少節點。由于數據每10分鐘收集一次，所以將調度周期離散化為時間點，時間點的間隔為10分鐘，長度為一天的調度周期共包含144個時間點，記為t1，t2，L，t144。

基于調度周期各時間點的各節點單車數量，構建調度過程中共享單車數量變化模擬器。在調度過程中，調度車在節點進行取車或者放車操作，在此之后的時間該節點的共享單車數量都會發生改變，這種改變既包含當前調度行為的改變，又包含用戶使用量的變化。在數據中共享單車的數量變化由用戶實際使用歸還單車行為引起，但數據并不能反映實際用戶需求，特別是在單車數量較少時，用戶可能無法在可接受的時間內獲得共享單車，而選擇其他交通方式。當調度車往節點投放共享單車時，節點的用戶使用數量可能會增加，節點單車數量越少增加越明顯;當調度車從節點回收共享單車時，節點的用戶使用量可能會減少，節點單車數量越少減少越明顯。設在時間ti，i∈{1，L，144}，在節點j回收/投放單車數量q，節點j在ti的單車數量變為num′j（ti）=numi（tj）-q，而在此后的時間，單車數量變為

3.2 調度結果分析

設置調度車默認容量C=50，平均行駛速度為500m/min。設置DDPG中衰減因子γ=0.9，軟更新系數μ=0.01，批量梯度下降樣本數m=64，目標網絡參數更新頻率η=100，對動作產生擾動概率p0=0.4×0.9i，其中i為迭代次數，最大迭代次數T=2000。基于模擬器利用強化學習進行調度，調度時間為4：00-20：00，得到的調度方案為（3， 4：00， 15）→（1， 8：00， 30）→（6， 9：00， -28）→（3， 9：50， -17），三元組三個元素分別表示調度節點編號、調度時間與調度單車數量。調度結果如圖2與表1中DDPG所示。實驗結果顯示調度完成后所有節點在調度周期內累積短缺共享單車數量減少了14%，累積多余共享單車數量減少了29%，總調度路徑長度為6.3km。可以得到結論，使用強化學習方法能得到有效的實時動態調度方案，使得共享單車系統運營效率得到提高。

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

4 結論

共享單車數量具有時變性的特點，動態的單車調度策略更能滿足實際的共享單車重置要求。本文提出利用強化學習方法解決實時動態的共享單車重置問題，并創造性地提出適用于強化學習的共享單車重置問題建模方法。基于爬蟲爬取的共享單車現實使用情況數據，構造了調度過程中系統環境變化模擬器，并利用強化學習方法進行模擬調度。結果顯示，調度完成后，系統累計缺少單車數量減少14%，累計多余單車數量減少29%。同時對比傳統將動態問題劃分為多階段靜態問題的方法，強化學習方法無論在調度效果還是在調度成本方面，都有更好的表現。在未來的研究中可以對模型進行擴展，考慮多車輛調度、允許在節點暫存單車、故障單車回收等情況。

參考文獻：

[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] 徐國勛， 張偉亮， 李妍峰. 共享單車調配路線優化問題研究[J]. 工業工程與管理， 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.