緊急危機供應鏈網路之救災運輸排程演算法

Abstract

近幾年來，世界各地由於地震、海嘯、颱風等層出不窮的緣故，加上其規模與影響程度的與日俱增，大規模緊急危機事件中救災運輸的相關議題也因此越來越受到重視。而緊急危機運輸供應鏈因為災害的發生，所有的需求滿足都必須透過運輸工具才能完成，同時物流的方向並非固定：除了要將食物、水等民生補給品運輸到災區之外，同時災區也有傷亡人員或是其他重要物品必須進行撤離的工作。因此，如何結合主規劃排程的概念，在緊急危機供應鏈的網路架構下，有效地利用有限的資源以及運輸工具來完成運輸救災的工作，以達到最佳的救災運輸規劃，是本研究所欲進一步深入探討的問題。 本研究的問題若使用混合整數規劃模式求解，會存在大量的{0,1}變數，使得求解時間過於冗長，而且並不保證一定能夠得到可行解，且發生無解的情況時，無法得知原因。基於整數規劃的不可行性，本研究提出一啟發式演算法解決救災運輸規劃排程的問題，主要是在緊急危機供應鏈網路中，考量運輸工具與節點的產能限制，完成多期、多項產品的運輸補給工作，滿足所有需求。 本研究提出的啟發式演算法主要流程包含了需求處理和需求規劃兩大部分：在需求處理部份包括了需求分組和需求排序，主要為考量多目標(最小化移入產品延遲成本與移出產品運輸週期、最小化規劃成本)而對需求所做的前置作業；需求規劃的部份則是進行最佳化的規劃排程，先利用需求分組的結果找尋最小成本的運輸方式，以達運輸工作的經濟規模，再利用循環式分配資源的原則，公平地分配給每個需求一定的資源，針對每個需求找尋最適的運輸路徑。 本研究設計了4個維度組合而成的16個情境測試，測試結果顯示：本研究之演算法在大部份情境中皆與ILOG CPLEX的規劃結果的各項數據皆無太大差異；而當問題到達一定的複雜程度，ILOG CPLEX耗費數十個小時才能得到規劃結果，因此在時間效能上，本演算法的表現遠勝於ILOG CPLEX。

Emergency supply chain operation is an important study issue recently due to change of climate and environment. Damages caused by earthquake, hurricane, tsunami, and forest fire as well as the terrorist attack affect our every day’s lives dramatically. To build an emergency protection net for human beings from these disasters is a more and more urgent job, which needs coordination from multi-national governments, profit or non-profit organization, military operations, and civilian personnel as well as a well-planned supply chain operation. Apart from political conflicts, emergency supply chain operation scheduling and planning is the most important factor to successfully administer and control damages resulted from a natural or human disaster. Emergency supply chain operations are different from regular business supply chain operations in that timing and efficiency are two most important factors instead of costs. Emergency supply chain operations have to fulfill all the demands (medical supply, medical personnel, patients, food, water, equipment, etc) in a very short period of time with limited capacity of transportation tools, which makes it even more difficult to plan. Mixed Integer Programming is a popular way to solve emergency supply chain planning problems. However, as such problems increase in complexity, the MIP model becomes insolvable due to the time and computer resources it requires. Therefore, this study proposes a heuristic algorithm, called Emergency Relief Transportation Planning Algorithm or ERTPA, to solve the emergency supply chain planning problems efficiently and effectively. The algorithm will group and sort demands according to the distances from the demand nodes to the depots, final products, due dates, and shared capacity, to name several possible criteria. Then, the algorithm plans the demands individually, using a minimum cost production tree. To show the effectiveness and efficiency of the heuristic algorithm, a prototype was constructed and tested to demonstrate the power of the algorithm using complexity and computational analysis.