- 學位論文
具裝卸設備限制之離散型動態船席指派問題研究
Modeling and Solving the Discrete and Dynamic Berth Allocation Problem with Limited Quay Cranes
摘要
臺灣四周環海，對外貿易仰賴海運，且位居亞洲經貿樞紐，是國際貨櫃運輸往來的交會點，不僅臺灣港口在國際貨櫃運輸的轉口貿易上扮演重要的角色，臺灣港口的競爭力更是影響臺灣國際經貿地位的重要關鍵之一。本研究主要針對考量碼頭裝卸設備調度的船席規劃進行混合整數規劃模式(Mixed Integer Programming Model)構建與利用禁忌搜尋法（Tabu Search）之移步（move）的概念進行啟發式演算法設計，首先我們在不考慮裝卸設備限制條件下，針對離散型動態船席指派問題（Dynamic Berth Allocation Problem）求解，然後根據此船席指派結果，構建出裝卸設備之可行調度路徑，再利用本研究構建之求解裝卸設備指派問題的最佳化子模式求解。最後，求解結果若為不可行解（碼頭所有裝卸設備即使經過調度仍無法滿足所有船舶之需求），便針對部份船舶進行重新排程，再以重新排程後之指派結果構建裝卸設備之可行調度路徑及利用最佳化子模式求解，重覆上述步驟至設定之停止條件。本研究設計之演算法與最佳化混合整數規劃模式的結果比較來看，平均差距在1.5%左右，而最佳化於求解大型例題時，需花費較長的時間才能求得一可行解，測試結果顯示本論文設計之演算法可提供符合實務需求的良好規劃品質。
並列摘要
Because of lacking natural resources, Taiwan deeply relies on international trade for economy development. However, Taiwan has excellent advantages for developing international trade due to its geographic location as the junction of international container transit. From the marine transportation viewpoint, Taiwan should fully take this geographic advantage to enhance operational effectiveness and efficiency at each international harbor. This study focuses on developing a heuristic algorithm to solve the dynamic berth allocation problem (DBAP) with limited number of quay cranes. Initially, ignoring the quay crane constraints we heuristically construct several trial solutions to the DBAP, and maintain a pool of some high quality solutions in terms of total flow time as inputs for the following procedure. Thereafter, for each high quality solution recorded, we repeat the following two steps until a stopping criterion is reached. At step 1, we build the feasible transfer arcs of cranes for each pair of ships at different berths and solve the crane allocation problem using a variant of minimum cost network flow model. If feasibility is obtained with respect to the cranes needed, we got a feasible solution; otherwise, we enter into step 2. At the second step, for those infeasible solutions (i.e. the cranes available at the container terminal can not satisfy the demand of cranes for all the ships even through transferring cranes) obtained, we try to reschedule the service start times for certain ships using information revealed in solving the optimization submodel. Based on the experimental results on small size problems, our algorithm yielded solution quality about an average of 1.5% inferior to the optimal solutions. However, the giant single optimization model took a lot of time to obtain the first feasible solution as the problem size was getting bigger. By contrast, the algorithm we developed spent much less time in producing near optimal solutions. Generally speaking, the algorithm we developed seems to provide practical but high quality solutions.