基于IC卡數據的公交路線聚合算法

戚陽 黃信程 張錦旺 何煦 于海洋

【摘 要】公交運行線路的制定需要了解區域內乘客最常用的通勤線路，本文提出了一種基于Apriori算法、DBSCAN算法和模糊支撐樹聚類的公交路線聚合算法，可以在已知路網拓撲結構以及區域內客流OD特征的條件下，求解區域內的典型路線。本文基于深圳市公交IC卡數據驗證了所提出方法的有效性。

【關鍵詞】公交路線聚合；典型路線；Apriori算法；DBSCAN算法；模糊支撐樹聚類

1.引言

隨著經濟的發展和人口數量的增加，我國一線城市逐漸暴露出公共交通運載能力與出行需求不匹配的問題，交通區域發展出現了不平衡的態勢。以深圳市為例，城市內不同的地區職住分離特征愈來愈明顯。目前深圳市以福田、南山、羅湖為主要就業地，以寶安、龍華、龍崗為主要居住地，因上班導致的平均通勤距離達到17.9公里。特殊的城市空間結構，給深圳市的城市交通帶來大規模潮汐性出行需求。而由于傳統的公交網絡的布設不符合如今的出行需求總量，導致有效的供給能力不能滿足群眾多樣化、多層次的出行需求，使得有條件的市民傾向于選擇個體化出行方式。大量私家車的上路給交通運輸網絡帶來極大的壓力，加重了城市道路的擁堵現象，也加劇了空氣污染等問題。

為了應對上述問題，在當今互聯網+興起的大背景下，定制公交的概念被提出。定制公交可以以用戶提交的需求數據為主，結合公共交通數據、小區住房數據以及地理信息等多維度數據，通過人工智能、機器學習、聚合算法等各種大數據技術，聚合生成線路，為白領用戶提供一人一座，家（住宅區）和公司（辦公區）之間直達的定制出行服務。大數據技術的應用有助于公交車線路的高效配置，提高車輛的有效路段里程，進而提高交通運輸效率；此外，大數據分析也具有較高預測能力，可降低誤報和漏報的概率，可隨時針對公共交通的動態性給予實時監控。因此，在駕駛者無法預知交通的擁堵可能性時，大數據亦可幫助用戶預先了解。除了提升用戶的出行體驗，也對緩解交通擁堵有很大價值。

為了合理地設置定制公交的線路，需要對行人的出行需求進行調查，掌握乘客的出行規律，并從需求中分析典型的出行路線用于制定行車路線。目前，很多研究者致力于研究基于公交IC卡等數據提取出出行需求特征的方法，一般將出行特征表示為OD矩陣的形式，矩陣中各個元素表示所研究區域的兩個區塊之間的出行需求。然而，如何基于提取的OD矩陣分析挖掘出最典型的車輛行車線路，仍然是需要不斷研究的一個問題，目前，大多研究都將這個問題轉化為聚類問題，例如K-means聚類等。

本文提出了一種公交路線聚合算法，在分析得到交通路網拓撲結構的情況下，采用Apriori算法[1]和DBSCAN算法[2]對人們的公共交通出行路線、公交站點、出行時段進行分析歸類。隨后分析現有公交信息，確定候選典型行車路線，最后根據模糊支撐樹聚類算法實現出行路線最優化，本文所提出的算法的流程圖如圖1。

2.算法介紹

2.1 城市道路網絡拓撲建模方法

將城市道路網絡的拓撲結構抽象為網絡模型，目前主要有兩種方法：一種稱為為主方法（Primal aproach），是將道路的交叉口抽象為圖的節點，連接交叉口之間的路段抽象為邊或弧；這種方法的特定是簡單直觀，保留了較完整的地理相關性，是傳統交通網絡建模方法，也是目前大部分GIS軟件所采用的建模方法。另一種為對偶法（Dual approach），可以認為是主方法的對偶，即將道路抽象為節點，道路與道路的連接關系表示為圖的邊或弧。一條完整道路的構建是將連續的路段按一定的規則綜合而成，目前主要有軸線法、名稱法和角度法。其中，軸線法采用軸線代表道路，是依據人的視覺將近似直線的路段合并為一條道路并用一條軸線表示；名稱法是指在合并路段時依據道路的名稱，將具有相同名稱的路段連接在一起；角度法的合并原則是依據格斯塔的連續性原則，通過計算路段與路段的夾角，并根據設定的夾角閾值生成道路。

實踐中這兩種建模方法各有特點。主方法直觀簡單，保留了路網的布局特點；對偶法忽略了地理實體的一些地理意義，如地理位置、道路長寬等，更適合探索網絡結構下的功能意義。對偶法中合并路段的幾種方法也各有優缺點。例如，軸線法軸線的生成主要依據人的視覺判斷，合并規則引入主觀因素，因此不同的人可能得到不同的軸線地圖，即方法不具有唯一性；名稱法的局限性在于合并規則完全依賴屬性信息，忽略了空間特性并喪失了直觀性，在缺少道路名稱信息或信息不準確的情況下無法完成；角度法的合并則完全從圖形角度考慮，不受人為因素和屬性因素影響。

2.2 基于Apriori算法和DBSCAN算法的公交路線聚類

（1）Aprioi算法

Apriori算法是常用的用于挖掘出數據關聯規則的算法，它用來找出數據值中頻繁出現的數據集合，找出這些集合的模式有助于我們做一些決策。比如在常見的超市購物數據集，或者電商的網購數據集中，如果我們找到了頻繁出現的數據集，那么對于超市，我們可以優化產品的位置擺放，對于電商，我們可以優化商品所在的倉庫位置，達到節約成本，增加經濟效益的目的。

Aprior算法的目標是找到樣本中最大K值的K項頻繁集，本文采用支持度作為頻繁集的判定標準。例如如果找到符合支持度的頻繁集AB和ABE，就保留ABE，因為AB是2項頻繁集，而ABE是3項頻繁集。

Apriori算法采用了迭代的方法，先搜索出候選1項集及對應的支持度，剪枝去掉低于支持度的1項集，得到頻繁1項集。然后對剩下的頻繁1項集進行連接，得到候選的頻繁2項集，篩選去掉低于支持度的候選頻繁2項集，得到真正的頻繁2項集，以此類推，迭代下去，直到無法找到頻繁k+1項集為止，對應的頻繁K項集的集合即為算法的輸出結果。

（2）DBSCAN算法

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一個比較有代表性的基于密度的聚類算法。與劃分和層次聚類方法不同，它將簇定義為密度相連的點的最大集合，能夠把具有足夠高密度的區域劃分為簇，并可在噪聲的空間數據庫中發現任意形狀的聚類。

DBSCAN的幾個概念：

Ε鄰域：給定對象半徑為Ε內的區域稱為該對象的Ε鄰域；

核心對象：如果給定對象Ε鄰域內的樣本點數大于等于MinPts，則稱該對象為核心對象；

直接密度可達：對于樣本集合D，如果樣本點q在p的Ε鄰域內，并且p為核心對象，那么對象q從對象p直接密度可達；

密度可達：對于樣本集合D，給定一串樣本點p1，p2….pn，p= p1，q= pn，假如對象pi從pi-1直接密度可達，那么對象q從對象p密度可達；

密度相連：存在樣本集合D中的一點o，如果對象o到對象p和對象q都是密度可達的，那么p和q密度相聯。

2.3 基于模糊支撐樹聚類算法生成區域內典型行車路線

區域典型行車路線庫由模糊支撐樹聚類算法實現。根據OD站點信息利用模糊支撐樹聚類算法的程序生成最優定制公交出行路線。最終該區域中各OD間的最優公交出行線路通過聚合構成區域典型行車路線。下面是對模糊支撐樹聚類算法的介紹：

（1）支撐樹

支撐樹算法也叫生成樹算法，在圖論的數學領域中，如果連通圖 G的一個子圖是一棵包含G 的所有頂點的樹，則該子圖稱為G的生成樹（SpanningTree）。生成樹是連通圖的包含圖中的所有頂點的極小連通子圖。圖的生成樹不唯一。從不同的頂點出發進行遍歷，可以得到不同的生成樹。常用的生成樹算法有DFS生成樹、BFS生成樹、PRIM 最小生成樹和Kruskal最小生成樹算法。

（2）模糊支撐樹聚類方法

模糊決策樹算法是傳統決策樹算法的一個擴充和完善，使得決策樹學習的應用范圍擴大到了能處理不確定性。模糊決策樹學習的歸納結果與傳統的比較，由于合理地處理了不精確信息，從而有著更強的分類能力及穩健性，使得知識表示的方式更為自然。由于能生成不同水平和不同置信度的推理規則，故而提供了一種構造專家系統的有效途徑，并可為決策者提供豐富的決策信息。

3.實驗結果

本文采用深圳市2012年8月6日至2012年8月10日的全市公交 IC 卡刷卡數據，以及相應時期的車站坐標、線路長度以及站距數據，來驗證本文所提出的算法。選用這五天數據的原因為，這五天為連續工作日（周一至周五），并且沒有假期。而在此階段，學生大多已經放假，其中的通勤乘客主要是以上班為主，滿足本文的研究對象。

對該周工作日的地鐵刷卡卡數及記錄數進行統計，得到表格如下：

隨后統計每張卡的刷卡次數，統計結果如圖3：

通過設置合理的支持度閾值，基于Aprioi算法可以成功地識別乘客的通勤線路

為了解決共站問題，即有些車站實質上是一個車站，卻因為線路不同，有不同的站號；有些車站距離很近，乘客有多種出行選擇，而不同車站識別結果卻不同；本文采取利用 DBSCAN 算法對站點進行聚類。算法輸入的數據為深圳公交車站站距位置表，其中包括了公交、地鐵的車站站距以及坐標。全表共有 61136 個不同的車站，將車站標識以及坐標輸入算法程序，之后新建字段―新車站標識‖，將算法識別后的結果，每個簇賦新值存入新車站標識中。在運行完算法后，最終得到新車站標識 7264 個。將全部 61136 個站點壓縮為 7264個站點，壓縮率 11.88%，為解決共站問題起到了很好的效果。

通勤乘客的出行時段雖然較為規律和固定，但是卻又有波動性，尤其是下班時間。一般上班時間是有要求固定的，而下班時間卻并不固定，因為會有加班或是下班后有活動的特殊情況。因此，采用時段模糊處理。改進方法后，再次對通勤乘客進行了識別，識別結果如下：

隨后我們基于模糊支撐樹聚類生成了區域內的典型行車路線，所得到的結果與我們先驗的認知較為相符。

4.結束語

本文提出了一種公交路線聚合算法，基于交通路網拓撲結構和出行客流OD特征，采用Apriori算法、DBSCAN算法和模糊支撐樹聚類算法分析區域內每位乘客的通勤路線并最終求解了區域內的典型行車路線。本文、基于深圳市公交IC卡刷卡數據對所提出的算法進行了驗證，證明了本文提出的算法的有效性。

基金項目：深圳市科技計劃項目（KJYY20160331162313860）

參考文獻：

[1] Agrawal R，Srikant R.Fast algorithms for mining association rules[M]// Readings in database systems（3rd ed.）.Morgan Kaufmann Publishers Inc.1996.

[2] Ester M，Kriegel H P，Xu X.A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise[C]// International Conference on Knowledge Discovery & Data Mining.1996.

（作者單位：深圳市東部公共交通有限公司）