引用

Chowdhury N K, Leung C K S. Improved travel time prediction algorithms for intelligent transportation systems[C]//International Conference on Knowledge-Based and Intelligent Information and Engineering Systems. Springer, Berlin, Heidelberg, 2011: 355-365.

摘要

出行時間預測為通勤者提供有用的信息，使他們能夠決定是否對他們的路線或出發(fā)時間進行必要的更改。這解釋了為什么旅行時間預測對于智能系統(tǒng)，尤其是智慧交通系統(tǒng)(ITS)變得重要。在過去的幾年中，已經(jīng)開發(fā)了幾種算法來預測出行時間，但是其中一些存在一些問題。在本文中，我們提出了解決這些問題并提高 ITS 出行時間預測性能和/或準確性的算法。

介紹

由于出行時間預測對于許多智能交通系統(tǒng)(ITS)應用(例如動態(tài)路線導航和行程計劃)至關重要，因此它在 ITS 中起著關鍵作用。隨著高級出行者信息系統(tǒng)的發(fā)展，出行時間預測已變得越來越重要可以幫助通勤者更好地調(diào)整他們的出行時間表。此外，對于許多動態(tài)路線導航系統(tǒng)而言，準確可靠的道路行駛時間預測也至關重要，因為這種預測有助于通勤者確定他們是否需要更改路線的起始時間甚至取消行程。此外，準確的行進時間預測可以在起點和目的地之間生成最快的路徑(參見最短的路徑)。由于交通流量的時變特征(例如區(qū)分高峰時段交通與非高峰時段交通的每日特征)會影響準確出行時間的估計，因此如何提供可靠的出行時間信息已引起許多研究人員的關注。

在本文中，我們的主要貢獻是提出了幾種旅行時間預測算法，它們可以進一步提高現(xiàn)有算法的準確性和/或性能。具體來說，我們提出了快速準確的算法來改善 ITS 的出行時間預測。

我們改進的出行時間算法

在本節(jié)中，我們研究了 SMA，CA 和 MKC 算法，并發(fā)現(xiàn)了它們相關的問題。 然后，我們提出了解決這些問題并進一步提高行程時間預測的準確性和/或性能的幾種算法。

改進的連續(xù)移動平均(iSMA)和改進的鏈平均(iCA)算法

SMA 和 CA 都存在以下問題：

問題 1. SMA 或 CA 所需的空間量與歷史出行次數(shù)成指數(shù)關系。給定 n 個歷史出行時間，SMA 和 CA 需要構(gòu)造一個 n×n 矩陣(或更準確地說，是一個 n×n 上三角矩陣，其中 n(n + 1)/2 個非空條目)。

改進的 k 均值聚類(iMKC)算法

問題 4.差異度量未應用于規(guī)范化的三維空間。取而代之的是，它對三個維度中每個維度的兩個歷史數(shù)據(jù) ti 和 tj 之和求和。不幸的是，每個維度使用了不同的單位(例如，以分鐘為單位測量出行時間的差異，以 km / h 為單位測量速度的差異)。

問題 5.在相異性度量中使用的三個維度(即旅行時間和速度)中的兩個是相關的。對于給定的路段(即具有固定距離)，行駛時間與其速度成反比，因為行駛時間 × 速度=道路段的距離。因此，保持兩個維度變得多余。

解決方案：為了解決問題 4 和 5，我們提出了第三種算法。 觀察與 MKC 中使用的不相似度度量相關的問題，我們提出的改進的改進 k 均值聚類(iMKC)算法使用了一個不同但更合適的不相似度度量。具體來說，我們的 iMKC 僅基于兩個唯一行駛時間 ti 和 tj 之間的差來測量差異：

通過這樣做，我們的 iMKC 可以解決問題 4 和 5，因為它避免了測量兩個相關的維度，并且不對以不同單位度量的差異求和。而且，它將聚類空間的維數(shù)從三個減少到一個。實驗結(jié)果表明，我們的 iMKC 導致比 MKC 更為準確的預測。

增強方法一：盡管我們的 iMKC 解決了問題 4 和 5，但可以進一步增強它。 例如，細心的讀者可能會注意到，相異性度量僅度量了行進時間的成對差異。 但是，在給定路段 S 和時間段 T 的情況下，在 n 個歷史行駛時間的集合中重復行駛時間并不罕見。 我們更好地記錄了這些出行時間的頻率。 因此，我們對 iMKC 的第一個增強就是捕獲此頻率信息。代替增加維度并陷入以不同單位計量的數(shù)量之和的潛在問題，我們通過相應的頻率 fi 和 fj 加權(quán)傳播時間 ti＆tj：

增強方法二：第一個增強功能側(cè)重于差異度度量，而第二個增強功能側(cè)重于聚類技術。由于 k-medoid 聚類通常比 k-means 聚類對噪聲和離群值更魯棒，因此我們對 iMKC 的第二個增強是使用 k-medoid 聚類。k 均值聚類和 k 質(zhì)形聚類之間的主要區(qū)別在于，前者的聚類以質(zhì)心表示(即，一個聚類中所有數(shù)據(jù)的中心)，而后者的聚類以質(zhì)體表示(即位于最中心的數(shù)據(jù)每個群集)。由于 iMKC 使用迭代優(yōu)化進行聚類，因此需要kn個比較才能在每次迭代中將 n 個旅行時間分配給 k 個聚類。盡管可能需要進行 n 個額外的比較才能找到 k 個質(zhì)心，但很常見的是 k 個質(zhì)心保持不變，而 k 個質(zhì)心從一次迭代更改為另一個。因此，作為獎勵，使用 k-medoid 可以減少迭代次數(shù)。實驗結(jié)果表明，使用 k-medoid 聚類的這種增強的 iMKC 比使用 k-means 聚類的 iMKC 提供了更準確的預測出行時間(并且更有效)。

總結(jié)

在本文中，我們分析了三種現(xiàn)有算法(即 CA，SMA，MKC)，并揭示了它們的問題，并提出了五種算法(即 iCA，iSMA，iMKC 及其兩個增強功能)作為解決這些問題并為 ITS 提升出行時間預測。 我們提出的 iCA 和 iSMA 算法使用非遞歸方程式直接計算預測的出行時間。它們通過減少時間和空間要求，同時維持預測的準確性，改善了出行時間的預測過程。我們的 iMKC 算法降低了聚類空間的維數(shù)，并在一個旅行時間維中測量了不相似性。它提高了預測的準確性和性能。 兩項增強功能通過捕獲差異度量中的行進時間頻率和/或使用 k-medoid 聚類進一步改善了 iMKC。實驗結(jié)果表明，我們提出的所有五種算法均改善了 ITS 的行程時間預測。

致謝

本文由南京大學軟件學院2020級碩士郭安翻譯轉(zhuǎn)述

本論文轉(zhuǎn)述項目受到國家自然科學基金重點項目(項目號：61932012，61832009)支持。

總結(jié)

以上是生活随笔為你收集整理的#时间预测算法_改进的智慧交通系统出行时间预测算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。