郑红星 王泉慧 任亚群

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

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

中图分类号： U692.4+3

文献标志码：A

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

0 引言

虽然班轮企业都会提前一个月左右公布船期表，但由于货运市场的起伏波动，以及天气和其他不确定因素的影响，使得每艘船舶的挂靠港口次序和每次运营的航线是不确定的。因此，为了尽可能保证货物按原船期表进行运输，并充分利用船队资源，提高航运企业的服务效率，需运用科学合理的方法对船舶调度进行优化。

船舶调度问题一直是相关各方研究的热点问题，是针对航运企业经营的每艘船，指定具体的航行路线、挂靠港口、运输任务及其运作时间表，通过合理的调度，高效利用船舶。……