研究疏散問題下估算最小路網清空時間

The Study on Estimating the Minimum Network Clearance Time for Evacuation Problems

陳香吟(Hsiang-Yin Chen)

指導教授 ： 許聿廷

國立臺灣大學/工學院/土木工程學研究所/碩士(2017年)

https://doi.org/10.6342/NTU201703558

摘要

路網清空時間定義為在疏散作業下清空路網的時間；也可以解釋為最後一個人/車離開路網疏散到安全地區的時間點。當災難發生時，短時間內將有大量的疏散需求於路網中產生，最小路網清空時間即是一個常見的目標式用來求解疏散問題。然而，在過去文獻中，對於路網疏散問題的解析方法多針對最小化系統總疏散時間(系統總人/車) 與最大化疏散流量的目標式建立數學模式；相對而言，對於最小化路網清空時間則缺乏一個明確的目標式以藉由解析方法進行求解。對於最小路網清空時間問題，過去文獻大多透過加入虛擬起點(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.

並列關鍵字

network evacuation problem ； clearance time ； dynamic programming ； multiple-origin multiple-destination

參考文獻

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.

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.