“货到人”拣选系统的两阶段随机规划模型

A Two-Stage Stochastic Programming Model for the “Goods to People” Picking System

摘要: 在“货到人”智能仓储拣选体系中，机器人的合理调度和任务分配影响着系统的效率与成本。为此本文同时考虑“货到人”拣选系统中的机器人调度和任务分配，建立了机器人空闲时间不确定的两阶段随机规划模型。第一阶段，对于给定的机器人数量，作出是否调度机器人的上层策略，使得机器人完成所有任务耗费的总期望成本最小；第二阶段，对于某个场景，作出如何合理地进行任务分配的下层策略，使得机器人完成所有任务的空闲时间成本最小。然后利用遗传算法对此模型进行求解，并通过实例仿真验证了模型的可行性。

Abstract: In the intelligent warehouse picking system of “goods to people”, the reasonable scheduling and task assignment of robots affect the efficiency and cost of the system. Therefore, this paper considers both robot scheduling and task assignment in the “goods to people” picking system, and establishes a two-stage stochastic programming model with uncertain robot idle time. In the first stage, for a given number of robots, the upper-level strategy of whether to schedule robots is made to minimize the total expected cost of robots completing all tasks; In the second stage, for a certain scene, the lower-level strategy of how to allocate tasks reasonably is made to minimize the cost of idle time for the robot to complete all tasks. Then the genetic algorithm is used to solve the model, and the feasibility of the model is verified by an example simulation.

1. 引言

随着互联网经济的发展，全球经济逐渐向数字经济转型，其中最具有代表性的一种表现就是电子商务的崛起。电子商务的繁荣发展促进了快递物流行业的兴起。如何提高物流体系的效率是电子商务企业现在最为关注的问题。在整个物流体系中，智能仓储系统是影响其效率的极为重要的一个部分 [1] 。美国亚马逊成功研发和应用Kiva机器人系统使整个仓储系统的存拣货效率有了大大的提高，它改变了传统的“人到货”拣选模式，提出一种新型的“货到人”拣选模式 [2] 。这种拣选模式中的任务分配是指机器人将系统接收到的每批订单的每个任务分别分配给系统中不同的搬运机器人，由机器人把订单包含的货物所在的货架搬运到拣选员工所在的拣选台的位置以供员工拣选。

近几年，已有很多学者对“货到人”拣选系统中的机器人任务分配问题进行了研究。比如袁瑞萍等 [3] 以机器人完成所有任务的最短时间为任务目标，分别建立了机器人在同步和异步拣选模式下的任务调度模型，并采用改进的协同进化遗传算法进行求解，得出多个拣选平台同步拣选效果较好。石媛媛等 [4] 建立任务均衡分配以及路程代价最优双重目标模型，结合提出的一种平衡拍卖启发式算法，解决了智能仓储机器人的任务分配问题。Nielsen等 [5] 研究了单个机器人的调度模型，并对其配送能力进行了约束，采用基于遗传算法的启发式算法求解机器人的配送任务数。谢永盛等 [6] 以机器人到任务位置路径最短为目标建立模型，利用改进的布谷鸟搜索算法，通过实例仿真，有效解决了机器人的任务分配以及路径规划。秦新立等 [7] 对机器人的电量、数目和任务载荷进行约束，以机器人的性能指标最优为任务目标，将多机器人的任务分配问题看作多旅行商问题，通过改进的蚁群算法很好的解决了多机器人的任务分配问题。王振庭等 [8] 以机器人执行任务时的转向次数、路程代价、最大任务等待时间为优化目标，采用遗传算法对机器人的任务进行分配，Q-learning算法对机器人分配到的任务进行具体路径规划。

在“货到人”拣选系统中，如何调度机器人也至关重要，已有学者对机器人的调度问题进行了研究。例如Milica等 [9] 构建了多目标机器人规划模型，提出了一种基于单移动机器人的多目标灰狼优化器方法，利用改进的遗传算法，解决了机器人的调度问题。Jia Ma等 [10] 建立了最小化机器人执行任务总时间和最大化单个机器人执行任务时间的多目标规划模型，提出一种新的基于Parcto的MOEA，在机器人的调度问题上取得了较好的结果。李腾等 [11] 考虑了机器人在完成任务的过程中行走距离的不确定性，建立鲁棒双层规划模型，通过遗传算法，解决了机器人的调度和任务分配问题。

综上所述，现有文献绝大多数以时间或运行成本为优化目标，没有考虑机器人的空闲成本，并且都假设机器人在行走过程中是畅通的，但在实际情况中，机器人在行走过程中有可能发生堵塞和排队，这样会造成机器人运行时间的不确定性。因此本文同时考虑“货到人”拣选系统中的机器人调度及任务分配问题，建立了机器人空闲时间不确定的两阶段随机规划模型。第一阶段，对于给定的机器人数量，作出是否调度机器人的上层策略，使得机器人完成所有任务耗费的总期望成本最小；第二阶段，对于某个场景，作出如何合理地进行任务分配的下层策略，使得机器人完成所有任务的空闲时间成本最小。然后利用遗传算法对此模型进行求解，并通过实例仿真验证了模型的可行性。

2. 两阶段随机规划模型

2.1. 问题描述

“货到人”拣选系统仓库的平面布局通常用二维平面栅格化地图表示 [12] ，如图1所示，主要由货架、拣选台、机器人停车区组成。

Figure 1. “Goods to people” picking system warehouse plan

图1. “货到人”拣选系统仓库平面图

机器人在接收到系统下发的任务分配信息时，先从初始位置移动到其被分配的第一个任务所对应的货架位置，然后将该货架搬运至拣选台前，等待工作人员在货架上挑选货物并打包，再将工作人员拣选完毕的货架搬运回货架原来的位置，并在该货架前等待下一个任务分配，以此循环，直到完成机器人被分配的所有任务。如果机器人在搬运货架的路途中发生堵塞，机器人可以选择等待或者改变路径。图2为一个机器人完成任务的流程图。

Figure 2. Flow chart of robot completing task

图2. 机器人完成任务流程图

为了建立一个合理的模型，本文提出以下假设：

1) 在初始时刻，仓库中的所有机器人都处于闲置状态。

2) 所有机器人在运行过程中的电力始终充足。

3) 所有机器人都从相同的初始位置开始。

4) 仓库内所有货物均不短缺。

5) 机器人将货架移回原位后，在货架位置等待下一个任务的分配。

6) 不考虑机器人的固定购买成本。

2.2. 模型建立

符号含义如表1所示。

Table 1. Symbol meaning table

表1. 符号含义表

(机器人调度)决策变量 $Y_i$ 表示是否调度机器人 $R_i$ 来完成任务，则

$Y_i=\{\begin{array}{cc}1,& 调度机器人R_i\\ 0,& 否则\end{array}$ (1)

(任务分配)决策变量 $X_{ij}$ 表示机器人 $R_i$ 是否完成任务 $Z_j$ ，则

$X_{ij}=\{\begin{array}{cc}1,& 机器人R_i完成任务Z_j\\ 0,& 否则\end{array}$ (2)

$T_{ij}\left({\xi }_k\right)$ 为第 $k$ 种场景下机器人 $R_i$ 完成任务 $Z_j$ 所花费的时间， $k=\left\{1,2\right\},{\xi }_k\in \Xi =\left\{{\xi }_1,{\xi }_2\right\}$ 。记 ${\tilde{T}}_{ij}\left({\xi }_k\right)$ 为机器人 $R_i$ 完成任务 $Z_j$ 额外的时间增加值。假设机器人完成任务时行走距离不变，路径状况分为两种情况：

第一种情况道路畅通无阻，即机器人在完成任务过程中不发生堵塞或排队，没有产生额外的时间损耗，即 ${\tilde{T}}_{ij}\left({\xi }_1\right)=0$ ，那么机器人完成任务的时间是：

$T_{ij}\left({\xi }_1\right)=\left(\frac{d_{BjQ}+d_{QBj}}{V_1}+\frac{d_{AiBj}}{V_2}\right)\ast X_{ij}$ (3)

第二种情况道路发生拥堵，即机器人在完成任务过程中发生堵塞或者在拣选台等候等情况，因本文假设发生这些情况时机器人不改变路径，而是在原地等待，直到可以通过，此时就会产生一个时间的增加值，即 ${\tilde{T}}_{ij}\left({\xi }_2\right)\ne 0$ ，那么机器人完成任务的时间是：

$T_{ij}\left({\xi }_2\right)=\left(\frac{d_{BjQ}+d_{QBj}}{V_1}+\frac{d_{AiBj}}{V_2}+{\tilde{T}}_{ij}\left({\xi }_2\right)\right)\ast X_{ij}$ (4)

$T\left({\xi }_k\right)$ 为第 $k$ 种场景下所有机器人完成任务的总时间，也就是每一个订单批次中执行任务时间最长的机器人的执行时间，则

$T\left({\xi }_k\right)=\underset{i=1,2,\mathrm{...},n}{\max }\left\{{\displaystyle \underset{j=1}{\overset{m}{\sum }}{T}_{ij}\left({\xi }_k\right)}\right\}$ (5)

两阶段随机规划问题是随机规划问题的一个分支，是特殊的期望值模型 [13] 。本文考虑了机器人调度与机器人任务分配问题，建立了基于机器人空闲时间不确定的两阶段随机规划模型。

第一阶段，从全局层面决定机器人是否被调度，对于给定的机器人数量，作出是否调度机器人的上层策略，使得机器人完成所有任务耗费的总期望成本最小。

第一阶段模型：

$\min$ $C$ (6)

$\begin{array}{l}={\displaystyle \underset{i=1}{\overset{n}{\sum }}{C}_r{Y}_i{D}_i+E_{\xi }\left[{\displaystyle \underset{i=1}{\overset{n}{\sum }}{C}_f\left(Y_i,\xi \right)}\right]}\\ ={\displaystyle \underset{i=1}{\overset{n}{\sum }}\left(C_r{Y}_i{D}_i+E_{\xi }\left[C_f\left(Y_i,\xi \right)\right]\right)}\end{array}$

$s.t.$ ${\displaystyle \underset{i=1}{\overset{n}{\sum }}{Y}_i\le n}$ (7)

$Y_i\in \left\{0,1\right\},i=1,2,\cdots ,n$ (8)

$d_{AiBj}=\left|x_{Ai}-x_{Bj}\right|+\left|y_{Ai}-y_{Bj}\right|$ (9)

$d_{BjQ}=d_{QBj}=\left|x_{Bj}-x_Q\right|+\left|y_{Bj}-y_Q\right|$ (10)

$D_{ij}=d_{AiBj}+d_{BjQ}+d_{QBj}$ (11)

$D_i={\displaystyle \underset{j=1}{\overset{m}{\sum }}{D}_{ij}\ast Y_i}$ (12)

其中目标函数将所有机器人完成任务所花费的总成本分为两个部分， ${\displaystyle {\sum }_{i=1}^n{C}_r{Y}_i{D}_i}$ 为机器人的行走成本。本文道路情况只考虑两种场景：堵塞和畅通，所以随机变量 $\xi$ 是离散的，只包含两个值，且分布律是已知的， $P\left({\xi }_k\right)=\left[P_1,P_2\right]$ ，每种情况对应的时间值也是确定的，所以空闲时间的成本值可以用空闲时间成本的期望值来表达，即可以用 $E_{\xi }\left[{\displaystyle {\sum }_{i=1}^n{C}_f\left(Y_i,\xi \right)}\right]$ 来表达。堵塞情况下时间的增加值假设服从均值为 $\mu$ ，方差为 $\sigma$ 的正态分布，且每个机器人完成任务的时间是相互独立的。式(7)表示调度机器人的数量不能超过系统中机器人的配置数量。

第二阶段，从局部层面决定任务如何合理地分配给机器人，对于某个场景，作出如何合理地进行任务分配的下层策略，使得机器人完成所有任务的空闲时间成本最小。

$\min$ $C_f\left(Y_i,{\xi }_k\right)$ (13)

$\begin{array}{l}=C_f\left(1-Y_i\right)T\left({\xi }_k\right)+C_f{Y}_i\left(T\left({\xi }_k\right)-{\displaystyle \underset{j=1}{\overset{m}{\sum }}{T}_{ij}\left({\xi }_k\right)}\right)\\ =C_f\left[\underset{i=1,2,\mathrm{...},n}{\max }\left\{{\displaystyle \underset{j=1}{\overset{m}{\sum }}{T}_{ij}\left({\xi }_k\right)}\right\}-{\displaystyle \underset{j=1}{\overset{m}{\sum }}{T}_{ij}\left({\xi }_k\right)}\right]\end{array}$

$s.t.$ ${\displaystyle \underset{i=1}{\overset{n}{\sum }}{X}_{ij}=1,j=1,2,\cdots ,m}$ (14)

$\left({\displaystyle \underset{j=1}{\overset{m}{\sum }}{X}_{ij}-1}\right)Y_i\ge 0,i=1,2,\cdots ,n$ (15)

$X_{ij}\in \left\{1,0\right\},i=1,2,\cdots ,n;j=1,2,\cdots ,m$ (16)

$k=\left\{1,2\right\},{\xi }_k\in \Xi =\left\{{\xi }_1,{\xi }_2\right\}$ (17)

其中，目标函数将机器人的空闲时间分为两个部分， $\left(1-Y_i\right)T\left({\xi }_k\right)$ 为没有被调度的机器人的等待时间， $Y_i\left(T\left({\xi }_k\right)-{\displaystyle {\sum }_{j=1}^m{T}_{ij}\left({\xi }_k\right)}\right)$ 为机器人在完成任务过程中由于堵塞排队所造成的空闲时间。式(14)表示一个任务只由一个机器人来完成。式(15)表示被调度的机器人至少需要完成一个任务。

3. 遗传算法

为了消除时间不确定性对求解造成的困难，可将问题转化为常规的规划问题进行求解 [14] ，先将第一阶段期望值的表达形式具体化，再在约束的条件下，寻找解集，使目标函数达到最优。本文中时间的不确定性是由于道路情况的不确定性造成的，道路情况分为堵塞和畅通两种场景，根据两种场景发生的概率，写出期望总成本的表达式。即：

$\min$ $C$ (18)

$\begin{array}{l}={\displaystyle \underset{i=1}{\overset{n}{\sum }}{C}_r{Y}_i{D}_i+E_{\xi }\left[{\displaystyle \underset{i=1}{\overset{n}{\sum }}{C}_f\left(Y_i,\xi \right)}\right]}\\ ={\displaystyle \underset{i=1}{\overset{n}{\sum }}{C}_r{Y}_i{D}_i}\\ +{\displaystyle \underset{k=1}{\overset{2}{\sum }}{C}_{f}P\left({\xi }_k\right)\left[\underset{i=1,2,\mathrm{...},n}{\max }\left\{{\displaystyle \underset{j=1}{\overset{m}{\sum }}{T}_{ij}\left({\xi }_k\right)}\right\}-{\displaystyle \underset{j=1}{\overset{m}{\sum }}{T}_{ij}\left({\xi }_k\right)}\right]}\end{array}$

遗传算法是一种模拟生物自然选择和遗传进化过程的优化算法，它在初始种群中根据适应度函数选择最优个体，通过染色体的交叉变异按照优胜劣汰的原则更新种群，最终得到适应度值最高的染色体 [15] 。遗传算法适合用于求解组合优化问题 [16] [17] ，机器人的调度与任务分配问题其实是一种组合优化问题，也就是NP-hard问题，因此本文选择与传统的遗传算法相结合，使用循环机器人个数的方式求解，先给定一个初始的机器人数量，再运用遗传算法。求解流程图如图3所示。具体步骤如下：

步骤一：初始化种群参数。染色体的编码方式采用实数编码，如图4所示，实数编码可以明显观察到机器人与其完成的任务之间的对应关系。

步骤二：计算适应度值。给定一个初始的机器人数量，运用遗传算法对模型进行求解，把期望总成本的倒数作为适应度函数，即：

$f\left(x\right)=\max \left\{\frac{1}{{\displaystyle \underset{i=1}{\overset{n}{\sum }}{C}_r{Y}_i{D}_i}+{\displaystyle \underset{k=1}{\overset{2}{\sum }}{C}_{f}P\left({\xi }_k\right)\left[\underset{i=1,2,\mathrm{...},n}{\max }\left\{{\displaystyle \underset{j=1}{\overset{m}{\sum }}{T}_{ij}\left({\xi }_k\right)}\right\}-{\displaystyle \underset{j=1}{\overset{m}{\sum }}{T}_{ij}\left({\xi }_k\right)}\right]}}\right\}$ (19)

步骤三：选择。将染色体按照适应度值的大小排序，适应度值越大，期望总成本就越小。用精英保留策略筛选适应度值较高的染色体作为父代染色体。

步骤四：交叉和变异。按照交叉概率变异概率对选择个体进行变异，随机生成一个父代染色体的变异位置，变异时只将该位置的基因变异成所调度的其他机器人的编号。

Figure 3. Flow chart of genetic algorithm

图3. 遗传算法流程图

Figure 4. Chromosome coding example

图4. 染色体编码示例

步骤五：输出机器人任务分配结果。设定种群最大迭代次数，当达到最大迭代次数时，停止计算，记录当前调度机器人数量下的历史最小期望总成本值以及任务分配结果。

步骤六：循环。将调度机器人的数量加1，再做一次遗传算法，直到调度机器人的数量等于系统中机器人的配置数量，停止循环，比较调度不同机器人数量的最小期望总成本，输出期望总成本最小的机器人调度数量以及任务分配结果。

4. 实例仿真与分析

4.1. 实例描述

仿真环境设定为一个50 m × 50 m的仓库，机器人的负载速度为1米/秒，空载速度为2米/秒，机器人在单位时间内的空闲成本为0.0006元/秒，行走单位距离所花费的成本为0.00086元/米，假设道路畅通的概率P1为0.5，道路堵塞的概率P2为0.5，仓库中有8个机器人，拣选台的位置为(25, 2)，指定机器人的初始位置为(0, 10)，空闲时间的增加值的均值设为2，方差设为0.99。实验所涉及到的任务坐标如表2所示。

Table 2. Task coordinates

表2. 任务坐标

4.2. 机器人任务分配结果分析

对两阶段随机规划模型的机器人任务分配问题进行仿真，遗传算法参数中，初始种群个数设为200个，最大迭代次数设为5000次，交叉概率和变异概率设为0.8。随机从表1选取任务的数量分别为40个、50个、60个、70个和80个，通过采用循环机器人数量的方式进行仿真，对比不同数量机器人的空闲时间成本、期望总时间成本和任务分配结果，以便选择调度最优机器人个数，考虑到任务数量比较多，初始调度机器人数量设为4个，最大机器人数量为8个，以下仿真实验的结果包括机器人的调度数量、总空闲时间成本、期望总成本和机器人任务分配结果。

图5~9的纵坐标表示搬运任务所花费的期望总成本，横坐标表示机器人的数量，实验结果显示，对于搬运相同数量任务，调度机器人数量的不同，所花费的总期望成本也不同，并且可以看出在完成相同数量任务时，花费的期望总成本随机调度器人数量的增加呈波动上升的趋势，调度8个机器人时花费的期望总成本都是最多的。

Figure 5. Minimum cost for scheduling robots to complete 40 tasks

图5. 调度机器人完成40个任务所花费的最小成本

Figure 6. Minimum cost for scheduling robots to complete 50 tasks

图6. 调度机器人完成50个任务所花费的最小成本

Figure 7. Minimum cost for scheduling robots to complete 60 tasks

图7. 调度机器人完成60个任务所花费的最小成本

Figure 8. Minimum cost for scheduling robots to complete 70 tasks

图8. 调度机器人完成70个任务所花费的最小成本

Figure 9. Minimum cost for scheduling robots to complete 80 tasks

图9. 调度机器人完成80个任务所花费的最小成本

图5、图6和图8显示当完成40个、50个和70个任务时调度4个机器人搬运任务所花费的期望总成本最小，分别为1.88元、2.30元和3.03元。从图7和图9观察出完成60个和80个任务时调度5个机器人所花费的期望总成本最小，分别为2.64元和3.39元。

完成40个、50个、60个、70个和80个任务的机器人最优数量、总空闲时间成本、期望总成本以及具体的任务分配结果如表3所示。随着完成任务数量的增加，机器人完成任务所花费的期望总成本也随之增加。在任务分配结果中，加粗的数字代表调度机器人的编号，其后面的数字代表该编号机器人被分配的所需要搬运的任务编号。表格显示对于不同搬运任务是数量情况，对于每个机器人被分配的任务数量是相对均衡的，搬运40个、50个和70个任务，调度的4个机器人每个搬运的任务数量区间分别为[9, 11]、[11, 14]和[15, 19]；搬运60个和80个任务，调度的5个机器人每个搬运的任务数量区间为[11, 14]和[15, 18]。

本文提出的基于空闲时间不确定性的两阶段随机规划模型，机器人在搬运过程中，发生堵塞、排队等，不改变原有路径，而是在原地等待，由此造成空闲时间不确定。将其仿真结果与普通的两阶段规划模型做对比，这里普通的两阶段规划模型的时间成本是指，不考虑堵塞、排队带来的空闲时间因素，也就是发生这类情况后，机器人不在原地等待，而是绕路避开，这里就会由于路程增加而产生的时间成本的增加。两种模型对比结果如表3所示，首先两种模型都可以得到具体的任务分配结果和各自最优总成本，并且任务分配结果是完全不同的。在搬运50个、60个和70个任务时普通的两阶段规划模型的仿真实验的时间成本是多于基于空闲时间不确定性的两阶段随机规划模型的仿真实验的空闲时间成本，并且普通的两阶段规划模型的仿真实验的总成本都多于基于空闲时间不确定性的两阶段随机规划模型的仿真实验的期望总成本，由此可以表明，在搬运过程中，发生堵塞、排队等情况时，让机器人在原地等待比绕路更节约成本。

Table 3. Robot scheduling, total idle time cost, expected total cost and task allocation results for different tasks

表3. 完成不同数量任务的机器人调度、总空闲时间成本、期望总成本以及任务分配结果

5. 结论

本文考虑了机器人在完成任务过程中由于堵塞、排队等耗费的空闲时间的不确定因素，建立的基于空闲时间不确定性的两阶段随机规划模型为机器人调度和任务分配问题提供了一种新的解决思路，第一阶段，对于给定的机器人数量，作出是否调度机器人的上层策略，使得机器人完成所有任务耗费的总期望成本最小化；第二阶段，对于两种场景，作出如何合理地进行任务分配的下层策略，使得机器人完成所有任务的空闲时间成本最小化，通过结合遗传算法，成功地解决了模型的求解问题，实现了机器人的高效调度和任务分配。通过仿真实验结果显示，该模型具有很好的可行性和有效性，可以得到具体的机器人调度数量以及任务分配方案，搬运任务数量的增加不代表调度机器人的数量也跟着增加，在完成40个任务至80个任务，调度4个或者5个机器人去搬运可以花费更少的成本，并且通过对比实验得出当机器人搬运过程中遇到堵塞、排队时，在原地等待再通过的方案比让机器人绕路避开的方案要更节省成本消耗。

基金项目

湖北省教育厅科学研究计划资助青年项目(Q20211111)、冶金工业过程系统科学湖北省重点实验室开放基金项目(Y201905)、国家自然科学基金项目(12361064)。