基于混合规则的环形穿梭车动态调度系统研究

王同庆 潘璐 张家敏 王静

摘   要：文章针对环形穿梭车动态调度问题，基于任务完成时间最小化构造解决环形穿梭车动态调度的基础模型。首先，将任务完成时间最小化的目标函数分解为穿梭车搬运距离最短和系统拥塞次数最少。其次，提出了改进的混合规则算法。最后，利用改进的混合规则算法求解模型。

关键词：穿梭车;混合规则;多指标评价;动态调度

环形穿梭车系统的设计与调度，影响货物运送的效率。其中，货物装载的顺序对最终消耗的时间有关键性的作用。每辆穿梭车只能沿环形轨道进行逆时针单向匀速运行，该环形轨道可以同时运行多台穿梭车，从而改善了直线往复式穿梭车输送能力有限的缺点。然而，由于系统采用封闭式轨道，在运行过程中，不合理的调度会加剧轨道堵塞，降低运行效率[1]。所以，探究车辆调度的装卸顺序对实际的调度有重要的意义。本文提出混合规则的环形穿梭车调度算法，模拟了穿梭车的调度过程。

1    问题描述

穿梭车的运行速度、车长以及数量对整个调度系统的效率有着重要的影响。其中，当穿梭车的数量少于进出货物端口时，会导致在同一时刻处理顺序的货物，不能在同一个运送周期内得到处理，使得货物运送的效率降低，导致总时间变长。当穿梭车数量多于进出货物端口时，虽然可以提高一个运送周期内货物处理的数量，但是由于穿梭车数量增多，发生拥塞的次数也会随之增加。因此，对穿梭车进行合理的调度，可以减少轨道的堵塞，提高环形穿梭车系统的运行效率[2]。

1.1  相关假设

（1）环形穿梭车、出入货端口在整个调度运行周期中有故障发生时，系统停止运行，对调度优化过程不产生影响。

（2）环形穿梭车到达出入货端口可立即完成出入货，不考虑其他因素。

（3）本文中环形穿梭车和出入货端口编号沿逆时针依次统一编号。

（4）在不考虑优化算法执行时间的情况下，即环形穿梭车系统调度是在理想情况下执行的可以忽略系统执行算法的时间。

2    模型建立

在不考虑环形穿梭车的车长情况下，要使系统的工作效率尽可能高，则需要考虑所有作业任务完成时间最短。因此，环形穿梭车系统调度的优化模型如式（1）所示。

其中，ti表示货物i完成上货下货所需的时间，N_goods表示所有货物的数量，包括系统A侧和B侧上货端口需要完成的作业任务量Ni之和，如式（2）所示。

由于在实际运算的过程中，货物作业任务完成时间t无法直接计算，但货物i在上货下货的过程中包括等待出入货的时间tiwait和出入货所用的时间tL/U，处理货物的时间包括上货和下货的时间，如式（3）所示[3]。

而货物i的等待时间包括上货之前等待的时间tiwait_L和等待下货tiwait_U的时间，如式（4）所示。

由于货物等待调度的时间主要与上货端口之前的货物上货时间有关，又由式（3）和式（4）可知货物任务完成时间的主要因素是货物等待下货时间tiwait_U和货物出入货所用的时间tL/U，因此，可将上述优化目标分解为所有环形穿梭车搬运距离之和最短及环形轨道堵塞造成停车次数最少两个方面[4]，如式（5）所示。

其中，目标函数式（1）表示使环形穿梭车运送距离与等待时间的最小化。x=（x1，x2，x3，…，xn）是一组可行解，表示环形穿梭车调度货物的序列;α，β分别为优化函数f1，f2的权重;f1表示可行解x对应的环形穿梭车运送距离的标准差的优化;f2表示环形轨道堵塞造成停车次数最少的。式（6）、式（7）给出了f1，f2的计算公式。

其中，N为穿梭车的数量，s是环形穿梭车的状态量，Si表示第i辆穿梭车的状态值，若Si=0表示穿梭车没有被分配任務;否则Si=1表示被分配任务;l为环形穿梭车搬运货物的距离，li表示第i辆穿梭车沿着运行方向到所承担任务上货端口的距离，若第i辆穿梭车未被分配任务，li=0;num（i，j）为第i辆穿梭车由于第j辆穿梭车而被堵塞。在本文中，由于环形穿梭车逆时针方向作业，因此i和j满足式（8）所示。

环形穿梭车系统对式（5）所示模型存在以下约束条件：为了保证穿梭车能够准确地停到上货端口，不会因为距离过短而使穿梭车驶过上货端口。若lstop表示停车距离，则应满足：

在考虑车身长度的情况下，还应该满足相邻两辆穿梭车之间的安全距离，若lsafe表示两辆车的安全距离，li，j表示第辆穿梭车和第j两穿梭车之间的实际距离，则应满足：

在本文中，为了简化问题，我们取两车的安全距离为穿梭车的车长。

3    基于规则的调度算法

（1）规则1：最近站点优先。取货规则为：从穿梭车的队尾开始，空闲穿梭车选择最近的入货端口装载货物;卸货规则为：从车队列的队尾开始，装载货物的穿梭车选择最近的出货端口卸载货物。

（2）规则2：最远站点优先。取货规则为：从穿梭车的队头开始，空闲穿梭车选择最远的入货端口装载货物;卸货规则为：从车队列的队头开始，装载货物的穿梭车选择最远的出货端口卸载货物。

（3）规则3：考虑到当穿梭车数量比较多时，大于入货端口数量，如果一起出发，势必发生大面积堵车现象。于是每次一趟车辆循环分解为两次小循环，第一组为与出货口数接近的车的数量，第二组为剩下的辆车，为防止拥塞现象，第二组的所有车辆都延迟一定的出发时间。

规则1避免了穿梭车队列后面的穿梭车选择较远的出货端口，此次运送距离变大，运送时间变长。规则2避免了穿梭车队列的前面的穿梭车选择较近的出货端口，在卸载货物过程中堵塞后面的穿梭车，整个系统的效率降低。规则3避免了因穿梭车数量较多导致拥堵现象的频发。

4    算例分析

本文采用穿梭车轨道长L=100 m，穿梭車数量分别为3—9，出货口数量为7，入货口数量为6进行实验模拟。求得不同数量下穿梭车调度系统的吞吐量（见图1）、以及穿梭车利用率变化（见图2）。

由图1可知，系统吞吐量随着穿梭车数量的增加而逐渐上升。在系统中少于7辆穿梭车时，系统中每增加一辆穿梭车，系统吞吐量约增加0.5个。而在系统中多余7辆穿梭车时，系统中每增加一辆穿梭车，系统吞吐量约增加0.1个。由图2可知，穿梭车利用率随着穿梭车数量的增加整体呈下降趋势。穿梭车数量在4～7个、8～9个区间内呈下降趋势;穿梭车数量在3～4个、7～8个区间内呈上升趋势。

5    结语

本文构建了基于混合规则的算法模型，对不同环形穿梭车数量进行了分析，得到了这些参数对系统吞吐量变换的影响。本文构建的模型高效、稳定，可以用于工厂仓库的中环形穿梭车系统的构建，从而提高货物分拣的效率，缩短货物总完工时间，对工厂的发展有着重要的意义。

[参考文献]

[1]江唯，何非，童一飞，等.基于混合算法的环形轨道RGV系统调度优化研究[J].计算机工程与应用唯一官方网站，2016（22）：242-247.

[2]YASSIR B，MOHAMMED D，MOHAMMED B，et al.Optimal preventive remanufacturing planning of production equipment under operational and imperfect maintenance constraints：a hybrid genetic algorithm based approach[J].Reliability Engineering & System Safety，2018（9）：1.

[3]EKREN B Y，HERAGU S S，KRISHNAMURTHY A，et al.An approximate solution for semi-open queueing network model of an autonomous vehicle storage and retrieval system[J].IEEE Transactions on Automation Science & Engineering，2013（1）：205-215.

[4]胡建伟，李东波，何非，等.环形穿梭车调度系统设计与开发[J].物流技术，2015（9）：266-268.

Abstract：In this paper， based on the dynamic scheduling problem of the ring shuttle， the basic model of the dynamic scheduling of the ring shuttle is solved based on the task completion time minimization structure. First， the objective function that minimizes the task completion time is decomposed into the shortest shuttle handling distance and the least system congestion. Then， an improved hybrid rule algorithm is proposed. Finally， the improved hybrid rule algorithm is used to solve the model.

Key words：shuttle; hybrid rules; multi-index evaluation; dynamic scheduling