高階馬可夫鏈在交通流上的應用

隨著社會經濟和交通事業的發展，交通擁擠的問題日漸受到重視。為了有效避免塞車，旅行時間的計算扮演著不可或缺的角色。針對此議題，我們運用高階的馬可夫鏈，預測路段每單位時間內的平均車速。馬可夫鏈已被廣泛應用於隨機過程的預測，藉由一段狀態的觀測，推測未來不同狀態的發生率。將馬可夫鏈運用於交通流，可以藉由資料的收集，推測長期的交通狀況。二階馬可夫鏈的轉移矩陣僅能描述一步的狀態變化率。然而，交通狀況的變化可能不僅僅只與前一期的狀態有關。為了更為精確地預測交通狀況，我們利用高階馬可夫鏈來表現其複雜的關係。本研究以真實的交通狀況為例，先將大量的交通數據經過分析，利用分析後的數據構造出高階馬可夫鏈的轉移張量，並求解張量特徵值問題。我們陳列不同階馬可夫鏈的數值結果，探討H/Z-特徵對在此問題的差異。此外，我們也比較不同階馬可夫鏈對於交通狀態的預測能力，最後預估其旅程時間

關鍵字

高階馬可夫鏈；非負張量； H-特徵對； Z-特徵對

並列摘要

With the development of social economy and transportation, the problem of traffic congestion is getting much more attention. In order to avoid traffic congestion, the calculation of travel time plays an important role. For this issue, we use the high-order Markov chain to predict the average flow rate of each road. Markov chain has been widely applied in the prediction of random processes. The occurrences of statuses are estimated via a sequence of observations. In the traffic flow, the long-term traffic condition can be estimated via a sequence of observations by applying the Markov chains. The one-step rate of state change can be described by the transfer matrix of the second-order Markov chain. However, changes in traffic conditions might be related to a few previous states. In order to more accurately predict the traffic condition, we use the high-order Markov chain to express the relationship between states. In this study, the real traffic data is used. First, we analyze the large quantity of traffic data. Then, the tensor of high-order Markov chain is formulated. Finally, we solve the tensor eigenvalue problem. We show the numerical results for the Markov chains of different orders and discuss the difference between H/Z-eigenpairs in this problem. In addition, we compare the accuracy between Markov chains of different orders and estimate the travel time.