| 摘要: | 重大天然災害的發生，將會造成人民生命財產的重大損失，更會摧毀原有的交通以及維生系統，使得災後緊急救援的設備與物資無法於第一時間進入災區。因此如何在最短時間內將受損道路搶通，便是緊急救援最重要的一步。實務上災後緊急救援除了搶修工作隊，還必須有補給工作隊支援搶修工作隊所需之物料。若物料無法及時供應搶修工作隊，將造成搶修的延遲，使得整體搶修排程大亂，進而影響整體救災的效率，而造成傷亡的增加。以往有針對災後搶修補給物料的問題進行研究，估算平均旅行時間以進行工作隊排程規劃。然而此作法卻忽略了實務上旅行時間的隨機性，若隨機性擾動過大時，則可能使原規劃結果失去優越性，亦即最佳化補給排程結果可能不為實際最佳排程。 緣此，本研究利用時空網路流動的技巧，在總運送成本最小化的目標下，考量實際營運時旅行時間之隨機變動狀況與實務上相關的營運限制，並配合緊急搶修工程排程計畫，發展一隨機旅行時間下物料後勤補給排程模式，之後，修正隨機性旅行時間為一固定平均旅行時間，發展一確定性災後物料補給作業排程模式，以期輔助當局有效地規劃物料補給排程。另外，本研究並發展一模擬評估方法，以評估實務排程、確定性與隨機性排程規劃的結果於實際營運環境中之績效優劣。此模式可定式為一含額外限制式之整數多重貨物網路流動問題，屬NP-hard問題，故為有效地求解實務大型問題，本研究利用問題分解策略及貪婪式演算法之觀念，並配合使用數學規劃軟體CPLEX，發展一啟發解法求解。最後，本研究以類似921大地震規模之災害為例，測試模式及求解演算法的績效，結果顯示本研究所發展之模式與啟發解法較實務作法為佳，可有效率地求解災後物料補給排程之規劃。 Natural disasters 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. In practice, not only the repair work teams rescue the disaster area, but also supply work teams support the logistic to the repair work teams. 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. Most of the logistical models in the past were formulated with the average travel times, meaning that stochastic disturbances arising from variations in vehicle travel times in actual operations were neglected. In the worst case scenario, where vehicle travel times fluctuate wildly during daily operations, the planned schedule could be disturbed enough to lose its optimality. Hence, we employ network flow techniques, with the objective of minimizing the total system cost, as well as the emergency repair schedule and related operating constraints, to construct a logistical support scheduling model under stochastic travel times. Then, we modified the variable travel time parameters in the stochastic supply work scheduling model as fixed variable to develop a deterministic scheduling model to help the authorities for planning effective logistical support schedules. In addition, we also develop a simulation-based evaluation method to evaluate the schedules obtained from the manual method, the deterministic and the stochastic scheduling models, in simulated real world operations. Our model is formulated as an integer multiple-commodity network flow problem with side constraints which is characterized as NP-hard. To efficiently solve realistically large problems occurring in practice, we use a problem decomposition technique and greedy algorithm, coupled with the use of a mathematical programming solver CPLEX, to develop a heuristic algorithm. Finally, to evaluate the model and the solution algorithm in practice, we perform a case study using real data of the 1999 Chi-Chi earthquake in Taiwan. The test results show that the models and the solution algorithm are better than actual operations and would be useful for logistical support scheduling under stochastic travel times. |
