A Heuristic Relief Transportation Planning Algorithm for Emergency Supply Chain

近幾年來，世界各地由於地震、海嘯、颱風等層出不窮的緣故，加上其規模與影響程度的與日俱增，大規模緊急危機事件中救災運輸的相關議題也因此越來越受到重視。而緊急危機運輸供應鏈因為災害的發生，所有的需求滿足都必須透過運輸工具才能完成，同時物流的方向並非固定：除了要將食物、水等民生補給品運輸到災區之外，同時災區也有傷亡人員或是其他重要物品必須進行撤離的工作。因此，如何結合主規劃排程的概念，在緊急危機供應鏈的網路架構下，有效地利用有限的資源以及運輸工具來完成運輸救災的工作，以達到最佳的救災運輸規劃，是本研究所欲進一步深入探討的問題。 本研究的問題若使用混合整數規劃模式求解，會存在大量的{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.謝詞 一 論文摘要 二 THESIS ABSTRACT 三 目錄 四 表目錄 六 圖目錄 九 第一章 緒論 1 第一節 研究動機 1 第二節 研究目的 2 第三節 研究範圍 3 第四節 研究架構 4 第二章 文獻探討 5 第一節 供應鏈上緊急危機事件之定義 5 第二節 緊急危機事件處理之相關研究 6 第三節 供應鏈管理之研究範疇、問題與模式分類 7 2-3-1 供應鏈管理之研究範疇 8 2-3-2 供應鏈管理之問題分類 8 2-3-3 供應鏈管理之模式分類 9 第四節 先進規劃排程與緊急危機事件 10 第五節 規劃排程問題之方法論 12 2-5-1 線性規劃與混合整數規劃 (Linear and Mixed Integer Programming) 12 2-5-2 拉氏釋限法(Lagrangian Relaxation Method) 13 2-5-3 基因演算法(Genetic Algorithm) 13 2-5-4 限制規劃法(Constraint Programming) 13 2-5-5 其他啟發式演算法(Heuristic Algorithm) 14 第六節 圖論演算法 15 第三章 問題描述與混合整數規劃 16 第一節 問題描述 16 3-1-1 緊急救災供應鏈網路架構 16 3-1-2 需求資訊 18 3-1-3 運輸工具 19 3-1-4 規劃時距 20 3-1-5 成本結構 22 第二節 假設條件 23 第三節 混合整數規劃模型 24 3-3-1 混合整數規劃模型 24 3-3-2 複雜度分析 31 第四章 緊急救災運輸排程演算法(Emergency Relief Transportation Algorithm, ERTPA) 33 第一節 演算法概述 33 第二節 演算法主要流程 35 第三節 需求分組演算法 37 第四節 需求排序演算法 42 第五節 規劃排程演算法概述 44 第六節 運輸規劃排程演算法 46 4-6-1 最小成本路徑規劃法(Minimum Cost Transportation, MCT) 46 4-6-2 循環式最短路徑規劃法(Round Robin Shortest Path Transportation, RRSPT) 47 第七節 時間(Time Complexity)複雜度分析 51 第五章 系統說明與模式分析 52 第一節 系統說明 52 5-1-1 資料結構 52 5-1-2 系統畫面與執行步驟 58 第二節 情境分析與設計 59 5-2-1 情境分析與設計 60 5-2-2 供應鏈資訊 61 5-2-3 需求及產品資訊 63 5-2-4 運輸工具與網路連結資訊 64 5-2-5 規劃範例 66 第三節 情境分析 72 5-3-1 延遲成本與運輸週期分析 72 5-3-2 規劃成本與規劃時間比較 77 第四節 效率分析 84 第五節 實例分析 86 第六節 演算法規劃結果與最佳解之差異分析 89 5-6-1 需求分組之影響 89 5-6-2 需求排序之影響 90 5-6-3 循環式最短路徑演算法之影響 90 第六章 結論 92 第一節 總論 92 第二節 未來研究方向 93 參考文獻 94 附錄A 情境分析之規劃結果 9