A MATHEMATICAL MODEL AND GENECTIC ALGORITHM SOLUTION METHODS FOR THE BERTH ALLOCATION PROBLEM WITH SEVERAL TYPES OF MACHINES

ABSTRACT Maritime shipping is vital to worldwide commerce. Due to the high flow in ports throughout the world, the efficient allocation of vessels in berths has become a problem. A new mathematical model and several algorithms are proposed in this paper to planning the allocation of the vessels in berths and the allocation of resources to the service of each vessel. Those resources, in general, are machines to load or unload vessels. The mathematical model was implemented on Cplex and can solve small scale instances, due to its high complexity. To solve larger instances, a genetic algorithm-based metaheuristic, a first-in first-out heuristic, and a machine allocation algorithm are also proposed in this paper. The model and the algorithms produce very useful and interesting results. Comparing, the results produced by the GA are, on average, 94% better than the results of the Cplex and 26% better than the results of FIFO.

摘要：海运是全球商贸的核心支撑。受全球港口作业吞吐量居高不下的影响，泊位船舶高效调度已成为亟待解决的关键问题。本文提出一种全新的数学模型与多种算法，用于开展泊位船舶分配规划以及单船服务资源分配工作；此类资源通常为用于船舶装卸作业的机械设备。该数学模型依托CPLEX平台实现，但由于其复杂度较高，仅可求解小规模算例。为处理大规模算例，本文进一步提出了基于遗传算法的元启发式算法、先进先出（First-In First-Out, FIFO）启发式算法以及机械设备分配算法。上述模型与算法均取得了极具实用价值与研究意义的结果。对比结果显示，遗传算法的求解结果平均较CPLEX求解结果提升94%，较先进先出启发式算法的求解结果提升26%。