雙層規劃Stackelberg Game模型在交通路網中之應用

The application of Bi-level Programming Stackelberg Game in Transportation Network

劉文豪(Wen-Hao Liu)

指導教授 ： 卓訓榮

國立交通大學/管理學院/科技管理研究所/碩士(2010年)

https://doi.org/10.6842/NCTU.2010.00015

摘要

本文回顧靜態路網指派模式(Static Traffic Assignment Model)的發展，自Wardrop提出旅行者行為假設後，所發展出來一系列靜態路網指派之數學模式；由Beckmann對成本函數做假設，所發展的數學模式(Mathematical Programming Problem，簡稱MPP)，經Aashitiani放鬆Beckmann成本函數之假設後所提出之非線性互補問題(Nonlinear Complementarity Problem，簡稱NCP)，和Smith、Dafermos所提出之變分不等式(Variational Inequality Problem，簡稱VIP)和Kuhn所提出不動點問題(Fixed Point Problem，簡稱FPP)。
首先，藉由前面理論發展為基礎，透過變分不等式條件方程式，構建為双層規劃等價模型。並討論在其交通路網中的應用，決策系統分成兩個層次:上層為系統最佳化問題，以系統總旅行成本最小為目標；下層為限制式，凿含用路人均衡路徑選擇限制式，使同時對同一時區出發之用路人均利用最短路徑到達目的地。
又依據Fisk(1984)認為系統最佳化與動態用路人選擇問題，屬於賽局理論之Stackelberg賽局。本研究針對Stackelberg賽局問題，其中局中人(相當於用路人)行為進行深入探討，並經過嚴謹的數學論証，更證實其所提出模型與用路人的均衡條件之間的等價性。因此，提出了一類符合常理的交通分配流組合決策模式，它是主從Stackelberg問題；我們可以透過變分不等式技巧將此問題轉化成MPEC問題，再透過MPEC的KKT架構，求解這個二層最適組合模式的最佳化條件。
最後，本研究將針對用路人行為的特性，建構成双層規劃Stakelberg賽局模型。再進一步研究如何結合變分不等式敏感度分析，應用於路網規劃和路網設計過程。並透過敏感度分析資訊，應用於二階層數學規劃問題的演算法求解程序中，期望能實際發展並求得模型最佳解的演算法。

關鍵字

Stackelberg問題 ,雙分不等式 ,交通指派

並列摘要

Under Wardrop’s first driver behavior principle, network user equilibrium assignment problem can be formulated as Mathematical Programming Problem (MPP), Nonlinear Complementarity Problem (NCP), Variational Inequality Problem (VIP), and Fixed Point Problem (FPP). Under certain conditions, in this research, we introduce the application of Bi-Level Stackelberg problems in transportation.
We want to deal our problems with variational inequality techniques, by transforming our problems into the MPEC (Mathematical Programming with Equalibrium Constraints) Problems.
Key Words: Traffic assignment, Stackelberg problem, variational Inequality, Bi-Level programming, MPEC problem.

並列關鍵字

Stackelberg problem ,Variational Inequality,Traffic assignment

參考文獻

[1] Stackelberg H.V.,Marktform und Gleichgewicht, Berlin: J. Springer, 1934

[2] Wardrop J.G.,“Some theoretical Aspects of Road Traffic Research,” Proceeding of Institute of Civil Engineers,PartⅡ,pp.325-378,1952.

[5] Dafermos S. C., “The Traffic Assignment Problem for Multiclass-user Transportation Network,”Transportation Science,Vol.6,pp.73-87,1972.

[6] Ashtiani H. Z., The Multi-modla Traffic Assignment Problem, Ph.D. Dissertation,M.I.T.,1979.

[7] Smith M.J.,”The Existence, Uniqueness and stability of Traffic Equilibria,”Transportation Research B,Vol. 13,pp.295-304,1979.