自適應的共享單車動態平衡

何濤 張健 徐鶴

摘? 要： 自行車共享系統成功的關鍵之一是重新平衡運營的效率，每個區域的自行車數量必須通過卡車運送以恢復到需求值。不同的時間區間用戶的用車需求波動較大，體現出“潮汐現象”的特征動態。為了有效地解決“潮汐現象”，減少區域之間車輛的調配以及滿足用戶的需求，通過深度學習提取區域分布特征以及強化學習自適應學習環境的結合，提出一種自適應的共享單車動態分布，旨在通過外部環境確定每個區域內不同時間點的不同狀態的需求值。仿真結果表明，所提出的算法可以快速平穩、實時滿足區域內的單車需求并減少區域之間的單車調配數量。

關鍵詞： 共享單車; 動態平衡; 深度學習; 強化學習; 區域分布; 單車調配

中圖分類號： TN915?34; TP301.6? ? ? ? ? ? ? ? ? ? ?文獻標識碼： A? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2019）16?0169?05

0? 引? 言

由于共享經濟的興起以及日益增長的環境、能源和經濟問題，近年來共享交通發展迅猛。在各種形式的共享使用手機中，公共自行車共享系統（Bicycle Sharing Systems）[1?2]越來越受歡迎，數據表明，2015年有超過500個自行車共享計劃在至少49個國家運行，共有100萬輛自行車。隨著數量的增加，共享單車系統通常會出現“供不應求”和“供過于求”的不均衡現象，在一定的時間段內租車量持續高于或者低于還車輛，并且會根據節假日或者天氣因素，以一定時間為循環周期重復出現，嚴重影響了系統的運行效率，“潮汐現象”是共享單車系統的設計和運行中普遍存在的規律。城市邊遠地帶的一些用地功能復合低的區域，用戶出行的需求趨勢相同，出行時間集中，短時間內對車輛的需求量大而波動頻繁是潮汐現象形成的主要原因。

對于“潮汐問題”，目前使用的辦法是自行車共享再平衡算法（Bike Sharing Rebalancing Problem）[3]， 采用額外調配的車輛，實現共享自行車的重新分配，以最大限度地降低總成本，通過自行車的高效率，低成本調度，有效提升公共自行車的流轉量，減少因為過飽和和過負載造成的阻礙，及時滿足供給和需求的相對均衡，保證用戶的正常使用。自行車共享再平衡算法采用靜態的優化方法，是一類特殊的商品的拾取和交付能力的車輛路由問題，通過設定混合整數線性規劃公式，并對公式設置約束條件從而求解車輛的路由問題和運輸問題。系統一般會在系統關閉的時候或者是使用量比較低的時候，例如夜間，按照每一個區域的需求量，對單車數目進行重新分配以及配送來實現系統的靜態平衡。

由于“潮汐現象”發生在一天中的多個時間段，而周期比較長的靜態平衡顯然不能有效地解決“潮汐現象”[4]，增加了車輛分布的不均勻和閑置率，降低了單車的有效使用，同樣也增加了區域之間的單車的調配難度和時效。對于共享單車在每一個區域的重新分配的需求量會依據客戶網絡中的客戶需求以及節假日、工作日等時間因素為參考進行預測，這樣的模型缺乏穩定性，難以按照環境的變化而做出相對應的處理，自適應性相對較差。

2? 算? 法

2.1? 模型架構

本文首先介紹提出的自適應的多時間段共享單車動態平衡框架，依據共享單車的隨機性和多狀態性，結合深度學習強大的特征提取和強化學習的策略定值能力，把子空間的狀態通過預處理傳輸給算法模型，根據算法模型的概率輸出，做出相應的動作以獲取最大的累積獎賞值，并根據動作生成新的區域狀態，按照設定的時間，不斷重復該動作以實現各區域之間的共享單車動態平衡。其整體框架如圖2所示。

圖2? 算法整體框架圖

Fig. 2? Overall framework diagram of algorithm

在子空間系統的大量共享單車分布區域中，假設存在n個單車集中分布區域[Pii=1，2，…，n]，每一個區域的共享單車需求數量分別依次對應為[Sii=1，2，…，n]，單車需求數量Si為約束條件-k～+k的范圍之間任意整數值，默認共享單車分布區域內的總數滿足用戶的需求，所以各區域需求的總和為0，即[i=0nSi=0]。

由于強化學習模型在與環境的交互過程中的轉移樣本和時間序列是高度相關的，但是模型要求訓練數據之間是相互獨立的，所以在每個更新都使用經驗回放機制從經驗池D中隨機采樣mini?batch數量的轉移樣本作為訓練數據來更新網絡的權值[11]。在訓練的初始階段，經驗池D中并沒有足夠的轉移樣本來訓練網絡，實驗中，通過采取隨機策略的方式存儲足夠多的轉移樣本到經驗池D中，以防止在學習的初期由于訓練數據太少，而導致學習較差的泛化性和陷入局部最優解的問題。

獎賞函數[12]是所有強化學習算法所必須的，為強化學習提供了目標，本文設計一個獎賞函數來映射每個狀態，以表達每一個動作的內在期望。獎賞函數先將當前狀態通過檢測網絡求出檢測結果，然后計算偏差，用偏差的變化來表征當前狀態的獎賞值。定義獎賞函數[Ra（s，s′）]，[s′]表示狀態s執行動作a后的狀態。當動作的轉移使各區域的需求更加均衡，獎賞值為1;否則，當動作的轉移使各需求值更加離散，獎賞會按照偏差做出相應得懲罰。

[R′ai（s，s′）=abs（s′i-0）k，? ?abs（s′i-0）>θ1，? ? ? ? ? ? ? ? ? ? ? ? ? ? ? abs（s′i-0）<θ]? （8）

[R=i=1NR′ai（s，s′）]? ? （9）

因為強化深度學習是免模型學習，對于動作的選擇在初期是未知的，通過選擇多樣的動作用于后期的迭代學習，可以使模型按照狀態?動作函數自行選擇并快速收斂。在動作的選擇初期，是一個無策略的學習過程，通過貪心策略可以嘗試所有可能的動作。后期動作可以從自身或者他人的記憶中學習經驗，動作選擇服從概率為[1-ε]貪婪策略[12]，并且服從概率為[ε]的非貪婪策略。

動作空間是在觀察到一個狀態以后，必須從當前的可選的動作中選擇一個動作。為了保持分布的均衡和減小區域之間的調度數量，動作為需求高的區域向需求低的區域的轉移單車的數量，區域按照缺少或者多余的數目排序，需求低的區域接收需求高的區域的轉移數目。[σ]是轉移動作和區域最大需求量k的比例，[σ的取值為{0%，10%，20%，30%，40%}]，相對應需求高的區域動作為a={k·0[%]，k·10[%]，k·20[%]，k·30[%]，k·40[%]}。

2.2? 模型的訓練過程

1） 存放轉移樣本的經驗池D容量初始化為N，記憶單元D={e1，e2，…，eN}，初始化深度學習網絡的參數[θt]，[θt]的值服從以0為中心，方差為1的截斷正態分布。

2） 初始化隨機生成子空間中各區域的共享單車需求狀態S，狀態S服從-k～+k的均勻分布，狀態S經過數據的預處理后通過算法模型。

3） 從動作集合A中選擇動作a，這里采取的是[ε-greddy]策略，以概率[1-ε]選擇一個隨機的動作a來鼓勵探索，否則以1-[ε]的概率選擇a=[maxQ]（S，a;[θt]）及對應Q值最大的，觀察得到下一個狀態S′和通過獎賞函數得到的獎賞值r，把與環境交互得到的轉移樣本et=存入到經驗池D。

4） 判斷經驗池D是否已經到達容量N，否則返回步驟2）直到經驗池到達容量。

5） 從經驗池D中隨機采樣數量固定的小批量的轉移樣本進行模型的訓練及后期的使用，設置[y=r+γmax QS′，a;θt]近似表示值函數的優化目標也就是最優值函數，并且誤差函數為[L=QS，a-r+γmax QS′，a;θt2]，使用式（6）求偏導更新參數[θt]的值。

6） 判斷損失函數L是否小于閾值T，否則返回到步驟5）直到損失函數小于閾值T。

7） 判斷隨機生成狀態S是否已經把全部的狀態組合遍歷結束，否則返回步驟2），直到狀態S遍歷完成。

3? 算法實驗及分析

實驗環境采用Python 3.5和tensorflow深度學習框架對算法進行仿真研究、分析算法性能和處理數據采用Matlab語言。假設在大量共享單車分布區域中，每一個區域的需求數在-k～+k內隨機分布，并且區域的需求數總和為零。經驗池的容量N設置為1萬個轉移樣本，mini?batch的規模為32，式（7）中的折扣因子[γ]設置為0.99，行為策略[ε-greddy]的參數[ε]設置為從訓練開始到10萬區間線性遞加的形式。每次的結果取10次仿真實驗結果的均值。

分布的區域個數對于模型的訓練速速和模型的收斂都有很重要的作用，通過設置不同的個數來比較區域數對于模型的影響。在共享單車分布范圍內，分別在區域數為3，4，5，6，7的情況下對模型進行訓練和預測。訓練的誤差值和獎賞值如圖3所示。

圖3a）中，當區域個數為5時，隨著訓練步數的增加，誤差值不斷縮小，獎賞值不斷增大;當步數為20萬步左右時，誤差值趨于穩定，保持不變，說明模型已經固定并且算法是合理的，而獎賞值隨著步數增加依然增長。由圖3b）可以得知，區域個數為3，4，5，7的折線在區域個數為6的下方，這是由于較多的區域個數可以滿足各種動作的選擇，可以有效地提升回報值;但是區域個數7的獎賞值在區域個數6的下方，說明個數太大時難以快速滿足區域的動態平衡。所以在動作為a={k·0%，k·10%，k·20%，k·30%，k·40%}的情況下，區域個數為6的模型的獎賞值是最大。

在機器學習中，提高算法的穩定性首先想到的是降低學習率。較高的學習率可能會導致過擬合，傳統的強化學習中使用較高的學習率會導致學習曲線發散和振蕩;使用小的學習率似乎能夠解決振蕩問題，因為每一步都采用了更小的步長進行更新。在區域個數為6，并且選擇的動作為a={k·0%，k·10%，k·20%，k·30%，k·40%}的情況下，式（7）中的學習率[α]分別選擇為0.99，0.5，0.099。得到訓練的誤差值和獎賞值如圖4所示。

從圖4a）可以看出，獎賞值的大小和學習率[α]成正相關關系，較高的學習率可以提高獎賞值，使單車分布更加均衡;但是通過圖4b）可以得出，更小的學習率可以使學習過程快速地趨于平穩，減少學習的訓練時間。

通過對比使用自適應的共享單車動態平衡算法和沒有使用算法來證明算法的可行性，在一片區域中區域個數為6，學習率[α]為0.99，使用學習好的模型進行模擬，極差值和方差值如表1所示。使用算法和未使用算法的極差對比如圖5所示。通過圖5可以看出，在使用自適應的共享單車動態平衡算法后，極差值明顯下降，說明算法在滿足單車動態平衡方面是可行的。

4? 結? 論

目前共享單車一般采用靜態平衡，使得共享單車不能實時滿足用戶的需求。為了有效地解決共享單車分布的問題，通過深度學習和強化學習的有機結合，提出自適應的共享單車動態平衡算法。本算法的意義在于，在已知環境的背景下，對多區域的不同時間段進行綜合考慮，自適應的選擇狀態所映射的動作，追求長時間下多區域的獎賞最大化，減小區域之間的調配數量并滿足每一個區域的需求量。但是，本算法在時間復雜度方面比較高，在學習和模型穩定方面需要較長的時間，在未來的工作中，將尋找更好的狀態?動作更新方法，使模型快速平穩。

參考文獻

[1] GAVALAS D， KONSTANTOPOULOS C， PANTZIOUS G. Design and management of vehicle sharing systems： a survey of algorithmic approaches [M]// OBAIDAT M S，? NICOPOLITIDIS P. Smart Cities and Homes. San Francisco： Morgan Kaufmann， 2016： 261?289.

[2] LAPORTE G， MEUNIER F， CALVO R. Shared mobility systems [J]. A Quarterly Joumal of Operations Research， 2015， 13（4）： 341?360.

[3] DELL′AMICO M， HADJICOSTANTINOU E， LORI M， et al. The bike sharing rebalancing problem： Mathematical formulations and benchmark instances [J]. Omega， 2014， 45： 7?19.

[4] MA T， LIU C， ERGODAN S. Bicycle sharing and public transit [J]. Transportation research record： journal of the transportation research board， 2015， 2534（1）： 1?9.

[5] DONGHYUN K， CHANYOUNG P， JINOH O， et al. Convolutional matrix factorization for document context?aware recommendation [C]// Proceedings of 10th ACM Conference on Recommender Systems. Boston： RecSys， 2016： 233?240.

[6] 譚國真，王瑩多.一種基于深度強化學習的交通信號自適應控制方法：CN201710258926.4[P].2017?04?19.

TAN Guozhen， WANG Yingduo. A traffic signal adaptive control method based on deep reinforcement learning： CN201710258926.4 [P]. 2017?04?19.

[7] DUCHI J， HZAAN E， SINGER Y. Adaptive subgradient methods for online learning and stochastic optimization [J]. Journal of machine learning research， 2011， 12（7）： 2121?2159.

[8] SILVER D， HUANG A， MADDISON， et al. Mastering the game of go with deep neural networks and tree search [J]. Nature， 2016， 529： 484?489.

[9] MNIH V， KAVUKKCUOGLU K， SILVER D， et al. Human?level control through deep reinforcement learning [J]. Nature， 2015， 518： 529.

（上接第173頁）

[10] O′NEILL J， PLEYDELLl?BOUVERIE B， DUPRET D， et al. Play it again： reactivation of waking experience and memory [J]. Trends in neurosciences， 2010， 33（5）： 220?229.

[11] SCHAUL T， QUAN J， ANTONOGLOU I， et al. Prioritized experience replay [J]. Computer science， 2015， 11（19）： 1511.

[12] 劉全，翟建偉.一種基于視覺注意力機制的深度循環Q網絡模型[J].計算機學報，2017，40（6）：1353?1363.

LIU Quan， ZHAI Jianwei. A deep recurrent Q?network based on visual attention mechanism [J]. Chinese journal of computers， 2017， 40（6）： 1353?1363.