變分不等式路網均衡指派模式對角化求解方法改良之研究

Abstract

對角化方法為求解變分不等式路網均衡指派模式的方法，過去曾有 Abdulaal 和 LeBlanc 提出流線法以及 Harker 的加速方法。在本研究中 ，我們發現 Harker 的方法幾乎無法產生任何的加速效果，而流線法所能 改善的效率亦相當地不穩定；因此本研究將針對這些方法提出二個改善的 策略。第一個策略將分別針對對角化方法外部循環與內部循環兩部份來改 善；在外部循環間我們以 PARTAN 方向搜尋的概念來改善 Harker 的方法 ，同時將改善 Frank-Wolfe 求解效率的方法應用在對角化方法的子問題 求解過程中，藉著同時對其外部循環與內部循環的加速，來提昇對角化方 法整體的求解效率。在第二個改善策略中，我們也將 PARTAN 方向搜尋的 概念，應用在流線法的求解過程之中，藉此更進一步提昇流線法的求解效 率。本研究所提的兩個改善策略，在測試結果中發現均有不錯的改善效果 ；同時我們亦將利用這些結果來探討以一般迭代演算法收斂條件為效率比 較基礎時，所可能造成的錯誤以及一些值得注意的問題。 Equilibrium network flow can be formulated as Varia- tional Inequality Problem (VIP) without symmetric assumption. Diagonalization method is one of the approaches to slove the equilibrium problem of the VIP model. Although the Diagonalization method is very easy to implement, the slow convergence of it's subproblem affects the performance of the method drastically. In the past, there are two strategies have been reported to improve it's computional efficiency on the origional approach : streamlined method and Harker's method. In this thesis, it is found that the performance of the streamlined method is very unstable and the use of Harker's accelerated step can't outperform the origional approach. As a result of these facts, we present two accelerated strategies on the former two strategies. The computional performance of all these strategies that mentioned above explored by numerical experiment.It is shown that the strategies we proposed can considerably reduce the algorithm's computional requirements. We also use these results to illustrate something that we should notice on the comparison basis of the computional performance for different algorithms.