Abstract: The ship scheduling affected by severe weather is a very complex optimization problem, and is also one of the key issues needed to pay attention in liner companies. Therefore, based on the premise of obtaining the latest weather forecasting information in the designed multi-stage rescheduling mechanism period and the real-time positions of all the ships in service in one liner company on a shipping network, the restriction of liner shipping schedule was focused on, and the realistic constraints such as the change of ship's speed between different ports and the ship capacity, a nonlinear mathematical model was built to minimize the total shipping cost of all the ships during the fixed planning period. And an improved genetic algorithm embedded with gene repair operator was designed to solve the built model. Then the optimal multi-stage rescheduling scheme, which was integrated by the solution strategies of charting for direct-transport, dispatching ship across different routes, adjusting port reaching order and goods transfer, was given. Experimental results of examples with large, medium, and small scales show that, compared with the traditional waiting method, multi-stage rescheduling saves more than 15% of the total shipping cost, verifying the effectiveness of the proposed model and scheme; compared with Cplex, the improved genetic algorithm has the calculation efficiency greatly improved and all the deviation values within 5%; and compared with Ant Colony Optimization (ACO) algorithm, Tabu Search (TS) algorithm, Quantum Differential Evolution (QDE) algorithm, the improved genetic algorithm has the cost reduced by about 10% in the effective time, proving that the algorithm is scientific. It can be seen that the proposed method can provide the reference for actual ship scheduling of liner companies.

Key words: waterway transportation, multi-type liner scheduling, improved genetic algorithm, multi-stage rescheduling mechanism, variable-time rolling, severe weather

摘要： 受恶劣天气影响的船舶调度是一个非常复杂的优化问题，也是班轮公司重点关注的问题之一。为此，针对某航运网络上的一家班轮公司的所有营运船舶，以获知设计的多阶段重调度机制时段内最新预报的天气信息和这些船舶的实时位置为前提，重点考虑班轮船期表的限制并兼顾港口间航速变化和船舶容量等现实约束，构建了以固定计划期内所有船舶的航运总成本最小为优化目标的非线性数学模型，并设计了嵌入基因修复算子的改进遗传算法用于求解该模型。由此，可以给出集成租船直运、跨航线调船、反挂和货物中转等解决策略的最佳多阶段重调度方案。通过对大、中、小规模的算例进行实验，实验结果表明，可知与传统等待办法相比，多阶段重调度节约了总航运成本的15%以上，验证了所提模型和方案的有效性；与Cplex相比，改进遗传算法的运算效率大大提高，且偏差值均在5%以内，而与蚁群优化（ACO）算法、禁忌搜索（TS）算法、量子差分进化（QDE）算法相比，改进遗传算法能在有效时间内降低10%左右的成本，验证了算法的科学性。所提方法可为班轮公司的实际船舶调度提供参考。

关键词: 水路运输, 班轮多船型船舶调度, 改进遗传算法, 多阶段重调度机制, 时间滚动, 恶劣天气