考虑岸桥缓存区和能耗节约的AGV协同调度方法

[0018][0019][0020][0021]
f1表示岸桥实际作业时刻与预设作业时刻的差值，即当前作业延误对后续作业的影响。f2表示无论是因为agv等待岸桥或是岸桥等待agv造成的等待延误时间。f3表示岸桥和agv因等待延误所产生的能耗。f1、f2在总目标函数中所占权重为1-λ，f3所占权重为λ；
[0022]
(1.3)约束条件：
[0023][0024]
表示任意编号的任务其之前仅有1个任务；
[0025][0026]
表示任意编号的任务其之后仅有1个任务；
[0027][0028]
表示同一岸桥作业两个连续任务时，岸桥实际作业的时间间隔要大于等于岸桥预设作业的时间间隔；
[0029][0030]
表示岸桥实际作业时刻要晚于预设作业时刻；
[0031][0032]
表示对于出口集装箱任务，岸桥实际作业时刻要晚于agv到达缓存区的时刻
[0033][0034]
表示对于进口集装箱任务，岸桥实际作业时刻要早于agv到达缓存区的时刻；
[0035][0036]
表示任意时刻，岸桥缓存区内由岸桥卸载的进口集装箱数量agv运走的进口集装箱数量岸桥装船的出口集装箱数量agv送达的出口集装箱数量之和不能超过岸桥缓存区容量c；
[0037]
[0038]
表示对于进口箱任务，当时即岸桥将1个进口箱卸载到缓存区中；
[0039][0040]
表示对于进口箱任务，当时即agv将1个进口箱运离缓存区；
[0041][0042]
表示对于出口箱任务，当时即岸桥将1个出口箱装载到船上；
[0043][0044]
表示对于出口箱任务，当时即agv将1个出口箱运至缓存区；
[0045][0046]
为agv任务的0-1决策变量；
[0047][0048]
为缓存区容量约束的0-1决策变量。
[0049]
进一步的，步骤(3)包括以下步骤：
[0050]
(3.1)设置包括交叉概率pc、变异概率pm、初始温度t0、终止温度tend、链长length(每个温度下的迭代次数)的初始参数。
[0051]
(3.2)随机生成一定规模的初始解染色体组，并对其进行包括选择、交叉、变异的遗传操作后筛选出最优适应度值的染色体r1作为模拟退火算法的初始解；
[0052]
(3.3)r1随机交换2个基因位置，并使染色体合法化，生成新的染色体r2。
[0053]
(3.4)计算r1和r2染色体适应度值之差，记δ＝f(r2)-f(r1)，由于本文所求目标函数是求最小值，所以适应度函数为：f(λ)＝1/(1-λ)(f1+f2)+λf3。
[0054]
(3.5)如果δ＜0则代表新染色体r2的适应度值更小，接受新解r2；或根据metropolis准则(以一定概率接受结果较差的解)，以exp(-δ/t)的概率接受新解r2；
[0055]
(3.6)将r2存入临时染色体组temp_chrom；
[0056]
(3.7)判断：如果内循环迭代次数达到链长length，从temp_chrom中取出最优适应度值的染色体并存入最终染色体组final_chrom中；
[0057]
(3.8)判断：如果外循环温度达到设定的终止温度tend，这时从final_chrom输出最优适应度值的染色体，即最终的最优解，否则降低温度回到步骤b。
[0058]
进一步的，步骤(4)包括以下步骤：
[0059]
(4.1)当能耗目标权重为0时，仅考虑延误时间目标，通过改变缓存区容量(c)和agv数量(n)得到最优的c和n的数量组合；
[0060]
(4.2)选取最优c和数量n组合的基础上，增加能耗目标权重系数λ进一步观察并选取合适的agv调度方案。
[0061]
本发明的技术效果如下：
[0062]
本发明提供一种解决码头实际作业中由于岸桥和agv间的相互等待而产生能耗的方法。通过设置岸桥缓存区，对岸桥和agv设备之间进行解耦，将岸桥和agv从相互等待的状
态释放出来，从而去执行其他任务，增加了设备间的作业连续性。进而通过合理的agv调度方案，减少作业总延误时间和总延误作业能耗。本发明提出了考虑岸桥缓存区和能耗节约的agv协同调度研究方法。分别赋予时间目标和能耗目标一定的权重，构建了以总延误时间和各设备总等待延误能耗为目标的混合整数规划模型，并分别用传统遗传算法(ga)和遗传-模拟退火算方法(ga-sa)进行求解验证。
[0063]
其中，遗传算法(ga)：核心思想是通过不断地演变进化，挑选出适应度值最接近目标函数的染色体；遗传算法主要包括初始化种群，计算个体适应度值，选择，交叉，变异，终止条件判断几大步骤；具有良好的全局搜索能力，但是容易陷入局部最优解，产生过早收敛的问题；
[0064]
模拟退火算法(sa)：用问题的求解过程与熔化物体退火过程的相似性，采用随机模拟物体退火过程来完成问题的求解。模拟退火算法收敛速度较快，但是对于全局信息的把控不多，这不利于使搜索朝着最优解的方向前进。
[0065]
本发明的遗传-模拟退火算法(ga-sa)：结合遗传算法的全局搜索能力和模拟退火算法局部搜索和快速收敛的能力，设计遗传-模拟退火算法(ga-sa)。遗传-模拟退火算法主要是将遗传算法的结果作为模拟退火算法的初始解输入，这样既提高了初始解的质量，又可以在后续搜索最优解的过程中摆脱陷入局部最优解的情况。
[0066]
本发明的有益效果如下：
[0067]
(1)通过合理的agv调度方案，减少作业总延误时间和总延误作业能耗。
[0068]
(2)对于码头决策者在调度作业中提高设备作业连续性，节约能耗，实现绿色低碳优化调度具有参考意义。
附图说明
[0069]
图1为本发明实施例的总体流程示意图。
[0070]
图2为自动化码头作业示意图。
[0071]
图3为实施例所使用的遗传-模拟退火算法流程图。
[0072]
图4为实施例不同c和n组合下ga求解模型的最优目标函数值。
[0073]
图5为实施例不同c和n组合下ga-sa求解模型的最优目标函数值。
[0074]
图6为实施例n＝4时，不同c下的ga迭代收敛曲线图。
[0075]
图7为实施例n＝4时，不同c下的ga-sa迭代收敛曲线图。
[0076]
图8为实施例不同下作业延误时间和设备等待延误能耗的变化曲线。
具体实施方式
[0077]
为了更好的理解本发明，下面结合附图和具体实施例对本发明进行进一步的解释。
[0078]
实施例1
[0079]
为了更好地理解本发明的技术特征、目的和效果，下面结合附图对本发明进行更为详细地描述。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明专利。需要说明的是，这些附图中均采用非常简化的形式且均使用非精准的比率，仅用于方便、清晰地辅助说明本发明专利。
[0080]
本实施例提供了一种考虑岸桥缓存区和能耗节约的agv协同调度方法，如图1所示的总体流程示意图，该方法包括以下步骤：
[0081]
(1)以岸桥作业延误时间，岸桥和agv双向等待时间以及设备等待延误能耗为目标建立多目标混合整数规划模型；
[0082]
(2)结合遗传算法的全局搜索能力和模拟退火算法局部搜索和快速收敛的能力，设计了遗传-模拟退火算法(ga-sa)。将遗传算法(ga)的结果作为模拟退火算法(sa)的初始解输入，在提升sa初始解质量的同时还摆脱了ga陷入局部最优的情况；
[0083]
(3)用ga-sa算法对调度模型进行求解，并与传统ga算法做比对.
[0084]
(4)通过实例分析ga-sa在收敛速度和收敛效果上相对于单纯的ga有所提升。在选取缓存区容量(c)和agv数量(n)组合的基础上，增加能耗目标权重系数λ进一步观察并选取合适的agv调度方案；
[0085]
进一步的，步骤(1)包括以下步骤：
[0086]
(1.1)对构建的模型提出假设和对符号进行规定，其码头作业示意图如图2所示
[0087]
a)集装箱任务的装卸顺序和岸桥预设操作时间已知
[0088]
b)当agv到达堆场时，堆场起重机能够及时作业
[0089]
c)不考虑agv断电的情况，且agv一次只能运输一只集装箱
[0090]
d)任意岸桥下方的缓存区容量大小相等
[0091]
(1.2)目标函数：
[0092]
minf＝(1-λ)(f1+f2)+λf3[0093][0094][0095]
f1表示岸桥实际作业时刻与预设作业时刻的差值，即当前作业延误对后续作业的影响。f2表示无论是因为agv等待岸桥或是岸桥等待agv造成的等待延误时间。f3表示岸桥和agv因等待延误所产生的能耗。f1、f2在总目标函数中所占权重为1-λ，f3所占权重为λ。
[0096]
(1.3)约束条件：
[0097][0098]
表示任意编号的任务其之前仅有1个任务；
[0099][0100]
表示任意编号的任务其之后仅有1个任务；
[0101][0102]
表示同一岸桥作业两个连续任务时，岸桥实际作业的时间间隔要大于等于岸桥预设作业的时间间隔；
[0103][0104]
表示岸桥实际作业时刻要晚于预设作业时刻；
[0105][0106]
表示对于出口集装箱任务，岸桥实际作业时刻要晚于agv到达缓存区的时刻
[0107][0108]
表示对于进口集装箱任务，岸桥实际作业时刻要早于agv到达缓存区的时刻；
[0109][0110]
表示任意时刻，岸桥缓存区内由岸桥卸载的进口集装箱数量agv运走的进口集装箱数量岸桥装船的出口集装箱数量agv送达的出口集装箱数量之和不能超过岸桥缓存区容量c；
[0111][0112]
表示对于进口箱任务，当时即岸桥将1个进口箱卸载到缓存区中；
[0113][0114]
表示对于进口箱任务，当时即agv将1个进口箱运离缓存区；
[0115][0116]
表示对于出口箱任务，当时即岸桥将1个出口箱装载到船上；
[0117][0118]
表示对于出口箱任务，当时即agv将1个出口箱运至缓存区；
[0119][0120]
为agv任务的0-1决策变量；
[0121][0122]
为缓存区容量约束的0-1决策变量。
[0123]
步骤(2)中，
[0124]
(2.1)遗传算法(ga)：核心思想是通过不断地演变进化，挑选出适应度值最接近目标函数的染色体；遗传算法主要包括初始化种群，计算个体适应度值，选择，交叉，变异，终止条件判断几大步骤；具有良好的全局搜索能力，但是容易陷入局部最优解，产生过早收敛的问题；
[0125]
(2.2)模拟退火算法(sa)：用问题的求解过程与熔化物体退火过程的相似性，采用
随机模拟物体退火过程来完成问题的求解。模拟退火算法收敛速度较快，但是对于全局信息的把控不多，这不利于使搜索朝着最优解的方向前进。
[0126]
(2.3)遗传-模拟退火算法(ga-sa)：结合遗传算法的全局搜索能力和模拟退火算法局部搜索和快速收敛的能力，设计遗传-模拟退火算法(ga-sa)。遗传-模拟退火算法主要是将遗传算法的结果作为模拟退火算法的初始解输入，这样既提高了初始解的质量，又可以在后续搜索最优解的过程中摆脱陷入局部最优解的情况。
[0127]
进一步的，步骤(3)包括以下步骤：
[0128]
(3.1)设置交叉概率、变异概率、初始温度、终止温度、链长(每个温度下的迭代次数)等初始参数。
[0129]
(3.2)随机生成一定规模的初始解染色体组，并对其进行选择、交叉、变异等一系列遗传操作后筛选出最优适应度值的染色体作为模拟退火算法的初始解。
[0130]
(3.3)随机交换2个基因位置，并使染色体合法化，生成新的染色体。(3.4)计算和染色体适应度值之差，记。由于本文所求目标函数是求最小值，所以适应度函数为：。
[0131]
(3.5)如果则代表新染色体的适应度值更小，接受新解。或者根据准则(以一定概率接受结果较差的解)，以的概率接受新解。
[0132]
(3.6)将存入临时染色体组。
[0133]
(3.7)判断：如果内循环迭代次数达到链长，从中取出最优适应度值的染色体并存入最终染色体组中。
[0134]
(3.8)判断：如果外循环温度达到设定的终止温度，这时从输出最优适应度值的染色体，即最终的最优解，否则降低温度回到步骤b。
[0135]
本实施例所使用的ga-sa算法流程图如图3所示；
[0136]
进一步的，步骤(4)包括以下步骤：
[0137]
(4.1)选取以2台岸桥，20个集装箱任务为实例。运用遗传-模拟退火算法(ga-sa)进行求解，其中岸桥装载一个出口箱的时间设定为120秒，卸载一个进口箱的时间设定为110秒；
[0138]
表1各岸桥任务作业序号和预设作业开始时刻(单位：秒)
[0139][0140]
(4.2)λ＝0时的仿真结果分析：当λ＝0时，即仅考虑时间目标，不考虑能耗目标时，目标函数变为：
[0141][0142]
为了得到最优的目标函数解，通过改变岸桥缓存区容量从c＝2至c＝9变化，以及改变agv数量从c＝3至n＝7变化。观察目标函数值的变化趋势，以找到最优的c和n组合，图4和图5分别为不同缓存区容量和agv数量下遗传算法(ga)和遗传-模拟退火算法(ga-sa)求解调度模型的最优目标函数值变化曲线。从图4和图5可以直观的看出，对于2台岸桥的20个任务，agv的数量设置为4辆是最合适的，能够使得作业效率最大化。
[0143]
图6、图7分别为＝4时，两种算法在从2变化至9时的迭代收敛曲线图，从图6可以看出，遗传算法最快能在80代左右达到收敛，大部分曲线要100代以后收敛。目标函数值最小能收敛到700左右，大部分分布在1500上下。从图7可以看出，遗传-模拟退火算法最快能在20代左右达到收敛，大部分曲线在60代以前收敛。目标函数值最小能收敛接近于0，大部分分布在500上下。为了进一步分析不同缓存区容量约束下agv的调度问题，量化比较不同缓存区容量，不同agv数量情况下的目标函数值。在matlab中运用遗传-模拟退火算法求解，每种情况运行10次，取均值，实验结果如表2所示。最优调度方案取合适c和n组合下的目标函数均值对应的个体。
[0144]
表2不同缓存区容量和agv数量下的目标函数均值(单位：秒)
[0145][0146]
从表2中可以知道，目标函数均值最小值为111，在c为8，n为4时取到。n为4时的目标函数均值普遍较小，且c在增加到5之后变化幅度较小。本着资源节约的角度出发，对于2台岸桥，20个集装箱任务的港口agv调度方案选取c为5，n为4，目标函数均值为174。具体的调度方案如表3所示。
[0147]
表3缓存区容量为5，agv数量为4时的agv调度方案
[0148][0149]
(4.3)λ≠0时的仿真结果分析：当时，既考虑时间目标，又考虑能耗目标，目标函数变为：
[0150][0151]
由(4.2)分析结果知，对于2台岸桥20个集装箱任务而言，缓存区容量为5，agv数量为4时，整体作业延误时间较低，设备间连续作业性较好。因此在此基础上，考虑能耗节约目标，通过改变能耗权重系数λ，改变能耗目标在总目标函数中的权重比，观察时间目标函数和能耗目标函数的变化，找到合适的权重配比。在matlab中运用ga和ga-sa算法求解，每种情况运行10次，最后取均值并得出收敛曲线；
[0152]
实验数据如表4所示，其中f
′
＝f1+f2。将表中的数据用折线图表示如图8所示。
[0153]
表4 c＝5,n＝4时两种算法求解对比结果
[0154][0155][0156]
(4.4)分析比对算法：对两种算法求解得出的仿真收敛曲线进行对比分析，发现两种曲线变化趋势大致相同，但ga-sa算法的收敛速度和收敛效果远优于传统ga算法。
[0157]
(4.5)分析实验结果：对于2台岸桥20个集装箱任务，在c为5，n为4时，目标函数收敛效果较好，系统作业延误较少，设备等待延误能耗较低，且ga-sa算法的收敛速度和收敛效果远优于传统ga算法。随着λ的增加，时间目标函数和能耗目标函数都有上下波动的情况，且随着能耗目标占比不断增加，时间目标函数会有所上升。最后得到效果比较好的agv调度方案。
[0158]
所以在实际港口作业中，要权衡考虑时间和能耗两者因素。ga-sa算法下λ＝0.6时的时间和能耗目标都较小，系统收敛效果比较理想，其具体的agv调度方案如表5所示。
[0159]
表5λ＝0.6时的agv调度方案
[0160][0161]
实验结果表明，对于2台岸桥20个集装箱任务，在c为5，n为4时，目标函数收敛效果较好，系统作业延误较少，设备等待延误能耗较低，且ga-sa算法的收敛速度和收敛效果远优于传统ga算法。随着λ的增加，时间目标函数和能耗目标函数都有上下波动的情况，且随着能耗目标占比不断增加，时间目标函数会有所上升。这说明在过于注重能耗目标占比时，会降低自动化码头作业效率，这为实际码头运输作业提供了参考意义，在对于时间目标和能耗目标的选择上需要根据实际需求综合考虑。
[0162]
尽管本发明的内容已经通过上述优选实施例作了详细介绍，但应当认识到上述的描述不应被认为是对本发明的限制。在本领域技术人员阅读了上述内容后，对于本发明的多种修改和替代都将是显而易见的。因此，本发明的保护范围应由所附的权利要求来限定。

技术特征：
1.考虑岸桥缓存区和能耗节约的agv协同调度方法，其特征在于包括以下步骤：(1)以岸桥作业延误时间，岸桥和agv双向等待时间和设备等待延误能耗为目标建立多目标混合整数规划模型；(2)结合遗传算法的全局搜索能力和模拟退火算法局部搜索和快速收敛的能力，设计传-模拟退火算法ga-sa，将遗传算法ga的结果作为模拟退火算法sa的初始解输入；(3)用ga-sa算法对调度模型进行求解，并与传统ga算法做比对；(4)在选取缓存区容量c和agv数量n组合的基础上，增加能耗目标权重系数λ进一步观察并选取合适的agv调度方案。2.根据权利要求1所述的方法，其特征在于步骤(1)包括以下步骤：(1.1)对构建的模型提出假设和对符号进行规定：a)集装箱任务的装卸顺序和岸桥预设操作时间已知，b)当agv到达堆场时，堆场起重机能够及时作业，c)不考虑agv断电的情况，且agv一次只能运输一只集装箱，d)任意岸桥下方的缓存区容量大小相等；(1.2)目标函数：minf＝(1-λ)(f1+f2)+λf
333
f1表示岸桥实际作业时刻与预设作业时刻的差值，即当前作业延误对后续作业的影响，f2表示无论是因为agv等待岸桥或是岸桥等待agv造成的等待延误时间，f3表示岸桥和agv因等待延误所产生的能耗，f1、f2在总目标函数中所占权重为1-λ，f3所占权重为λ；(1.3)约束条件：表示任意编号的任务其之前仅有1个任务；表示任意编号的任务其之后仅有1个任务；表示同一岸桥作业两个连续任务时，岸桥实际作业的时间间隔要大于等于岸桥预设作业的时间间隔；
表示岸桥实际作业时刻要晚于预设作业时刻；表示对于出口集装箱任务，岸桥实际作业时刻要晚于agv到达缓存区的时刻表示对于进口集装箱任务，岸桥实际作业时刻要早于agv到达缓存区的时刻；表示对于进口集装箱任务，岸桥实际作业时刻要早于agv到达缓存区的时刻；表示任意时刻，岸桥缓存区内由岸桥卸载的进口集装箱数量agv运走的进口集装箱数量岸桥装船的出口集装箱数量agv送达的出口集装箱数量之和不能超过岸桥缓存区容量c；表示对于进口箱任务，当时即岸桥将1个进口箱卸载到缓存区中；表示对于进口箱任务，当时即agv将1个进口箱运离缓存区；表示对于出口箱任务，当时即岸桥将1个出口箱装载到船上；表示对于出口箱任务，当时即agv将1个出口箱运至缓存区；为agv任务的0-1决策变量；为缓存区容量约束的0-1决策变量。3.根据权利要求1所述的方法，其特征在于步骤(3)包括以下步骤：(3.1)设置包括交叉概率p
c
、变异概率p
m
、初始温度t0、终止温度tend、链长length的初始参数；(3.2)随机生成一定规模的初始解染色体组，并对其进行包括选择、交叉、变异的遗传操作后筛选出最优适应度值的染色体r1作为模拟退火算法的初始解；(3.3)r1随机交换2个基因位置，并使染色体合法化，生成新的染色体r2；
(3.4)计算r1和r2染色体适应度值之差，记δ＝f(r2)-f(r1)，适应度函数为：f(λ)＝1/(1-λ)(f1+f2)+λf3；(3.5)如果δ＜0则代表新染色体r2的适应度值更小，接受新解r2；或根据metropolis准则，以exp(-δ/t)的概率接受新解r2；(3.6)将r2存入临时染色体组temp_chrom；(3.7)判断：如果内循环迭代次数达到链长length，从temp_chrom中取出最优适应度值的染色体并存入最终染色体组final_chrom中；(3.8)判断：如果外循环温度达到设定的终止温度tend，这时从final_chrom输出最优适应度值的染色体，即最终的最优解，否则降低温度回到步骤b。4.根据权利要求1所述的方法，其特征在于步骤(4)包括以下步骤：(4.1)当能耗目标权重为0时，仅考虑延误时间目标，通过改变缓存区容量(c)和agv数量(n)得到最优的c和n的数量组合；(4.2)选取最优c和数量n组合的基础上，增加能耗目标权重系数λ进一步观察并选取合适的agv调度方案。

技术总结
本发明涉及考虑岸桥缓存区和能耗节约的AGV协同调度方法，包括以下步骤：(1)以岸桥作业延误时间，岸桥和AGV双向等待时间和设备等待延误能耗为目标建立多目标混合整数规划模型；(2)结合遗传算法的全局搜索能力和模拟退火算法局部搜索和快速收敛的能力，设计遗传-模拟退火算法GA-SA，将GA的结果作为模拟SA的初始解输入，在提升SA初始解质量的同时还摆脱了GA陷入局部最优的情况；(3)用GA-SA算法对调度模型进行求解，并与传统GA算法做比对；(4)在选取缓存区容量(c)和AGV数量(n)组合的基础上，增加能耗目标权重系数λ进一步观察并选取合适的AGV调度方案。本发明在码头调度作业中通过合理的AGV调度方案，可减少作业总延误时间和总延误作业能耗。间和总延误作业能耗。间和总延误作业能耗。


技术研发人员：陈信强 戴锦宇 韩冰 陈宇航 吴中岱 赵思硕
受保护的技术使用者：上海海事大学
技术研发日：2023.04.18
技术公布日：2023/7/20