遺傳演算法為基的滾動式時窗船席分配法求解動態船席分配問題

A GA and Time Window Based Rolling Method for Dynamic Berth Allocation Problems

林昱寬(Yu-Kuan Lin)

指導教授 ： 楊烽正

國立臺灣大學/工學院/工業工程學研究所/碩士(2006年)

https://doi.org/10.6342/NTU.2006.03072

摘要

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

關鍵字

船席分配問題 ； 滾動式 ； 遺傳演算法 ； 動態

並列摘要

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.

並列關鍵字

Berth Allocation Problem ； Rolling ； Genetic Algorithm ； Dynamic

參考文獻

許冠文，「遺傳演算法和啟發式裝箱演算法為基之單一容器裝填最佳化方法」，碩士，台灣大學工業工程學所，2005。

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).