考量國道事件發生隨機性之緊急應變派遣模式

A dispatch model of emergency response teams by considering stochasticity of freeway incident occurrence

李弘亦(Hong-Yi Li)

指導教授 ： 許聿廷

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

https://doi.org/10.6342/NTU202002220

摘要

高速公路壅塞所造成的車輛延滯會降低高速公路的運作效率，進而衍生龐大的社會成本；而壅塞可分為重現性與非重現性，其中事件發生所造成的非重現性延滯約占總延滯的13%至30%。因此減少事件應變所花費的時間、提高整體應變效率，能夠改善高速公路的延滯狀況。現行臺灣高速公路的事件應變方式仍以人工指派相應事故班處理，但短時間內若有多起新的事件發生，這種靜態的指派方式便無法達到有效率的事件應變。近年也有研究提出了基於實時交通數據的動態事件應變模式，但其調度決策無法考量到後續可能發生的事件，僅能以當前之狀態最佳化應變決策。本研究提出一以多場站車輛途程問題為基礎之動態事件應變指派模型以及該模型之運作流程，目標為最小化整體事件之應變時間，同時將潛在事件發生的隨機性納入考量，使模型能得出更為穩健、有效率的決策。為了使應變模型的求解時間縮短至可於實務上應用，本研究建構了禁忌搜索演算法作為數學模型的求解方式，而測試之結果顯示該方法可以將求解時間縮短至40秒內。本研究以中華民國交通部高速公路局北區養護工程分局之轄區路網為案例，以應變模型所得出之結果與原先調度決策進行比較與分析。案例分析之結果顯示本研究所提出的事件應變模型之決策可對事件的應變效率產生不同程度的改善，尤其在高事件發生頻率之情境，其事件應變時間改善效益可達14%至42%。此外，於有無考量事件發生隨機性之測試中，模型在考量事件隨機性之條件下對總應變時間之改善可達約3.79%，但若過度考量隨機性反而會導致總應變時間增長，因此需設置合理的參數以確保所求得指派決策的可靠性。本研究之事件應變模型可協助高速公路交控中心於實際之事故班派遣上得出更有效率的指派決策，尤其是在短時間內有多起事件發生之情境下，對於現行之調度方式能有更大的改善幅度。

關鍵字

高速公路事件應變 ； 事件發生隨機性 ； 動態派遣模型 ； 車輛途程問題 ； 禁忌搜索演算法

並列摘要

Delay caused by freeway congestion can decrease the efficiency of freeway operation and induce considerable social costs. Among the two types of congestion, recurrent and non-recurrent congestion, the non-recurrent delay caused by the incident accounts for around 13% to 30% of the total freeway delay. Hence, shortening the time spent on incident response and improving response efficiency are critical for reducing the delay of the freeway. In current freeway incident response in Taiwan, response tasks are manually assigned to the corresponding emergency response team. However, if there are mutiple incidents occurring in a short period, such a static dispatch strategy may not be able to efficiently deal with each incident. In recent years, dynamic dispatch models for incident response based on real-time data have been proposed. However, the scheduling of response tasks derived from these dynamic models does not consider the incidents that may occur in the near future, and can only optimize the response decision according to the current information. By contrast, this study proposes a dynamic dispatch model of emergency response teams for freeway incidents based on the multi-depot vehicle routing problem and the online operation procedure of the proposed model. The major objective is to minimize the total incident response time while taking into account of the stochasticity potential incident occurrence so that the model can make more robust and efficient dispatch decisions. To shorten the solution time of the proposed model for the application in practice, this study constructs a tabu search algorithm as the solution method for the mathematical model. A test shows that this algorithm can decrease the solution time to around 40 seconds. This study uses the network of the jurisdiction of the Northern Region Branch Office, Freeway Bureau, MOTC as a case, and compares the strategies determined by the proposed model with the historical dispatch decisions. The results of the case study indicate that the proposed model can improve the efficiency of the incident response. Especially in the scenario where the frequency of incident occurrence is relatively high, the improvement can reache 14% to 42%. In addition, in the test of whether the stochasticity of incident occurrence is considered or not, the proposed model provides additional 3.79% improvement in terms of total response time when considering the stochasticity. However, over-emphasis on the stochasticity may lead to an increase in the total response time because of relatively conservative strategies. Hence, it is necessary to set reasonable values for the relevant parameters to ensure the reliability of the derived dispatch decisions. The proposed dispatch model for incident response can help the freeway traffic control center implement more efficient response task assignment in the practical dispatch of response teams. Particularly when there are multiple incidents occurring in a short period, the model can generate more significant improvement compared with the current dispatch method.

並列關鍵字

freeway incident response ； stochasticity of incident occurrence ； dynamic dispatch model ； vehicle routing problem ； tabu search algorithm

參考文獻

Bertsimas, D., Ng, Y. (2019). Robust and stochastic formulations for ambulance deployment and dispatch. European Journal of Operational Research, 279(2), 557-571.

Cordeau, J.-F., Maischberger, M. (2012). A parallel iterated tabu search heuristic for vehicle routing problems. Computers Operations Research, 39(9), 2033-2050.

Cordeau, J. F., Gendreau, M., Laporte, G. (1997). A tabu search heuristic for periodic and multi‐depot vehicle routing problems. Networks: An International Journal, 30(2), 105-119.

Garey, M. R., Johnson, D. S. (1979). Computers and intractability (Vol. 174): freeman San Francisco.

Ghiani, G., Guerriero, F., Laporte, G., Musmanno, R. (2003). Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies. European Journal of Operational Research, 151(1), 1-11.