基于迭代贪婪启发式算法的离散动态泊位分配问题总服务时间最小化

Minimizing the total service time of discrete dynamic berth allocation problem by an iterated greedy heuristic.

作者信息

Lin Shih-Wei, Ying Kuo-Ching, Wan Shu-Yen

机构信息

Department of Information Management, Chang Gung University, 259 Wen-Hwa 1st Road, Kwei-Shan, Taoyuan 333, Taiwan.

Department of Industrial Engineering and Management, National Taipei University of Technology, No. 1, Section 3, Chung-Hsiao East Road, Taipei 10608, Taiwan.

出版信息

ScientificWorldJournal. 2014;2014:218925. doi: 10.1155/2014/218925. Epub 2014 Sep 8.

DOI:10.1155/2014/218925

PMID:25295295

原文链接:https://pmc.ncbi.nlm.nih.gov/articles/PMC4175388/

Abstract

Berth allocation is the forefront operation performed when ships arrive at a port and is a critical task in container port optimization. Minimizing the time ships spend at berths constitutes an important objective of berth allocation problems. This study focuses on the discrete dynamic berth allocation problem (discrete DBAP), which aims to minimize total service time, and proposes an iterated greedy (IG) algorithm to solve it. The proposed IG algorithm is tested on three benchmark problem sets. Experimental results show that the proposed IG algorithm can obtain optimal solutions for all test instances of the first and second problem sets and outperforms the best-known solutions for 35 out of 90 test instances of the third problem set.

摘要

泊位分配是船舶抵达港口时进行的首要作业，也是集装箱港口优化中的一项关键任务。使船舶在泊位停留的时间最短是泊位分配问题的一个重要目标。本研究聚焦于离散动态泊位分配问题（离散DBAP），其目标是使总服务时间最小化，并提出了一种迭代贪婪（IG）算法来解决该问题。所提出的IG算法在三个基准问题集上进行了测试。实验结果表明，所提出的IG算法能够为第一和第二个问题集的所有测试实例获得最优解，并且在第三个问题集的90个测试实例中的35个实例上优于已知的最佳解。