自动化集装箱码头AGV调度研究

黄泽乾 丁 涛 王 雅

(武汉理工大学交通学院 武汉 430063)

0 引 言

全自动化小车属于一种自主移动的机器人，在没有接触控制的情况下能够实现隔空控制货物运输，并且能够提前设定运输轨迹，从而完全实现无人化，节省人力的使用，降低工人的劳动强度，能大幅降低人工费；全自动小车全电动化，能够充电无限续航，节省燃料费，达到节能减排、降低成本、提高效率的目的[1-3].如今码头前沿的拥挤较程度大，小车工作效率较低，与预想的工作效率差距较大[4].小车运行过程中需要众多因素来对任务进行分配，从而提高码头前沿运行效率[5].文中旨在通过线性规划模型，运用遗传算法对模型进行优化求解，使小车对任务进行择优自动选择，选择方法为最短路法.

1 问题描述

1.1 模型条件设置

AGV调度问题主要是从给AGV分配任务并且选择最佳的任务顺序来完成任务从而得到最短的路径.单AGV调度的时候就相当于合理地分配任务的顺序得到最短的路径，而多AGV的调度需要将任务合理分配到每台AGV上，并且使得总的AGV调度的路程最短，把多AGV调度的最短时间问题转换为最短路径问题[6-8].

对AGV小车的调度做如下假设.

1) 一般的情况下小车在运行过程中有加速和减速，但是小车的加速和减速在每次任务中都是必要的，并不影响实验的最后结果，所以假设所有小车都是匀速行驶.

2) 假设AGV小车的通信始终都是良好的，不存在设备故障情况.

3) 当系统中有任务出现时直接把任务转换成运输网络的节点i到节点j.

4) 由于集装箱的装载时间和卸载时间都是必需的，此处只研究通过就近点选取达到规划路径问题，因此，忽略集装箱装卸时间.

5) 在速度一定的情况下，最短时间问题可转换为最短路径的问题.

1.2 模型概述

在以上假设的基础上，设置集装箱一个码头的区域有a(a∈(1,2,…,m))辆AGV小车，在某一时间段内有b(b∈(1,2,…,n))个集装箱任务需要处理，在处理任务的过程中从a辆AGV小车中随机选取k(k≤a)辆小车去执行任务，任务的起点直接为小车的起点.本模型是AGV小车调度的路径问题，但是设定的小车是匀速行驶，所以最短路径转换为最短时间问题.

在进行任务i的时候，di为任务i起点到终点做完后的最短路径，做完任务i后做任务j,dij为任务i的终点到任务j的起点的最短路径，其中i，j∈{1,2,…,n}.

第k辆AGV执行完第i个任务后是否继续执行第j个任务，即

(1)

(2)

则目标函数为

min {maxg(k)=∑i∑jxijk(di+dij)}

k∈{1,2,…,a}

(3)

s.t.

(4)

j∈{1,2,…,b},k∈{1,2,…,a}

(5)

i∈{1,2,…,b},k∈{1,2,…,a}

(6)

xijk∈{0,1},i,j=1,2,…,b,k∈{1,2,…,a}

(7)

yki∈{0,1},i=1,2,…,b,k∈{1,2,…,a}

(8)

约束条件(3)为目标函数，是所有AGV在执行任务时，找出单个AGV执行任务所用的最大时间；约束条件(4)(5)(6)为每个任务都被一辆AGV执行并且只执行一次，不重复执行；约束条件(7)为AGV是否执行了任务i后再执行任务j；约束条件(8)为任务i是否被第k辆AGV执行.

该模型的意义在于每个任务都被执行并且只被一辆AGV小车执行一次，并且在AGV只有一辆的时候只制作任务执行顺序，目标函数就是在满足以上条件的情况下，使得完成这个时间段的所有任务所耗的时间最少，使得最后在完成每个任务的前提下，实现任务顺序的合理分配和路径的合理选择[9-10].

2 遗传算法

2.1 编码与解码

编码过程 需要生成任务数和小车数的矩阵y，举例见表1.

表1 任务和小车序号分配

若第i个任务被第k辆小车执行，那么对应的(k，i)则为1，被执行的任务不再重复执行所以其余小车对应此任务的位置均为0，因此，每一列只允许有一个1.接着在满足一列只能有一个1的情况下只能对每一列单独编码.

每个任务都被AGV1小车执行，取出第一列[1,0,0]，第一列长度为3，随机生成一个数x，对列的长度取余向0取整最后取绝对值加1，得到需要取出这一列的第几位数，并将取出的数放入另外一个初始为空的矩阵中，删除此列的此位数，形成一个新列，对此列重复进行直到列的元素全被取到另一个矩阵中；重复以上步骤直到每一个任务都被重新编排最后解码形成新的矩阵y.

2.2 GA工具箱

基于建立的上述模型和对算法求解的仿真，根据模型在MATLAB中编写遗传算法，由于用于求解工具为gatool，因此，只需编码、解码和适应度函数便能满足求解条件.

3 实验设置

3.1 调度仿真

为了验证上述算法的可行性，假设整个集装箱码头的一个区域有六个节点(在此处各个节点可代表码头堆场、岸桥、仓库、集装箱修理场，集装箱清洁场地等集装箱需要搬运的场地)，各个节点之间的最短距离见表2.现在有b个任务由a辆AGV小车完成，AGV小车的行驶速度为1(将时间最短问题转换为路径最短问题)，这b个任务的起讫点见表3.使用MATLAB中的遗传算法工具箱来进行求解最优解.使用默认的参数：交叉概率0.8，变异概率0.2.

表2 各节点之间的最短距离

表3 各个任务和任务的起讫点

3.2 实验结果

在集装箱码头的作业过程中，不同的任务数量需要不同数量的AGV小车来进行作业.

所以对表2任务进行了不同AGV小车数量的研究，设置AGV小车数从1～6得到了表4.

表4 不同数量的AGV对应不同的时间

将表4的数据绘制成折线图，得到横轴为AGV小车，纵轴为进行任务所用的时间，见图1.

图1 AGV数量和对应时间

由图1可知，随着AGV固定数量的增长，时间的减少并不是线性的，即不是固定数量的时间减少，而是凹函数形式的减少.在调用3台AGV的到调用4台AGV时时间的减少量明显下降，在调用5台到调用6台AGV时时间没变，出现这种情况意味着每个时间段的任务群需要对应AGV小车的数量，小车的数量过多时，时间减少量降低或几乎不变，因此,确定合适每个时间段任务群的AGV小车调度数量是非常有必要的.

3.3 卸船调度仿真

上述实验是假设码头的各个位置,比如,从集装箱堆场到集装箱修理厂，岸桥到堆场，岸桥到仓库，仓库到堆场等不同位置之间的调度，接下来模拟码头卸船时的AGV调度.假设岸桥用了两个，堆场用了四个，卸一艘船，船上需要卸载的集装箱为100TEU，使用6台AGV小车进行作业，每辆AGV小车的运行都按双线运行并且假设小车之间不会发生碰撞和拥堵，见表5.

表5 集装箱码头的岸桥和场最短距离

假设任务见表6.

表6 执行任务表

卸船调度任务表见表7.

表7 卸船调度任务列表

由表7可知，在拟定了小车的运行路径的时候,每辆小车的任务分配与用时仍然非常均衡.由节点顺序可以看出，每一辆小车都是尽量在完成了一个调度任务后，寻找就近的岸桥进行下一个任务的调度，使得空载行驶的距离较短，比如,从1号岸桥运送集装箱到了6号堆场后，再找到2号装卸桥继续作业，而不是回到1号装卸桥，减少空载距离，每台AGV小车任务分配得很均衡，用时都相差不大，实现了AGV小车调度高效运行.

4 结 束 语

港口中各个场地间的调度与卸船时固定路线的调度均可使用此模型，并且运用此模型对于小车的就近点选择与路径选择达到了任务分配均匀的目的,建立了以最末任务结束时间最小化为目标的混合整数规划模型，减少小车停留时间，尽量使每一辆小车都在运行，实现效率最大化和调度最优化.本模型可用于将任务提前分配给每一辆小车，得到最优的任务分配方式，后续可通过对各种影响因素的分析调整任务的分配，进一步提高小车作业效率.

文中未考虑具体的某种不确定性因素对集装箱码头调度的影响、AGV小车的避障问题，以及某种具体的因素对小车数量的影响，以后可针对此类问题再做深入研究.