丁 一， 仲 颖， 林国龙， 温 馨

(上海海事大学 科学研究院， 上海 201306)



丁 一*， 仲 颖， 林国龙， 温 馨

(上海海事大学 科学研究院， 上海 201306)

为优化航线设计，降低船舶企业运营成本，在研究VRP(Vehicle Routing Problem)的基础上，将其方法扩展应用到不定期船舶调度问题，船舶运输需要在路径优化时同时考虑不确定航行时间及需求时间窗，用线性近似的方法来消除不确定航行时间的影响，通过惩罚函数的引入表示需求时间窗，建立充分考虑时间因素的数学模型，以总成本最小为目标.运用扫描法和禁忌搜索算法，将问题分为二个阶段，第一阶段，通过扫描法将VRP转化为TSP(Traveling Salesman Problem)，然后用禁忌搜索算法解决TSP，通过算例证明了提出算法的有效性，为实际不定期船舶的航线规划提供了参考.

时间窗； 随机航行时间； 航线规划； 扫描法； 禁忌搜索算法

一般将船舶运输模式分为3类，分别为工业船运、不定期船运和班轮船运[1].不定期船运输是指无固定航线、固定挂靠港口和班期的一种船舶营运方式，在整个水路运输中占有相当高的比重.

对于带时间窗的VRP的研究， Archetti[2]等提出了第一个求解SDVRPTW (Vehicle Routing Problems with Split Deliveries and Time Windows)的精确算法，他们运用禁忌搜索算法和新的有效不等式对子问题分别求解，一种新的启发式算法则被用于寻找最优拆分点.

对于VRPST(Vehicle Routing Problem with Stochastic Travel Time)的研究，Zheng和Liu[3]运用一种混合智能算法求解车辆模糊旅行时间问题.

综上所述，国内外关于运输路径优化的问题，重点在于研究车辆路径问题，但是在国际贸易中，海上运输担负着将近90%的海上货运量，船舶航线规划问题与车辆路径问题相比较，有其自己的特性.首先，船舶单次的行程比较长，时间也更久，航行时间较容易受天气等多种因素的影响[4]，因此其随机性较大；……