基于模拟退火遗传算法的内河港口船舶进出港调度方法

李於彬

(中铁长江交通设计集团有限公司,重庆 400121)

0 引 言

经济全球化的发展,使得水路运输的运量不断上升,船舶也逐渐向高速化、大型化的方向发展。进出港船舶数量的大幅增加,造成港口资源中的航道、泊位等配置紧张,船舶进出港耗费大量的时间,港口服务的满意度逐渐下降[1]。在不大幅改变港口硬件设施的条件下,对船舶进出港的调度方案进行优化处理,提高进出港的效率,可以有效避免或减少港口船舶压港、滞港等现象[2]。

增加港口规模,能够有效改变港口拥挤的状态,但是港口的扩建需要消耗大量的经费,建设周期过长[3]。对于内河港口来说,利用优化算法调整船舶进出港口的调度方案,优化船舶的进出港时间,能够最大效率的发挥港口的作用,改善港口的通航效率。在相关方面的研究中,郑红星等[4]综合考虑了船舶进出港受到的约束条件以及泊位的工作约束情况等,通过建立进出港调度规划模型,利用算法分析确定各类船舶的进出港最优时间段,大幅提高了港口的运行效率。Kim K H[5]等在船舶进出港模型中,考虑了船舶停靠的具体位置和具体时间,并利用成本最优的优化调度方式,采用模拟退火算法获得模型的最优解,取得了不错的效果。

本文针对内河航道中船舶进出港的调度问题,研究了基于模拟退火算法和遗传算法的调度模型,综合考虑船舶进出港过程中的速度、距离、泊位以及装卸时间等因素,发挥两种算法的优势,实现资源调度的最优化。通过试验结果证明,求解后的调度模型可以有效提高港口的船舶进出港效率,降低资源消耗并提高港口的经济效益,为类似内河港口的调度方法研究提供了参考。

1 内河港口调度

1.1 传统调度方法

传统的船舶调度,以“先到先走”的服务模型为基础。进入港口的船舶,通过调度安排进入航道,到达指定泊位后进行停泊装卸作业[6]。而其他未通过进港审核的船舶,则需要在锚地等待,待泊位内的船只完成作业后,安排其进港,调度效率较低。

船舶符合出港的条件时,同样向调度中心发出申请,由中心对其出港进行调度放行。由于调度或其他原因,出现进出港船舶冲突的情况时,安排船舶原地等待,待问题解决后,依次排队出港[7]。

由于这种人工操作的船舶调度方式,运行效率主要依靠工作人员的个人经验,使得船舶通行效率受到严重影响。大量的物资滞留,也会造成巨大的经济损失,迫切需要具有多目标协调的能力的调度方法来实现船舶调度高效率运行[8]。

1.2 内河港口调度约束条件

对于内河港口的船舶调度来说,除了需要考虑船舶的进出港时间,还需要考虑内河航道上是否存在其他船舶,航道内这些非调度的船舶运行状态,同样会对港口的调度效率产生严重影响,需要综合考虑[9]。

对于港口的船舶进出港调度模型来说,如何在确保船舶安全的前提下,实现船舶的进出港操作,最大限度的保证港口的运转效率,是调度模型需要处理的核心问题和关键所在[10]。

一般情况下,船舶在锚地等待的时间越短,港口的运转效率越高。从而可以在船舶调度模型的建立中,在全面考虑调度公平性的前提下,以船舶在港口的等待时间作为港口调度模型效果的衡量指标,进行进出港调度[11]。

在综合考虑船舶安全性的前提下,调度模型的约束条件主要包括三个方面:航道尤其是潮汐航道内的船舶进出港时间、泊位问题、安全距离等。

对于被调度进出港的船舶,需要保证其在此行进过程中与其他同向船舶之间安全距离。因此需要在调度中,要求后方船舶的航行速度不能超过前方船舶,避免意外碰撞的发生[12]。安全调度距离涉及到的参数包括船舶的航速和两者间的距离等。一般情况下,为了保证船舶间的安全性,要求两者的安全距离大于船体平均长度的六倍。在船舶同向行驶的过程中,需要前后两船之间具有足够的速度差或距离差,从而在前船到达目的地时,与后船的距离保持在安全距离以外。

两艘同向行驶船舶的安全时间间隔,可以用公式表示为

θij≥Xij×

(1)

式中:Vi和Vj分别为i,j两船航行的速度;Ti和Tj分别为i,j两船从出发到目的地之间行驶的时间;Li为船舶i的自身长度;Xij为两船的关系系数,当两者是前后船的关系时,取值为1,否则取0。

泊位的调度过程中,需要保证剩余泊位长度大于船体长度。对于长度较大的船体,当其进港时,需要保证在其到达泊位的时间内,离开的船体长度可以为其提供足够长的泊位位置。

2 模拟退火遗传算法

2.1 模拟退火算法

模拟退火算法主要是模拟工业技术中的退火工艺,其工艺原理为,利用高温提高材料内部的原子动能,提高其热运动能力,进而回到自身最优化的位置[13]。

模拟退火算法中的主要参数包括初始温度、升温速率、恒温温度等。通过调整计算过程中的温度参数,通过组合迭代的关系,找到问题的最佳答案。

2.2 遗传算法

遗传算法的工作原理来自于达尔文的进化论理论,该算法主要通过染色体的变化,结合实际应用,利用不同种群之间的交叉、变异和选择的步骤的操作,找到求解问题的最优解。

遗传算法的主要计算流程为:获取初始种群,利用适应度函数对种群加以评价,选择所有初始个体中的最佳个体作为父代,与其他染色体进行交叉、变异操作,形成新的子代。继续利用适应度函数对其进行评价,直到找到最优解。

2.3 模拟退火与遗传算法的结合

模拟退火算法与遗传算法在最优解的寻找方面都具有各自的优势,将其有机结合形成融合算法,既能够增强算法的全局搜索能力,又可以有效避免出现算法早熟的现象。

利用融合后的算法求解船舶进出港的调度序列问题,可以首先利用遗传算法的染色体规则来描述模型的船舶,并根据算法中的决策变量xij来设计染色体。

船舶在进出港的过程中,时间具有随机性,因此需要对决策变量xij进行拆分,将所有参与到调度进港的船舶分成进港和出港两个决策变量。设染色体A表示进出港船舶的顺序,对其进行实数编码,同一个泊位的先后两艘出港船舶代表泊位使用的先后顺序[14]。

对于调度队列同样利用自然数进行编号,其序号为队列顺序编码,与船舶到达时间一致。利用染色体对于出港船舶进行编码,编码的顺序由实际规则参数决定,对于同一泊位中的船舶,其编码反映了其进出港的先后顺序。

2.4 融合后算法的优化

遗传算法中,交叉算子对于进化起到决定作用。交叉规则能够有效提高种群内染色体的搜索范围,并能够将优秀的染色体加以保存,避免由于交叉破坏原有的计算结果。采用的混合交叉操作如下。

根据染色体的长度,以随机的方式产生多段染色体交叉序列。根据合适的位置选择,来交换对应的染色体基因片段。对于基因结合后出现冲突的染色体进行检测,并根据情况进行修复。

变异算子的作用在提高算法的搜索能力,利用基因突变的原理,避免过早出现算法收敛。

计算过程中,遗传算法的变异概率Pm和交叉概率Pc一般是通过试验测试来获得的。这些参数的一成不变使得当系统工作条件发生变化时,算法的计算结果与实际情况严重不符,造成算法失效,影响整个港口的调度运行。

为了提高整个模型的搜索范围,需要提高模型的交叉概率,从而保证新染色体的出现,避免出现计算过早收敛、不能找到最优解的情况。但是过高的交叉概率又会造成计算前期的搜索结果不具备代表性。因此对于染色体交叉概率的设置,需要符合一定的规则,既不能一成不变,又不能超出范围,需要随着种群的变化而改变。

在算法的设计中,对于需要提升种群进化速率的情况就要提高交叉概率,对于需要保护染色体的情况,则需要降低交叉概率。

模型的交叉概率可以用函数形式来表示,计算公式表示为

(2)

式中:Pc1代表染色体交叉概率的上限;Pc2代表染色体交叉概率的下限;γ为系统优异程度的比值,代表当前优秀个体与群体内最优个体之间的差距程度。在差距较大时γ较小,需提高整个模型的交叉概率,刺激染色体变化。

同样,对于模型的变异概率,如果变异概率太小,则容易使算法陷入局部最优,而无法获得全局最优解。如果变异概率过大,则会使优秀个体发生变异,同样出现找不到最优解的情况。

为此,同样需要变异概率利用公式。其表示式为

(3)

式中:Pm1代表染色体变异概率的上限;Pm2代表染色体变异概率的下限;γ为系统优异程度的比值。

通过交叉概率和变异概率的变化,能够动态调整系统模型参数,对于整个模型求解效率的提高具有重要意义。概率的调整随着种群而变化,使其符合种群规律,且每一次的变化均符合自适应变化规律。这种动态调整参数的方法,能够有效提高遗传算法的效率,避免出现找不到最优解的情况。

3 实验结果与算法验证

3.1 实验条件设置

为了验证该模型的有效性,利用Matlab 2017b软件对于算法进行验证。在计算机上进行算法计算,电脑配置为:CPU i5-65003.2 GHz,内存8 Gb。

实验数据以重庆港数据为例,进行算法的验证。港区航道水深6.2 m,均为双向航道,港内共有十个泊位,依次为泊位1,泊位2,……,泊位10。候泊区水深约为5.3 m,作业区的宽度为2n mile,长度为2.7n mile,为长方形区域。设定各船舶的平均速度相同,均为7节,以提高系统计算效率。泊位信息如表1所示。

表1 泊位信息

设定混合算法中模拟退火算法的初始温度为100 ℃,终止温度设定为1 ℃。

温度下降策略为指数下降,表示式为

Tk+1=0.9Tk

(4)

式中:Tk为k时刻的温度。

设定初始种群内个体的数量为500,交叉概率初始值为0.7,变异概率初始值为0.2。

3.2 实验结果对比

(1)调度结果

以该港口在12月中旬某天的数据为参考,船舶停靠数据规范后如表2所示。

表2 规范后的船舶停靠数据

利用上述算法,对整个船舶的调度进行排序和安排,综合考虑各船舶的出发时间以及船体长度的限制,出发时间早且符合进出港调度长度的船舶先安排,出港时间晚的后安排,综合考虑船舶停靠时间的要求。优化后排序结果为8、4、2、13、12、14、5、3、7、15、1、11、6、9、10。

使用上述算法对该港口进行船舶调度,最终对所有船舶调度形成一个调度序列,总体调度的结果为使得船舶总等待时间为1 075 min,平均等待时间为72 min。具有较好的公平性,并能有效保证船舶通航的效率。总体结果,符合模型的预期。

(2)算法对比

对其船舶数据进行扩充,利用相同的潮汐数据和泊位情况进行对比。分别设定总调度的船舶数量分别为20艘、30艘和40艘,进出港的船舶数量各占一半。

在相同的条件下,利用常用的船舶调度算法与上述算法进行对比,船舶总等待时间的对比结果如表3所示。

表3 不同算法船舶总等待时间对比情况

从表3中可以看到,对于所有算法的总调度时间均会随着船舶的数据增多而呈现增加的情况,且船舶数量越多,等待时间也就越长。但从计算结果上看,改进后算法还是要优于其他两种算法的。

当船舶为20艘时,改进后算法的平均等待时间约为1 185 min,而FCFS算法和Random算法的平均等待时间分别约为1 625 min和4 231 min。当船舶为30艘时,改进后算法的平均等待时间约为1 525 min,而FCFS算法和Random算法的平均等待时间分别约为2 621 min和8 064 min。当船舶为40艘时,其他两种算法的差距更大,说明改进后算法的效率更高。

分析原因可知,FCFS 算法约束条件随着船舶的数量增多,而出现过多约束触发,因此等待时间越来越长。而Random 算法的随机性过大,存在大量的约束条件,这些约束条件的出现,使得船舶进出港的调度,需要大量的等待时间,甚至在船舶过多时出现了调度冲突的情况。

(3)算法的收敛性

为了证明改进后算法的收敛能力,以20艘船舶调度迭代曲线为例,使用混合调度算法的收敛结果如图1所示。

图1 改进后算法的收敛曲线

可以看到,改进后算法在收敛过程中,先是在一个大的范围内进行搜索,发挥种群多样性的优势,最终使得种群均值与最优解重合,算法在第205代左右发生收敛,完成船舶调度的寻优过程。

(4)同类算法对比情况

为了证明模拟退火遗传算法的优势,比较其与其他遗传算法的性能对比情况。在相同的运行环境中,将算法与CWSGA遗传算法进行对比。同样考虑船舶数量为20、30、40艘的情况,对比结果如表4所示。

表4 不同算法船舶总等待时间对比情况

从实验结果的总体来看,相比CWSGA算法,改进后算法的调度结果更优。在20、30、40艘的情况下,改进后方法船舶的等待时间均小于CWSGA算法,证明改进后算法的调度能力更强,调度效果更好,更适合用于内河港口的进出港调度问题。

4 结 论

针对内河港口船舶进出港的调度问题,研究了基于模拟退火遗传算法的调度策略研究。通过分析船舶调度的约束条件,充分发挥模拟退火算法和遗传算法的优势,对遗传算法中的交叉因子和变异因子进行优化,使其更符合船舶调度的应用要求。通过实验结果验证,改进后的算法,对于内河港口的船舶调度能够有效给出最优方案。将改进后算法与其它算法进行对比,改进后算法的计算效率更高,船舶的等待时间更短。在不改变港口规模的情况下,利用改进后的调度方法,能够有效提高港口的效率,为水路运输事业的发展提供思路。