臺灣博碩士論文加值系統

路網清空時間定義為在疏散作業下清空路網的時間；也可以解釋為最後一個人/車離開路網疏散到安全地區的時間點。當災難發生時，短時間內將有大量的疏散需求於路網中產生，最小路網清空時間即是一個常見的目標式用來求解疏散問題。然而，在過去文獻中，對於路網疏散問題的解析方法多針對最小化系統總疏散時間(系統總人/車) 與最大化疏散流量的目標式建立數學模式；相對而言，對於最小化路網清空時間則缺乏一個明確的目標式以藉由解析方法進行求解。對於最小路網清空時間問題，過去文獻大多透過加入虛擬起點(super source)與虛擬訖點(super sink)以將多起點多訖點路網轉換為單一起訖點路網，以簡化數學表示方式。然而加入虛擬起點將導致路網中疏散需求產生的分布狀況無法被真實地反映，若要確實地在多起點多迄點的路網疏散問題中求解最小路網清空時間時有其相當的複雜度和挑戰性。
動態規劃即是一種處理複雜問題的最佳化求解方法，係將原本較複雜的問題分解為一系列相互關聯的子問題，再利用子問題的最佳解進一步推求原問題的最佳解。因此，本研究透過動態規劃方法提出一數學模式以估算多起點多迄點路網疏散問題下的最小路網清空時間。在動態規劃求解的架構下，本研究並發展了計算路網清空時間、車流指派與更新路網中依時性剩餘容量的啟發式演算法，此演算法可協助判定每個子問題路網中依時性的瓶頸點，亦即疏散路網中的壅塞點。本研究以經典的 Sioux Falls 路網進行實驗分析，驗證所提出的方法是有效且可行；在每個子問題中，依路網依時性剩餘容量有效率地使用路網容量並求得該子問題最小網絡清空時間，並以每一子問題中所指派車流對路網容量的耗用，依序更新路網車流和剩餘容量，及至求得完整路網中的最小路網清空時間車流分布。

Network clearance time is the time required to clear a network under evacuation; it can be interpreted as the time for the last person (vehicle) to leave the network for a place of safety as well. The minimization of network clearance time is a commonly used objective in evacuation problems, as it is critical when the surge of demand in a short period overwhelms the existing network capacity. However, in previous studies on evacuation problems, the minimization of network clearance time lacks explicit mathematical formulation in contrast to other objectives, such as the minimization of total evacuation time (the system optimal flow) and maximization of the throughput (the earliest arrival flow); thereby, it cannot be analytically solved. Compared with the problem for a single-origin single-destination network, the problem for a multiple-origin multiple-destination network problem is more complex but reflects actual evacuation situations. To address this problem and attain scalable mathematical formulation, most of the previous studies added a super source and a super sink to transform it into an s-t (single-origin single destination) network. However, adding a super sink may affect the original demand pattern. Hence, this study proposes a dynamic programming approach to estimate the minimum network clearance time and determine evacuation assignment in a multiple-origin multiple-destination evacuation network, which decomposes a complex problem into a sequence of inter-related sub-problems with a super sink only. In addition, a heuristic algorithm of calculating network clearance time, assignment and time-dependent residual capacity is developed, which can identify time-dependent bottlenecks in each sub-problem. To verify the proposed approach is valid and feasible, a well-known Sioux Falls Network is used for a case study for the proposed optimization model. The minimum network clearance time for each sub-problem results from the flow assignment to best use the residual capacity of the network, which collectively determines the minimum network clearance time and the associated traffic flow pattern for the entire network.

口試委員審定書 i
誌謝 ii
摘要 iii
ABSTRACT iv
TABLE OF CONTENT v
LIST OF FIGURES vii
LIST OF TABLES viii
CHAPTER 1 INTRODUCTION 1
1.1 Background 1
1.2 Research Objectives 4
1.3 Thesis Organization 5
CHAPTER 2 LITERATURE REVIEW 7
2.1 Traffic Assignment for Network Evacuation 7
2.2 Objectives of Network Evacuation Problem 9
2.3 Clearance Time Estimation 11
2.4 Summary of Literature Review 12
CHAPTER 3 METHODOLOGY 14
3.1 Dynamic Programming Approach 14
3.2 Problem Statement 16
3.3 Model Formulation for the Network Clearance Time 17
3.3.1 Network Representation and Notation 17
3.3.2 Illustration of the Important Process 20
3.3.3 Mathematical Model Formulation 27
3.3.4 Solution Algorithm 32
CHAPTER 4 NUMERICAL EXPERIMENT 36
4.1 Case Validation 36
4.2 The Sioux Falls Network 41
4.2.1 Data Input 41
4.2.2 Results of the Sub-problem 42
4.2.3 Results Analysis 50
CHAPTER 5 CONCLUSIONS AND FUTURE WORK 55
5.1 Conclusions 55
5.2 Future Research 58
REFERENCES 61
APPENDIX 64

Baumann, N. and Skutella, M. (2009). “Earliest arrival flows with multiple sources.” Mathematics of Operations Research, 34(2), 499-512.
Bertsekas, D. P. (2010). “Dynamic programming and optimal control.” Belmont, Mass.: Athena Scientific, 2nd ed.
Center for Research on the Epidemiology of Disasters (CRED). The International Disaster Database http://www.emdat.be/ accessed in November 2016.
Chiu. Y. C., Zheng. H., Villalobos. J., and Gautam. B. (2007). “Modeling no-notice mass evacuation using a dynamic traffic flow optimization model.” IIE Transactions, 39(1), 83-94.
Daganzo, C.F. (1995). “The cell transmission model, part II: Network traffic.” Transportation Research Part B, 29 (2), 79-93.
Hobeika, A. G. and Kim, C. (1998). “Comparison of traffic assignments in evacuation modeling.” IEEE Transactions on Engineering Management, 45(2), 192-198.
Hsu, Y. T. and Peeta, S. (2015). “Clearance time estimation for incorporating evacuation risk in routing strategies for evacuation operations.” Networks and Spatial Economics, 15(3), 743-764.
Hsu, Y. T. (2013). “A generalized operational framework for mass evacuation integrating demand, supply, and disaster characteristics.” Doctoral dissertation, Purdue University.
Jarvis, J. J. and Ratliff, H.D. (1982). “Some Equivalent Objectives for Dynamic Network Flow Problems.” Management Science, 28(1), 106-109.
Liu, Y., Lai, X. and Chang, G.L. (2006). “Cell-Based Network Optimization Model for Staged Evacuation Planning Under Emergencies.” Transportation Research Record, 1964, 127-135.
Mawson, A. R. (2005). “Understanding Mass Panic and Other Collective Responses to Threat and Disaster.” Psychiatry, 68(2), 95–113.
Miller-Hooks, E. and Patterson, S. S. (2004). “On solving quickest time problems in time-dependent, dynamic networks.” Journal of Mathematical Modelling and Algorithms, 3(1), 39-71.
Momoh, J. A. (2008). Electric Power System Applications of Optimization, Second Edition. Marcel Dekker, New York.
Megiddo, N. (1974). “Optimal flows in networks with multiple sources and sinks.” Mathematics Programming, 7, 97-107.
Peeta, S., Sharma, S., and Hsu, Y. T. (2011). “Dynamic real-time routing for evacuation response planning and execution.” Purdue University Press, West Lafayette.
So, S.K. and Daganzo, C.F. (2009). “Managing evacuation routes.” Transportation Research Part B, 44 (4), 514-520.
Stern, E. (1989). “Evacuation intentions of parents in an urban radiological emergency.” Urban Studies, 26(2), 191-198.
Hu, T. Y., and Wu, Y. H. (2015). “An Integrated Traffic Corridor Control Model for Emergency Evacuation.” In Transportation Research Board 94th Annual Meeting (No. 15-2575).
Huang, H. H., Hsu, Y. T., and Miralinaghi, M. (2017). “A Location Problem of Two-Level Disaster Relief Facilities for Vulnerable Networks.” In Transportation Research Board 96th Annual Meeting (No. 17-06756).
Xie, C., Lin, D.Y. and Travis Waller., S. (2010). “A dynamic evacuation network optimization problem with lane reversal and crossing elimination strategies.” Transportation Research Part E, 46(3) 295–316.
Zhang. H. and Haghani. A. (2016). “A two-stage optimization framework for optimizing large-scale vehicular evacuation routing and scheduling operation with uninterrupted traffic flow.” International Journal of Transportation, 4(2), 47-68.
劉佳欣。(2007)。"消耗性救災物資需求預測"，碩士論文，國立交通大學交通運輸研究所。
宋明安。(2005)。"緊急救災物流輸配送系統模式構建"，碩士論文，國立交通大學交通運輸研究所。