船舶航线优化是一个复杂的过程,其目的是在考虑动态变化的天气条件下,以燃油消耗、航行时间、安全性或二者及以上的组合为目标寻找给定航程的最优路径。传统的航线优化算法无法同时优化多个目标且鲁棒性较差,而进化算法非常有利于解决与动态天气变化相关的航线多目标优化问题。因此,在SPEA2的基础上进行算法的改进并应用于多目标航线优化中,针对算法收敛慢的问题,借助Dijkstra算法生成初始种群。此外,对算法的种群更新策略和交叉、变异算子进行改进,提高了种群的质量和防止陷入局部最优。与其他进化算法进行比较,证明改进后的算法能更好地应用于多目标航线优化并获得更优秀的Pareto前沿。
Ship route optimization is a complex process whose purpose is to find the optimal route for a given voyage based on fuel consumption, duration time, safety, or a combination of the two or more under dynamic weather conditions. The traditional route optimization algorithm cannot simultaneously optimize multiple objectives and with poor robustness, while the evolutionary algorithm has a great advantage to solve the multi-objective route optimization problem related to dynamic weather change. Therefore, the algorithm is improved based on SPEA2 and applied to multi-objective route optimization. Aiming at the problem of slow convergence of the algorithm, the Dijkstra algorithm is used to generate the initial population. In addition, a new population renewal strategy and crossover and mutation operator are proposed to improve the quality of the population and prevent the population from falling into local optimum. Compared with other evolutionary algorithms, it is proved that the improved algorithm can be better applied to multi-objective route optimization and obtain a better Pareto frontier.
2023,45(16): 125-128 收稿日期:2022-12-30
DOI:10.3404/j.issn.1672-7649.2023.16.025
分类号:U692.3+1;TP301.6
作者简介:王军(1963-),男,博士,教授,研究方向为航运管理与海运风险工程
参考文献:
[1] WALTHER L, RIZVANOLLI A, WENDEBOURG M, et al. Modeling and optimization algorithms in ship weather routing[J]. International Journal of e-Navigation and Maritime Economy, 2016, 4: 31–45
[2] 蒋美芝, 吕靖. 基于 Pareto 蚁群算法的船舶风险规避路径优化[J]. 交通运输系统工程与信息, 2019, 19(1): 192–199.
[3] 李鹏飞. 多目标船舶气象航线优化算法的研究与仿真[D]. 吉林: 吉林大学, 2019.
[4] ZITZLER E, LAUMANNS M, THIELE L. SPEA2: Improving the strength Pareto evolutionary algorithm[J]. TIK-report, 2001, 103.
[5] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-II[J]. IEEE transactions on evolutionary computation, 2002, 6(2): 182–197
[6] 李密青, 郑金华, 罗彪, 等. 一种基于邻域的多目标进化算法[J]. 计算机应用, 2008(6): 1570-1574.
[7] KIM M, HIROYASU T, MIKI M, et al. SPEA2+: improving the performance of the strength pareto evolutionary algorithm 2[C]//International Conference on Parallel Problem Solving from Nature, 2004: 742–751.
[8] LI X, WANG H, WU Q. Multi-objective optimization in ship weather routing[C]//2017 Constructive Nonsmooth Analysis and Related Topics (dedicated to the memory of VF Demyanov)(CNSA), IEEE, 2017: 1–4.
[9] ZITZLER E, THIELE L. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach[J]. IEEE transactions on Evolutionary Computation, 1999, 3(4): 257–271
[10] VENETI A, KONSTANTOPOULOS C, PANTZIOU G. Evolutionary computation for the ship routing problem in: Modeling[J]. Computing and Data Handling Methodologies for Maritime Transportation, 2018: 95–115