混合型粒子群演算法求解船舶途程規劃問題

A Hybrid Particle Swarm Optimization Approach for Ship Routing Problem

葛玉祥(Ko, Yu Hsiang)

指導教授 ： 林則孟

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

摘要

本研究將考量多種產品和多種船型並存在靠港限制情境下的船舶途程規劃問題，同時也將船舶的裝卸貨與航行時間加入考量，在過去研究中很少同時將這些限制與條件加入考慮，而本研究將這些同時加入考量，且在加入考量後能更貼近實務上所面臨的問題。本研究將提出以混合型粒子群演算法求解船舶途程規劃問題會有較佳的求解品質與效率，在實驗中也顯示和傳統的基因演算法與粒子群演算法相比能有更好的求解效率與品質。
在過去文獻中，大多數船舶途程規劃問題在需求上都是確定的，並未考量顧客需求是具有隨機性的現象，故本研究也將探討隨機需求下的船舶途程規劃問題。但是顧客的需求是具有變異性的，因此必須透過多次模擬以消除隨機性所帶來的干擾，本研究將利用模擬預算最佳分配(Optimal Computing Budget Allocation, OCBA)進行模擬資源分配，有效率地分配抽樣次數以減少運算時間和模擬成本，並且可有效的提升求解品質。
到目前為止，有關船舶途程規劃的研究大多都是在已知取貨地點的情況下進行求解，極少將多廠區訂單分配問題加入考量，因此，本研究將探討將訂單分配題加入於船舶途程規劃問題進行共同求解，並利用回饋式演算法進行求解，實驗結果顯示將訂單分配問題加入考量後能夠更全面性地評估各個方案，使得績效值能夠有顯著提升。

關鍵字

船舶途程問題 ； 隨機需求 ； 模擬預算最佳分配 ； 混合型粒子群演算法

並列摘要

Ship routing problem (SRP) is an important and well-known combinatorial optimization problem encountered in many transport logistics and distribution systems. The SRP has several variants depending on some restrictions such as time window, multiple vessels and so on. In this research, considering the ship routing problem with multi-product, heterogeneous vessel and having loading and port constraints The problem is to find an optimal assignment of the ship routing and loading volume of demand simultaneously in order to minimize the total cost satisfy capacity of ships.
Since SRP is an NP-hard problem, we propose a hybrid particle swarm optimization (HPSO) to solve ship routing problem. HPSO is an improved algorithm based on particle swarm optimization (PSO) incorporated with crossover and mutation operators can provide better solving quality. The performance of the proposed method is compared with genetic algorithm (GA) and particle swarm optimization (HPSO). The experimental results show that the proposed algorithm exhibits good performance and solving effectiveness for the test problem.
In the real situation, the demand of customers are not constant. It would change by temporary or seasonal demand. Therefore, we consider stochastic demands of customers. We apply optimal computing budget allocation (OCBA) to allocate simulation resource. It can allocate simulation resource efficiently and reduce solving time.

並列關鍵字

Ship Routing Problem ； Stochastic Demand ； Optimal Computing Budget Allocation ； Hybrid Particle Swarm Optimization

參考文獻

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

2. 翁毓峯，”結合訂單分配與船舶途程規劃問題”，清華大學工業工程與工程管理學系，碩士論文，2013

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

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

5. Berbeglia, G., Cordeau, J. F., Gribkovskaia, I. and Laporte, G., “Static pickup and delivery problems: A classification scheme and survey”, TOP, 15, 1-31 (2007)