具有订单完成时间约束的拣选机器人调度仿真

李 腾，冯 珊

(哈尔滨商业大学管理学院，黑龙江 哈尔滨 150028)

1 引言

拣选作业是整个物流作业的关键环节，直接影响企业的服务水平。通过拣选机器人代替传统的人工拣选的智能仓储系统得到了越来越多的应用[1-2]。目前，许多智能仓储系统，特别是电商平台使用的智能仓储系统，体现出“拣选为主，存储为辅”的特点，其关键在于如何高效地完成拣选作业以满足消费者对配送时效的要求[3]。科学合理地调度拣选机器人完成任务直接影响智能仓储系统的运作效率，已经成为智能仓储系统的研究重点[4-5]。

目前，机器人调度问题已经受到国内外学者的广泛关注，Luo等[6]针对集装箱码头的机器人调度问题，同时考虑装载与卸载过程，以船舶的泊位时间最小为目标函数建立混合整数规划模型，利用遗传算法进行求解，实现了机器人的调度。Angeloudis等[7]开发了一种新的机器人调度方法，将不确定因素加以考虑，解决了集装箱码头作业的分配并降低了成本。Chaudhry等[8]考虑了柔性制造系统中设备与机器人的同时调度，提出了一种改进的遗传算法，降低了完工时间。周炳海等[9]研究了物料配送机器人调度问题，考虑了机器人之间的协同调度，以投入成本和能耗成本为优化目标建立模型，利用自适应大邻域搜索算法进行求解，通过算例验证了协同调度不仅可以减少机器人的数量，还可以降低能耗成本。沈博文等[10]对仓储物流机器人调度问题进行研究，以仓储物流机器人完成任务的总代价最小为目标函数，并考虑了系统的拥塞程度，实现了仓储物流机器人的智能调度。袁瑞萍等[11]研究了“货到人”订单拣选系统中的任务调度问题，最小化所有任务的完成时间，对比多个拣选工作站同步拣选与异步拣选两种拣选方式，利用改进遗传算法对两调度模型进行求解，通过实例仿真得出同步拣选具有更高的效率。

目前，对于机器人调度问题的相关研究主要集中于集装箱码头系统、生产制造系统与物流仓储系统，对于机器人调度问题，部分订单对完成时间有严格的要求，而上述文献中没有考虑任务的时间窗约束，并且上述有关智能仓储系统机器人调度文献中，没有考虑到机器人的等待时间。因此，本文针对智能仓储系统，在不改变已有任务下发顺序的情况下，以拣选机器人执行所有任务所花费的总成本最小为优化目标，任务分配结果为决策变量，同时考虑拣选机器人在拣选工作站的排队等待时间，分别建立硬时间窗约束与软时间窗约束下的拣选机器人调度模型。

2 拣选机器人调度模型

2.1 问题描述

“货到人”智能仓储系统布局如图1所示，主要由货架、拣选机器人、拣选区域、拣选机器人停车区域，拣选机器人充电区域以及拣选机器人行走通道组成。其中，货架的放置原则为背靠背放置，每个货架的规格相同，并且每层货架上存储不同种类的货物。货架之间为拣选机器人的行走通道，拣选区域由多个拣选工作站组成，每个拣选工作站配有一名工作人员将指定的货物从货架中拣出。智能仓储系统的主要工作流程为：仓库管理系统接收订单后，按照搬运货架次数最少的原则对订单进行分批，然后将处理后的订单发送至调度系统，调度系统需要确认订单中任务所在货架的位置以及各个拣选机器人的位置，其次调度拣选机器人来执行任务。此时，拣选机器人将移动到货架位置，并将货架托运至规定的拣选工作站进行排队等待，该拣选工作站的工作人员按照拣选机器人到达的顺序将订单中的货物从货架中取出，然后放置在指定的货箱中，同时拣选机器人将货架托运至原来位置，并在此位置等待调度系统为其再次分配任务。

图1 智能仓储系统布局

智能仓储系统拣选机器人调度是指在调度系统的控制下，以某个参数为优化目标，确定各个拣选机器人将要执行的任务以及各自执行任务的顺序，在满足一定的约束条件下提高拣选效率，降低智能仓储系统的运行成本。具有时间窗约束的拣选机器人调度问题是指在传统的拣选机器人调度问题基础上加入时间窗的约束，即智能仓储系统要求任务在一定时间范围内完成拣选工作。在智能仓储系统中，任务的下发顺序取决于任务的到达时间，本文针对智能仓储系统拣选机器人调度问题，在不改变任务序列的情况下，以最大限度满足系统对时间的严格要求进而提高消费者满意度。

针对智能仓储系统拣选机器人调度问题，本文做出以下假设：

1)初始时刻，智能仓储系统中所有拣选机器人处于空闲状态；

2)智能仓储系统中所有拣选机器人的行驶速度相同，不考虑拣选机器人的加减速；

3)拣选机器人在完成任务的过程中，电量始终充足；

4)货架上的货物是随机放置的；

5)拣选机器人在完成任务后，将货架托运至原来位置，并在此位置等待下一个任务；

6)每个拣选工作站的拣选人员每次的拣货时间相同，分货时间相同。

2.2 数学模型

为建立数学模型，本文定义了如下参数：

1)m表示拣选机器人的总数量，i表示第i台拣选机器人，取值范围为i∈[1，m]；n表示任务的总数量，j为第j个任务，取值范围为j∈[1，n]，其中有w个任务具有时时间窗约束，k表示第k个具有时间窗约束的任务，取值范围为k∈[1，w]；

2)(xAi，yAi)表示第i台拣选机器人的位置坐标，(xTj，yTj)表示第j个任务的位置坐标，(xP，yP)表示拣选工作站的位置坐标；d1ij表示第i台拣选机器人从初始位置到第j个任务所行驶的最小距离，d2ij表示第i台拣选机器人从第j个任务到拣选工作站所行驶的最小距离，d3ij表示第i台拣选机器人从拣选工作站回到第j个任务所行驶的最小距离，其中所有最小距离均为曼哈顿距离；

3)v表示拣选机器人的行驶速度；

4)t1表示拣选人员的拣货时间，t2表示拣选人员的分货时间；

5)r表示每次下发任务的数量，每次下发的时刻为上一批任务中最早到达该拣选工作站的时刻，取值范围为r∈[1，n]；

6)l表示任务到达拣选工作站的顺序，取值范围为l∈[1，n]；

7)tjc表示第j个任务被下发的时刻；

8)tlj表示第l个到达拣选工作站的第j个任务到达该拣选工作站的时刻；

9)t(l-1)jp表示第l-1个到达拣选工作站的第j个任务被拣选完成的时刻，tlkp表示第l个到达拣选工作站的第k个具有时间窗约束的任务被拣选完成的时刻；

10)tiljq表示由第i台拣选机器人完成的第l个到达拣选工作站的第j个任务在该拣选工作站的等待时间；

11)Ti为第i台拣选机器人完成被分配任务所花费的总时间，T为所有任务的完成时间；

12)Cr表示每台拣选机器人单位时间内的运行成本，C表示拣选机器人完成所有任务的总成本；

13)[tETk，tLTk]表示第k个任务最早最晚拣选完成的时间要求；

14)决策变量Xij表示第i台拣选机器人是否完成第j个任务；

在智能仓储系统中，拣选机器人完成所有任务的总时间为所有拣选机器人完成各自任务所耗费的最长时间。本文以拣选机器人完成所有任务的总成本最小为目标函数，以拣选机器人调度为决策变量，考虑了部分任务的时间窗约束以及拣选机器人在拣选工作站的排队等待时间，分别建立硬时间窗的拣选机器人调度模型与软时间窗的拣选机器人调度模型：

硬时间窗拣选机器人调度模型：

minC=T·Cr·n

(1)

T=max{Ti，i=1，2，…，m}

(2)

(3)

(4)

t(l-1)jp=t(l-1)j+ti(l-1)jq+t1+t2

(5)

tETk≤tlkp≤tLTk

(6)

Xij∈{0，1}，i=1，2，…，m，j=1，2，…，n

(7)

(8)

上述模型中，式(1)为拣选机器人调度模型的目标函数，表示拣选机器人完成所有任务的总成本最小。式(2)表示拣选机器人完成所有任务所花费的总时间。式(3)中拣选机器人完成任务的时间取决于拣选机器人的行走时间与在拣选工作站的排队等待时间，并按照拣选机器人每次完成任务所停留的位置将其行走距离分为三个部分。式(4)表示拣选机器人在拣选工作站的排队等待时间与拣选机器人到达拣选工作站的时刻和该拣选机器人所在排队队列中的前一台拣选机器人被拣选完成的时刻有关。式(5)表示拣选机器人被拣选完成的时刻，取决于拣选机器人到达拣选工作站的时刻、拣选机器人在拣选工作站的排队等待时间、工作人员的拣货时间与分货时间。式(6)表示智能仓储系统要求部分任务的拣选完成时间需要满足时间窗约束。式(8)表示一个任务同时只能由一台拣选机器人托运。

软时间窗拣选机器人调度模型

(9)

T=max{Ti，i=1，2，…，m}

(10)

(11)

(12)

t(l-1)jp=t(l-1)j+ti(l-1)jq+t1+t2

(13)

(14)

Xij∈{0，1}，i=1，2，…，m，j=1，2，…，n

(15)

(16)

与硬时间窗拣选机器人调度模型相比较，软时间窗拣选机器人调度模型中智能仓储系统对任务被拣选完成的时间要求没有那么严格[12-13]，本文采用线性惩罚函数，即对没有在系统希望时间范围内完成的任务予以惩罚。式(9)表示拣选机器人完成所有任务花费的总成本，其中Cpk表示第k个具有时间窗约束的任务被拣选完成所造成的惩罚成本。式(14)中fk1与fk2分别表示具有时间窗约束的任务被提前或延迟拣完的单位惩罚成本，任务被延迟拣完产生的惩罚成本大于被提前拣完的惩罚成本，即fk2>fk1，tMETk表示任务k的可接受最早拣完时间，tMLTk表示任务k的可接受最晚拣完时间。

3 模型求解

遗传算法是模拟生物自然选择与进化的一种启发式算法，该算法不受约束条件的限制，具有并行性、高效性等特点，通过利用遗传的基本操作，如染色体之间进行交叉和变异，提高种群的多样性，进而寻找问题的全局最优解[14-15]。由于本文所研究的是具有时间窗约束的拣选机器人调度问题，因此采用遗传算法进行求解，其流程如图2所示，具体求解步骤如下：

1)设置初始种群的个数，确定一次下发任务的数量，将订单中的任务按照每次的下发数量进行分组，规定每组任务内不能调用同一台拣选机器人执行任务，利用实数对染色体进行编码，染色体的长度表示任务的总数，染色体中每个基因位表示任务的序号，基因位上的实数表示该序号的拣选机器人完成对应基因位的任务。利用实数进行编码可以直接观察到各个拣选机器人执行的任务以及依次执行的任务序列。

2)计算种群内所有染色体的适应度值。首先计算拣选机器人完成所有任务所花费的运行成本，其次观察每个任务完成拣选的时刻是否符合其时间窗要求，计算由于不符合时间窗要求所造成的惩罚成本，最终染色体的适应度值为拣选机器人执行所有任务所花费的总成本的倒数，以硬时间窗拣选机器人调度模型为例，其适应度函数为：

(17)

3)在上述种群中，将染色体按照适应度值进行排序，采用精英保存策略选择出一定数量的适应度值较高的优良染色体作为父代。

4)确定交叉概率，本文将染色体按照每次下发任务的数量进行分段，在染色体的段数范围内随机生成两个实数作为两父代染色体的交叉位置，其次，两父代染色体对应交叉位置的基因段进行交叉操作，产生新的个体，采用这种交叉方式保证了每组内不会调用相同的拣选机器人执行任务。

5)确定变异概率，在染色体长度范围内，随机生成一个实数作为父代染色体的变异位置，将此位置的基因变异成拣选机器人的序号，该序号不能与同一段基因位上的序号相同，代表不能同时调度一台拣选机器人完成一组内的多个任务。

6)设置最大迭代次数，如果迭代次数达到最大迭代次数，停止迭代，输出拣选机器人完成所有任务所花费的总成本、拣选机器人的调度结果与所有任务的拣选完成时间。

4 仿真与结果分析

为了验证遗传算法求解拣选机器人调度模型的有效性，将初始种群的个数设置为100个，交叉概率与变异概率分别设置为0.9和0.08。对于每一个算例，均采用相同参数，运行10次取其最小值作为最终结果。假设实验在50m× 50m的智能仓储系统中进行，拣选工作站的位置坐标为(5，2)，以10台拣选机器人和60个任务为例，其位置坐标分别见表1和表2，该批任务中有10个任务具有时间约束。其中拣选工作站对应工作人员的拣货时间为8s，分货时间为6s，按照每台拣选机器人每小时的功率为100W，电费为0.86元/千瓦时计算，得出系统中每台拣选机器人每秒内的运行成本为0.00083元。每3个任务为一组下发一次，下发时间为上一组任务中最早到达该拣选工作站的时刻。该批任务的完成时间为所有拣选机器人完成各自任务耗时最长的时间。

表1 拣选机器人位置坐标

表2 任务位置坐标

首先对硬时间窗约束下的拣选机器人调度进行仿真。若任务没有在要求时间内完成，惩罚成本设置为一个较大数值，相较于运行成本，这里选择惩罚成本为10元。仿真结果如图2所示，拣选机器人调度结果见表3，任务的硬时间窗以及完成拣选的时刻见表4。

图2 硬时间窗约束下完成所有任务所花费的总成本

表3 硬时间窗约束下拣选机器人调度结果

表4 任务的硬时间窗以及完成拣选的时刻

图2表示硬时间约束下拣选机器人完成所有任务所花费的总成本，图中可以看出随着迭代次数的增加，成本不断减少，最终得到最优调度结果使其成本达到最小值，说明遗传算法能够对该模型进行求解。表3中拣选机器人调度结果的第一位数字表示拣选机器人的序号，后面为拣选机器人依次执行的任务的序号。从表4中可以看出，所有具有硬时间窗约束的任务被拣完的时刻均在各自的硬时间窗范围内。

为进一步验证硬时间窗约束的拣选机器人调度模型，将具有硬时间窗约束的任务数量增加，拣选机器人完成所有任务所花费的总成本如图3所示。

图3 具有硬时间窗约束的任务总数不同情况下拣选机器人完成所有任务所花费的总成本

图3表示具有硬时间窗约束的任务总数不同情况下拣选机器人完成所有任务所花费的总成本，从图中可以明显看出，随着具有硬时间窗的任务数量增加，拣选机器人调度问题的可行解数量减少，成本呈缓慢上升趋势，直至具有硬时间窗约束的任务数量为19时，成本明显上升。仿真结果显示，第58个任务的拣选完成时间不在其硬时间窗约束范围内，意味着此时拣选机器人不能在硬时间窗约束下顺利完成所有任务。

因此，本文通过增加拣选机器人的调度数量来完成上述任务，将拣选机器人的数量分别取11、12、13、14、15，结果如图4所示。

图4 19个任务具有硬时间窗约束下调度不同数量的拣选机器人完成所有任务所花费的总成本

图4表示19个任务具有硬时间窗约束下调度不同数量的拣选机器人完成任务所花费的总成本，图中可以看出当调度11台拣选机器人时，上述任务可以顺利完成。随着拣选机器人的调度数量的增加，拣选机器人在拣选工作站的等待时间增加，使得完成所有任务的总时间也会增加，进而导致成本上升。

通过以上结果看出，对于具有硬时间窗约束的拣选机器人调度问题，当具有硬时间窗的任务增加到一定程度时，拣选机器人不能顺利完成任务，可以通过增加拣选机器人的调度数量完成任务。但需要考虑机器人的硬件投入成本。

因此，针对上述任务，采用软时间窗约束的方式，允许在可接受最早时刻前拣完和可接受最晚时刻后拣完，但通过加入惩罚成本对其进行惩罚。当18个任务具有时间窗约束时，采用硬时间窗约束的方式可以顺利完成任务，因此按照软时间窗约束方式与硬时间窗约束方式完成上述任务的时间相同，将max1与max2分别取0.5元、0.6元。仿真结果如图5所示，拣选机器人调度结果见表5，表6为任务的软时间窗以及完成拣选的时刻。

图5 19个任务具有软时间窗约束下拣选机器人完成所有任务所花费的总成本

表5 软时间窗约束下拣选机器人调度结果

表6 具有时间约束的任务软时间窗以及完成拣选的时刻

图5表示19个任务具有软时间窗约束下拣选机器人完成所有任务所花费的总时间，采用软时间窗约束时所有的任务都可以顺利完成，从表6中可以看出，只有第11个任务与第19个任务没有在各自希望的时间范围内完成，造成了一定的惩罚成本，其总成本为12.2885元，但该成本低于硬时间窗约束下调度11台拣选机器人时所花费的总成本。

为了验证软时间窗约束下的拣选机器人调度模型，将具有时间约束的任务数量增加，仿真结果如图6所示。

图6 具有软时间窗约束的任务总数不同情况下拣选机器人完成所有任务所花费的总成本

图6为具有软时间窗约束的任务总数不同情况下拣选机器人完成所有任务所花费的总成本，图中可以明显看出，随着具有时间约束的任务数量增加，总成本呈缓慢上升趋势，当有22个任务具有时间约束时，其总成本依然小于硬时间窗约束下调度11台拣选机器人时所花费的总成本。

综上分析，当智能仓储系统对部分任务采用硬时间窗约束时，随着有时间约束的任务数量增加，拣选机器人完成所有任务所花费的总成本增加，当具有时间约束的任务数量增加到一定程度时，拣选机器人不能顺利完成所有任务，因此只能通过增加拣选机器人的调度数量使得任务能够在其硬时间窗内顺利完成。而当智能仓储系统对部分任务采用软时间窗约束时，所有任务都可以顺利完成，可能会造成一定的惩罚成本，但其总成本低于采用硬时间窗约束时增加拣选机器人的调度数量所花费的总成本。由于智能仓储系统中拣选机器人的数量有限，通过增加拣选机器人的调度数量来完成更多具有时间约束的任务不切实际，因此，采用软时间窗约束的方式进行调度不仅可以完成所有任务，还可以降低智能仓储系统运行的总成本。

5 结束语

在“货到人”智能仓储系统中，科学合理地调度拣选机器人完成任务是提高物流效率，降低物流成本的主要途径。本文从拣选机器人调度角度进行优化，通过使系统的运行成本最小，即拣选机器人完成所有任务所花费的总成本最小，利用时间窗理论，以最大限度满足系统对部分任务完成时间的要求，同时考虑拣选机器人在拣选工作站的排队等待时间，分别建立硬时间窗约束下与软时间窗约束下的拣选机器人调度模型。利用遗传算法对两模型进行求解，解决了拣选机器人的调度与拣选序列问题。仿真结果表明当具有时间约束的任务增加到一定数量时，采用软时间窗约束的方式能够使得所有任务顺利完成，并且可以降低系统运行的成本，进而为“货到人”智能仓储系统的应用实践提供了参考。