結合訂單分配與船舶途程規劃問題之探討

Hybrid Metaheuristic Approach for Integrated Multi-Plant Order Allocation and Ship Routing Problem

翁毓夆

指導教授 ： 林則孟

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

摘要

在實務上，許多跨國企業同時擁有位於不同區域的生產工廠以及運輸船隊進行貨物配送，此類型企業的短期營運問題主要在於客戶訂單的處理與船舶途程規劃，由於此問題直接反應到是否可以快速的滿足客戶需求，因此該如何當各工廠位於不同區域的情況下，再加上船舶屬性、港口限制和訂單內容互相影響的環境下，把客戶訂單分配在合適的生產工廠，並且有效率的規劃船隊的航行路徑進行配送，是個非常重要的決策工作，目前有些企業仍然依靠人工的方式進行訂單的處理與船舶排程，但隨著訂單業務成長的情況下，傳統的人工已無法應付此工作，因此如何使用電腦系統同時進行訂單分配與船舶途程規劃，減少規劃人員經驗的差異及安排更符合全域最佳的規劃以最小化單位運輸成本，即為本研究的目的。
本研究將著重在實務上產業專用船運的短期營運問題進行探討，在多產品及多廠區的情境下，問題區分成多廠區訂單分配問題(Multi-Plant Order Allocation Problem, MPOAP)與船舶途程規劃問題(Ship Routing Problem, SRP)。在實務上兩個問題是互相影響的問題，文獻上並無探討在兩種問題同時考量的情況下做一個最佳化的求解決策，故本研究將使用回饋式（Inner-outer iterative）搜尋架構將兩個子問題MPOAP與SRP進行整合性求解，在MPOAP中使用門檻值接受法並搭配噪音擾動法求解SRP，以單位運輸成本最小化為目標下，求得最佳多廠區訂單分配及船舶路徑組合，且實驗中將利用其與多種演算法在不同情境下進行比較以說明此方法組合的優勢。另本研究將考慮兩大隨機性部分，其一為問題隨機性，海上船運時常受到天氣不定因素影響航行時間的不確定性，導致運輸成本有變異性，其二為使用隨機演算法所求解SRP每次最佳解答案不一，在回饋於MPOAP顯著影響求解品質，綜合以上，需進行多次重複抽樣的方式縮小隨機產生的變異，故本研究進一步利用回饋式搜尋演算法結合OCBA(Optimal Computing Budget Allocation)，欲透過OCBA有效率地分配抽樣次數達到減少運算時間並且更貼切符合實務狀況。

關鍵字

多廠區訂單分配問題 ； 船舶路徑規劃問題 ； 回饋式演算法 ； OCBA

參考文獻

2. 李忠憲，”運用粒子群最佳化解決多場站之收送貨問題”，交通大學運輸科技與管理學系，碩士論文，2011

4. 陳百傑，”以啟發式演算法求解時窗限制車輛途程問題“，中原大學工業工程學系，碩士論文，2002

1. 古薇涵，”多產品情境下之多廠區訂單分配與船舶路徑規劃問題”，清華大學工業工程與工程管理學系，碩士論文，2012

7. 羅文韋，”考量庫存限制下之多廠區訂單分配與船舶途程規劃問題”，清華大學工業工程與工程管理學系，碩士論文，2012

8. Ai, T. J., V. Kachitvichyanukul, “A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery”, Computers and Operations Research, 36, 1693-1702 (2009)