盧文躍，劉彥斌

（中電?？导瘓F(tuán)有限公司，浙江 杭州 310012）

0 引言

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

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

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

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

現(xiàn)有方法往往在區(qū)域劃分中較少考慮租賃點(diǎn)間的流動相關(guān)性。考慮到公共自行車在租賃點(diǎn)間的流通有其特定的規(guī)律，本文擬通過引入模塊度運(yùn)用層次聚類算法將具有流通相關(guān)性租賃點(diǎn)劃入同一區(qū)域從而盡可能地避免跨區(qū)域的長距離調(diào)度，減少資源浪費(fèi)。基于此，本文首先對調(diào)度區(qū)域進(jìn)行自然小區(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)度特性以及社團(tuán)結(jié)構(gòu)特性。

1.1 模塊度

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

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

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

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

1.2 PBS模型定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2：while模塊度Q增大do

3：for每一個(gè)節(jié)點(diǎn)i do

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

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

6：for每一個(gè)相對增益ΔQ′jdo

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

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

9：else

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

11：end if

12：end for

13：end for

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

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

16：end while

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

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

3 應(yīng)用實(shí)例

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

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

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

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

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

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

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