一種狀況相依之交通時間最佳化研究

A State-dependent Traffic-time Optimization

劉昀昇(Yun-Sheng Liu)

指導教授 ： 游張松

國立臺灣大學/管理學院/商學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.01645

摘要

本研究提出狀況相依速度調節最佳化問題，是為一個體企圖藉由調整本身行動之速度以達到交通旅行最佳效用，例如最短旅行時間、最平順之駕駛過程…等。一個狀況相依速度調節最佳化問題包含三種特徵，狀況相依之非線性關係、非封閉之編碼區間、多目標規劃。如此的特徵，使得傳統之模型存在著高度的運算複雜度，是為高階次方成長。因此，本論文提出一種幾何方式的呈現模式，得以精準地詮釋狀況相依速度調節最佳化問題之內在行為，同時，並發現到具有群集形式的解集合空間。根據對於狀況相依速度調節最佳化問題的發現，本研究提出一種最佳化之模型與有效的演算法「快速搜尋演算法(FSA)」，得以針對狀況相依速度調節最佳化問題取得最佳解。最後，本研究更以實際之交通資料進行實驗，得出可行之最佳解作為實際案例。本研究之貢獻在於成功地解析狀況相依速度調節最佳化問題，可直接應用於既有之衛星導航系統，更可延伸至其他具有狀況相依性之應用領域。

關鍵字

狀況相依速度調節最佳化問題 ； 運輸管理 ； 物流 ； 最佳化 ； 演算方法

並列摘要

This thesis proposed a state-dependent velocity-scheduling (SDVS) problem which tries to optimize travel utilities, such as traffic-time, driving smoothness…etc, by altering the entity’s traveling velocity. The SDVS problem consists of three major physical characteristics: 1) A State-dependent problem, 2) Open-state configuration, 3) Multi-objective optimization. Such characteristics make formal model of SDVS problem to be computational complex, with a high-ordered complexity. Therefore, in this thesis, we propose geometrical representation for the SDVS problem. By adopting the geometrical representation, we discover the inner-state and inter-state behavior of SDVS problem. Based on the geometrical representation, we identify the solution cluster of SDVS problem. Hence, we propose an optimization model and an efficient algorithm (Fast-searching Algorithm, FSA) to solve SDVS problem. Finally, we use a real world data as experiment and get the optimized result as a real world case. The contribution of this thesis is successfully resolve the ambiguity of the SDVS problem as initiative, which can be adopted into GPS guiding system and extended to other state-dependent applications.

並列關鍵字

SDVS Problem ； Transportation ； Logistics ； Optimization ； Algorithm

參考文獻

[1] A. D. Febbraro, D. Giglio, N. Sacco. Urban Traffic Control Structure Based on Hybrid Petri Nets. 2004. IEEE Transactions on Intelligent Transporatation Systems, 5(4). pp. 224-237.

[2] B. J. Driessen, K. S. Kwok. 1998. A Multi-Objective Dynamic Programming Approach to Constrained Discrete-Time Optimal Control. Proceedings of the American Control Conference. pp. 2077-2083.

[3] C. S. Shih, W. S. Liu. 2002. State-Dependent Deadline Scheduling. Proceedings of the 23rd IEEE Real-time Systems Symposium.

[4] E. W. Dijkstra. 1959. A note on two problems in connexion with graphs. Numerische Mathematik, 1, S. pp. 269–271.

[5] G. Perakis, G. Roels. 2006. An Analytical Model for Traffic Delays and the Dynamic User Equilibrium Problem. Oper. Res. 54(6). pp. 1151-1171.