應用混合式粒子群演算法進行離散型船席及變動式橋式起重機指派

A Hybrid Particle Swarm Optimization for Simultaneous Discrete Berth Allocation and Variable-in-Time Quay Crane Assignment

徐賢斌(Hsien-Pin Hsu)

《運輸學刊》 29卷1期 (2017/03) Pp. 1-33

https://doi.org/10.6383/JCIT.201703_29(1).0001

摘要

船席指派與橋式起重機指派是貨櫃碼頭的兩大船邊作業問題。有效解決此兩大問題，可提升貨櫃碼頭作業之效率。過去之研究，基因演算法是解決貨櫃碼頭船邊作業問題的主要方法。近年來，粒子群演算法(Particle Swarm Optimization, PSO)崛起，並逐漸被應用於解決組合最佳化問題。但將其應用在解決貨櫃碼頭船邊作業問題之研究則仍罕見。因此，本研究提出一個混合式粒子群演算法 (Hybrid PSO, HPSO)來同時解決「動態及離散型」船席指派與「動態式」橋式起重機指派問題。在結合動態排序及離散事件技術後，HPSO並且可進行「變動式」橋式起重機指派。在與傳統之基因演算法(Genetic Algorithm, GA)比較後，此HPSO顯示了較佳之規劃結果。本研究中之GA係採用兩點交配及交換突變運算，並且只能進行「固定式」橋式起重機指派。

關鍵字

船席指派問題 ； 橋式起重機指派問題 ； 粒子群演算法 ； 動態排序

並列摘要

Berth allocation problem (BAP) and quay crane assignment problem (QCAP) are two essential seaside problems in a container terminal (CT). They can impact the performance of a CT significantly due to the uses berth and quay crane, two scarce resources in a CT. It is noted that genetic algorithm (GA) have been playing the main role in dealing with the two problems. However, particle swarm optimization (PSO) has been considered as a good competitor to GA in solving combinational optimization problems (COPs). But it has never been used to deal with the two problems in terms of variable-in-time QC assignment. This has prompted us to propose a new hybrid PSO (HPSO) to deal with the “dynamic” and “discrete” BAP (DDBAP) and “dynamic” QCAP (DQCAP) at the same time. The HPSO hybridizes a PSO with a simulated-based heuristic and, together with the techniques of dynamic rank order values (DROVs) and discrete events, it can perform variable-in-time QC assignment. To investigate its effectiveness, the HPSO has been compared to a GA that employs two-point crossover (TPX) and swap mutation (SWM) operations. The results of the experiments show that the HPSO outperforms the GA in terms of fitness value (FV).

並列關鍵字

Berth allocation problem ； Quay crane assignment problem ； Hybrid particle swarm optimization ； Genetic algorithm

參考文獻

徐賢斌(2014)。應用混合式粒子群演算法同時求解貨櫃碼頭動態船席指派問題及橋式起重機指派問題。國立高雄海洋科技大學學報。28，97-117。

Bierwirth, C.,Meisel, F.(2010).A Survey of Berth Allocation and Quay Crane Scheduling Problems in Container Terminals.European Journal of Operational Research.202(3),615-627.

Bierwirth, C.,Meisel, F.(2015).A Follow-up Survey of Berth Allocation and Quay Crane Scheduling Problems in Container Terminals.European Journal of Operational Research.244(3),675-689.

Brown, G. G.,Lawphongpanich, S.,Thurman, K. P.(1994).Optimizing Ship Berthing.Naval Research Logistics.41(1),1-15.

Buhrkal, K.,Zuglian, S.,Ropke S.,Larsen, J.,Lusby, R.(2011).Models for the Discrete Berth Allocation Problem: A Computational Comparison.Transportation Research Part E: Logistics and Transportaion Review.47(4),461-473.