Abstract: The multi-type liner scheduling problem in liner enterprises caused by the fluctuation of cargo demand and tide with line schedule announced in advance was studied. Firstly, the structure of near-sea transportation routes of a liner enterprise was systematically analyzed. Then, with the consideration of the real situations like large ships need to tide in and out of ports, ship renting is permitted under appropriate conditions, and the limits of a liner schedule, a nonlinear programming model of multi-type liner scheduling was built with the objective of minimizing the total transportation cost. Finally, in view of the characteristics of the model, an Improved Genetic Algorithm (IGA) embedded with gene repair was designed to solve the problem. Experimental results show that the proposed liner scheduling scheme can improve the ship utilization ratio by 25%-35% compared with the traditional experiential liner scheduling scheme, the CPU processing time of IGA is reduced by 32% on average compared with CPLEX in medium scale, and the transportation cost of IGA is reduced by 12% on average compared with ant colony algorithm in medium and large scales. All above demonstrates the validity of the proposed model and algorithm which can provide a reference for liner enterprises in liner scheduling.

Key words: multi-type liner scheduling, liner schedule prediction, nonlinear programming, variable speed, tide

摘要： 针对班轮企业由于提前公布船期表，但受货运需求的波动和潮汐的影响引起的多船型船舶调度问题进行研究。首先系统分析了一家班轮企业近洋运输航线结构；然后考虑大型船舶需乘潮进出港口，以及适当条件下允许租船的实际情况，兼顾班轮船期表的限制，构建了以运输总成本最小为目标的班轮多船型船舶调度非线性规划模型；最后考虑模型的特点，设计了嵌入基因修复的改进遗传算法（IGA）用于模型求解。实验结果表明，与传统的经验调度方案相比，得到的船舶调度方案在船舶利用率上能提高25%~35%；中规模算例下与CPLEX相比，IGA的CPU处理时间平均降低77%；中、大规模算例下与蚁群算法相比，IGA计算的运输费用平均降低15%。实验结果验证了所提模型和算法的有效性，可为班轮企业船舶调度提供参考。

关键词: 班轮多船型船舶调度, 船期表预知, 非线性规划, 可变航速, 潮汐