一種基於模擬退火算法的公交實時到站時間預測方法
2023-04-24 15:14:11 2
一種基於模擬退火算法的公交實時到站時間預測方法
【專利摘要】本發明公開了一種基於模擬退火算法的公交實時到站時間預測方法，包含以下的主要步驟：（1）基於歷史行車數據建立不同站點不同班次的公交車歷史運行時間的資料庫；（2）採用模擬退火算法對歷史運行時間數據進行訓練，對數據進行聚類，形成一個基於時間段聚類的不同路段的平均行駛時間OD矩陣；（3）利用被預測公交車的動態運行信息來修正由模擬退火算法預測的平均行駛時間OD矩陣，得到該公交車的最佳平均行駛時間。本發明不僅充分發揮模擬退火算法在啟發式迭代優化搜索算法方面的優勢，而且還根據公交車運行的最新數據自動修正平均行駛時間OD矩陣中的參數，是一種動態的公交車到站時間預測模型和計算方法。
【專利說明】一種基於模擬退火算法的公交實時到站時間預測方法
【技術領域】
[0001]本發明涉及城市智能公交系統【技術領域】，具體涉及一種基於模擬退火算法的公交實時到站時間預測系統和方法。
【背景技術】
[0002]公交車到站時間預測是公交系統智能化和信息化的關鍵技術，受到了國內外研究人員的極大關注。但是由於種種客觀因素的影響，一直很難找到非常有效的方法來得到比較準確的預測結果。目前統計出影響預測準確性的因素有:(1)公交車輛的定位精度的影響。目前的車載GPS系統本身的定位精度是影響公交車到站時間的重要因素之一。(2)道路交通擁堵情況的影響。城市道路擁堵情況以及其它車輛與公交車的相互影響，使得公交車的行駛速度很難控制。(3)道路交叉口的信號燈的影響。(4)交通流量隨時間變化而變化的影響。如早晚尖峰時段、工作日和周末等流量都是不同的。(5)天氣變化的影響。如雨、雪、霧霾、沙塵等不可避免延緩車輛的到達時間。(6)上下客人流量的多少也會影響車輛在站臺的停留時間。
[0003]以上的這些不確定的影響因素很難找到一個數學公式來表達出來，是完全非線性的問題，目前這個問題被人們歸類為NP難題。在分析這個問題過程中，人們發現諸如交通流量、客流集散度等在不同星期的對應時間上具有高度的相似性，而天氣變化的影響力也具有某種程度的可估計性。而城市交通控制系統與公交系統是不相連的，公交系統無法得到交叉路口的交通信號燈的時間信息，信號燈的延誤是一種不確定的影響因素。由此可見，公交車到站時間的預測具有一定的規律性，並且受到多種隨機因素的影響，所以必須在充分利用歷史運行數據的基礎上採用先進的智能控制理論和方法來解決。目前的車輛到站時間預測方法主要有:歷史趨勢法、多元線性回歸法、時間序列分析、卡爾曼濾波法、神經網絡、隨機排隊機理論模型以及專家系統等。
[0004]基於歷史數據的到達時間預測模型是以大量公交行車歷史數據為基礎，假設交通模式具有循環變化的規律，在特定路段內歷史行駛時間與當前行駛時間是一致的。專利號200510110083提出了基於人工神經網絡結果的公交車到達時間預測模型，以到達時間、站點滯留時間以及公交時刻表時間差為輸入，由最小預測誤差確定隱含層權重和參數的最優解，由預測結果選擇、訓練網絡來確定最佳的訓練函數。人工神經網絡模型具有解決複雜非線性問題的能力，但是在實際應用中卻需要利用經驗嘗試選擇較優的訓練函數、學習函數以及一些參數達到一定的預測精度，同時很難實現實時在線的訓練和動態預測。專利號200910199431.4提出了一種公交車到站時間預測模型控制方法，採用BP神經網絡對歷史數據進行訓練，然後引入公交車的動態運行信息來修正BP神經網絡方法得到的平均行程時間。專利號201310099912.4提出了用於公交系統的自適應調度方法，根據統計的歷史行車時間採用遺傳算法預測路線行車時間。專利號201210256952.3提出了一種基於最大熵理論的公交車到站時間實時預測系統和方法，但是該方法缺少基於歷史數據的經驗，很難處理公交運行過程中的不確定的隨機因素的影響，該方法的實時性和自適應性較差。[0005]模擬退火算法(SA)是一種優秀的優化算法,首先是由Metropolis等於20世紀50年代初提出的，它是依據固體退火原理而發展起來的。其基本原理是:首先讓固體溫度升高至充分高，然後再讓其徐徐冷卻，溫度升高時，固體內部粒子變為紊亂無序，內能增大，而固體內部的粒子慢慢冷卻時逐漸趨向有序，在確定的每個溫度其狀態都可以達到平衡；最後在常溫時變得穩定，即達到基態，內能降到最低。依據退火準則，當粒子在溫度t時，其趨於平衡的概率為exp (-AJt)，其中J為溫度為t時刻的內能，AJ為其內能的改變量。Kirkpatrick等人於1983年將SA應用到組合優化問題當中，將內能E映射為目標函數值，溫度t映射成控制參數，從而得到解組合優化問題的SA:由初始解i以及控制參數初值t開始，對待求解進行「產生一個新解一〉計算目標函數差一〉捨棄或者接受」的迭代，並不斷衰減t的值，算法終止時所得到的解即為所得最優或近似最優解，它是一種啟發式迭代優化搜索算法和模式識別算法。
【發明內容】
[0006]本發明的目的是為了克服現有的公交車實時到站時間預測不準的問題，提供一種基於模擬退火算法的公交實時到站時間預測方法。
[0007]為了實現上述的發明目的，本發明採用下述的技術方案:
[0008]一種基於模擬退火算法的公交實時到站時間預測方法，包含以下的順序步驟:
[0009]步驟1、基於歷史行車數據建立不同站點不同班次的公交車歷史運行時間的資料庫；
[0010]步驟2、採用模擬退火算法對歷史運行時間數據進行訓練，對數據進行聚類，形成一個基於時間段聚類的不同路段的平均行駛時間OD矩陣；
[0011]步驟3、利用被預測公交車的動態運行信息來修正由模擬退火算法預測的平均行駛時間OD矩陣，得到該公交車的最佳平均行駛時間；
[0012]所述步驟2中，採用模擬退火算法對歷史運行時間數據進行訓練，對數據進行聚類，形成一個基於時間段聚類的公交站臺間的平均行駛時間OD矩陣，包括如下順序步驟:
[0013]步驟2.1、以歐式距離作為相似度測度建立最優數學模型，適應性函數選取誤差平
方和作為目標函數
【權利要求】
1.一種基於模擬退火算法的公交實時到站時間預測方法，其特徵在於，包含以下的順序步驟: 步驟1、基於歷史行車數據建立不同站點不同班次的公交車歷史運行時間的資料庫；步驟2、採用模擬退火算法對歷史運行時間數據進行訓練，對數據進行聚類，形成一個基於時間段聚類的不同路段的平均行駛時間OD矩陣； 步驟3、利用被預測公交車的動態運行信息來修正由模擬退火算法預測的平均行駛時間OD矩陣，得到該公交車的最佳平均行駛時間； 所述步驟2中，採用模擬退火算法對歷史運行時間數據進行訓練，對數據進行聚類，形成一個基於時間段聚類的公交站臺間的平均行駛時間OD矩陣，包括如下順序步驟: 步驟2.1、以歐式距離作為相似度測度建立最優數學模型，適應性函數選取誤差平方和作為目標函數
2.如權利要求1所述的基於模擬退火算法的公交實時到站時間預測方法，其特徵在於:所述步驟I中的基於歷史行車數據建立不同站點不同班次的公交車歷史運行時間的資料庫，包括如下順序步驟: 步驟1.1、收集公交車運行過程中的歷史數據，所述公交車運行過程中的歷史數據為同一線路上不同發班時間的公交車運行的經度、緯度、時間、速度； 步驟1.2、基於上述信息計算出不同站點之間、不同發班時間的公交車運行時間，形成歷史運行時間的資料庫。
3.如權利要求1所述的基於模擬退火算法的公交實時到站時間預測方法，其特徵在於:所述步驟3中，利用公交車的動態運行信息來修正由模擬退火算法預測的平均行駛時間OD矩陣，得到公交車的最佳平均行駛時間，包括如下順序步驟: 步驟3.1、公交行車數據處理中心系統模塊獲取當前公交車的行車實時數據，確定當前該車的實際路段位置，通過平均行駛時間OD矩陣獲得該車到達預測站臺的一般行駛時間T0; 步驟3.2、公交行車數據處理中心系統模塊判斷車輛的實時速度是否低於5公裡/小時，如果實時速度低於5公裡/小時且持續時長超過I分鐘，公交行車數據處理中心系統模塊直接發送「路段擁堵，公交車到達將延後」的信息給公交站臺信息顯示模塊，公交站臺信息顯示模塊對其進行顯示，並執行步驟3.3 ;若實時速度不低於5公裡/小時，則返回步驟3.1 ； 步驟3.3、公交行車數據處理中心系統模塊獲取剛經過預測站臺的一輛公交車的相同路段的行車實時行車時間T1 ； 步驟3.4、公交行車數據處理中心系統模塊通過計算時間T1和Ttl的平均值(Tc^T1) 2作為該車到達預測站臺最佳行駛時間Tbest,並將該最佳行駛時間Tbest發送給公交站臺信息顯示模塊，公交站臺信息顯示模塊對其進行顯示； 步驟3.5、車輛到站後，公交行車數據處理中心系統模塊判斷車輛是否出站，若為是，執行步驟3.1 ;若為否，公交站臺信息顯示模塊顯示「車輛到站」信息。
4.如權利要求3所述的基於模擬退火算法的公交實時到站時間預測方法，其特徵在於:所述的公交行車數據處理中心系統模塊獲取當前公交車的行車實時數據的周期為10~15秒。
5.如權利要求3所述的基於模擬退火算法的公交實時到站時間預測方法，其特徵在於:所述的公交行車數據處理中心系統模塊把計算得到的車輛到站時間預測值發送給公交站臺信息顯示模塊的時間周期是30~60秒。
6.如權利要求3所述的基於模擬退火算法的公交實時到站時間預測方法，其特徵在於:所述的同一路同一方向的車輛到站時間預測值只發送距離最近的一次發送給公交站臺信息顯示模塊的時間周期是30~`60秒。
【文檔編號】G06F19/00GK103678917SQ201310685431
【公開日】2014年3月26日 申請日期:2013年12月13日 優先權日:2013年12月13日
【發明者】許志興, 陳冠雄, 肖華, 吳鑫梁, 姜明富, 周少鏵 申請人:杭州易和網絡有限公司