Abstract: With the increasing competition in the shipping market and the development of large-scale container ships,more and more shipping enterprises choose the mode of hub-and-spoke shipping network. As an important part of hub-and-spoke shipping network, the feeder network optimization problem is highly concerned by scholars. This study discusses the feeder scheduling problem considering the variable navigation speed andeconomic navigation speed,and establishes a nonlinear mixed integer programming model to minimize the total operation cost by taking into account the time window restrictions of the hub ports and the feeding ports. Themodel of a small-scale example is solved by the professional solver, and the accuracy of the model is verified. At the same time, an improved genetic algorithm is designed to solve the scheduling problem of large-scale feeder ships. In order to further improve the quality of the solution,a multi-agent evolutionary algorithm is designed. The numerical results show that the operation cost in the scenario with variable speed is lower than the operation cost in the scenario with economic navigation speed. In terms of algorithm efficiency, the convergence speed of genetic algorithm is faster,but the multi-agent evolutionary algorithm can obtain a better solution with higher accuracy.

Key words: hub-and-spoke network, containership scheduling, nonlinear programming, genetic algorithm, multi-agent evolutionary algorithm

摘要： 随着航运市场的竞争不断加剧和集装箱船舶大型化的发展,越来越多的航运企业选择轴-辐式航运网络模式。支线船舶调度问题作为轴-辐式航运网络的重要组成部分受到研究者的高度关注。本文研究了可变航速和经济航速两种情境下的支线船舶调度问题,同时考虑枢纽港和喂给港的取送箱时间窗限制,以航运企业运营成本最小化为目标函数建立非线性混合整数规划模型。首先使用专业的规划求解器进行小规模算例的求解,验证了模型的准确性。同时运用改进的遗传算法对大规模支线船舶优化调度模型进行求解。为了提高求解效果,进一步设计了多智能体进化算法进行求解。数值结果表明,可变航速的运营成本低于经济航速的运营成本;在算法效率方面,改进遗传算法收敛速度较快,多智能体进化算法则可以提高求解精度。

关键词: 轴-辐式网络, 支线船舶调度, 非线性规划模型, 遗传算法, 多智能体进化算法