臺灣博碩士論文加值系統

船席分配問題係安排船隻靠岸作業時間與碼頭作業位置以降低作業時間與等候時間，並可分為連續型與離散型兩種類型。而本研究求解的是連續型船席問題。過往的船席分配研究泰半假設船隻資料是固定的，無法滿足實務需求。實務上船隻常無法在預期時間抵港且裝卸作業也無法如期完成。本研究提出一以時窗與遺傳演算為基的滾動式船席分配法求解具非確定因子的船席分配問題。此時窗為基的作法係由抵港船隻觸發排程系統由抵港時間延伸一段時間形成時窗。時窗內已排定靠港作業、作業中、及預期出現的船隻納入排程考量形成一個滾動式的遺傳演化模式，目標是最小化時窗內所有未完成分配的船隻的額外作業時間和等候時間和。本研究假設每艘船隻有作業時間最短的作業位置，當排程系統排定的作業位置不同時會有額外作業時間。等候時間是船隻抵港時間與排程系統分配的靠岸作業時間差。為驗證本研究提示的方法的成效及實用性，實作一套「遺傳演算之時窗滾動式船席分配系統」，透過船隻陸續進港的情境模擬滾動地觸發排程系統分配抵港船隻的靠岸作業時間及碼頭作業位置。本研究同時測試數個類型範例和貪婪法為基的啟發式求解模式與無時窗的遺傳演算法的排程結果比較，證實時窗與遺傳演算為基的滾動式船席分配法確能求解較具有實際性的動態船席分配問題外，分配的結果也較前兩者佳。

The berth allocation problem can be regarded as an optimization problem that schedules the docking time and location for cargo ships to minimize the waiting time and loading/unloading time. The berth allocations problem can be classified into continuous and discrete problems depending on the type of berths is either long public berth or is short and dedicated. This research focuses on the former ones. Previous researches usually assume the arrival information of ships are fixed, which is not practical in the real applications. The on time rate of ship arrivals is not high and the problem have uncertainties involved. This research proposes a time window and GA based rolling scheduling method for real berth allocations to deal with the uncertainties. The scheduling task is triggered concurrently by an arrived ship. Starting from the trigger time, a specified time window is constructed to round in the ships that have been docked and that are anticipated to arrive within the time window, for scheduling consideration. Then, a GA optimization model for theses ships is built to schedule the docking times and positions for these ships. The arrived ship is then assigned with the docking time and location. A prototype system is developed to verify the proposed method and a simulation framework is built to simulate the arrivals of ships. Sixteen numerical examples of four types of arrival patterns are constructed to test the performance of the method. Scheduling results of the method are compared with those from the FCFS method. Results show that the method outperforms FCFC methods in most of the examples and is more practical than other methods.

誌謝 I
摘要 II
ABSTRACT III
目錄 IV
表目錄 VI
圖目錄 VII
中英文名詞對照表 VIII
符號列表 IX
第1章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究流程 3
1.4 章節概要 5
第2章 文獻回顧 6
2.1 船席分配問題 6
2.2 遺傳演算法之原理介紹 9
2.3 文獻探討小結 11
第3章 滾動式船席分配遺傳演算法 13
3.1 貨櫃碼頭營運問題描述 14
3.2 碼頭的時間空間座標系與排程系統使用的船隻資料結構 16
3.2.1 碼頭時間空間座標系定義 16
3.2.2 船隻物件相關資料結構定義 18
3.3 滾動式遺傳演算法求解動態船席分配問題 26
3.3.1 求解模式 26
3.3.2 船席分配動態模擬 30
3.3.3 以貪婪法為基的求解模式 32
3.3.4 遺傳演算法染色體替換機制 32
3.3.5 時空齊步遺傳演算法 33
3.3.6 空間演化遺傳演算法 37
3.3.7 改善式時空齊步與改善式空間演化求解模式 41
3.4 小結 43
第4章 演算法效能分析及範例測試 45
4.1 系統介紹 45
4.2 範例資料 46
4.3 演算法穩健性測試 52
4.4 範例測試 55
4.5 小結 64
第5章 結論與建議 65
5.1 結論 65
5.2 建議 66
參考文獻 67

Chen, C.-Y. and Hsieh, T.-W. "A time-space network model for the berth allocation problem." thIFIP TC7 Conference on System Modelling and Optimization.
Guan, Y. and Cheung, R. K. (2004). "The berth allocation problem: models and solution methods." OR Spectrum, 26(1), 75-92.
Guan, Y., Xiao, W.-Q., Cheung, R. K., and Li, C.-L. (2002). "A multiprocessor task scheduling model for berth allocation: heuristic and worst-case analysis." Operations Research Letters, 30(5), 343-350.
Imai, A., Nagaiwa, K., and Tat, C. (1997). "Efficient planning of berth allocation for container terminals in Asia." Journal of Advanced Transportation, 31, 75-94.
Imai, A., Nishimura, E., and Papadimitriou, S. (2001). "The dynamic berth allocation problem for a container port." Transportation Research Part B: Methodological, 35(4).
Imai, A., Nishimura, E., and Papadimitriou, S. (2003). "Berth allocation with service priority." Transportation Research Part B: Methodological, 37(5), 437-457.
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.
Kim, K. H. and Moon, K. C. (2003). "Berth scheduling by simulated annealing." Transportation Research Part B: Methodological, 37(6), 541-560.
Lim, A. (1998). "The berth planning problem." Operations Research Letters, 22(2-3).
Nishimura, E., Imai, A., and Papadimitriou, S. (2001). "Berth allocation planning in the public berth system by genetic algorithms." European Journal of Operational Research, 131(2), 282-292.
許冠文，「遺傳演算法和啟發式裝箱演算法為基之單一容器裝填最佳化方法」，碩士，台灣大學工業工程學所，2005。