以粒子群演算法應用於船席調配問題之研究

Abstract

船席調配問題(Berth Allocation Problem, BAP)當船舶數增加到某一程度時，將屬於NP-hard問題，故必須使用一個具有效率的演算法進行求解。本研究，使用粒子群演算法(Particle Swarm Optimization, PSO)求解BAP，而PSO最重要的部分為設定為粒子數，故在本實驗過程中，將粒子數分為10、20和30，三種型式，迭代數，以 50、100和150次，並將船舶數規模依25艘、50艘、75艘和150艘船舶進行樣本測試。模擬測試中並與Guan and Chung學者在2004年所提出的綜合啟發式解法(Composite Heuristic, CH)來進行比較分析。 測試結果後發現，在小樣本船舶規模數時，綜合啟發式解法的求解效率優於粒子群演算法的求解效率，而當船舶規模逐漸增加，粒子群演算法的求解效率較佳，在參數設定方面，也以粒子數30，迭代次數150所呈現的求解品值較佳且達到收斂性。

The Berth Allocation Problem becomes a NP-problems when the number of ships increases to certain extent. Therefore, this research have to use a streamlined calculating methods to find a more efficient way to solve the BAP problems. Particle Swarm Optimization is used to solve problems in this research. The most important part of PSO is parameter setting. This experiment used three parameter setting particle numbers, 10, 20 and 30. In addition, iterative numbers were set at 50, 100 and 150. The above settings were tested on the following number of model ships: 25, 50, 75 and 150. This testing also used Guan and Chung' s Composite Heuristic, CH analysis, published in the 2004 journal for comparison. The test result, in small number of model ship, shows Composite Heuristic, CH is more efficient than that of Particle Swarm Optimization Algorithm. On the contrary, when there is a gradual increase in ships, the Particle Swarm Optimization Algorithm has better efficiency. With respect to parameter setting, we also found that particle number 30 and iterative number 150 show better result of reaching convergence.