在無非退化性假設下以敏感性資訊求解二階路網設計問題

Abstract

均衡路網設計問題是就一路網考慮以擴建路段，增建新路段，或增加路網 容量，減少擁擠。此一問題的目標一般是求改變道路容量使整個路網擁擠 成本最小，或是求整個路網擁擠成本加新容量擴充成本最小。此一問題的 模化形式有離散（discrete）型與連續（continu- ous）型兩類，當擴建 之容量以可分離形式考慮時為離散型模式，否則為連續型模式。以往對於 此類問題的求解，對較大型之實際路網應用時，不論此兩類模式的任一種 ，大部份解法在計算上皆很耗時，且無法保證解的好壞。在求解均衡路網 設計問題時，必須考慮用路人對道路改變後的反應造成的路網流量重分配 ，亦即需假設路網流量形態為滿足使用者均衡之流量形態，以避免產生 Braess 矛盾現象，造成增建容量卻使得路網使用成本更高。Friesz 等人 在 1990 年提出了利用均衡路網流量的敏感性資訊，以求算獲得對連續型 最佳化模式的求解搜尋方向，藉以求解此問題。由於此方法在求解的過程 中，求解搜尋的方向有考慮到用路人對路網狀況改變時的反應，因此應為 一較佳的方法。在他們的例題測試中，在求解效率以及解的優劣上都有不 錯的結果。但如同本論文中所述，他們在尋找均衡路網流量的敏感性資訊 時，須有一非退化性的假設，而其所使用的方法並無法保證滿足此一假設 。為使此一解法更為完整，本文建議使用另兩種方法：廣義反矩陣法與最 短距離法，來求得均衡路網流量的敏感性資訊，並用於求解連續型均衡路 網設計問題。本文亦作例題的測試執行以說明此方法的可行性與結果。