基于復(fù)雜網(wǎng)絡(luò)的公共自行車調(diào)度區(qū)域劃分方法研究

盧文躍，劉彥斌

（中電?？导瘓F有限公司，浙江 杭州 310012）

0 引言

隨著城市規(guī)模的擴大，交通擁堵狀況日益嚴(yán)重。作為解決“最后一公里”難題的公共自行車系統(tǒng)（Public Bicycle System，PBS）能夠緩解城市道路交通的壓力，減少污染物的排放。隨著公共自行車系統(tǒng)規(guī)模不斷擴大以及共享單車的出現(xiàn)，公共自行車系統(tǒng)的服務(wù)要求也越來越高，但用車高峰時段仍常會出現(xiàn)部分租賃點無車可借或者車輛無法歸還的現(xiàn)象?！敖柢囯y、還車難”已經(jīng)成為了公共自行車運營公司亟待解決的問題。

目前有關(guān)公共自行車運營系統(tǒng)的研究主要集中在租賃點選址、網(wǎng)點規(guī)模優(yōu)化、區(qū)域劃分及調(diào)度等方面。租賃點選址和網(wǎng)點規(guī)模研究[1~3]主要是基于周邊居民人口及對應(yīng)的出行需求進行相應(yīng)測算。考慮到租賃點的建設(shè)成本及工程復(fù)雜度，租賃點一旦建成基本不會變動，而自行車調(diào)度靈活性較高，基本每天都需要相應(yīng)的調(diào)度實現(xiàn)車輛的再平衡，且實現(xiàn)效果較為明顯。

對于自行車調(diào)度，國內(nèi)外學(xué)者對其進行了大量的研究。如Kadri[4]等人通過集成遺傳算法、貪婪搜索算法、局部搜索算法和分支定界算法來確定自行車租賃點的調(diào)度路徑。Battarra[5]等人提出了一種基于整數(shù)規(guī)劃公式的以租賃點調(diào)度次序成本最低的精確算法，并成功運用到多達60個租賃點的實例中。Benjamin[6]等人使用馬爾科夫決策過程方法，開發(fā)了一個決策支持工具，用以確定調(diào)度站點的優(yōu)先級及相應(yīng)的調(diào)度需求量。張建國[7]等人從成本最小化和租賃點滿意度最大化目標(biāo)出發(fā)，在平峰時段和高峰時段分別建立車輛調(diào)配的路徑優(yōu)化模型，并用蟻群算法求解出了不同時段對應(yīng)的車輛調(diào)配路徑。以上方法大都缺少對自行車調(diào)度區(qū)域劃分的研究，從而導(dǎo)致算法的求解周期長、調(diào)度實時性較差、調(diào)度路徑過長，且無法適用于大型的公共自行車系統(tǒng)。

目前針對公共自行車調(diào)度區(qū)域劃分的相關(guān)研究并不多。申興發(fā)[8]等人采用LDA模型和K-means聚類算法對租賃點進行聚類和功能識別，并用POI（Point of Interest）數(shù)據(jù)驗證結(jié)果的有效性，但未涉及調(diào)度區(qū)域的劃分。張晶等[9]人通過數(shù)據(jù)分析估算初始中心點進行第一次K-means聚類，然后引入調(diào)度需求量進行二次K-means聚類調(diào)整得到最終的區(qū)域調(diào)度劃分結(jié)果，該方法主要考慮了空間距離及調(diào)度需要量等影響因素，但忽略了車輛潮汐、站點流通性等因素的影響，無法滿足跨區(qū)域的調(diào)度需求；董紅召等[10]人則根據(jù)公共自行車租賃點間的自流動性，采用關(guān)聯(lián)規(guī)則對強相關(guān)性租賃點進行聚類劃分并形成劃分方案，該方法的缺點在于只考慮了部分租賃點間的流動相關(guān)性，且相關(guān)性閾值的確定較為困難。

現(xiàn)有方法往往在區(qū)域劃分中較少考慮租賃點間的流動相關(guān)性。考慮到公共自行車在租賃點間的流通有其特定的規(guī)律，本文擬通過引入模塊度運用層次聚類算法將具有流通相關(guān)性租賃點劃入同一區(qū)域從而盡可能地避免跨區(qū)域的長距離調(diào)度，減少資源浪費?；诖?，本文首先對調(diào)度區(qū)域進行自然小區(qū)的劃分；然后，基于小區(qū)間的流動性采用基于模塊度的層次聚類算法，獲得一次聚類結(jié)果；最后基于屬性標(biāo)定合成二次聚類結(jié)果，形成公共自行車的調(diào)度區(qū)域劃分方案。

1 基于復(fù)雜網(wǎng)絡(luò)的調(diào)度區(qū)域劃分模型

復(fù)雜網(wǎng)絡(luò)（Complex Network）是指具有自組織、自相似、吸引子、小世界、無標(biāo)度中部分或全部性質(zhì)的網(wǎng)絡(luò)，其具有小世界特性、無標(biāo)度特性以及社團結(jié)構(gòu)特性。

1.1 模塊度

復(fù)雜網(wǎng)絡(luò)中的社團發(fā)現(xiàn)用于發(fā)掘復(fù)雜網(wǎng)絡(luò)中的社團結(jié)構(gòu)，社團內(nèi)部的連接較為緊密，而社團之間的連接較為松散[11]。為了比較各種社團結(jié)構(gòu)發(fā)現(xiàn)算法的優(yōu)劣，Newman等[12]人提出了模塊度的概念，用以表征復(fù)雜網(wǎng)絡(luò)在社區(qū)劃分下與隨機網(wǎng)絡(luò)的差異。模塊度為：

式中，eij表示社團i與社團j之間連接邊數(shù)占網(wǎng)絡(luò)總連接邊數(shù)的比例；Tre是矩陣e的跡；‖e2‖表示矩陣e2的和范數(shù)。模塊度Q表示為復(fù)雜網(wǎng)絡(luò)中社團內(nèi)部的連邊所占之比例與隨機連接情況下社團內(nèi)部連邊所占比例之期望值的差值。對于無向加權(quán)網(wǎng)絡(luò)[10]，對應(yīng)的表達式為：

頂點i和j之間邊的權(quán)重值；Ci表示頂點i所在的社團，當(dāng)頂點i和頂點j在同一社團中時，δ（Ci，Cj）=1，否則δ（Ci，Cj）=0。

基于模塊度的優(yōu)化算法主要有GN算法[14]、FN算法[14]、CNM算法、BGLL算法[15]。其中BGLL算法是一種重疊社團發(fā)現(xiàn)算法，算法兩層迭代，外層的迭代是自下而上的凝聚法，內(nèi)層的迭代是凝聚法加上交換策略，避免了單純凝聚方法的缺點。相較于其他方法，BGLL算法復(fù)雜度更低，能在短時間消耗下處理上千萬的復(fù)雜網(wǎng)絡(luò)，同時還能保持良好的社團劃分效果。因此，本文將選擇拓展后的BGLL算法來優(yōu)化模塊度。

1.2 PBS模型定義

公共自行車系統(tǒng)（Public Bicycle System，PBS）是以租賃點為節(jié)點的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，租賃點間自行車的流通量表示了網(wǎng)絡(luò)節(jié)點的邊的權(quán)重值，因此可用復(fù)雜網(wǎng)絡(luò)的思想來研究公共自行車系統(tǒng)租賃點的社團結(jié)構(gòu)。同時，公共自行車在租賃點間的流通存在潮汐現(xiàn)象，應(yīng)用社團劃分可將具有流通相關(guān)性的租賃點劃分在同一社團，使得社團內(nèi)部的租賃點間的流通相關(guān)性較強而社團間的流通相關(guān)性較弱。為了簡化和描述算法，這里給出城市公共自行車系統(tǒng)相關(guān)概念[13]。

公共自行車租賃點拓撲網(wǎng)絡(luò)可表示為G=（V，E）。u，v表示為V中的兩個租賃點，三元組（u，v，T）表示租賃點u，v之間存在有向連接關(guān)系。其中T表示在指定時間內(nèi)從租賃點u到租賃點v之間的自行車流通量。鑒于公共自行車在租賃點間流動是雙向的，公共自行車租賃點網(wǎng)絡(luò)是一個有向加權(quán)圖，結(jié)合復(fù)雜網(wǎng)絡(luò)中模塊度的定義，得出公共自行車網(wǎng)絡(luò)的模塊度為：

式中，Q為公共自行車網(wǎng)絡(luò)的模塊度；u，v分別表示u節(jié)點和v節(jié)點；表示在時間段[t1，t2]內(nèi)從節(jié)點u到節(jié)點v公共自行車流通量；表示在時間段[t1，t2]內(nèi)整個PBS中的自行車的流通量；δ（Cu，Cv）為克羅內(nèi)克函數(shù)，若u節(jié)點與v節(jié)點在同一集合內(nèi)，則克羅內(nèi)克函數(shù)的值為1，否則值為0。

BGLL算法主要應(yīng)用于無向加權(quán)網(wǎng)絡(luò)中，此處對其進行了拓展（后邊統(tǒng)一稱為層次貪婪算法），可計算出租賃點網(wǎng)絡(luò)在節(jié)點調(diào)整時產(chǎn)生的相對增益：

式中，ΔQ′表示p節(jié)點轉(zhuǎn)移集合后產(chǎn)生的模塊度的相對增益；為p節(jié)點與所要轉(zhuǎn)移的集合間的公共自行車流通量之和；表示所要轉(zhuǎn)移的集合內(nèi)所有節(jié)點的公共自行車歸還量總和；kpo表示p節(jié)點的公共自行車的借出量；kpi表示p節(jié)點的公共自行車的歸還量；表示所要轉(zhuǎn)移的集合內(nèi)所有節(jié)點的公共自行車借出量之和；W為整個公共自行車系統(tǒng)中的公共自行車流通量。上述各統(tǒng)計量均為時間段[t1，t2]內(nèi)的統(tǒng)計量。

由層次貪婪算法劃分的公共自行車租賃點區(qū)域能在區(qū)域內(nèi)部達到一定的自平衡狀態(tài)，可通過定義公共自行車系統(tǒng)的不平衡度模型來驗證其自平衡特性，其關(guān)鍵參數(shù)包括：

（1）租賃點不平衡度[15]Hj（τ）為在時間段τ內(nèi)，租賃點借出的公共自行車數(shù)量與歸還的公共自行車數(shù)量的差值。

（2）區(qū)域不平衡度Hα（τ）為在時間τ內(nèi)，區(qū)域α內(nèi)所有租賃點不平衡度的總和。

2 模型的算法實現(xiàn)

如圖1所示是基于復(fù)雜網(wǎng)絡(luò)的調(diào)度區(qū)域劃分流程圖。將自行車租賃點劃分自然小區(qū)作為基本節(jié)點，通過層次貪婪算法進行第一次聚類，結(jié)合地理位置、租賃點數(shù)量、調(diào)度需求量進行二次聚類，形成調(diào)度區(qū)域方案，具體步驟如下。

圖1 基于復(fù)雜網(wǎng)絡(luò)的調(diào)度區(qū)域劃分流程圖Figure 1 Division of scheduling area based on complex network

①站點OD量的計算。用戶在使用公共自行車作為出行工具時，一次完整的交易包括在起始站點的刷卡借車以及終止站點的刷卡還車。在自行車交易表中記錄的關(guān)鍵字段包括起始站點u、租車時間、歸還站點v、歸還時間等，站點OD量的計算即是對于所有的租賃點對（u，v），獲得其三元組（u，v，T）的值。

②自然小區(qū)劃分。公共自行車主要通過調(diào)度車進行調(diào)度，為使最終形成的調(diào)度區(qū)域符合道路走向，需要事先對站點進行自然小區(qū)的劃分。城市道路等級分快速路、主干路、次干路、支路四級，對于公共自行車租賃點所在區(qū)域，按照道路等級從高到低分割成網(wǎng)格，形成最基本的網(wǎng)格單元即為自然小區(qū)。

③自然小區(qū)判別?；谒泄沧孕熊囎赓U點的經(jīng)緯度位置進行所歸屬的自然小區(qū)判別，將同一自然小區(qū)內(nèi)的所有公共自行車租賃點合并作為一個節(jié)點，同時將各自然小區(qū)間的公共自行車流通量作為節(jié)點間的公共自行車流通量，生成自然小區(qū)節(jié)點對（p，q）以及三元組（p，q，T）。

④第一次聚類。構(gòu)造以自然小區(qū)為節(jié)點的復(fù)雜網(wǎng)絡(luò)，以模塊度為目標(biāo)函數(shù)，通過層次貪婪算法進行節(jié)點的聚類劃分。以每個小區(qū)作為單獨節(jié)點，歸入不同的集合中，遍歷節(jié)點并將節(jié)點歸入到相鄰集合中前后的相對增益最大且大于0的集合中，計算完所有節(jié)點，再將同一集合的各節(jié)點合并為新的節(jié)點并計算新節(jié)點間的公共自行車流通量，重復(fù)以上過程直到整個公共自行車網(wǎng)絡(luò)的模塊度不發(fā)生變化。對應(yīng)的具體步驟如下，可得到對應(yīng)的第一次聚類劃分結(jié)果。

輸 入：三元組D={（p1，q1，T1），（p2，q2，T2），...，（pm，qm，Tm）}；

過程：函數(shù)FirstCluster（D）

1：計算所有節(jié)點組成網(wǎng)絡(luò)的模塊度Q

2：while模塊度Q增大do

3：for每一個節(jié)點i do

4：將節(jié)點i歸入到相鄰節(jié)點所在集合

5：計算所有歸入前后產(chǎn)生的相對增益（ΔQ′1，ΔQ′2LΔQ′n）

6：for每一個相對增益ΔQ′jdo

7：if相對增益ΔQ′j大于0

8：獲取最大的相對增益ΔQ′j，并將節(jié)點i歸入該節(jié)點所在集合

9：else

10：節(jié)點i保留在原集合中

11：end if

12：end for

13：end for

14：將同一集合的節(jié)點合并為新的節(jié)點，并計算新節(jié)點間的流通量

15：計算新節(jié)點網(wǎng)絡(luò)的模塊度Q

16：end while

輸出：每個節(jié)點及節(jié)點所屬集合編號{（p1，C1），（p2，C2），...，（pm，Cm）}

⑤二次聚類。對前一次聚類劃分的各個區(qū)域進行屬性的標(biāo)定，綜合各個聚合區(qū)域的地理位置、調(diào)度需求量、租賃點的數(shù)量屬性進行區(qū)域合并，使得生成的最后調(diào)度區(qū)域的各屬性值基本平衡，同時其數(shù)量與調(diào)度中心的數(shù)量相一致，即為最后的調(diào)度區(qū)域劃分方案。

3 應(yīng)用實例

本文以某地區(qū)公共自行車系統(tǒng)作為研究對象，其中有效租賃點的數(shù)量為457個（有交易數(shù)據(jù)的租賃點數(shù)量）。取2018年10月22日至10月28日的自行車交易數(shù)據(jù)作為樣本數(shù)據(jù)，經(jīng)過濾3min以內(nèi)行程及其他異常數(shù)據(jù)，得到了近9000條交易記錄。圖2所示對該區(qū)域按照道路網(wǎng)進行劃分得到了187個自然小區(qū)（后文主要以主城區(qū)部分為重點進行說明）。

圖2 某地區(qū)自然小區(qū)劃分分布圖Figure 2 Distribution map of natural districts in a certain area

針對劃分好的自然小區(qū)，將自行車租賃點按經(jīng)緯度位置進行匹配，計算獲得各自然小區(qū)間的自行車流通量。此處以自然小區(qū)作為基本節(jié)點，運用層次貪婪算法進行第一次聚類，其模塊度的變化如圖3所示。由圖3可知，模塊度由最初的0.2423經(jīng)過三層的節(jié)點遍歷最終達到了0.5886（橫坐標(biāo)表示節(jié)點成功轉(zhuǎn)移的次數(shù)，面板顏色的深淺表示了不同的層，虛線表示每層結(jié)束對應(yīng)的模塊度的大?。皟蓪拥哪K度變化較大而第三層的模塊度基本不變。圖4a）表示了第一次聚類的分析結(jié)果，可以看到該地區(qū)主城區(qū)部分被分為了7個區(qū)域，對應(yīng)了不同的顏色，黑色的自然小區(qū)表示該區(qū)域內(nèi)無自行車租賃點。對于聚類得到的大區(qū)域的“空洞”部分，可按就近原則將其歸入到對應(yīng)的區(qū)域中，如3區(qū)域的方框部分的自然小區(qū)可歸入到3區(qū)域中，對應(yīng)的結(jié)果如圖4b）所示。對于同區(qū)域內(nèi)的租賃點之間流通相關(guān)性較大，而區(qū)域間的租賃點間的流通相關(guān)性較小，因此區(qū)域內(nèi)部的租賃點的自行車數(shù)量能達到一定的自平衡狀態(tài)。

圖3 模塊度的變化曲線Figure 3 Variation curve of modularity

圖4 第一次聚類劃分結(jié)果圖Figure 4 Results of the first clustering partition

根據(jù)第一次聚類劃分結(jié)果，對各個區(qū)域的屬性特征進行標(biāo)定，根據(jù)每個區(qū)域的地理位置、租賃點數(shù)量以及調(diào)度需求量進行二次聚類。對應(yīng)7個區(qū)域的屬性情況如表1所示?？梢钥闯觯瑓^(qū)域1和區(qū)域6的租賃點數(shù)量較少，在地理位置是相鄰的，且區(qū)域1對應(yīng)的調(diào)度需求量為9而區(qū)域6的調(diào)度需求量為-20，可進一步實現(xiàn)平衡，因此可對其進行合并。同理也可以對區(qū)域2和區(qū)域3進行合并，最終將所有區(qū)域劃分為5個區(qū)域，如圖5所示。劃分結(jié)果以區(qū)域5為中心，其他4個區(qū)域分布于東南西北四個方向。區(qū)域5的租賃點最為集中，主要對應(yīng)了商業(yè)區(qū)及住宅區(qū)；區(qū)域3則以景區(qū)為主；區(qū)域4和區(qū)域1則主要以產(chǎn)業(yè)園區(qū)等工作區(qū)域為主；區(qū)域7則主要為郊區(qū)。表2展示了結(jié)果區(qū)域的租賃點數(shù)量以及區(qū)域不平衡度。區(qū)域不平衡度需要通過跨區(qū)域調(diào)度來進行平衡，而表中所示所有區(qū)域在一周產(chǎn)生的不平衡度都遠小于租賃點數(shù)量，說明區(qū)域內(nèi)部達到了較好的自平衡狀態(tài)且無需進行短期的跨區(qū)域調(diào)度。因此，相較于傳統(tǒng)的依據(jù)經(jīng)驗的區(qū)域劃分以及運用K-means聚類等方法并未考慮區(qū)域間流通關(guān)系的區(qū)域劃分，該方法通過研究區(qū)域的流通相關(guān)性可以盡可能地減少調(diào)度車的跨區(qū)域調(diào)度，同時較好均衡了各區(qū)域的屬性特征，提高了公共自行車的調(diào)度效率。對于跨區(qū)域調(diào)度，只需以月或者年為單位對區(qū)域間自行車數(shù)量進行適當(dāng)調(diào)整。

表2 二次聚類劃分區(qū)域不平衡度Table 2 Regional imbalance degree by secondary clustering

圖5 二次聚類結(jié)果圖Figure 5 Results of the secondary clustering

表1 第一次聚類劃分區(qū)域的屬性標(biāo)定Table 1 Attribute calibration table of the first clustering division area

4 結(jié) 語

本文通過道路網(wǎng)劃分獲得自然小區(qū)，以自然小區(qū)為節(jié)點應(yīng)用層次貪婪算法進行第一次聚類，然后結(jié)合區(qū)域的地理位置、租賃點數(shù)量以及調(diào)度需求量進行二次聚類得到最終的劃分結(jié)果，并結(jié)合區(qū)域不平衡度對區(qū)域的自平衡特性進行驗證。該方法綜合了區(qū)域內(nèi)部自行車的自流動特性以及區(qū)域間的租賃點數(shù)量和調(diào)度需求量的平衡，可減少區(qū)域間的跨區(qū)域調(diào)度，實現(xiàn)區(qū)域內(nèi)的自行車數(shù)量的動態(tài)自平衡，能夠較好地滿足城市公共自行車系統(tǒng)調(diào)度的功能需求。

本文所述方法選用道路網(wǎng)劃分后的自然小區(qū)作為基本單元進行聚類，但在實際應(yīng)用中，基本節(jié)點的確定可以更為靈活，可將不可分割的租賃點放置于同一基本單元內(nèi)。同時道路網(wǎng)劃分的精細度也會影響最后的區(qū)域劃分結(jié)果，精細度越高劃分效果越好。公共自行車調(diào)度區(qū)域的劃分是研究租賃點車輛再平衡的基礎(chǔ)，未來也可以在區(qū)域劃分的基礎(chǔ)上進行公共自行車調(diào)度研究。