多產品情境下之多廠區訂單分配與船舶路徑規劃問題

Metaheuristics for a Multi-Plant Order Allocation and Ship Routing Problem

古薇涵

指導教授 ： 林則孟

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

摘要

隨著國際貿易的發展，各國間的貨運往來多以海上運輸為主，整體營運受訂單、工廠、港口與船舶的變動而影響，使得許多公司轉型為整合性企業，當各工廠位於不同區域，訂單的運輸成本便是企業進行訂單分配所需考慮的因素，如何將訂單分配給適合的工廠製造使得船舶運輸總成本最小即為本研究目的。因此，本研究將針對產業專用船運的短期營運問題進行探討，在多產品及多廠區的情境下，將此問題分為多廠區訂單分配問題（MPOAP）與船舶路徑規劃問題（SRP）。
個案公司現行作法由多個部門以人工方式協同規劃且資訊並無統一，導致規劃時間過長，因此，本研究提出兩種搜尋架構模式，分別為兩階段方法（Two phase method）與回饋式演算法（Inner-outer iterative algorithm），其中，使用基因演算法（GA）/門檻值接受法（TA）求解MPOAP，產生訂單與工廠的方案後，並分別結合和弦搜尋演算法（HS）求解SRP，以單位運輸成本最小化為目標，找出最佳的船舶路徑組合。在實驗過程中發現，求解SRP之HS具有隨機性，進行多次抽樣後產生的績效值皆不同，因此，需依賴重複抽樣的方式縮小隨機產生的變異，故本研究進一步提出以回饋式演算法為架構的GA+HS結合OCBA，透過OCBA決定各方案之抽樣次數，以有效率地分配抽樣次數並減少運算時間。
為了測試方法的可行性，先使用小型問題進行四種演算法組合之驗證，再透過公司一期實務資料進行求解，由實驗得知，不論訂單量大小皆可找到不錯的可行解，而不同的搜尋架構各有其優缺點，其中，兩階段方法之優點是求解快速，於實務上大型資料的應用可能較符合公司求解效率的需求；回饋式方法具有高穩定性且可找到較佳的成本績效。最後加入OCBA皆可減少運算時間，並在大型問題中可求得近似最佳解。因此，本研究提出的方法可以輔助派遣人員作業，以減少規劃時間並有效的做出正確決策，進而降低實務上的成本。

關鍵字

多廠區訂單分配問題 ； 船舶路徑規劃問題 ； 兩階段方法 ； 回饋式演算法 ； 基因演算法 ； 門檻值接受法 ； 和弦搜尋演算法

參考文獻

5. 陳玉琪，「供應鏈訂單分割與途程模式之研究」，中原大學工業工程研究所碩士論文，2002。

6. 曾煥雯，「跨廠訂單分配模式之構建—應用模擬退火演算法」，元智大學工業工程研究所碩士論文，2000。

7. 劉向邦，「以和弦搜尋演算法為基礎之混合式全域搜尋演算法求解含凹形節線成本最小成本轉運問題之研究」，中央大學土木工程學系碩士論文，2008。

8. 劉珮伶，「考量產品配送下之多廠區訂單分配問題應用門檻值接受法」，元智大學工業工程與管理研究所碩士論文，2004。

9. 羅冠君，「基於和聲搜尋演算法與離散拉格朗日法之混合演算法於結構最佳化設計的研究」，中央大學土木工程研究所碩士論文，2008。