考量庫存限制下之 多廠區訂單分配與船舶途程規劃問題

Metaheuristic for Multi-Plant Order Allocation and Ship Routing Problem under Factory`s Inventory Restricted

羅文韋

指導教授 ： 林則孟

國立清華大學/工學院/工業工程與工程管理學系/碩士(2012年)

摘要

在實務上，許多跨國企業會同時擁有多區域的生產工廠與運輸船隊進行貨物配送，此類型企業的船隊在船舶運輸的分類中可稱為產業專用船運(industrial shipping)，該船隊的短期營運操作問題主要在於客戶訂單的處理與船舶途程規劃，由於客戶訂單的處理與船舶排程直接影響到企業是否可以快速的滿足客戶需求，且在船舶屬性、港口限制和工廠庫存互相影響的環境下，要如何把客戶訂單分配在各區域的生產工廠，並且有效率的規劃船隊的航行路徑進行配送，是個非常複雜決策工作，目前有些企業仍然依靠人工的方式進行訂單的處理與船舶排程，隨著近年來運輸成本的上升與訂單業務增加，傳統的人工已無法應付此工作，因此如何使用電腦系統同時進行訂單分配與船舶途程規劃，降低船舶運輸的成本亦減少規劃人員經驗的差異，成為目前主要需解決的問題。
本研究主要探討產業專用船運的短期營運問題，將原始問題分為多廠區訂單分配問題(MPOAP)與船舶途程規劃問題(SRP)。並在單位運輸成本最小為規劃目標下，在訂單分配問題建構基因演算法與粒子群演算法分別進行求解，在船舶途程規劃問題建構門檻式變動鄰域搜尋法進行求解，本研究使用兩種搜尋架構將子問題的演算法進行整合求解，分別為兩階段式架構演算法與回饋式架構演算法，最後利用個案公司的實例資料進行參數實驗與求解分析。
經過實驗與分析發現兩階段與回饋式方法在實務資料與測試資料中都可以有效求解，且回饋式演算法求解的績效在訂單數量越大時越優於兩階段演算法，而兩階段演算法求解效率較好，所花費的運算時間小於回饋式演算法，因此，可證明本研究方法可應用於實務問題且回饋式演算法可比兩階段演算法帶來更多利潤，決策者可視不同需求與情境選擇使用不同的演算法。

關鍵字

訂單分配問題 ； 船舶途程規劃問題 ； 基因演算法 ； 粒子群演算法 ； 變動式鄰域搜尋法

並列摘要

無資料

並列關鍵字

Ship Routing Problem ； Order Allocation Problem ； Variable Neighborhood Search ； Genetic Algorithm ； Particle Swarm Optimization

參考文獻

3. 劉慧燕，“不定其船運船舶排程問題之研究”，國立成功大學交通管理科學研究所，博士論文，2011。

5. Bronmo ,G., Christiansen, M., Fagerholt, K. and Nygreen, B., “A Multi-start local search heuristic for ship routing scheduling a omputational” Computer and Operations Research Society , Vol.34,pp.900-917,2007.

6. Chen ,J. C., Hsieh,W. H.,Cheng, C. H. and Chen, C. S. ,“Hybrid Meta-Heuristics for Vehicle Routing Problem with Time Window Constraints” , Institute of Electrical and Electronics Engineers,2009 .

7. Chut, P. C. and Beasley, J. E., “A Geneic Alogorithm for the Generalised Assignment Problem ” , Computers Operational Research, Vol. 24, No. 1, pp. 17-23, 1997.

9. Korsvik ,J. E., Fagerholt, K., and Laporte,G., “A large neighbourhood search heuristic for ship routing and scheduling with split loads” ,Computers & Operations Research , Vol. 38,mpp. 474–483,2011.