應用機率型動態規劃構建動態路徑導引之研究

A Study of Dynamic Route Guidance with Application of Probabilistic Dynamic Programming

彭柏凱(Po-Kai Peng)

指導教授 ： 蕫啟崇

淡江大學/管理學院/運輸管理學系碩士班/碩士(2007年)

https://doi.org/10.6846/TKU.2007.00390

摘要

近年來ITS的發展與應用可提供旅行者路徑導引之功能，主要目標在提供用路人適當的即時資訊，導引用路人避開壅塞路段以縮短旅行時間，經由相關文獻回顧得知路徑導引策略可透過不同準則進行路徑導引規劃，其中大部份是以最短路徑或最短旅行時間方式從交通管理者觀點規劃用路人之導引路徑，卻忽略用路者之決策行為因素。近來姜禹辰已成功示範了結合以馬可夫鏈構建用路人路徑變換行為之動態規畫模式，本研究續其成果，但以不同方式構建並分析機率型動態規劃適合應用在包含駕駛者路徑選擇行為之動態路徑導引。
本研究動態導引過程中考慮了用路人的途中路徑選擇行為，定義為逐點動態決策行為，利用變換機率構建代表逐點動態決策行為可能出象，構建結合路徑變換機率之動態規劃問題，以求解用路人最佳期望動態路徑導引。本研究探討資訊影響下途中逐點動態決策行為，包括駕駛者透過車外VMS或車內導航系統所提供的路徑導引資訊所形成之連續地(動態)路徑決策(變換)行為，並利用無異帶的觀念構建逐點動態決策行為。
本研究採用歷史O-D資料利用DynaTAIWAN進行整體路網模擬，再選取兩地區(台北、台中)樣本透過特殊設計之問卷觀察與蒐集駕駛者連續行程之逐點動態行為記錄並校估參數構建路徑變換模式，且校估台北地區車外系統(個人化、一般化)、台北地區車內系統、台中地區車外系統(個人化、一般化)、台中地區車內系統等模式，如此可利用其模式結果進行計算個別駕駛者路徑在接受行程即時交通資訊下之變換機率。
本研究並將研究路網範圍中所有可行之路徑，以擴展樹的概念定義階段及狀態構成多階段之動態規劃路網，每個階段的成本函數將駕駛者在每一個決策點行為機率以及對應節省時間乘積之加權後的成本函數，最後利用動態規劃之逆溯遞迴(backward recursion)方式進行計算求解駕駛者以行為機率為加權的即時動態期望最短路徑。
本研究成功的利用駕駛者逐點動態變換行為機率，結合動態規劃方式求算駕駛者最佳期望路徑為動態導引之基礎，經由兩地區(台北、台中)兩資訊系統(車內、車外)分別求解出2條期望動態導引路徑，有別於傳統方式求解之單一最短路徑。此結果可提示針對不同族群的人會有不同建議路徑的產生，亦即分眾式導引的效果。

關鍵字

逐點動態路徑選擇行為模式 ； 路徑導引 ； 動態規劃

並列摘要

Dynamic programming (DP) determines the optimum solution to an n-variable problem by decomposing it into n stages with each stage constituting a single variable problem. This technique can be easily constructed to solve a shortest-path problem. If stochastic nature of problem is concerned, probabilistic dynamic programming can be applied in that the states and the returns at each stage are probabilistic. In this thesis, a route guidance problem is solved as finding a dynamic shortest route in a time dependent probabilistic programming problem. Under this formulation, route choice probability is introduced at each consecutive decision node (stage of diversion). The series of choices over entire trip can be defined as node-to-node dynamic route choice behavior.
The node-to-node dynamic route choice behavior is of the most interest to study the individual driver’s route choices under the influence of the route guidance information where individual driver makes consecutive route switch decisions along with the traveling route. This particular issue has been successfully modeled with various forms and extensions under the notion of the “Indifference Bands” applied with Probit model specifications by Tong and his students at Tamkang University in recent years. The probability of “swithching” or “route choice” at each decision node along the route, reflecting the compliance outcome to the routing diversion via either in-vehicle devices or road side VMS, can therefore be estimated under these model specifications.
This thesis applies a newly developed network simulation program, DynaTAIWAN, for generation time dependent system performance indices over the selected study area (e.g., link travel time) with the embedded dynamic route assignment procedure. A complimented survey with rolling-plane feature was designed to perform controlled experiments where selected sample of travelers were selected to perform routing decision over trips for simulated scenarios under either In-Vehicle guidance or VMS environment.
Choice models were calibrated and probabilistic dynamic programming formulated accordingly. Expected optimum route was then solved for each individual sample traveler respectively. The results have demonstrated the possibility of various routing suggestions across individual driver departing at the same space-time slot, which suggested the development of the diversified dynamic route guidance based on the current modeling treatments and findings. The analysis of aggregate behavior over entire network can be encouraged in the future.

並列關鍵字

Dynamic Route Switch Model ； Route Guidance ； Dynamic Programming

參考文獻

6. 姜禹辰，「應用馬可夫鏈探討駕駛人在車內導引資訊下之逐點動態路徑選擇行為」，私立淡江大學運輸科學研究所碩士論文，民國94年6月。

7. 蘇秋如，「個人化路徑導引資訊：動態路徑選擇行為模式之應用」，私立淡江大學運輸科學研究所碩士論文，民國95年6月。

1. Chee-Chung Tong “A Study of Dynamic Departure Time and Route Choice Behavior of Urban Commuter.” Ph.D. dissertation, Department of Civil Engineering, The University of Texas at Austin, Austin, Texas,1990.

9. 張鈞萍，「發展緊急救援車輛之行車路徑導引系統與號誌優先通行控制邏輯之研究」，國立成功大學交通管理科學研究所碩士論文，民國91年6月。

12. Mammar S., Messmer A., Jensen P., Papageorgiou M., Haj-Salem H. and Jensen L.(1996)“Automatic control of Variable Message Signs in Aalborg”, Transportation Research Part C. Vol.4.No.3.pp.131-150