混合集束搜尋法和粒子群演算法求解碼頭泊位指派問題

Hybrid Beam Search and Particle Swarm Optimization to Solve the Berth Allocation Problem

周昊(Hao Chou)

指導教授 ： 丁慶榮

元智大學/工程學院/工業工程與管理學系/碩士(2012年)

https://doi.org/10.6838/YZU.2012.00049

摘要

國際間的貨物交易大多經由海路運送，標準化的貨櫃運輸型態更是其中主流；台灣屬於海島型經濟環境，位於經貿樞紐，是國際貨櫃運輸的重要交會點。因此，港口的競爭力優劣相當關鍵。在海運的過程中，船舶將大部分的時間花費在港口作業上，若能有效的降低碼頭作業時間，將可以提升港口進爭力。
　　本研究針對船舶碼頭的指派問題(Berth Allocation Problem)進行探討，以規劃期間之船舶的等候時間最小化以及船舶的總服務時間最小化分別作為目標函數。由於碼頭指派問題屬於NP-hard，正確解法無法在合理時間內求解，因此求解方法採用集束搜尋法(Beam Search, BS)、粒子群最佳化演算法(Particle Swarm Optimization, PSO)，以及使用將集束搜尋法之求解結果當作粒子群演算法的部分初始解(BS-PSO)進行求解。
　　測試例題包括靜態與動態兩類，靜態例題為平行機台之標竿測試例題，動態例題則採用基隆港港口相關運作之資料隨機產生。從結果可以發現，BS可以在短時間內找到不錯的解，PSO則是具有較好的求解能力，而BS-PSO雖然求解時間較長，但相較於BS或PSO，能夠有最好的結果，其部分初始解使用BS的較佳解能有效控制PSO的收斂速度，因此相較其他方法還能夠有所進步。本研究中針對離散型的動態與靜態碼頭問題進行測試，未來能夠利用PSO的特性進行研究連續型的碼頭指派問題。

關鍵字

碼頭指派問題 ； 集束搜尋法 ； 粒子群演算法 ； 混合型演算法 ； 離散型

並列摘要

Located in Southeast Asia, Taiwan has been an important international transportation hub and center and relies heavily on sea transportation. Reducing the vessel turnaround time is an important issue for improving terminal efficiency thus improving the competitiveness over other Southeastern countries.
　This study deals with the discrete berth allocation problem (BAPD), where minimizing the total waiting time and total service time are both considered. Since the problem is NP-hard, we propose a beam search (BS), particle swan optimization (PSO), and a hybrid algorithm BS-PSO in which the solutions obtained by BS are used as initial solutions of PSO. Both instances in the static and dynamic berth allocation problem are tested. The static instances are extracted from the benchmarks of parallel machine scheduling problem, while the dynamic instances are randomly generated by a set of simulated data based on the real data from the Keelung Port.
　Taking the advantages of the BS quick achieving near optimal solutions and PSO obtaining lower costs than BS, the BS-PSO is able to provide improved terminal efficiency. The results show that the hybrid BS-PSO obtains the best solution among three algorithms. Compared with first come first served heuristic, BS-PSO can improve results by up to 11.1%. In the future, the research will advance the study using BS-PSO in the continuous berth allocation problem.

並列關鍵字

Discrete ； Berth Allocation Problem ； Beam Search ； Particle Swarm Optimization ； Hybrid Heuristic

參考文獻

23. 楊禮瑛，「應用粒子群演算法求解OVRP問題之研究」，國立交通大學運輸科技與管理研究所，碩士論文，2011。

2. 王雅賢，「粒子群最佳化演算法改良之研究」，中原大學資訊管理研究所，碩士論文，2006。

1. 王俊軒，「集束搜尋法求解可變作業強度之資源限制專案排程」，國立清華大學工業工程與工程管理研究所，碩士論文，2008。

9. 洪長裕，「以啟發式搜尋法求解資源限制專案排程」，國立清華大學工業工程與工程管理研究所，碩士論文，2009。

8. 柯芳伸，「具裝卸設備限制之離散型動態船席指派問題研究」，元智大學資訊管理研究所，碩士論文，2009。