基于有限状态机的调度派车决策支持方法

徐建峰 胡 静

上海振华重工（集团）股份有限公司 上海 200125

0 引言

对于整个码头而言，岸边集装箱起重机（以下简称岸桥）的效率并不是单台的，而是所有作业岸桥的效率。本文所述方法是使各台岸桥的自动导航小车（以下简称AGV）投放尽量均衡，即在一段时间内，首先使各台岸桥主小车的作业中断时间尽量短，然后使各台岸桥主小车不作业时间的最小值最大。这个方法就是调度派车，即将某1 台无任务的AGV 分配给最合适的岸桥，执行与该岸桥对应的集装箱水平运输任务。调度是按固定时间间隔执行的线程，在每次调度线程执行期间都要给当前无任务的AGV 指定运输任务，AGV 收到任务后开始执行，执行完成后再由另一次调度线程指定下一个运输任务。

为了更高效地实现调度派车，本文引入了有限状态机。有限状态机（Finite-State Machine，FSM）又称有限状态自动机，是一种针对系统的数学模型，能描述系统在有限个状态之间的转移行为、系统在状态变化时产生的动作行为。有限状态机模型适用于描述一类状态敏感的系统[1]，该类系统具有有限种可能的状态，系统的状态变化由输入推动。输出时间与输入时间有关，输出的内容则取决于输出时的系统状态。根据系统的有限状态机模型，能够推算出有限状态机模型的输入-输出对应关系，且这种对应关系与系统的输入-输出对应关系一致。基于以上特性，有限状态机模型可作为针对真实系统的模拟系统，用于要求真实系统的场合，如对真实系统自身测试[2，3]、基于真实系统的软件开发和测试[4，5]等。

1 引入有限状态机

集装箱码头的岸桥主要分单小车岸桥和双小车岸桥2 大类，其中自动化码头主要使用双小车岸桥，本文着重研究的是双小车岸桥的AGV 调度派车决策方法。双小车岸桥主要由主小车、门架小车以及中转平台组成，负责船与AGV 之间的集装箱运输，其卸船流程为：主小车负责从船上抓箱并放箱到中转平台，门架小车则负责从平台上抓箱并放箱到AGV；装船流程为：门架小车负责从AGV 上抓箱并放箱到平台，主小车负责从中转平台上抓箱并放箱到船。

岸桥主小车的作业过程可以用有限状态机进行描述，该状态机仅包含主小车、中转平台和钩3 个对象。主小车包含作业状态属性，可能有装卸和等待2 个属性值。中转平台对象包含2 个属性，即中转平台上存放的钩数、中转平台可存放的钩数上限。钩是岸桥的作业单位，没有属性。当岸桥单箱装卸时，一钩相当于一个集装箱；当岸桥双箱装卸时，一钩相当于2 个20 ft 集装箱。该状态机相关的事件有：

1）主小车作业开始事件 当事件发生时，主小车的作业状态为装卸，并令岸桥主小车作业完成事件在T时间之后发生。

2）主小车作业完成事件 当事件发生时，主小车的作业状态为等待。若岸桥正在装船，则令中转平台的钩数为-1；若此时中转平台上的钩数仍大于零，则立刻触发作业开始事件。若岸桥正在卸船，则令中转平台的钩数为+1；若此时中转平台上的钩数仍小于最大值，则立刻触发作业开始事件。

3）装船钩平台到达事件 令中转平台的钩数为+1，若此时岸桥主小车的作业状态为等待，则触发岸桥主小车的作业开始事件。

4）卸船钩平台离开事件 令中转平台的钩数为-1，若此时岸桥主小车的作业状态为等待，则触发岸桥主小车的作业开始事件。

图1 为岸桥卸船作业过程描述，图中给出了以有限状态机方法描述某岸桥主小车卸船作业过程的3 个例子，中转平台上能放的最大钩数为2。图中的箭头表示时间，单横线表示主小车的作业开始事件和作业完成事件（可能重叠），双横线表示卸船钩平台离开事件，箭头左侧的数字表示中转平台上的钩数，右侧灰色区域则表示岸桥主小车处于装卸状态的时间。

图1 以有限状态机描述的岸桥主小车卸船作业过程图

图1 中的3 个过程开始时，岸桥中转平台上都有1钩。在过程（1）中，由于未派出AGV，导致无钩离开平台，主小车做完1 钩后就进入等待状态不再作业。在过程（2）中，由于AGV 到达及时，岸桥主小车能连做2 钩，之后才进入等待状态不再作业。在过程（3）中，由于AGV 未及时到达，主小车做完第1 钩后作业发生中断，直到卸船钩离开事件发生后才能继续做1 钩，之后才进入等待状态不再作业。由图1 推断，由于主小车作业可能中断，影响岸桥作业情况的因素不仅包括派出AGV 的数量，还有AGV 的派出时间。

2 需量控制方法

需量方法是按照岸桥作业路上的钩数判断岸桥对AGV 需求迫切程度的方法。作业路包括岸桥、对岸桥服务的AGV、对岸桥服务的堆场起重机（ASC）等。对于卸船作业路，可以对主小车、中转平台、门架小车以及作业路内AGV 上的钩数进行加权求和作为指标，并以指标值作为衡量岸桥对AGV 需求程度的依据，该方法的缺陷是这种指标忽略了岸桥主小车的作业中断。在岸桥主小车短期将发生中断的情况下，按照需量方法判断得到的岸桥对AGV 的需求程度可能与实际情况不符。对于装船作业路，虽然按照需量方法也能在形式上将岸桥对AGV 的需求程度计算成数值，但若正值岸桥装船或卸船工况，要按照需量方法判断各台岸桥对AGV 的需求程度，则还需要合理的方法将装船需量和卸船需量进行统一。

图2 为需量方法判断结果与实际情况不符的缺陷示意图。在图2 中，横向虚线表示与本次派出AGV 有关的卸船钩的平台离开事件的发生时间，其他符号的含义与图1 相同。图中有2 台岸桥正在进行卸船作业，且在调度发生时，2 台岸桥的中转平台均已经放满，岸桥正处于等待状态。在之前的调度中，已向岸桥1 派出了1台AGV，向岸桥2 派出了2 台AGV。然而，由于岸桥1 的卸船钩平台离开事件发生较晚，反而是岸桥2 首先进入等待状态不再作业。如果仅按照需量判断，很容易得到岸桥1 更需要AGV 的结果；然而，由于岸桥1 的中断时间较长，将AGV 派给岸桥2 反而更合理。

图2 需量方法的缺陷示意图

3 基于有限状态机的调度派车决策支持方法设计

本文在有限状态机基础上引入事件和状态这2 个与时间有关的因素，形成调度派车的决策支持方法。该方法假设：1）同一岸桥的主小车对每个装船钩的作业时间为定值，对每个卸船钩的作业时间为定值；2）与已派出AGV 对应的装船钩中转平台到达事件和卸船钩中转平台离开事件的发生时间均可准确预计。

在调度派车决策支持方法设计中，B为调度考虑的时间长度；I为可派车的岸桥总数，各岸桥的编号为i或i′，1 ≤i，i′≤I；Ei为不考虑装船钩的中转平台到达事件和卸船钩的中转平台到达事件时岸桥i主小车的最后一次作业完成事件发生的时间点。

当调度开始时，在考虑主小车吊具和中转平台上的钩数、不考虑卸船箱中转平台离开事件和装船箱中转平台到达事件的条件下，计算得到岸桥主小车作业的停止时间。对于装船岸桥，该时间为中转平台为空，且岸桥主小车空车回到平台外等待位的时间；对于卸船岸桥，该时间为中转平台放满，且岸桥主小车带箱回到平台外等待位的时间。Mi为岸桥i每一钩作业的时间；Oi为调度不考虑的时间长度。

从调度时刻起，装船岸桥的装船箱中转平台到达事件的时间一般明显晚于卸船岸桥的卸船箱平台离开事件的时间。为了避免出现调度结果中AGV 向卸船岸桥过分集中的情况（尤其是装船岸桥与卸船岸桥同时刚开始做新的WorkQueue 时），本方法对每台岸桥定义一个时间Oi，并在计算giji′时从计算结果中扣除。该时间的实际意义是本次调度无法对中转平台造成影响的时间。

对于装船岸桥，Oi是ASC 出箱时间、ASC 将集装箱放到AGV 上的交接时间、AGV 从海侧交互车道（WSTP）到岸桥后的缓存停车道（QCPB）的时间的最小值、AGV 从QCPB 到岸桥作业车道（QCTP）的时间的最小值、门架小车从作业车道上方空车下降起始到将AGV 上一钩集装箱抓起并放至中转平台为止的时间等的总和。

对于卸船岸桥，Oi是AGV 从当前位置到QCTP 的时间的最小值、门架小车从作业车道上方带箱下降起始到将一钩集装箱放至AGV 上并空车回到中转平台抓起下一钩集装箱为止的时间等的总和。

J为码头的AGV 总数，各个AGV 的编号为j，1 ≤j≤J；Fj为表示本次调度中第j台AGV 是否可被派给岸桥的0 ～1 变量。Aij表示本次调度开始前第j台AGV 对应的钩是否正在向第i台岸桥中转平台移动的0 ～1 变量，若已将第j台AGV 派给装船岸桥i，且对应的装船钩平台到达事件尚未发生，则令Aij＝1，否则Aij＝0。若已将第j台AGV 派给卸船岸桥i，且对应的卸船钩平台到达事件尚未发生，则令Aij＝1，否则Aij＝0。Tij为第i台岸桥与第j台AGV 对应的卸船钩平台到达事件或装船钩平台离开事件的发生时间。

在调度时，每台已分配给岸桥的AGV 总是处在某种状态，且在卸船箱中转平台离开事件或装船箱中转平台到达事件发生前还会依次经历若干种状态。假设AGV处于某一种状态的时间长度总是可以估计的，已知AGV进入当前状态的时间，即可由此推断出卸船箱中转平台离开事件或装船箱中转平台到达事件的发生时间。

事件的发生时间可以按照如下方式计算：首先对AGV 所有未经历的状态的时间求和（S1）；然后若当前时刻到AGV开始当前状态的时间小于当前状态的时间，则将二者的差值（S2）加到上一步的求和结果上（形成S3），再从调度时间往后推相应的时间（S3）即可。hiji′为将第j台AGV 派给第i台岸桥后，岸桥i′主小车作业中断的总时间；giji′为将第j台AGV 派给第i台岸桥后，岸桥i′主小车不再作业的时间点；fij为将第j台AGV 派给第i台岸桥后，对应决策方案的评价值；决策变量xij为若本次调度将第j台AGV 派给岸桥i，则有xij＝1，否则xij＝0；因变量Liji′为本次调度将第j台AGV 派给第i台岸桥之后，岸桥i′的所有卸船钩平台到达事件或装船钩平台离开事件发生时间的集合。

调度派车决策的目标是找到令评价值最小的派车方法，主要考虑的因素是岸桥的作业中断时间最小，次要的目标是岸桥的最早作业停止时间到调度时间范围终点的时间最小。目标函数设计公式为

式中：ω为常数，且有ω＞＞1。

最晚岸桥主小车作业完成事件发生时间的计算方法为

式（2）中的hiji′和giji′可以用参数B、Ei、Mi、Oi和Liji′进行计算，计算过程中的K为集合Liji′中的元素个数；pk为集合Liji′的第k个元素，此处1 ≤k≤K；Gk为第k步迭代后的不再作业时间，0 ≤k≤K；Hk为第k步迭代后的中断时间，0 ≤k≤K。

步骤1：当过程开始时，令k＝0，G0＝Ei，H0＝0。若K＞0，则转入步骤2，否则转入步骤5。

步骤2：将Liji′中的元素按由小到大的顺序排列，形成元素序列p1～pK。令k＝1，转入步骤3。

步骤3：若pk≤Gk-1，则令Gk＝Gk-1+Mi，令Hk＝Hk-1；否则，令Gk＝pk+Mi，令Hk＝Hk-1+pk～Gk-1。转入步骤4。

步骤4：若k＜K，则令k＝k+1，转入步骤3；否则，转入步骤5。

步骤5：另giji′＝max(0，GK-Oi)，令hiji′＝HK，输出giji′和hiji′过程结束。

式（1）、式（2）相关附加限定条件为

式（3）表示所有的AGV 均不可能同时处于“可以派给岸桥”和“钩事件尚未到达中转平台”这2 种状态，且可能不属于这2 种状态中的任意一种。

式（4）表示任意1 台AGV 在判断Ti′j是否属于Liji′时，只要满足以下2 个条件之一即可：

1）第j台AGV 已经分配给第i′台岸桥

2）第j台AGV 在本次调度中被分配给第i′台岸桥

式（5）表示第j台AGV 不可以被调度时，不能将其派给岸桥。

式（6）表示无论如何分配，都不应使岸桥的不再作业时间超出调度考虑的范围。

式（7）表示1 次调度只派出1 台AGV 给岸桥。

4 应用案例

到目前为止，该调度派车决策方法已实施于自动化码头项目中，其中码头A 和码头B 已投入商业运营，其调度优化效率如表1 所示。

表1 调度优化效率表

在表1 中，优化前时间点是指项目开始调度优化前的时间点；优化前效率是指调度优化前码头岸桥设备作业的平均效率；优化后时间点是指调度派车决策方法应用并调优后的时间点；优化后效率是指调度派车决策方法应用并调优后岸桥设备作业的平均效率；效率提升百分比是指调度派车决策方法应用并调优后岸桥作业效率的提升百分比。引入调度派车决策方法后，调度系统在分配AGV 和岸桥作业时序控制上始终保障了岸桥的作业中断时间最小以及岸桥的最早作业停止时间到调度时间范围终点的时间最小，因而作业效率能得到较大的提升。效率提升百分比的计算方式为

根据表1 所示，由于调度派车决策方法的引入，为码头A 的作业效率提高了7 个Move/h，效率提升百分比约为31.8%；为码头B 的作业效率提高了6 个Move/h，效率提升百分比约为28.6%。以上案例说明，调度派车决策方法的投入使用，能够极大提升自动化码头的生产作业效率，也帮助公司大大缩短了项目交付时长。

5 总结

本文在有限状态机的基础上设计了1 套调度派车决策的方法，大大缩减了岸桥的中断时间及其最早作业停止时间至调度时间范围终点的时间，使岸桥和AGV 等设备更加有节奏地均匀分布作业，极大地提升了码头岸桥作业的整体效率。