臺灣博碩士論文加值系統

船席調配問題(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.

中文摘要 i
英文摘要 ii
誌謝 iii
目錄 iv
表目錄 v
圖目錄 vi
第一章 緒論 1
1.1 研究動機與目的 1
1.2 研究內容 2
1.3 研究範圍與限制 3
1.4 研究流程 4
1.5 專有名詞解釋 6
第二章 文獻回顧 7
2.1 船席調配問題 7
2.1.1 離散型船席調配問題 8
2.1.2 連續型船席調配問題 9
2.1.3 其他 12
2.2 數學模式 13
2.2.1 符號說明 13
2.3 綜合啟發式解法 15
2.4 粒子群演算法 18
2.5 小結 21
第三章 粒子群演算法求解船席調配問題 22
3.1 PSO應用在BAP 22
3.2 小結 28
第四章 研究設計與測試分析 29
4.1 系統建置與測試 29
4.1.1 系統環境 29
4.1.2 小樣本測試 31
4.2 演算法比較 32
4.3 參數設定 36
4.4 小結 49
第五章 結論與建議 50
5.1 結論 50
5.2 建議 50
參考文獻 51
附錄 53
簡歷 62

1. 李維平、吳昌志、賀嘉生、江正文 (2009)，改良粒子群演算法求解旅行家問題，資訊科學應用期刊，第四期，頁33-40.
2. 林君信，黃明居(1991)，知識庫系統應用於基隆港貨櫃船席調配作業之研究，運輸，第13期，頁1-21。
3. 林昱寬 (2006)，遺傳演算法為基礎的滾動式時窗船席分配法求解動態船席分配問題，國立台灣大學工業工程學研究所碩士論文。
4. 胡曉輝(2002)，粒子群優化算法介紹， http://web.ics.purdue.edu/~hux/ tutorials.shtml。
5. 郭信川、張建仁、劉清祥(2004)，粒子群演算法於最佳化問題之研究，科技與管理學術研討會。
6. 張企宏 (2004)，貨櫃碼頭分派問題之研究，私立元智大學工業工程與管理學系碩士論文。
7. Brown, G.G., Cormican , K.J., Law phongpanich, S. and Widdis, D.B. (1997) . “Optimizing submarine berthing with a persistence incentive” Naval Research Logistics (44) ,301-318.
8. Chen, C.-Y. and Hsieh, T.-W. (1999) . “A time-space network model for the berth allocation problem” Conference on System Modelling and Optimization.
9. Guan Y and Cheung RK (2004) . “ The berth allocation problem: models and solution methods. ” OR Spectrum (1) , 75-92
10. Guan, Y., Xiao, W., Cheung, R., Li, C., (2002). “A multiprocessor task scheduling model for berth allocation: heuristic and worst-case analysis. ” OperationsResearch Letters 30 (5), 343–350.
11. Imai, A., Nishimura, E. and Papadimitriou, S., (2001). “The dynamic berth allocation problem for a container port. ” Transportation Research Part B 35 (4), 401–417.
12. Imai, A., Nishimura, E., and Papadimitriou, S. (2003). “Berth allocation with service priority. ” Transportation Research Part B 37 (5), 437–457.
13. Imai, A., Sun, X., Nishimura, E., and Papadimitriou, S. (2005). “Berth allocation in a container port: using a continuous location space approach. ”Transportation Research Part B: Methodological, 39(3), 199-221.
14. J. Kennedy and R. C. Eberhart(1995). “Particle swarm optimization,” in: Proc. IEEE Int. Conf. on Neural Networks, Perth, Australia (4), 1942-1948.
15. Kim, K. H. and Moon, K. C. (2003). “Berth scheduling by simulated annealing. ” Transportation Research Part B: Methodological, 37(6), 541-560.
16. Lai, K.K. and Shih, K. (1992) . “ A study of container berth allocation. ” Journal of Advanced Transportation 26 (1) ,45–60.
17. Legato, P. and Mazza , R.M. (2001). “Berth planing and resources optimization at a container terminal via discrete event simulation. ” European Journal of Operational Research (133) ,537-547.
18. Lim, A., (1998). “ The berth planning problem. ”Operations Research Letters 22 (2), 105–110.
19. Lee, D. H. and J. H. Chen. (2010). “The continuous berth allocation Problem: A greedy randomized adaptive search solution. ”Transportation Research Part E: Logistics and Transportation Review 46(6) , 1017-1029.
20. Park, Y. M., and Kim, K.H. (2003) . “A scheduling method for Berth and Quay cranes, ”OR Spectrum (25), 1-23.
21. Salman A., Ahmad I., and Madani S. (2003) . “Particle swarm optimization for task assignment problem,” Microprocessors and Microsystems (26) , 363-371.
22. Shi Y. and Eberhart R.C. (1998). “Parameter selection in particle swarm optimization. ” In: PortoVW, Saravanan N, Waagen D, Eiben AE, editors. Proceedings of 7th International conference on evolutionary programming, New York: Springer ,591-600.
23. Tasgetiren M.F., Liang, Y.C., Sevkli, M., and Gencyilmaz, G. (2007). “Particle swarm optimization algorithm for makespan and total flowtime minimization in permutation flow shop sequencing problem.” European Journal of Operational Research, (177) ,1930-1947.
24. Wang, F.and Lim, A., (2007). “A stochastic beam search for the berth allocation problem. ” Decision Support Systems 42 (4), 2186–2196.