應用二階式啟發式演算法於動態及連續型船席指派

A Two-stage Heuristic for Solving the Dynamic and Continuous Berth Allocation Problem

國與國之貿易以海洋運輸為主，而海洋運輸則有賴港埠及碼頭基礎建設。如何提升碼頭效率及發揮港埠功能是一個重要的議題。本研究之重點在解決「動態及連續型」船席指派問題。經由船席之有效利用，以發揮港埠功能。此類型問題中，會同時考慮到達船以及在途船，並將碼頭視為連續泊線以供這些船舶停靠。本文中，提出一個二階式啟發式演算法來解決此類型問題。首先，產生船舶的隨機資料（包含船舶長度、作業時間、預計到達時間及期望停靠點）之後，在第一階段中本演算法會依據船舶預計到達時間，產生一個船舶置入順序。隨後，在第二階段中，本演算法會依序將船舶依其期望停靠點以及預計到達時間點置入時空圖中，如置入後發現重疊情形，則在考量偏移成本及相關限制（船體、碼頭）之下，進行船舶偏移以化解衝突，來產生最佳或近似最佳之可行解。本演算法以最小化總成本為目標。總成本則包含等待時間以及作業時間成本。本研究中，以java程式語言實作此演算法，並進行實驗，再經過對數據分析後，以探討解的品質以及該方法之可行性。實驗結果顯示，在目標函數下該演算法可求得最佳或近似最佳解，且其運算時間可應付實際作業需求。 Maritime transport is the major means for international trading, which depends heavily on port infrastructure, including berth. How to best utilize the berths of a port is an essential issue. This research focuses on dealing with one specific type of berth allocation problem (BAP)-the dynamic and continuous berth allocation problem (DCBAP)-in which both arrived and incoming ships are considered and a quay is entirely used as a continuous line to accommodate the calling ships. A two-stage heuristic has been proposed to solve the DCBAP. At the first stage, with the randomly generated ship data, the heuristic creates a ship placement sequence based on the estimated times of arrival (ETAs) the calling ships. At the second stage, it places ships into a time-space diagram one by one according to their desired berthing locations and ETAs. While placing a ship and this causes an overlap of ships the heuristic moves the ship to resolve the overlap based one the estimated costs of three different moving direction (i.e. up, down or right). Then, the least-cost moving direction is the first priority used to resolve the overlap. The aim is to minimize the total cost consisting of sub-costs that includes waiting and handling. Java language was used to implement this heuristic. Our experimental results showed that the heuristic was able to find the optimal/near-optimal solution with reasonable time.