應用重力式互動性馬可夫鏈求解路網之隨機均衡

Abstract

重力式互動性馬可夫鏈(Gravity-type interactive Markov chain：GIM) 乃由Smith and Hsieh在1994年所提出，在此GIM模式中，系統在每一時段 中流量的改變分別受到引力(如人口)及斥力(如遷移成本)函數的影響。而 以理論分析的觀點而言，個體在GIM模式中的選擇行為與以羅吉特模式為 基 礎的隨機交通量指派問題類似，即GIM模式經適度轉換後，恰與羅吉 特模 式之隨機均衡指派的問題相符合，因此若運用此模式求解隨機交 通量指派 問題上，似乎恰可描述其自我調整至均衡狀態的動態過程。 本研究嘗試應用GIM模式建立路網均衡指派問題的重力式互動性馬可夫模 式，其研究目的如下：(1) 證明重力式互動性馬可夫鏈的穩定狀態( Steady state)條件會等同於該路網的隨機均衡解(SUE)的條件；(2)發展 一新的演算法，可藉以求解路網之隨機均衡解(SUE)；(3)比較GIM演算法 法與其他現 有演算法，如MSA法及Frank-Wolfe法；(4)分析GIM演算法 收斂至SUE 之過程。 本研究以Mathmatica作為計算工具，針對不同演算法運算，由例題的測試 結果得知，系統調整比例(值對路網的收斂與否及收斂速度有極大的影響 ； 而以GIM演算法求解具overlapping路網之問題，在路網中路徑重覆路 段 情形不嚴重的情形下，仍可求解路網之隨機均衡。 The Gravity-type Interactive Markov models(GIM models) were introduced by Smith and Hsieh in 1994,in which migration flows in each time period are postulated to vary directly with some population-dependent measure of attractiveness and inversely with some symmetric measure of migration costs. From the viewpoint of theoretical analysis, the choice behavior of individuals inGIM models is similar to that of drivers in selecting routes in logit-based stochastic traffic assignment problems. This study is trying to formulate the GIM model of the stochastic traffic assignment in a road network. The followings will be the goal of this study: (1). Prove that the steady-state conditions of the GIM model is equivalent to the stochastic user equilibrium (SUE) conditions of the problems.(2).Develop a new algorithm for solving the SUE of the problems.(3).Compare the GIM algorithm with exiting algorithm, e.g. Frank-Wolfe method, MSA.(4).Analyze the convergence to the SUE of the GIM algorithm. This method has implemented by Mathmatica. The computation of different algorithms on different examples shows that the adjustment ratio have a great influence on the speed of convergence. And the level of overlapping in the network is slight, we can solve the stochastic user equilibrium problems that haveoverlapping links in the network by GIM algorithm.