共享自行車分區域動態調度優化

趙斌 謝仁雄

［收稿日期］2022-1115

［第一作者］趙斌（1975-），男，湖北十堰人，理學博士，湖北工業大學教授，研究方向為應用統計學，數據科學與決策，金融統計，質量控制與管理，生物數學

［文章編號］1003-4684（2023）02-0116-05

［摘要］為合理安排共享自行車的擺放，提高使用效率，根據共享自行車隨機流動這一特點，運用考慮隨時間變動的模糊平均聚類將使用區域分為三類區域，并使用馬爾科夫轉移矩陣計算各個區域的轉移概率。在此基礎上改變三個區域的擺放方式，通過蒙特卡洛方法模擬兩種擺放方式，結果發現不同比例的調配方式，使用效率差異明顯，改善比例后的擺放方式在總體上能顯著提高共享自行車的使用效率。當各區域使用人員相同，共享自行車數量不同時，最大使用效率的閾值為20；區域共享自行車相同，使用人數不同時，最大使用效率的閾值為35。

［關鍵詞］共享自行車； 模糊平均聚類； 轉移概率； 蒙特卡洛模擬

［中圖分類號］TP391.4? ［文獻標識碼］A

在共享經濟的背景下，一系列共享運營模式應運而生。共享自行車是其中之一，共享自行車的出現很好地解決了城市交通接駁問題，極大完善了城市交通運營體系，這種綠色交通工具對實現國家“碳中和”及“碳達峰”目標具有重要意義。共享自行車這一概念最早提出在1965年荷蘭阿姆特丹實驗室的“Witte Fietsen”（即白自行車）公共自行車項目中[1]。共享自行車的出現，減少了私家車的使用，不僅在一定程度上緩解了交通壓力，同時加速了國家“碳達峰”與“碳中和”目標的實現。根據研究表明人口基數為370萬的東京世田谷區，共享車站每增加一個，單車共用可以減少二氧化碳排放量0.05～0.06萬噸[2]。現如今，共享自行車系統已經得到了極大完善，人們可以在共享自行車的任意指定擺放點使用并將共享自行車歸還到指定區域。相比于傳統的城市共享自行車系統，現在的共享自行車系統具有更寬闊的擺放區域以及隨意性。在2016年出現的摩拜和OfO等共享自行車公司，允許用戶使用智能手機APP掃描自行車上提供的二維碼使用自行車，值得注意的是在使用完自行車后，用戶可以把自行車放在指定區域范圍內，并通過智能手機支付騎行費用（以低費率），這種新的自行車共享概念快速在全球得到普及。在中國上海推出移動共享單車一年內，注冊用戶超過1300萬，共享單車供應量超過100萬輛，Xiaotong Cui（2018）根據公眾差異意愿對共享自行車進行了分析，發現公眾最感興趣的是新的運營模式[3]。然而這種模式也帶來了一系列問題，共享自行車的隨意擺放給人行道的通行帶來不便，極易造成自行車丟失的情況，同時管理成本也是極大的。為了方便管理減少成本，提高自行車的使用效率，Imed Kacem（2016）等人提出了自行車共享系統靜態再平衡問題的分支定界算法，在一定程度上優化了自行車的調度問題，不過這種算法的前提是車輛在車站之間進行旅行，每個車站必須由車輛準確地訪問一次，而且只能訪問一次，受限于這一假定，這種算法并不適用于任意擺放的調度問題[4]；Faghih-Imani（2016）等對以蒙特利爾BIXI系統為基礎的自行車共享系統基礎設施安裝使用決策進行研究，研究表明基礎設施對自行車的使用有重大影響，這項研究結果為設計或修改以最大化利用為目標的自行車共享系統提供了有用的信息[5]；在中國新型共享自行車方面，YiWu（2017）等提出了PSS-EPR耦合模型，但是該模型只限于理論敘述并沒有做實證分析，具有局限性[6]。共享自行車的動力學難以測量，每個用戶的轉移路徑以及停放都具有隨機性，要建立合適的模型來預測又受限于交通、天氣、人流量、時間等等因素；馬新衛（2020）發現考慮站點重要度的動態調度優化模型可將用戶使用滿意度由55.03%提升至73.00%[7]；劉雪嬌（2020）綜合考慮軌道站點、周邊自行車基礎設施條件、區位因素、混合用地泊位共享等對共享單車泊位需求的影響，對自行車的調度進行了政策優化[8]；劉祝銘（2021）設計了一種同時考慮區域內缺車數以及調度成本的優化調度系統，仿真運用系統24 h后發現，全天總缺車時段最多可減少76%[9]；肖梅等（2021）利用深度學習方法準確預測出出行時段浮動單車在研究區域內的需求量[10]；韓世行等（2022）從微觀角度出發，利用微觀數據減低了共享自行車的調度成本[11]；李浩等（2022）通過多尺度分析，發現共享自行車在時空上的需求變化并對北京市的共享自行車需求量進行了更細致的預測[12]。已有研究中，多數學者通過對共享自行車的需求量進行預測，根據預測量調配共享自行車的數量，忽略了區域內部的復雜結構，如何充分考慮不同區域間的流動差異對共享自行車的合理調配至關重要。

1??? 方法描述

結合共享自行車使用的時空差異以及隨機性，使用模糊平均聚類方法，對數據進行空間聚類，再通過馬爾科夫方法對共享自行車的轉移進行概率測算，最后運用蒙特卡洛模擬方法得到最佳調配比例。

1.1??? 模糊平均聚類

模糊平均聚類（FCM）是一種無監督的聚類方法，1965年Zabeh[13]提出模糊集的概念，在此基礎上1969年Ruspini[14]提出來模糊聚類模型。1973年Dunn[15]給出了模糊均值模型的定義，Bezdek[16]在模糊隸屬度上引入加權指數優化了該聚類方法，文章考慮將高頻地區標記為Hi，平常區域標記為Ai，低頻區域標記為Li，由此對模糊均值聚類進行了設計。

對于一個包含n個樣本的數據集X=x1，x2，…，xn，聚類過程將其分為m類，即c1，c2，…，cm，得到劃分矩陣：

U（x）=μijIc×m（1）

其中μij為樣本xj到ci的隸屬度，一般情況下，聚類劃分的結果應滿足：

Umi=1ci=X（2）

ci∩cj=Φ，i，j=1，2，…，m（3）

ci≠Φ，i=1，2，…，m（4）

基于數學的觀點，ci類通過下式確定：

ci=xj|‖xj－vi‖≤‖xj－vp‖，xj∈x（5）

vi=∑xf∈cixf/|ci|（6）

其中，p≠j，p=1，2，…，c且i=1，2，…，c，‖·‖表示樣本間的距離度量，vi為ci類的聚類中心，ci表示ci類中的樣本數。

聚類過程中采用的聚類準則通常是誤差平方和：

SSE=∑ci=1∑xj∈ci‖xj－vi‖2（7）

對于給定數據集中的每個樣本點，誤差是其到最近聚類中心的距離。一般地，在給定聚類數目的情況下，聚類的目標就是獲得使誤差平方和最小的聚類劃分。考慮到共享自行車每個單位時間的使用頻率不一樣，因此存在一單位時間內屬于高頻區域，另一時間屬于平常區域的情況，在時間維度上屬于混合類型，故將時間維度上的穩定聚類中心作為消除時間差異的聚類中心。采用以下劃分方式：

Mp={U|μij∈［0，1］，i，j;0<∑nj=1μij0，j}（8）

Mf={U|μij∈［0，1］，i，j;0<∑nj=1μij

其中Mp是概率劃分，Mf是模糊化分，模糊劃分是概率劃分的一種特殊情況。將時間維度考慮進劃分區域，得到序列矩陣。

1.2??? 馬爾科夫轉移概率

通過上述方法得到三個不同區域，將從高頻區域轉入高頻區域的共享自行車數量記為h，轉入平常區域的共享自行車數量記為b，轉入低頻區域的共享自行車數量記為c，類似的，得到其他區域間的轉移情況，最終構造出轉移矩陣p：

HiAiLiHihbcAianmLidef

∑3j=1πj=1存在πJ，當πj≥0且 ，πP=π時，稱{πJ}是{xn}的平穩分布，則有：πP=π，即：

hπ1+aπ2+dπ3=π1（10）

bπ1+nπ2+eπ3=π2（11）

cπ1+mπ2+fπ3=π3（12）

由式（10）（11）（12）相加易得：

π1+π2+π3=1（13）

由此可引入計算矩陣：

A=h-1a1bn－11cm1

通過計算A－，得到A－的最后一行為A－3=s，p，q，根據馬爾科夫性有s+p+q=1，由A－3可知共享自行車轉移到區域Hi的概率為s，若共享自行車流動總量為M，則流入區域Hi的共享自行車為s*M，使用期望為SHi/NUMHi，其中分子為該區域的轉出總量，分母為通過蒙特卡洛模擬產生的區域共享自行車動態總量；轉移到平常區域的概率為p，流入量為，p*M，使用期望為SAi/NUMAi；轉移到蕭條區域的概率為q，對應流入量為q*M，使用期望為SLi/NUMLi。

2??? 數據描述

以上海市摩拜共享自行車2016年8月份的使用情況為例，該數據統計了102358條共享自行車使用情況，包括起點位置、終點位置、行駛軌跡、車輛信息以及開始使用時間和結束使用時間。

圖1顯示共享自行車使用時間集中在0～45 min之間且有較長的拖尾現象，這正符合共享自行車解決短程接駁問題的理念。圖2顯示，2016年8月份上海共享自行車使用數量總體上表現出快速上升趨勢，從月初的1912輛快速升至月末的5317輛，共享自行車在上海具有廣泛的使用且普及度越來越高。共享自行車使用熱點圖見圖3。

圖3為上海2016年8月份的共享自行車使用起點情況，使用區域周邊稀疏中心密集，且區域使用熱度差別明顯，由于城市交通的特性，在中心區域城市道路較為擁堵，共享自行車受交通擁堵的影響較小，便利簡潔的使用方式得到青睞。因此，上海共享自行車的使用情況以中心區域為主。根據區域進行模糊平均聚類，使用地理矩陣作為權重進行劃分。劃分情況如圖4與圖5。

圖4展示的是上海市共享自行車的區域使用情況，上海共享自行車使用情況呈現左右低頻使用地區包夾高頻使用地區的空間分布模式。上海作為我國的金融中心，在國家大力推動碳金融發展背景下，共享自行車的使用能夠助力上海碳金融的發展，上海中心區域的共享自行車使用頻率較高，而周邊區域使用頻率較低，說明上海共享自行車的投放及使用受區域影響較大，中心區域是人口流動的主要區域。圖5展示的是上海共享自行車按照3個層次劃分的具體結果，低頻與平常區域包裹著高頻區域，空間規律明顯。

根據上述區域劃分情況，通過用戶終點位置確定轉移概率，也即各區域轉入量與區域總轉出量之比，構造轉移矩陣如下：

HiAiLiHi0.8420.1240.034Ai0.2380.7370.025Li0.3420.6500.005

通過公式（10）-（13）得到計算矩陣，進一步計算該矩陣的逆并求得穩定轉移概率為：[0.574，0.236，0.190]。

3??? 蒙特卡洛模擬

由于數據受限，不包含客戶使用的具體信息，通過已有數據得到三類區域及轉移概率后采用蒙特卡洛模擬方式進行后續實驗。結合實際情況將模擬方式分為兩類情況：第一種各區域使用人員相同，共享自行車數量不同；第二種各區域共享自行車相同，使用人數不同。

3.1??? 第一種模擬模式

設定各區域人數，假設三個區域的共享自行車分別為m、n、w，在人數相同的情況下，共享自行車三個區域的使用期望是相同的。各區域排隊時間服從參數為[0.574，0.236，0.190]的指數分布，則第i輛車等待人使用的時間為：

fi=λie－λix（14）

計算x次模擬所需要的等待時間：

Fi（x）=max{f1（x），…，fm（x）}（15）

Ti（x）=∑xi=1Fi（x）（16）

其中T（x）≤3600。

由此可得其1 h內的平均使用效率：

Hi（x）=3600-Ti（x）3600（17）

總體使用效率為：

P1（x）=mH1（x）+nH2（x）+wH3（x）（18）

其中ρ為共享自行車總體充分利用比。

3.2??? 第二種模擬模式

這種情況假定使用人數充足，但是不同區域流入時間不同，而且車輛流入與人們使用時間不同步。假設其服從λi+γi的指數分布，其中λi受不同區域出行頻率的影響，γi受不同區域車輛流入的影響，這里γi設置為0.33，則第i輛車等待人使用的時間為：

fi=（λi+γi）e－（λi+γi）x（19）

根據公式（3）、（4）可得到這種情況下的總平均使用效率

P2（x）=mH1（x）+nH2（x）+wH3（x）（20）

4??? 模型求解

將第二節中的穩定轉移概率作為等待指數，也即指數分布的參數。將數據帶入式（14）得：

f1=0.574e－0.574x

f2=0.236e－0.236x

f3=0.19e－0.19x

帶入方程（16）得：

T1（x）=0.574xe-0.574x

T2（x）=0.236xe-0.236x

T1（x）=0.19xe-0.19x

再將數據帶入方程（17）（18）便可得到使用效率：

P1=3600（m+n+w）－（0.574mxe－0.574x+0.236nxe－0.236+0.19wxe－0.19x）

類似的得到p2。

對m、n、w進行模擬找到最佳比例，控制總量為50000，模擬結果如圖6。

曲線在m、n、w的比例在1∶0∶0及0∶0∶1之間，且存在明顯的閥值。確定相同比例0.75∶0.15∶0.1，進一步畫出兩種模式的模擬圖：

觀察圖像可知當x<3時，p1模型較好，當x≥3時p2模型較好，即x<3選擇第一種擺放方式；當x≥3時選擇第二種擺放方式；當x=20時，第二種擺放方式一個小時內的共享自行車的使用效率達到閾值；當x=35時，第一種擺放方式一個小時內的共享自行車的使用效率達到閥值。

5??? 結論及建議

由圖7可以得出結論，在使用人數小于3的情況下，兩種模擬方式1 h內的總體平均使用效率都是遞減的，當使用人數大于3時，兩種模擬方式都是遞增的。值得注意的是受限于共享自行車的總量，并不是使用人數一直增加，總體平均使用效率也會一直增加；當x>35時，兩種方式都達到閾值，兩種擺放方式沒有區別；當一個小時的使用量為20～35之間時，第二種方式雖然閾值更小，但是其使用效率大于第一種方式，因此選擇第二種方式進行擺放。這篇文章考慮的是共享自行車總量一定的情況。當使用效率達到閾值時，應當考慮適當添加共享自行車的總量。

合理的共享自行車調配既能使企業獲得盡可能高的利潤，又能減少共享資源的浪費，方便大家出行的同時又減少了污染以及交通壓力，在各區域使用人數相同的情況下，各區域的自行車的流入量不同，導致后續出現高頻區域無車可用而低頻區域自行車無人問津的情況，因此在實際的共享自行車調度當中，為了控制成本應當采取就近原則增加高頻區域的自行數量，相應降低低頻地區的共享自行車數量，將每小時的使用效率控制在35最佳；在各區域自行車相同的情況下，應當充分考慮共享自行車的流動情況，重點關注使用頻率高的地區，合理調配區域的共享自行車，將每小時的使用效率控制在20最佳。另外應當提高高頻區域的共享自行車停泊點，防止亂停亂放現象，這也是提高使用效率的有效方式之一，并且能夠降低共享自行車的調度成本；在低頻使用地區合理整合共享自行車停泊點，降低區域調度管理難度。共享自行車合理的調配可以極大利用好共享自行車資源，但是共享自行車的調配影響因素很多，要全面考慮各個因素的影響，得到合理的模型十分困難，有待于繼續研究改進。

［參考文獻］

［1］王偉.“互聯網+”時代，共享單車該怎么管[J].運輸經理世界，2017（Z1）：66-71.

[2]HAORAN Z. Mobile phone GPS data in urban bicycle-sharing： Layout optimization and emissions reduction analysis[J]. Applied Energy， 2019， 242（C）： 138-147.

[3]XIAOTONG CUI. Influencing factors of public participation willingness in shared bicycles and intervention strategies[J]. Journal of Discrete Mathematical Sciences and Cryptography， 2018， 21（06） ： 1437-1442.

[4]AHMED ABDELMOUMENE KADRI，IMED KACEM，KARIM LABADI. A branch-and-bound algorithm for solving the static rebalancing problem in bicycle-sharing systems[J]. Computers & Industrial Engineering， 2016， 95： 41-52.

[5]AHMADREZA FAGHIH-IMANI ，NAVEEN ELURU. Determining the role of bicycle sharing system infrastructure installation decision on usage： Case study of montreal BIXI system[J]. Transportation Research Part A， 2016， 94： 685-698.

[6]YI WU，DAJIAN ZHU. Bicycle sharing based on PSS-EPR coupling model： exemplified by bicycle sharing in China[J]. Procedia CIRP， 2017， 64： 423-428.

[7]馬新衛. 多源數據驅動的互聯網租賃自行車智能調度優化方法[D].南京： 東南大學， 2020.

[8]劉雪嬌. 共享單車泊位配建研究[D]. 長沙：中南林業科技大學， 2020.

[9]劉祝銘. 基于使用者的無樁式公共自行車調度方法研究[J].智能城市， 2021， 7（14）： 14-15.

[10] 肖梅， 張穎， 黃洪滔，等. 基于LSTM網絡的浮動單車需求量預測[J].武漢理工大學學報（交通科學與工程版）， 2021， 45（06）： 1010-1016.

[11] 韓世行， 牛睿琪， 高鈺，等. 共享電單車微觀調度優化研究[J]. 時代汽車， 2022（09）： 4-6.

[12] 李浩， 曹元密， 涂輝招. 共享單車騎行需求預測研究[J]. 綜合運輸， 2022， 44（05）： 92-101.

[13] ZADEH L? A. Fuzzy sets[J]. Information and Control， 1965， 8（03）：338-353.

[14] RUSPINI E H. A new approach to clustering[J]. Information andControl， 1969， 15（01）： 22-32.

[15] DUNN J C. Fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters[J]. Journal of Cybernetics， 1973， 3（03）： 32-57.

[16] BEZDEK J C. Fuzzy mathematics in pattern classification[D]. Ithaca， NY： Cornell University， 1974.

Dynamic Scheduling Optimization of Shared Bicyclesin Different Regions

ZHAO Bin， XIE Renxiong

（School of Sciences， Hubei Univ. of Tech.， Wuhan 430068， China）

Abstract：In recent years， the concept of sharing continues to maintain a high fever. The emergence of shared bikes has effectively solved the problem of the last kilometer of travel， but also greatly improved people's travel efficiency. However， we often encounter situations that we cannot find shared bikes or a lot of shared bikes unoccupied. It is aimed to reasonably arrange the placement of shared bikes， and improve the use efficiency of shared bikes. According to the characteristics of shared bicycle random flow， using the fuzzy average clustering over time will be divided into three categories， and Markov transfer matrix will be used to calculate the transfer probability of each area， on the basis of this change the way of the three areas， through the Monte Carlo method will be used to simulate the best display way. The results show that the use efficiency of different proportions is obviously different， and the placement mode after improving the proportion can significantly improve the use efficiency of shared bikes. When the users of the area are different， the maximum threshold of use efficiency is 20; the same regional shared bikes， and the threshold of the maximum use efficiency is 35.

Keywords：shared bike; fuzzy average clustering; transfer probability; Monte Carlo simulation

［責任編校： 閆品］