软时间窗与随机航行时间的不定期船舶航线规划

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

(上海海事大学 科学研究院， 上海 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]，因此其随机性较大；其次，码头的设备数量和规模有所限制，船舶特别是大型船舶卸货时间也较长，因此时间窗是不容忽视的；此外，船舶载货量大，一般是单次行程服务于多个需求点，再回到配送中心的.本文是在研究VRP问题[5-7]的基础上，将其方法扩展应用到不定期船舶调度问题，船舶运输需要在路径优化时同时考虑不确定航行时间及需求时间窗，这两个因素的引入都会使得原本就是NP-Hard的TSP问题更加复杂，用线性近似的方法来消除不确定航行时间的影响[8]，通过惩罚函数的引入表示需求时间窗.运用扫描法[9]和禁忌搜索算法，将问题分为二个阶段，第一阶段，通过扫描法将VRP转化为TSP，然后用禁忌搜索算法[10]解决TSP.

1 问题描述和符号表示

1)物流配送中心的位置为已知且唯一，设置配送中心为0；

2)需求点的位置及需求量已知；

3)需求点与需求点的线路与距离为已知且确定；

4)船舶经过需求点时只有卸货而无装货，货物配送完毕后以空船返回配送中心；

5)船舶的最大载重量相同.

表1 各需求点的需求量和坐标

表2 各港口之间的随机航行时间分布情况、卸货时间以及时间窗

符号表示：a：单位航行成本；b：每使用一艘船的固定成本；c：船舶早于时间窗到达的惩罚成本；d：船舶晚于时间窗到达的惩罚成本；Q：船舶最大载货量；wi：船舶k为了满足港口i的时间窗约束，在港口外的等待时间;dij：港口i到港口j的距离;qi：港口i的需求量;qik:港口i由船舶k运输的量;

opi：港口i的卸货时间；[ei，li]：港口i的时间窗.

2 数学模型

目标函数：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

qij≥0,wi≥0,

(9)

yik=0或1 ∀ixijk=0或1 ∀i，∀j.

(10)

式(1)表示确保船舶不超过最大载重量；(2)保证每个节点的运输需求均被满足；(3)保证每艘船舶都是始于母港，访问客户节点后，最后又回到母港；(4)和(5)保证每艘船最多访问每个客户节点1 次，且访问后必须离开；(7)表示每个节点至少被访问一次.

3 算法研究

算法的思想：以确定的航行时间求得初始解，再构造虚拟时间窗，以虚拟时间窗的惩罚函数代替初始的惩罚函数，进行两次求解，最后获得修正解.

3.1 不确定性航行时间的近似处理

图1 随机航行时间的线性近似图Fig.1 The approximate linear figure of random sailing time

3.2 虚拟时间窗的构造

软时间窗下惩罚函数：

虚拟时间窗下的惩罚函数：

3.3 求解所用的方法

3.3.1 扫描法 Gillett和Miller于1974年所提出的求解车辆路线问题的方法，此方法属于先分群再排路线的方式.该方法采用极坐标来表示各需求点的区位，然后任取一需求点为起始点，定其角度为零度，以顺时钟或逆时钟方向，以车容量为限制条件进行服务区域之分割，进行车辆配送的分组作业，由此实现将VRP转化为TSP.3.3.2禁忌搜索法 禁忌搜索算法最早是由

Glover 提出的，它是一种“局部搜索”的修正方法，从一些初始解开始，试图找到更好的解，然后从这个新的解开始，继续寻找好的解，这一过程不断重复，直到找到的解不再改善为止.

4 求解过程

采用“先分组再排线路”的二阶段求解方法，进行配送线路的安排.

4.1 构造初始解

以扫描法为基础，修改其演算方法进行初始解的构造，此算法可以达到先分组的目标，而且此方法在选择配送点进行求解时，可以将临近的点选入同一群组中，满足初始解的基本需求.而在船舶路线规划方面，在构造初始路线时，加入“船舶载重限制”的条件，使得初始解的每一群组均能满足此限制.

4.2 禁忌搜索

禁忌搜索的步骤如下：

1)输入需求点的数据；

2)设定参数，禁忌名单长度设为4，最大重复搜寻次数设为100；

3)目标函数和移步.

在计算目标函数值之前，首先建立一个对称矩阵，存放两两需求点之间的距离.计算目标函数值时，使用点对交换(Pair Swap)的节点交换法作为禁忌搜索法的移步方法，来达到临近搜寻的目的.

表3 需求点之间的距离

4.3 最优解的改善

建立初始解所使用的扫描法，被纳入组中的需求点就无法在不同的路线中跳动，得到较差的初始解结果.此处使用两种不同线路中交换节点的方法来弥补这个缺陷，期望能在需求点尽量相邻的条件下，找出更好的路线规划.

4.4 求解结果

以0点为原点，任意做一条射线，逆时针方向扫描，得到7种初始解，如表4所示.

表4 扫描法求解结果

表5 最终求解结果

图2 航线规划最终结果Fig.2 The end results of route planning

5 结束语

航行时间为随机时候的总成本是1 000.6，比航行时间是确定值的时候的998.8多了1.8，这说明随着航行时间不确定性的引入，带来了时间窗惩罚成本的上升.海上运输担负着将近90%的海上货运量，国内外对公路运输的研究文献很多，相比之下，对船舶航线，特别是不定期班轮航线的研究不多，由于不定期船舶运输没有固定的船期、固定的航线、以及固定的挂靠港，因此对于不定期船经营公司来说，如何规划船舶航线是十分重要的问题.本文根据船舶运输的特点，将其抽象为随机航行时间且带有需求时间窗的多重旅行商模型.运用扫描法和禁忌搜索算法，将问题分为二个阶段，第一阶段，通过扫描法将VRP转化为TSP，然后用禁忌搜索算法解决TSP，并通过算例证明了算法的有效性，本文中所用到的算法，为实际不定期船舶的航线规划提供了参考.

[1] Meng Q， Wang S， Henrik A，et al. Containership routing and scheduling in liner shipping: Overview and future research directions[J]. Transportation Science， 2013， 0461:1-16.

[2] Archetti C， Bouchard M， Desaulniers G. Enhanced branch and price and cut for vehicle routing with Split deliveries and time windows[J].Transportation Science， 2011， 45(3)： 285-298.

[3] Zheng Y， Liu B. Fuzzy vehicle routing model with credibility measure and its hybrid intelligent algorithm[J]. Applied Mathematics and Computation， 2005， 176(2)：673-683．

[4] 靳鹏欢，随机因素影响下的不定期船航次优化研究[D]. 大连：大连海事大学， 2012: 1-11．

[5] 李 娜. VRP在支线船舶调度中的扩展应用研究[D].大连：大连海事大学， 2006; 1-41．

[6] 谢秉磊， 郭耀煌， 郭 强. 动态车辆路径问题：现状与展望[J]. 系统工程理论方法应用， 2002， 11(2): 116-120．

[7] Archetti C， Feillet D， Gendreau M， et al. Complexity of the VRP and SDVRP[J]. Transportation Research Part C， 2011， 19: 741-750.

[8] 戴 韬， 杨稀麟. 考虑时间窗与随机航行时间的船舶航线规划[J]. 计算机工程与应用，2012， 48(25)：234-238．

[9] 邱爱华. 扫描法和遗传算法在物流配送车辆优化调度中的应用研究[D]. 北京：北京交通大学，2008: 1-42．

[10] 郎茂祥， 胡思继. 车辆路径问题的禁忌搜索算法研究[J]. 管理工程学报，2004， 18(1)：81-84．

Tramp ship routing plan with soft time window and random sailing time

DING Yi， ZHONG Ying， LIN Guolong， WEN Xin

(Institute of Science， Shanghai Maritime University， Shanghai 201306)

This paper is based on the study of VRP problems， and the method is extended to tramp scheduling problem， using a linear approximation method to eliminate the uncertain effect of the time of sailing and introducing a penalty function to deal with the time window. Using the scanning method and the tabu search algorithm， which divided the problem into two stages， the scanning method converted the VRP into TSP. Then the tabu search algorithm was utilized to solve the TSP with an example to prove the performance of the proposed algorithm. which provided a reference for the tramp ship when making route plan．

time window; stochastic travel time; ship route planning; scanning method; tabu search algorithm

2014-12-24.

国家自然科学基金项目(71301101)；上海教育委员会科研创新重点项目(11ZS1145)；上海市教委重点学科资助(J50704)．

1000-1190(2015)03-0387-05

U697.1

A

*E-mail: yingzhongbs1@163.com．