基于遺傳算法—支持向量機模型的快速公交行程時間算法研究

熊 浩，韓 印 （上海理工大學 管理學院，上海 200093）

0 引言

隨著生活水平的提高車輛數量的增加，擁堵已成為大城市出行亟待解決的問題，提出公交城市提高公共交通的利用率，促進公共交通，以解決大城市的交通擁堵問題。然而，低準時率的公共交通影響了人們對出行方式的選擇。人工智能技術的進步，智慧城市理念的普及，使得人們對于公共交通到站時間預測采用智能化和自動化的方案。

現有的公交到港時間預測模型可以分為三類：交通流理論模型，時間序列分析模型和機器學習模型，根據它們的不同原理。交通流理論模型精度低，校準困難?？柭鼮V波器模型具有較高的預測精度，較強的可操作性和在線預測，但對異常觀測的抗干擾性較差?；跈C器學習方法的預測模型具有較高的精度，神經網絡模型具有良好的學習能力，能夠很好地跟蹤非線性，非平穩時間序列數據。但它需要大量的歷史數據，并且存在諸如學習或學習不足以及局部最小化等問題。支持向量機是一種通過優化方法解決機器學習問題的新工具。近年來，它已被用于公交車行程時間預測，并且當數據樣本很小且維數很高時，它仍然可以做出更好的預測。

綜上所述，支持向量機模型能基于小數據樣本，預測出較準確的到站時間。因此，本文旨在建立基于支持向量機理論的公交通行時間綜合預測模型，并在此基礎上，使用BRT數據作為數據庫，在不同時間段實現BRT行程時間預測，并將預測結果與實際到達時間進行比較，以驗證模型的準確性。分析了所提出的預測模型在不同時間段的適用性。

1 算法原理簡介

將公交的行程時間分為相鄰兩站之間的運行時間和本站的駐站時間。

其中：ti+1為到達i+1站點的時間；ti為到達i站點的時間；si為在i站點駐站時間；Ti,i+1為車輛在i和i+1站點之間各段運行時間。

在路段運行時，運行時間受天氣、路段、交叉口、發車時間、上下行等因素影響；在站臺停留時，駐站時間受到車輛、客流量、站臺形式、天氣等因素影響。

1.1 支持向量機（SVM） 算法

SVM的主要思想是將訓練數據集非線性地映射到高維特征空間（這個高維特征空間是希爾伯特空間）。此非線性映射的目的是在映射到高維特征空間之后將輸入空間中的線性不可分數據集轉換為線性可分離的數據集。然后創建分類超平面作為決策表面，以使正例和負例之間的隔離邊最大化，是結構風險最小化的近似實現。它具有在各種功能集中構建功能的多功能性，不需要特定的功能形式，并且可以用于非線性系統，比如輸出變量（如公交車行駛時間）和輸入變量（如交通狀況，客流要求等）之間的復雜關系。

SVM算法是具有線性約束的二次優化問題，結果是唯一且最優的。沒有其他神經網絡訓練方法需要非線性優化，容易導致陷入局部最小值的風險。給定一組數據點 （x1,y1）、 （x2,y2）、 （x3,y3）、 （xk,yk），X表示輸入向量空間，Y表示輸出變量空間。SVM具有以下的函數形式：

其中：φ（x）是一種非線性映射函數，可以將輸入向量空間X映射到高維特征空間H。

系數ω和b通過最小化規則化風險函數進行計算：

其中：第一項||ω||2稱為正則化項，最小化||ω||2可使函數盡可能平滑，提高函數的泛化能力。第二項）稱為經驗風險函數，即通過測量不敏感損失函數得到的實驗誤差；常數C用于平衡結構風險與經驗風險，通常C＞0。通過引入松弛變量ξi和并將上述問題轉換為以下形式：

為了解決上述優化問題，引入拉格朗函數將上述形式轉化為以下對偶問題：

其中：ai和叫做拉格朗日因子。

則：

將核函數K（xi,xj）引入式 （7），得：

核函數K（xi,xj）為向量xi和xj在特征空間φ（xi）和φ（xj）上的內積。根據現有文獻，本研究選擇徑向基核函數進行預測。徑向基核函數如下：

為了獲得結果最好的SVM模型，分別采用交叉驗證、粒子群算法和遺傳算法尋找參數C和γ的最優組合。

1.2 支持向量機（SVM）算法行程時間應用

影響公交車出行時間的因素非常復雜，包括天氣狀況、公交車運行時間、交叉口延誤、路況、緊急情況等，這些都可能導致公交車行程時間的非線性變化。SVM模型具有很強的非線性預測能力，可以應用于模型預測。

因此在路段運行時，運行時間的影響因素包括天氣、路段、交叉口、發車時間、發車站點、上下行。在站臺停留時，駐站時間的影響因素包括車輛類型、客流量、站臺形式、站臺編號、天氣、到站時間。

1.3 遺傳算法優化原理

遺傳算法（Genetic Algorithm，GA）最初是由美國Michigan大學Holland教授于1975年首次提出的，并出版了專著“自然與人工系統的適應”，遺傳算法的名稱逐漸為人所知，繼承是生物的普遍特征，自生命誕生以來，它已經開始了漫長的進化過程。父母將遺傳信息傳遞給后代，后代具有與父母相同或相似的特征；突變是遺傳過程中親本和后代之間性狀的差異。它尋找基于自然進化規則的解決問題，例如適者生存，其特征不受搜索空間是連續還是略有不同的限制。它也適用于大規模并行計算，為傳統數學方法難以解決或明顯無效、復雜、非線性和優化的問題提供了一種新的有效方法。

遺傳算法基于自然選擇和生物遺傳機制，用于全局優化，分類和評估其他數據挖掘技術的適用性。它通常包括3個基本操作，即父母選擇、親子交叉和子代變異。具體步驟如下：

（1）確定參數編碼方案，并以二進制編碼模式編碼SVM相關參數。

（2）確定適應度函數，交叉驗證模式中的準確率是遺傳算法的適應度函數。

（3）遺傳算法優化操作。

（4）遺傳優化后，得到支持向量機的最優參數，最終得到最佳分類結果。

整個算法流程如圖1：

1.4 模型參數

為了便于引入模型，之后要使用的主要模型參數符號如表1所示。

圖1 遺傳算法—SVM模型預測行程時間圖

表1 符號和參數

2 數據處理

2.1 基礎數據處理

為了驗證模型的有效性，以上海市71路中運量公交線路為例對模型進行計算。71路中運量公交線路東起延安東路外灘，西至申昆路樞紐，共計25個站點，全長28.8km。該線路的公交車輛上面均裝配有以GPS裝置為主體的記錄設備，該設備能夠采集公交車的實時經緯度坐標、到站時刻、離站時刻、站點名稱、站點編號、設備編號等信息，并將信息實時傳輸。每輛公交車的設備編號是唯一的，可用作匹配路段行程時間的標識。

數據是2017年11月21日到11月24日的上海市71路中運量公交各項數據?？偣驳玫?06 854條數據，經過分析，有效數據有91 863條。數據類型見表2和表3。

表2 BRT站間運行數據類型

表3 BRT駐站時間數據類型

上海市71路中運量線路及站點如圖2所示：

2.2 數據分析

對處理后數據進行分析，7天的客流數據進行小時時間段分布，如圖3所示，得出此線路公交車高峰運行時間在早上7:00～9:00和晚上5:00～7:00。在此基礎上，對此線路運行站點客流進行分析，得出全天的客流呈現雙駝峰，但早高峰剛性出行人數較多，所以短時上下車客流較多。

3 實驗結果與分析

3.1 模型檢驗

本實驗使用Matlab用于測試遺傳算法優化模型的準確性。

3.1.1 評價指標確定

為了確定所研究的遺傳算法優化參數的SVM模型預測結果的準確性，將前3天數據平均值和預測當天實際值作為比較加入，并且使用以下3個評估指標來評估預測結果：平均絕對誤差（Mean Absolute Error，MAE），平均絕對誤差百分比（Mean Absolute Percentage Error，MAPE） 和均方根誤差（Root Mean Square Error，RMSE）。其計算公式見公式（10） 至公式（12）。

圖2 上海市71路中運量線路及站點圖

圖3 上海市71路中運量上下客人數柱狀圖

其中，N為觀測值、預測值對數。

3.1.2 結果對比

利用matlab對數據進行預測，將其預測結果與實際結果進行對比。由表4可以看到，GA預測出的數據雖跟實際值有8%～10%左右的誤差，但相比使用前3天的平均值得出的結果，GA預測更加精準。

GA-SVM預測出的駐站時間偏差相比運行時間稍大，這是因為71路大部分是專有路權，運行中所受干擾較普通公交小。

3.2 結果分析

圖4顯示了早高峰相鄰每站時間的結果對比。在GA-SVM模型和平均值對比下，GA-SVM算出的每站時間趨勢與實際值更加相近，且偏差不大。但平均數趨勢不甚明顯，可能是由于平均數綜合了全天的數據，本次只是早高峰的數據。

圖5更是驗證了之前的結果。圖5在前5站由于人少、交通干擾少，兩種算法的行程時間值和實際值偏差不大。但到達第6站之后進入市區，平均值出現大幅偏差，而GA-SVM的值趨勢仍趨近真實值，但由于模型學習了3天的全天數據，本次實驗只針對早高峰，導致部分時間預測出現偏差較大。

圖4 相鄰每站時間預測結果對比

圖5 行程時間預測結果對比

4 結束語

本文預測了上海中運量車的到達時間，并將到達時間分為車站間的運行時間和車站的駐站時間。根據天氣、時間、公交車類型和平臺類型等影響因素，建立支持向量機回歸預測模型，并通過matlab驗證模型的準確性。通過數據分析，討論了3天到達時間數據對后一天到達時間預測的影響，為決策者更好地選擇公交到達時間預測模型提供了指導。研究結果表明：

（1）所建立的基于遺傳算法參數尋優的支持向量機模型，經過數據學習后，能預測出較為準確的快速公交到站時間和行程時間。結果表明，遺傳算法尋優參數更加準確。

表4 時間對比

（2）GA-SVM針對小批量數據的學習能預測出比較準確的駐站時間和運行時間。相比平均值法，得出的時間更加精準，更加適用。