| 摘要: | 重大天然災害的發生，例如颱風及地震，其將造成人民生命財產的重大損失，更會摧毀原有的交通以及維生系統，使得災後緊急救援的設備與物資無法於第一時間進入災區。因此如何在最短時間內將受損道路搶通，便是緊急救援最重要的一步。以往曾有學者針對災後搶修問題進行相關研究與探討，然其並未考量搶修工作隊需求物料補給的部分。若搶修工作隊之物料需求無法及時滿足，將造成搶修的延遲，使得整體搶修排程大亂，進而影響整體救災的效率，並造成傷亡的增加。 緣此，本研究利用時空網路流動的技巧，構建一物料補給之排程模式，在總補給成本最小化的目標下，配合緊急搶修工程的進行，以及相關的通行限制，發展一套模式，在有限的時間內求解出最佳補給路線及時程安排。在模式構建上，則以整數流動的方式定式補給車輛與需求物料於時空中的排程，並依據實務上的條件，加以限制各網路中車輛與物料的流動關係。本模式定式為一混合整數多重貨物網路流動問題，屬於NP-hard 問題。本研究於範例測試中，首先以類似921集集大地震規模之災害為例進行測試，為了驗證本模式能應用於實務上更大型之網路問題，故本研究以921集集大地震之路網資料為背景，產生一組大型網路作為測試範例，並發展一套啟發解法以有效率求解大規模問題。最後利用個人電腦，測試模式及求解演算法之績效，經測試與結果分析發現結果甚佳，顯示本研究所構建之物料補給排成模式與求解方法應可為未來道路搶修工程單位之參考。 Natural disasters, such as earthquakes and typhoons, are inevitable and inflict devastating effects, in terms of human injuries and property damage. These damages can disrupt the traffic and lifeline systems, obstructing the operation of rescue machines, rescue vehicles, ambulances and relief workers. Most of the emergency repair models in the past were formulated neglecting logistical support. In practice, to reduce the risk of repair work and the length of repair time, work teams do not return to their work stations. Rescue machinery, fuel and other resources are supplied to the work teams by support units. If the demand of repair work teams is not supplied in time, the schedule of repair work would be delayed, which will not only affect the rescue efficiency but can also increase human injuries. Hence, in this research we will employ network flow techniques to construct a logistical support scheduling model. We consider minimizing the total cost for logistical support, as well as the time windows based on the emergency repair schedule and related operating constraints, to develop a model for planning logistical support schedules within a limited time. In the modeling a time-space network for logistical support and each material are constructed. A number of operational constraints between these networks according to real constraints are set. Our model is formulated as a mixed-integer, multiple-commodity network flow problem that is characterized as NP-hard. To efficiently solve realistically large problems occurring in practice, we develop a heuristic. Then, to evaluate the model and the solution algorithm, we perform a case study on personal computers, using real data of the 1999 Chi-chi earthquake in Taiwan. The preliminary results are good, showing that the model could be useful for the logistical support scheduling. |
