運用螞蟻演算法求解動態船席指派問題

Abstract

本研究之核心為船席指派問題(Berth Allocation Problem, BAP)，旨在給予船舶相應的指派船席。我們可事先得到船舶抵達時間的動態資訊，動態BAP的目標式為最小化總服務時間，隱含了所有船舶的等待時間以及處理時間。另外，船舶的處理時間與服務船席具相關性，進而會影響船席的指派決策。由於BAP為一排序問題，而螞蟻演算法(Ant Colony Optimization, ACO)在排序問題上的搜尋能力以及求解過程相較於其他巨集啟發式演算法更有優勢。因此，本研究採用螞蟻演算法作為求解方法。首先，透過螞蟻演算法產生船舶的指派順序，再藉由啟發式指派法則，根據船舶的抵達時間以及與船席相關的處理時間，進一步將船舶指派到相應船席進行服務。由數值測試可知，啟發式演算法與文獻中採用拉式鬆弛法之研究相較，能有效提升求解品質。

The focus of this study is the Berth Allocation Problem (BAP), which determines the assignment of the berths to the calling ships. Given the dynamic information of the ship arrival times, the objective of the dynamic BAP is to minimize the total service times, defined as the sum of the waiting times and handling times, for all calling ships. In particular, the handling time is assumed to be berth-dependent and thus affected by the berth assignment decision. Owing to the nature of the sequencing decision problem associated with the BAP, this study chooses the Ant Colony Optimization (ACO), which has some inherited advantages over other meta-heuristics due to its sequential framework for the searching process and the solution building procedure. This study designs an ant-based algorithm to generate the ship assignment sequence, by which a greedy heuristic assigns a berth to a ship and determines the berthing window by considering its arrival time and the berth-dependent handling time. In the numerical experiment, the developed algorithm is compared with a solution algorithm based on Lagrangian Relaxation in the literature. It is found that the developed ant-based algorithm is promising with respect to the solution quality for the dynamic BAP.