航空货站自动化存取系统作业调度优化

宋宇博，蒋兆远，孙秉珍

（1.兰州交通大学机电技术研究所，730070兰州；2.兰州交通大学 交通运输学院，730070兰州）

航空货站自动化存取系统作业调度优化

宋宇博1，蒋兆远1，孙秉珍2

（1.兰州交通大学机电技术研究所，730070兰州；2.兰州交通大学 交通运输学院，730070兰州）

为从作业调度角度提高航空货站自动化存取系统运作效率，在分析双板作业和防冲突避让对指令序列完工时间影响的基础上，以指令序列完工时间最短为优化目标，建立了航空货站自动化存取系统调度优化模型，并设计了一种改进的蚁群算法对模型进行求解.为避免算法在搜索过程中陷入局部最优，在引入权重信息素和随机扰动策略的基础上，提出了具有变异率的状态转移参数，用于在寻优过程中决定蚂蚁的移动方向.仿真结果表明：改进的蚁群算法较基本蚁群算法和遗传算法具有更好的全局搜索能力和求解精度，所提出的调度优化方法获得的指令序列完工时间较先到先服务调度策略有至少37%的改进.

航空货站；自动化存取系统；作业调度；双板作业；死锁；蚁群算法

随着航空物流的发展，航空货站的规模和吞吐量不断扩大，建立高效的自动化存取系统（automatic storage and retrieval system，AS／RS）对满足航空物流地面服务要求十分必要.多端口出入式AS／RS凭借其高效的出入库效率多被航空货站采用，该系统是在多端口出入式货架系统基础上配置两台可以双板作业的升降式转运车（elevation transfer vehicle，ETV）而构成的新型自动化存取系统，ETV具有双板作业能力，一次行程可以同时存放和取出多个航空集装箱（unit load device，ULD），如图1所示.航空货站AS／RS与普通AS／RS作业调度的优化目标是一致的，主要是最小化指令序列的完工时间，提高ULD出入库效率，但与普通AS／RS相比较，航空货站AS／RS具有多端口出入库、双板作业、防冲突避让等作业特点，其调度问题更加复杂.为达到指令序列完工时间最小化的目标，需在同时考虑双板组合和避免死锁的前提下去选择分组与排序方案.

图1 ETV作业行程

目前，关于AS／RS调度问题的研究集中在两个方面，分别为基本调度问题的研究和扩展调度问题的研究.基本调度问题是在单一作业模式和复合作业模式下，优化堆垛机的作业过程，实现总的作业时间最短或总的运行距离最短.相关研究有，文献［1］在单一作业模式和复合作业模式都有效的情况下，对指令序列完工时间进行了计算和比较.文献［2］将单一作业模式和复合作业模式同时融合在作业调度过程中，提出了混合作业调度策略，该策略要求堆垛机在满足复合作业条件时进行复合作业，否则执行单一作业，该调度策略有效地提高了堆垛机的作业效率.文献［3］将AS／RS调度问题转化为TSP问题，并通过改进的遗传算法进行求解.文献［4］认为在一般情况下，给定指令序列的优化调度问题是NP-hard问题，并将问题的复杂性归结为有效的存储位置随着入库指令的占用和出库指令的腾空在不断变化，但是在一些特殊情况下，一些排序问题可以在多项式时间内解决.在上述基本调度问题中加入用户个性化的使用需求，便产生了扩展的调度问题.例如文献［5］研究了存储位置不确定条件下的调度优化问题，得出了计算时间代价较高的结论.文献［6］在存储位置和出库位置均不确定的情况下，通过出入库位置选择来获取符合用户出入库要求的最佳调度方案.文献［7］提出了一个指令排序的数学模型，该模型解决了满足用户需求约束的排序优化问题.文献［8］充分利用AS／RS的闲置时间进行托盘预先部署，将下一个阶段期望被用到的托盘存放在靠近出／入库端口的位置，以此来减少实际出库的运行时间.另一类扩展的调度问题是由于AS／RS结构的不断创新而产生的，例如多载具堆垛机的研发，使堆垛机在一个作业周期内可以访问多个存储位置，调度过程出现了更多的路径选择.文献［9］基于欧洲机械搬运协会标准建立了一个分析模型，用来评估双载具AS／RS的作业时间.文献［10］基于类型存储策略，应用遗传算法对三载具堆垛机调度问题进行了求解.文献［11］将传统堆垛机的复合运动在水平和垂直方向进行了拆分，由多个水平运动和垂直运动的平台代替，并设计了平台作业调度算法，适用于具有出库时间约束的出库作业.文献［12-13］研究了同一巷道内两台堆垛机并行作业过程中的协同调度问题，通过规划堆垛机移动轨迹来实现协同作业.文献［14］在文献［12-13］基础上提出了一种快速的作业调度方法，解决同一巷道内多个堆垛机的协同作业.

综上所述，在已有文献描述的AS／RS各种作业调度问题中，大多数文献着重考虑的是同端出入式AS／RS中堆垛机的调度优化问题，而多端口出入式AS／RS中多个堆垛设备的调度问题几乎没有得到关注.本文将从作业指令分组和排序两个子问题联合优化的角度，对具有双板作业和防冲突避让特点的多端口出入式AS／RS双ETV调度问题进行研究.

1 问题描述

航空货站AS／RS作业过程中，到达的出入库作业指令形成指令序列，系统按照指令周期运作，每个周期内对当前未执行的指令序列进行调度优化，其优化结果作为下一指令周期的执行方案，指令周期为ETV取下ULD的作业时间.航空货站AS／RS双ETV调度优化问题可描述为：指令周期内，到达的n条作业指令｛O1，O2，O3，…，On｝构成指令序列O，每条指令的源地址和目的地址已知；n条作业指令由两台ETV逐条完成；两台ETV共用同一巷道，一台ETV不能越过另一台ETV进行作业；ETV1能够访问全部货位，ETV2不能访问指定范围内的货位；两台ETV并行作业过程中有安全作业距离限制；每台ETV最多可以同时装载两个ULD；作业指令一旦开始执行就必须将ULD从源地址搬运到目的地址，不能中途卸载；货架单元格横纵尺寸均为定值；假设无论在装载或空载情况下，ETV在水平和垂直方向均作匀速运动且速度已知；忽略ETV取货和存货耗时.问题是n条作业指令如何合理地派送给不同的ETV，并为每台ETV指派的作业指令排序，在满足约束条件的前提下，使得n条作业指令的完工时间达到最小.

作业指令 i源地址 （Soi，Woi，Hoi）和目的地址（Sdi，Wdi，Hdi）已知的情况下，其完成时间表示为，其中S为侧方向坐标（区分地址在巷道的那一侧），W为列方向坐标，H为层方向坐标，P为货位宽度，Q为货位高度，Vw为ETV水平方向速度，Vh为ETV垂直方向速度.若指令j为指令i的紧前指令，第k台ETV从指令j的目的地址运行到指令i的源地址所需时间为，则单台 ETV 的 指 令 序 列 完 工 时 间 为 Tk=，其中 Ok为指派给第 k台ETV的作业指令集合，Yjik= 0，1{ }，取1表示指令j是指令i的紧前作业指令，否则取0.

当指令i、j满足双板作业条件时，若以双板作业的方式完成指令i、j，ETV访问路径节点的路线如图2（a）所示；若以单板作业的方式完成指令i、j，ETV访问路径节点的路线有两种可能，分别如图2（b）和图2（c）所示.

由图2可知，双板作业通过合并相邻指令的重合路径，消除了单板作业过程中的空载运行路段（指令i目的地址➝指令j源地址），有效地缩短了指令序列的完工时间.图2（b）、2（c）所示情况下双板作业可以节省时间分别为

图2 ETV作业路线

单台ETV的指令序列完工时间中加入双板作业的影响，则转 化 为，其中Ujik= ｛0，1｝，取1表示作业指令i和j执行双板作业，否则取0.

双ETV并行作业模式下，作业路径冲突是不可避免的，防冲突避让是避免冲突的有效途径，根据避让方向可将防冲突避让分为前进避让、后退避让和等待避让3种类型，如图3所示.无论哪种类型的避让都会中断ETV的当前作业进程，从中断当前作业进程到恢复至中断点继续作业所花费的时间为防冲突避让时间，可以表示为其中为避让开始时刻，Eaik为避让结束时刻.

图3 ETV防冲突避让类型

双ETV并行作业模式下，加入防冲突避让的影响，单台 ETV的指令序列完工时间转化为 Tk=其中Zik= {0，1}，取1表示执行作业指令i时第k台ETV执行避让，否则取0.

2 数学模型

2.1 符号定义

ETV集合M，k，k′为 ETV集合索引.第 k台ETV在任意时刻同时作业的指令数量qk.两台ETV之间最小作业距离l.Xik=｛0，1｝，取1表示作业指令i分配给第k台ETV，否则取0.另外为了建模方便，设置补充变量 Dijk，Mijk，Nijk和 Gij.Dijk可取0或1，取1表示第k台ETV执行的两条相邻指令i、j，其作业路径沿巷道方向同向且有重合，否则取0.Mijk可取0或1，取1表示由第k台ETV执行的两条相邻指令i、j满足Soj≠Sdi，否则取0.Nijk可取0或1，取1表示指令i、j是由第k台ETV执行的两条相邻指令，且指令j，满足Soj=Sdj，否则取0.Gij可取0或1，取1表示分别由不同ETV执行的两条作业指令i和j，其作业区域有重合，否则取0.

2.2 调度模型

机场货运站AS／RS双ETV调度优化问题的整数规划模型的目标函数为模型中式（1）为目标函数，表示最小化指令序列的完工时间，其中表示将花费时间最多的ETV所需的作业时间作为指令序列的完工时间，约束（2）确保每条作业指令都能由ETV执行，约束（3）确保每条作业指令只能由一台ETV执行，约束（4）确保分配给ETV的指令按照排列的顺序依次执行，约束（5）确保在存在ETV调度死锁的情况下首先执行ETV避让，再执行当前作业指令，当出库指令的目的地址与入库指令的源地址相同时，约束（6）确保入库指令优先执行，约束（7）确保每台ETV最多只能同时执行两条作业指令，约束（8）确保指令i，j能够由第k台ETV执行双板作业，约束（9）确保在作业过程中，两个ETV之间的距离大于等于安全距离l，约束（10）确保源地址或目的地址在指定区域的出入库作业指令由指定的ETV（该ETV能访问全部货架地址）执行，约束（11）确保任意一条作业指令最多只能有一条紧后执行的作业指令，约束（12）确保任意一条作业指令最多只能有一条紧前执行的作业指令.

3 算法实现

为了避免基本蚁群算法易陷入局部最优的弊端，本文在算法寻优过程中引入权重信息素和扰动策略，在保障基本蚁群算法确定性选择的基础上，增添探索新路径的概率，来提高算法的全局搜索能力.

3.1 权重信息素

权重信息素与普通信息素不同，该信息素用来描述各个子路径在最优路径中的权重，是根据全局信息进行更新.ξij表示指令节点i到j的权重信息素值，该信息素释放在指令节点上.与普通信息素的更新规则不同，权重信息素不挥发，也不叠加，其数值更新在每次蚂蚁完成遍历之后进行.假定在当前的路径寻优图中，指令节点i到j的权重信息素值为ξij（t），则按照下式对权重信息素进行更新，即

由式（13）可知，较长的子路径可以得到权重信息素的二次强化，以增加该子路径被选择的概率，提高算法的全局收敛性.

3.2 转移策略的改进

基本蚁群算法中蚂蚁根据路径上的信息素残留值决定移动方向，蚂蚁k从节点i转移到节点j的转移概率计算公式为

式中：τij（t）为t时刻节点i到节点j的信息素残留值；ηij（t）为τij（t）的倒数，表示由节点i转移到节点j的期望程度；α为蚂蚁在路径选择过程中残留信息素的受重视程度；β为蚂蚁在路径选择过程中启发信息所起的作用；Ak为蚂蚁k当前可以访问的指令节点集合.

从基本蚁群算法的转移概率公式可以看出，节点之间的信息素残留值越大、时间越短的路径对应的转移概率值就越大，被蚂蚁选中的概率越大.基于这一选择思想，将转移概率公式进行简化，引入更为简洁的转移参数公式为

普通信息素反映的是局部路径的选择概率，权重信息素反映的是全局信息，虽然两种信息素在蚂蚁路径搜索的过程中都是对最优信息起到正反馈作用，但是两者在转移系数公式中应该有不同的启发因子.基于转移参数公式的简化思想，式（15）可改进为

式中γ为权重信息素在路径选择过程中的受重视程度.

为了避免搜索停滞现象，增加了随机扰动策略，以一定的概率去探索残留信息素不是最多的路径，提高路径搜索的全局性.同时为防止最优路径被漏选，对残留信息素值最大的路径单独计算其转移系数.综上考虑，本文设计了具有随机变异率的转移参数，其计算公式为

式中：pm为随机变异率，在区间（0，1）服从均匀分布的随机变量；p1，p2为常数.

3.3 算法仿真步骤

改进的蚁群算法求解航空货站AS／RS双ETV调度优化模型的基本思路：路径寻优图由源地址和目的地址构成的指令节点组成（ETV的待命位作为蚂蚁的起点），生成等于指令序列规模两倍数量的蚂蚁，每组两只，每只蚂蚁代表1个ETV，从待命位出发；每只蚂蚁在路径寻优图中未被访问的节点中筛选满足约束（6）、（10）的节点，作为当前蚂蚁下一步可以访问的节点备选集合；蚂蚁在确定下一个访问节点时，通过式（17）计算转移参数，选择转移参数值最大的节点作为当前蚂蚁的下一个访问节点；每只蚂蚁经过的节点代表分配给该ETV的作业指令，每只蚂蚁经过节点的先后顺序代表指令执行的先后顺序，两只蚂蚁遍历全部节点形成两组路径，该路径作为ETV的一个调度方案，具体流程见图4.

图4 改进蚁群算法流程

4 算例分析

以国内某国际机场集装区AS／RS为例进行仿真.该AS／RS配置两台ETV，ETV垂直方向的运行速度为0.4 m／s，ETV水平方向的运行速度为2 m／s，ETV之间的安全作业距离为4列列宽，ETV1可以访问全部地址，ETV2不能访问货架第1列至第8列范围内的地址.货架规模为2排5层45列，货位宽度为2.8 m，层高为2.4 m.沿巷道方向设置23个出入库端口，其中空侧13个，陆侧10个，作业指令序列按照要求规模随机生成.仿真工具为MATLAB7.0，运算的计算机配置：处理器Intel（R）Core（TM）i5＠2.5 GHz，内存4.00 GB.算法中最大循环代数为200，残留信息素影响因子α=1，残留信息素影响因子β=10，权重信息素影响因子γ= 25，信息素挥发系数ρ=0.1，选择概率p1=1／4，p2= 2／3.

为了验证改进的蚁群算法对航空货站AS／RS双ETV调度问题求解的有效性，将该算法分别与基本蚁群算法和遗传算法进行性能对比.图5为不同问题规模下蚁群算法改进前后的优化结果对比曲线，图中的指令序列完工时间为每种问题规模下10次仿真结果的平均值.图6为改进蚁群算法与遗传算法针对问题规模为30的指令序列的算法收敛曲线对比图.

图5 蚁群算法改进前后对比

图6 改进蚁群算法与遗传算法收敛对比曲线

由图5、6可见，改进的蚁群算法获得的最优解均优于基本蚁群算法和遗传算法，这是由于改进蚁群算法中引入了权重信息素和随机扰动策略.权重信息素的引入使信息素的更新通过全局更新和局部更新相结合的方法进行，这种方法不但能增强最优信息的正反馈，同时也在一定程度上抑制停滞现象.另外，随机扰动策略对路径选择形成干扰，以一定的概率去探索残留信息素不是最多的路径，蚂蚁对新路径的探索概率大大增加，避免了寻优过程过早陷入局部最优.同时确定性选择又保证了蚂蚁总是选择转移参数最大的路径，保证了改进的蚁群算法收敛到全局最优解.

在小规模问题情形下，针对指令序列规模为5、6、8分别随机生成5组数据，每组数据采用枚举算法和改进蚁群算法分别求解，仿真结果如表1～3所示，表中tEA对应数据为不同指令序列规模下枚举算法得到的指令序列完工时间，tIACO对应数据为不同指令序列规模下改进蚁群算法10次仿真实验的平均指令序列完工时间，Nopt为改进蚁群算法求得最优解和次优解的次数.

表1 指令序列规模为5的算法对比结果

表2 指令序列规模为6的算法对比结果

表3 指令序列规模为8的算法对比结果

表1～3中改进蚁群算法的10次求解结果中，求得最优解和次优解的次数均超过7次，具有较高的求解精度.

为了验证本文优化方法的有效性，仿真对比了不同指令序列规模下先到先服务调度策略和本文优化方法的调度效果.仿真实验针对每种问题规模下的指令序列均求解10次，结果如表4所示.表中tFCFS对应数据为先到先服务调度策略下的平均指令序列完工时间，tmin为10次仿真中本文优化方法得到的最短指令序列完工时间，tmax为10次仿真中本文优化方法得到的最长指令序列完工时间，tavg为本文优化方法10次仿真的平均指令序列完工时间.

表4 不同调度策略的仿真结果

由表4可知，在不同指令序列规模下，本文的优化方法得到的完工时间均优于先到先服务调度策略，改进率分别为 53.61%、37.35%、40.66%、46.30%、44.48%.先到先服务调度策略在作业调度过程中同样需满足作业流程约束，符合双板作业条件的相邻指令同样执行双板作业，但其调度过程缺少对分组结果的调配，对双板组合方案的对比，对调度死锁的避让选择，对指派给每台ETV的指令排序等方面的集成优化，所以导致指令序列完工时间中包括了大量不合理的ETV避让时间和ETV空载运行时间.

5 结 论

1）在作业指令源地址和目的地址已知的情况下，研究了具有双板组合和防冲突避让特点的航空货站AS／RS双ETV调度优化问题.以最小化指令序列完工时间为优化目标，建立了航空货站AS／RS双ETV调度整数规划模型，并设计了改进的蚁群算法进行求解.仿真结果表明，在不同问题规模下，本文优化方法均能获得较高质量的调度方案，在避免死锁的同时能有效缩短ETV的空载运行时间.

2）改进蚁群算法中引入了权重信息素和随机扰动策略，并对转移概率公式进行了修正，提出了具有变异率的状态转移参数，用于寻优过程中决定蚂蚁的移动方向.仿真结果表明，改进蚁群算法能够较好地克服过早收敛到局部最优的缺点，在相同的循环代数下，改进的蚁群算法较基本蚁群算法和遗传算法具有更高的求解精度.

［1］GRAVES S C，HAUSMAN W H，SCHWARZ L B.Storageretrieval interleaving in automatic warehousing systems［J］. Management Science，1977，23（9）：935-945.

［2］EBEN-CHAIME M，PLISKIN N.An integrative model for automatic warehousing systems［J］.International Journal of Computer Integrated Manufacturing，1996，9（4）：286-292.

［3］FANG J F，WANG Y，LEI C L，et al.The way of solving traveling salesman problem the research on scheduling in AS／RS［J］.Procedia Engineering，2011，16：601-607.

［4］HAN M H，MCGINNIS L F，SHIEH J S，et al.On sequencing retrievals in an automated storage／retrieval system［J］.IIE Transactions，1987，19（1）：56-66.

［5］LEE H F，SCHAEFER S K.Retrieval sequencing for unitload automated storage and retrieval systems with multiple openings［J］.International Journal of Production Research，1996，34（10）：2943-2962.

［6］HACHEMI K，SARI Z，GHOUALI N.A step-by-step dual cycle sequencing method for unit-load automated storage and retrievalsystems［J］.Computersand Industrial Engineering，2012，63（4）：980-984.

［7］GAGLIARDI J P，RENAUD J，RUIZ A.On sequencing policiesforunit-load automated storage and retrieval systems［J］.International Journal of Production Research，2014，52（4）：1090-1099.

［8］JAIKUMAR R，SOLOMON M M.Dynamic operational policies in an automated warehouse［J］.IIE Transactions，1990，22（4）：370-376.

［9］AZZI A，BATTINI D，FACCIO M，et al.Innovative travel time model for dual-shuttle automated storage／retrieval systems［J］.Computers and Industrial Engineering，2011，61（3）：600-607.

［10］POPOVIC D，VIDOVIC M，BJELIC N.Application of genetic algorithms for sequencing of AS／RS with a tripleshuttle module in class-based storage［J］.Flexible Services and Manufacturing Journal，2014，26（3）：432-453.

［11］HU Y H，ZHU Z D，HSU W J.Load shuffling algorithms for split-platform AS／RS［J］.Robotics and Computer-Integrated Manufacturing，2010，26（6）：677-685.

［12］HINO H，KOBAYASHI Y，HIGASHI T，et al.Motion planning method for two stacker cranes in an automated storage and retrieval system［J］.International Journal of Automation Technology，2012，6（6）：792-801.

［13］KUNG Y，KOBAYASHI Y，HIGASHI T，et al.Motion planning of two stacker cranes in a large-scale automated storage／retrieval system ［C］／／IEEE International Conference on Robotics and Biomimetics. Phuket，Thailand：IEEE，2011：168-173.

［14］KUNG Y，KOBAYASHI Y，HIGASHI T，et al.Order scheduling of multiple stacker cranes on common rails in an automated storage／retrievalsystem ［J］. International Journal of Production Research，2014，52（4）：1171-1187.

（编辑 魏希柱）

Job scheduling optimization of automatic storage and retrieval system at air freight station

SONG Yubo1，JIANG Zhaoyuan1，SUN Bingzhen2

（1.Institute of Mechatronic Technology，Lanzhou Jiaotong University，730070 Lanzhou，China；2.School of Traffic and Transportation，Lanzhou Jiaotong University，730070 Lanzhou，China）

To improve the operation efficiency of automatic storage and retrieval system （AS／RS）at air freight station in term of job scheduling，on the basis of analyzing the effect of double unit load device（ULD）transport combination and anti-collision avoidance to the completion time of command sequences，a scheduling optimization model of AS／RS whose objective was to minimize the completion time of command sequences was established，and an improved ant colony algorithm was given to solve this model.To avoid trapping in local optimum in the search process，weight pheromone and random perturbation strategy were introduced.Besides，a state transfer parameter with a mutation probability was proposed to decide the moving direction of ants in the optimization process. Simulation results indicate that comparing with basic ant colony algorithm and genetic algorithm，the improved algorithm has better global search ability and solution precision.In comparison with the first-come-first-served scheduling strategy，the completion time of command sequences obtained by the scheduling optimization method proposed in this paper is improved by 37%at least.

airfreight station；automatic storage and retrieval system；job scheduling；double ULD transport；deadlock；ant colony algorithm

TP391

A

0367-6234（2015）09-0112-07

10.11918／j.issn.0367-6234.2015.09.021

2014-10-16.

国家自然科学基金（71161016）；国家科技支撑计划（2012BAH20F05）；兰州交通大学青年基金（2011012）.

宋宇博（1977—），男，讲师，博士研究生；蒋兆远（1954—），男，教授，博士生导师.

宋宇博，songyubo＠mail.lzjtu.cn.