自適應(yīng)的共享單車動態(tài)平衡

何濤 張健 徐鶴

摘? 要： 自行車共享系統(tǒng)成功的關(guān)鍵之一是重新平衡運(yùn)營的效率，每個區(qū)域的自行車數(shù)量必須通過卡車運(yùn)送以恢復(fù)到需求值。不同的時間區(qū)間用戶的用車需求波動較大，體現(xiàn)出“潮汐現(xiàn)象”的特征動態(tài)。為了有效地解決“潮汐現(xiàn)象”，減少區(qū)域之間車輛的調(diào)配以及滿足用戶的需求，通過深度學(xué)習(xí)提取區(qū)域分布特征以及強(qiáng)化學(xué)習(xí)自適應(yīng)學(xué)習(xí)環(huán)境的結(jié)合，提出一種自適應(yīng)的共享單車動態(tài)分布，旨在通過外部環(huán)境確定每個區(qū)域內(nèi)不同時間點(diǎn)的不同狀態(tài)的需求值。仿真結(jié)果表明，所提出的算法可以快速平穩(wěn)、實(shí)時滿足區(qū)域內(nèi)的單車需求并減少區(qū)域之間的單車調(diào)配數(shù)量。

關(guān)鍵詞： 共享單車; 動態(tài)平衡; 深度學(xué)習(xí); 強(qiáng)化學(xué)習(xí); 區(qū)域分布; 單車調(diào)配

中圖分類號： TN915?34; TP301.6? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識碼： A? ? ? ? ? ? ? ? ? 文章編號： 1004?373X（2019）16?0169?05

0? 引? 言

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

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

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

2? 算? 法

2.1? 模型架構(gòu)

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

圖2? 算法整體框架圖

Fig. 2? Overall framework diagram of algorithm

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

由于強(qiáng)化學(xué)習(xí)模型在與環(huán)境的交互過程中的轉(zhuǎn)移樣本和時間序列是高度相關(guān)的，但是模型要求訓(xùn)練數(shù)據(jù)之間是相互獨(dú)立的，所以在每個更新都使用經(jīng)驗(yàn)回放機(jī)制從經(jīng)驗(yàn)池D中隨機(jī)采樣mini?batch數(shù)量的轉(zhuǎn)移樣本作為訓(xùn)練數(shù)據(jù)來更新網(wǎng)絡(luò)的權(quán)值[11]。在訓(xùn)練的初始階段，經(jīng)驗(yàn)池D中并沒有足夠的轉(zhuǎn)移樣本來訓(xùn)練網(wǎng)絡(luò)，實(shí)驗(yàn)中，通過采取隨機(jī)策略的方式存儲足夠多的轉(zhuǎn)移樣本到經(jīng)驗(yàn)池D中，以防止在學(xué)習(xí)的初期由于訓(xùn)練數(shù)據(jù)太少，而導(dǎo)致學(xué)習(xí)較差的泛化性和陷入局部最優(yōu)解的問題。

獎賞函數(shù)[12]是所有強(qiáng)化學(xué)習(xí)算法所必須的，為強(qiáng)化學(xué)習(xí)提供了目標(biāo)，本文設(shè)計一個獎賞函數(shù)來映射每個狀態(tài)，以表達(dá)每一個動作的內(nèi)在期望。獎賞函數(shù)先將當(dāng)前狀態(tài)通過檢測網(wǎng)絡(luò)求出檢測結(jié)果，然后計算偏差，用偏差的變化來表征當(dāng)前狀態(tài)的獎賞值。定義獎賞函數(shù)[Ra（s，s′）]，[s′]表示狀態(tài)s執(zhí)行動作a后的狀態(tài)。當(dāng)動作的轉(zhuǎn)移使各區(qū)域的需求更加均衡，獎賞值為1;否則，當(dāng)動作的轉(zhuǎn)移使各需求值更加離散，獎賞會按照偏差做出相應(yīng)得懲罰。

[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）

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

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

2.2? 模型的訓(xùn)練過程

1） 存放轉(zhuǎn)移樣本的經(jīng)驗(yàn)池D容量初始化為N，記憶單元D={e1，e2，…，eN}，初始化深度學(xué)習(xí)網(wǎng)絡(luò)的參數(shù)[θt]，[θt]的值服從以0為中心，方差為1的截斷正態(tài)分布。

2） 初始化隨機(jī)生成子空間中各區(qū)域的共享單車需求狀態(tài)S，狀態(tài)S服從-k～+k的均勻分布，狀態(tài)S經(jīng)過數(shù)據(jù)的預(yù)處理后通過算法模型。

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

4） 判斷經(jīng)驗(yàn)池D是否已經(jīng)到達(dá)容量N，否則返回步驟2）直到經(jīng)驗(yàn)池到達(dá)容量。

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

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

7） 判斷隨機(jī)生成狀態(tài)S是否已經(jīng)把全部的狀態(tài)組合遍歷結(jié)束，否則返回步驟2），直到狀態(tài)S遍歷完成。

3? 算法實(shí)驗(yàn)及分析

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

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

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

在機(jī)器學(xué)習(xí)中，提高算法的穩(wěn)定性首先想到的是降低學(xué)習(xí)率。較高的學(xué)習(xí)率可能會導(dǎo)致過擬合，傳統(tǒng)的強(qiáng)化學(xué)習(xí)中使用較高的學(xué)習(xí)率會導(dǎo)致學(xué)習(xí)曲線發(fā)散和振蕩;使用小的學(xué)習(xí)率似乎能夠解決振蕩問題，因?yàn)槊恳徊蕉疾捎昧烁〉牟介L進(jìn)行更新。在區(qū)域個數(shù)為6，并且選擇的動作為a={k·0%，k·10%，k·20%，k·30%，k·40%}的情況下，式（7）中的學(xué)習(xí)率[α]分別選擇為0.99，0.5，0.099。得到訓(xùn)練的誤差值和獎賞值如圖4所示。

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

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

4? 結(jié)? 論

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

參考文獻(xiàn)

[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] 譚國真，王瑩多.一種基于深度強(qiáng)化學(xué)習(xí)的交通信號自適應(yīng)控制方法：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] 劉全，翟建偉.一種基于視覺注意力機(jī)制的深度循環(huán)Q網(wǎng)絡(luò)模型[J].計算機(jī)學(xué)報，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.