张　敏王　燕　薛　景　李　重

（南京工业大学交通运输工程学院　南京　210009）1（南京邮电大学计算机学院　南京　210023）2



航运调度中的自动化研究

张敏1王燕2薛景2李重2

（南京工业大学交通运输工程学院南京210009）1（南京邮电大学计算机学院南京210023）2

摘要首先，考虑时间窗、载货率、分批多次运输等因素，我们建立船舶调度模型，最小化碳排放量。然后，我们用贪心算法先得出多个较优解。之后，我们将贪心得出的解和其他随机解作为初始解，用遗传算法进行求解，研究结果表明：本方法可以有效的减少二氧化碳的排放，在较短时间内制定船舶日程表。这为编写船舶自动调度软件奠定基础，有助于提高船舶调度领域中的自动化程度。

关键词船舶调度时间窗低碳环保贪心遗传算法

一、引言

绿色航运系统是指航运公司从装货点到达卸货点，在满足卸货点需求量和时间窗要求，不超载，不超速等要求的情况下，满足经济航速、低碳战略的要求。模拟退火方法具有收敛速度快，全局搜索的特点，Osman［1］对车辆路径规划问题（VRP）的模拟退火算法进行了研究，他提出的模拟退火方法主要适合于解决路线分组。遗传算法具有求解组合优化问题的良好特性，Holland［2］首先采用遗传算法（GA）编码解决VRPTW问题。本文根据Min Zhang［3］等人的研究，考虑了大量现实情况，将遗传算法［4］、贪心算法和实际约束联系起来。设计一种能够解决复杂的约束条件的算法，是我们能够制定更有效的航运计划，符合绿色航运系统的要求。

二、算法设计

现有一配送中心使用若干船舶向若干客户送货，配送中心的装货时间窗，每个客户的需求量、需求紧急程度、收货时间窗已知，任一客户可被多次访问，任一船舶可多次出航，直至满足所有需求。

1、贪心遗传算法步骤

船按到达配送中心时间决定出发顺序，以客户重要程度和时间窗的约束（一般时间窗紧迫的客户重要性会比较高）决定船走的路线：船到达第一重要客户i需装的货小于船的最小载货量就前往次重要的客户j，直至船的载货量大于最小载货量小于最大载货量。然后安排下一艘船，直至得到可行的较优解。

本文设计的贪心遗传算法基本步骤如下：

①选择编码方式；

②使用贪心算法得到的可行解，及产生随机解作为初始种群；

③计算初始种群的适应值；

④满足终止条件，则终止；

⑤不满足终止条件｛

交叉｛

If（新解适应值大于旧解）

选择新解

Else

选择旧解

｝

变异｛

If（新解适应值大于旧解）

选择新解

Else

选择旧解

｝

计算适应值；

｝回到④。

2、初始种群的建立

（1）编码方式的选择

解采用自然数数组的表示方式，用0表示配送中心，用1，2，3…n表示客户。

（2）产生初始种群

由贪心法可以得到可行解，放入初始种群中。一般而言，将贪心得到的解分解为所有船从配送中心出发的次数接近最优解。所以初始种群的长度大体固定，即从配送中心出发的次数比贪心解增减2。每次从配送中心出发后途经随机不超过总客户数的点后，返回配送中心，且客户不重复。按以上方法产生一定量的随机解。

交叉变异生成新的种群后，比较新生成的子代和相同位置父代的适应度，若父代更好，就用父代取代子代。当适应度差别较大时，比较所有个体的适应度，复制最好的5个个体，同时删去最差的5个个体。

（3）染色体拆分为可行解

每个解由一串数字组成，0作为分界线可将这串数字拆分为多段。例如12034056可由0分为12，34，56。将前后补足起始点和终点，变为0120，0340，0560。由于有V艘船，可将这些数字串按顺序分给船，作为船的运行路线。如12034056这个解代表船一走0120，船二走0340，船三走0560。

（4）分配卸货量

按照顺序遍历V艘船的路径。解拆分后，每艘船可能得到多段路径，每一段代表着船出行一次。按顺序遍历每艘船的k段路径。一段路径由0和m个不重复的非0数字组成，这m个数字代表船要途经的m个客户。这条船的载货量为在这m个客户的卸货量之和。先计算这m个客户的总需求量，若大于船的最大载货量，则按事先设定好的每个客户的重要性（根据截止时间远近，客户重要等级等因素决定）顺序卸下该客户的需求量，即优先满足重要客户，船的载货量为船的最大载货量；若小于船的最大载货量，则按这段路径的顺序卸下该客户的需求量，船的载货量为途经客户的卸货量和。同时在船途经的每个客户i对应的位置记录这艘船这次出行在该点的卸货量。

（5）适应值的计算

一个较优解应该尽可能满足时间窗的要求和客户的需求。一个解是一串数字，这串数字除了0之外有num个数字，这些数字代表着船要途经的客户，因此，每个客户至少出现一次，否则必然得不到可行解。如果有客户没有出现，就给予无限大的惩罚pmax，不需要进行之后的计算。将解拆分后，按照顺序遍历V艘船的路径，每次船出行的载货量若小于最小载货量，则不能出行，因此给予一个较大的惩罚p1。遍历船每次出行途经的客户，若船途经一个已经没有需求的客户i，属于排放过多二氧化碳，因此给予较小惩罚p2；若船途经客户i时，已经超过i的卸货时间，给予惩罚p3，使p2＜p3＜p1。当遍历完船的路径，若仍有客户需求没有被满足，则实际中客户满意度将大大降低，所以给予最大的惩罚p4。则适应度为：

适应度值越小越好。

（6）终止条件

一个解满足所有的时间窗要求和客户需求，且碳排放比已知解更少则终止。或发生早熟，交叉无法产生新的可行解，变异产生新解的速度也过慢，就停止。

（7）交叉

①基于次序的杂交：从父代中选择数量相同位置的集合，产生二进制的掩码串。将父代A中掩码为0的位置复制到子代a中相同的位置上，其余位置用父代B相同位置的基因填充。将父代B中掩码为0的位置复制到子代b中相同的位置上，其余位置用父代A相同位置的基因填充。从而产生两个新的子代。例如01032505404670780808和01023605054707808，选取第2到10位进行杂交，结果为010226054547670780808和010335050044707808。通过删除多余基因和添加缺乏基因使子代合法化。

②部分调度交换杂交：将染色体切换成一段段的路径，将第n段的父代a和父代b交换，产生新的子代a，b。通过删除多余基因和添加缺乏基因使子代合法化。

（8）变异

随机选择一条染色体，观察其适应度高低，若不是优秀的个体，则发生变异。随机选择一个非0基因，将其插入该染色体中的某一随机位置。

参考文献

［1］Osman I H. Meta-strategy simulated annealing an Tabu search algorithms for the vehicle routing problem［J］. Annu Oper Res，1993，41：77～86.

［2］John Holland. Hidden order：How adaptation builds complexity［M］. Basic Books，1996.

［3］Min Zhang，Yoshiaki Ishihara，Ahusaku Hiraki. Ship Scheduling by Pure Car Carries with Time Windows and Split Loads in Changeable Speeds［J］. Japan Industrial Management Association，2013.7，356-365.

［4］玄关男，陈润伟.遗传算法与工程优化［M］.北京：清华大学出版社，2012.

张敏（1984～），女，南京工业大学交通运输工程学院，讲师。

王燕，女，南京邮电大学计算机学院，本科生。

薛景（1980～），男，南京邮电大学计算机学院，讲师。

李重，男，南京邮电大学计算机学院，本科生。

Research on the Shipping Scheduling Automation

Zhang Min1Wang Yan2Xue Jing2Li Zhong2
（College of Transportation Science & Engineering，Nanjing Tech University Nanjing 210009）1（School of Computer Science & Technology，Nanjing University of Posts and Telecommunications Nanjing 210023）2

AbstractFirst，considering time windows，load factors，batch shipment，we set up ship scheduling model to minimize carbon emissions. Then，we use the greedy algorithm to obtain several optimum solutions. After that，we take the above solutions and other random solutions as initial solutions，and use genetic algorithm to solve the problem. Results show that：This method can effectively reduce the carbon emissions，create schedules for ships in a relative short period of time.

KeywordsShip scheduling Time windows Low-carbon environmental-friendly Greedy genetic algorithm

中图分类号O221.4

文献标识码A

文章编号160323-7235

作者简介