移动机器人履行系统中订单分配和AGV调度联合优化方法

移动机器人履行系统中订单分配和agv调度联合优化方法
技术领域
1.本发明涉及移动机器人技术领域，尤其涉及一种移动机器人履行系统中订单分配和agv调度联合优化方法。


背景技术：

2.在rmfs(robotic mobile fulfillment system，移动机器人履行系统)动态订单处理研究中，有方案研究的场景为货架重复有序的访问拣货台，拣货员按一定顺序拣选订单。一个拣货台可以同时拣选的订单数有限，且货架可在拣货台等待订单的换入和换出，局限性在于只考虑了单拣货台的情况。然后建立了以最小化货架访问次数为目标函数的混合整数规划模型，提出了两种动态规划算法分别求解订单排序和货架排序，再用模拟退火算法将它们结合起来。实验结果表明经过优化的订单拣选可以减少一半以上的机器人数量。还有方案基于同样的场景使用变邻域搜索算法来求解该问题。分别设计了vns-os和vns-rs算法求解订单处理顺序和货架访问顺序，并且提出了交替这两个算法同时优化订单、货架排序的ah算法。在不同规模的算例求解中均取得不错的效果，结果表明优化后的订单拣选方案可以有效的提高货架的利用率。
3.还有方案在假设一个货架只能访问一个拣货台的条件下，研究多个拣货台的订单分配问题，并且建立以选择货架数量最小化为目标函数的混合整数规划模型，接着在此基础上进行订单排序和货架排序的优化。其次设计了结合数学规划方法的启发式算法对模型进行求解，在货架可重复访问和不可重复访问的算例中分别进行了实验，结果表明货架可重复访问的场景下访问次数更少，原因是订单分配和排序可以有更多的组合。该论文相较之前的研究，更进一步考虑了订单分配给拣货台的问题，但实际上是分成两个阶段进行求解。
4.还有方案考虑了多个拣货台的订单处理排序和货架访问排序，并且货架可以访问多个拣货台。通过设置货架访问拣货台的时间，约束货架不能同时服务多个拣货台，然后建立了以货架访问次数最少为目标函数的混合整数规划模型。接着设计了自适应大规模邻域搜索算法求解模型，在实际案例验证中减少了62％的货架移动次数。
5.关于agv(automated guided vehicle，自动导向车)的动态调度研究，有方案研究rmfs中的agv任务指派问题，考虑拣货台的拣货速度来分配拣货任务，认为任务应当优先分给当前拣货速度快的拣货台。然后设计了邻域搜索算法来求得近似最优解。最后应用仿真的方法验证实例，实验结果表明考虑拣货速度分配货架任务比随机分配货架任务效率更高。
6.agv联合其他资源调度在rmfs场景下这方面的研究较少。有方案研究车间agv的调度问题，以agv给车间配料区补料搬运时间最短为目标建立数学模型，设计了一种改进的遗传算法进行任务分配和排序优化，并采用分段式交叉变异算子以避免常规交叉变异算子出现非法解的状况，最后通过实例验证了该方法的有效性和可行性。还有方案同时车间考虑作业调度和无冲突agv路径，以完工时间最短建立混合整数规划模型，并采用两阶段蚁群算
法进行求解，在13个算例中均表现优异。
7.上述现有技术中的rmfs订单处理方法的缺点包括：没有考虑agv调度，默认采用货架访问次数来代替agv的行驶路径成本和时间成本，以简化问题着重关注订单批次与货架的供需匹配。而在agv调度问题的相关研究中，假设条件中均包含拣货台需求已确定或访问货架已确定。但实际情况是，订单的需求需要货架来满足，而货架的移动则依赖于agv，三者密不可分。在多拣货台的场景下订单的分配势必影响着agv的调度。


技术实现要素：

8.本发明的实施例提供了一种移动机器人履行系统中订单分配和agv调度联合优化方法，以实现有效地提高移动机器人履行系统的工作效率。
9.为了实现上述目的，本发明采取了如下技术方案。
10.一种移动机器人履行系统中订单分配和agv调度联合优化方法，包括：
11.step1：初始化参数，输入订单数据d
pi
、货架库存数据c
mi
、货台订单处理上限e、agv任务数量上限l、时间计算参数、任务之间的走行时间t
msm
′s′
、域算子输入常数、扰动次数k和迭代次数上限n
max
；
12.step2：生成初始解，令迭代次数n＝0，依次执行订单分批算法、货架选择算法、订单批次指派算法和给移动机器人agv分配任务算法得到订单分配方案、货架访问方案和agv任务分配方案的初始解，将所述初始解同时赋给当前最优解obj和局部最优解obj
max
；
13.step3：变换邻域搜索局部最优解，以obj为输入，依次在货架供应商品种类减少、货架任务删除、货架任务重新分配、货架任务交换和货架替换五个邻域中进行局部搜索，不断的改进当前最优解obj域变换规则，当在货架替换邻域搜索中找不到更优的解时，转入step4；
14.step4：判断obj是否优于obj
max
，如果是，令obj
max
＝obj，转入step5；否则，直接转入step5。
15.step5：判断迭代次数n是否大于或者等于n
max
，如果是，输出obj
max
，算法终止；否则令n＝n+1，转入step6；
16.step6：在邻域内扰动生成新的解，以扩大搜索空间；
17.在1～e随机生成一个整数，将整数赋给扰动次数k后随机选择一个扰动邻域，以obj
max
输入，执行邻域算子k生成新解并赋给obj，转入step3。
18.优选地，建立移动机器人履行系统中订单分配和agv调度联合优化的混合整数规划模型,所述混合整数规划模型的相关集合、参数和决策变量如表1，2和3所示：
19.目标函数与约束条件
20.ioarsp问题的目标是最小化系统完工时间，目标函数见式(6)，其中u表示系统完工时间；
21.minimizeu(6)
22.模型包括四类约束条件：拣货台订单分配约束、货架与拣货台商品供需约束、agv执行货架任务约束以及时间约束；
23.(1)拣货台订单分配约束
24.订单需要分配到拣货台，按照订单商品需求进行拣选。
[0025][0026][0027]
式(7)表示每个订单都有且只被分配到一个拣货台，式(8)表示每个拣货台处理的订单数量有限制；
[0028]
(2)货架与拣货台商品供需约束
[0029]
货架访问拣货台进行拣选时，商品的供应与需求需要平衡；
[0030][0031][0032][0033]
式(9)表示货架访问拣货台就会供应商品，如果不供应商品，货架就不访问拣货台，式(10)表示任一货架供应所有拣货台的任一商品的数量不能超过其库存量，式(11)表示所有货架供应任一拣货台的任一商品的数量之和正好等于其需求量，其中表示分配到拣货台s的所有订单中商品i的需求量之和；
[0034]
(3)agv执行货架任务约束
[0035]
货架任务需要分配给agv，agv执行货架任务需要有顺序；
[0036][0037][0038][0039][0040][0041][0042][0043]
式(12)表示每一个货架访问拣货台的任务都需要一台agv完成，且仅能由一台agv完成，式(13)表示每一个agv执行的任务数量有限制，式(14)表示搬运同一货架的不同任务不能被分配给不同的agv，只能分配给同一台agv，式(15)和(16)表示分配到任务的agv都从车场出发去执行任务，执行完任务后都要回到车场，没有任务的agv则一直待在车场，式(17)和(18)表示分配到agv的每一个任务都有前序任务和后序任务，前序任务中包含离开车场任务，后序任务中包含回到车场任务；
[0044]
(4)时间约束
[0045]
时间约束包括货架任务相关时间和agv返回车场时间的约束；
[0046][0047][0048][0049][0050][0051][0052][0053][0054][0055][0056][0057]
式(19)表示搬运同一货架的不同任务是连续的，式(20)表示货架任务在拣货台的拣货结束时间为拣货开始时间加上拣货时间，其中拣货时间由固定拣货时间b和固定拣取一种商品的时间a与货架供应商品种类的乘积组成，式(21)表示货架到达之后才能开始拣货，式(22)表示货架到达拣货台的时间点要大于搬运该货架的agv上一任务的结束时间与两任务之间的走行时间之和，式(23)和式(24)表示先到达拣货台的货架任务先服务，式(25)保证了货架访问顺序的唯一性，式(26)表示拣货台不能同时处理多个货架任务且每个货架任务的处理是连续、不可中断的，并且先服务的货架任务先离开，式
[0058]
(27)表示当货架不访问拣货台时，此货架任务的到达、开始服务、结束时间均为0，式(28)表示每个agv回到车场的时间点大于该agv上一任务的结束时间与两任务之间的走行时间之和，式(29)表示系统完工时间大于任意一个agv回到车场的时间。
[0059]
优选地，所述订单分批算法的步骤如下：
[0060]
按订单关联度的大小，逐一处理订单对，如果订单对中的两个订单都还未被分配到批次，计算该订单对与各批次的关联度，将该订单对同时分配给关联度最大的批次；如果有一个订单已经分配到批次，并且批次还可以容纳新订单，将未分配的订单分配到该批次。批次的数量与拣货台数量相同。
[0061]
优选地，所述货架选择算法的步骤如下：
[0062]
首先计算货架满足度，找到满足度最大的一对货架和批次，将该货架和批次形成匹配关系，然后更新货架的库存，重新计算货架的满足度，重复上述操作，直至货架满足度最大的值为0，货架选择方案记录的是货架是否访问批次以及供应的商品种类数，货架满足方案记录的是货架供给哪个批次哪种货物的数量。优选地，所述订单批次指派算法的步骤如下：
[0063]
首先计算各批次到各拣货台的距离，找到距离最小的一对批次和拣货台，根据订单分批和货架选择的计算结果，将批次中的订单和对应的货架访问集合全部指派给该拣货台，重复上述操作，直至所有批次都匹配上拣货台，经过上述过程，订单分配给了拣货台，同
时确定了拣货台的货架访问方案。
[0064]
优选地，所述系统完工时间的计算过程如下：
[0065]
step1：初始化每个拣货台任务队列中上一任务离开时间为0，离开车场任务的e值为0，其余任务的e值为一个足够大的数g，删除没有货架任务的agv，更新每个agv的第一个任务为当前任务，并计算它们的g值；
[0066]
step2：比较每个agv当前任务的g值，找到g值最小的任务t(m,s)和对应的小车k，将任务t添加到拣货台s的访问队列中，更新任务t的开始拣选时间t和离开拣货台时间e；
[0067]
step3：判断小车k的下一任务是否是终点任务，若为否，则将小车k的下一任务更新为当前任务，并计算其g值，执行step2；若为是，则计算终点任务的g值，删除小车k，并判断是否所有任务都已完成，如果所有任务都已完成，执行step4，否则执行step2；
[0068]
step4：所有agv都已回到车场，终点任务的g值，即最后一个agv回到车场的时间，也是问题的系统完工时间。
[0069]
优选地，拣货台订单交换邻域算子的步骤如下：
[0070]
针对已有的订单分配方案，随机选择两个不属于同一拣货台的订单，交换这两个订单所属的拣货台，形成新的订单分配方案，接着重新计算这两个拣货台的商品需求，根据拣货台的商品需求的改变剔除多余的货架，判断现有的货架序列能不能满足需求，如果不能满足需求，加入新货架；如果能够满足商品需求，则不再加入新货架，将新的货架访问拣货台任务插入到现有的agv任务分配方案中，最终形成一个新的解。
[0071]
优选地，拣货台订单重新分配邻域算子的步骤如下：
[0072]
针对已有的订单分配方案，随机选择两个拣货台，将其中一个拣货台的任一订单从该拣货台中移除，再分配到另外一个拣货台，重新计算这两个拣货台的商品需求，对于订单数减少的拣货台，剔除多余的货架；对于有新增订单的拣货台，判断已有货架方案是否能满足拣货台需求，如果可以满足，则无需加入其它货架，如果不能满足，则需要选择合适的货架加入访问序列，再更新agv任务分配方案，形成一个新的解。
[0073]
优选地，货架供应商品种类减少邻域算子的步骤如下：
[0074]
基于当前的货架访问拣货台方案，随机选择n个货架任务形成任务集合，从任务集合中逐个取出货架任务，进行一次如下操作：删除任务中任意一种商品的供应量，分由其他访问相同拣货台的货架来供应，得到一个候选解，如果不能剔除任务中任何一种商品的供应量，则跳过该任务，最后将候选解与当前解比较，更新当前解。
[0075]
优选地，货架任务交换邻域算子的步骤如下：
[0076]
基于当前的agv任务分配方案，随机选择n个不重复的agv任务对构成集合，从集合中逐个取出任务对，进行一次如下操作：将两任务的位置交换一次，生成候选解，将多个候选解与当前解比较，更新当前解，将相同货架的任务打包后进行交换，一个货架的访问任务通过一个agv执行。
[0077]
优选地，货架任务重新分配邻域算子的步骤如下：
[0078]
基于当前的agv任务分配方案，随机选择n个agv任务构成集合，从集合中逐个取出任务，进行一次如下操作：将任务重新分配给另一个agv，生成候选解，最后将多个候选解与当前解比较，更新当前解，为满足相同货架任务需由一个agv连续执行的条件，重新分配的时候同样需要先找出相同货架序列。
[0079]
优选地，货架任务删除邻域算子的步骤如下：
[0080]
基于当前的货架访问拣货台方案，随机选择n个货架任务构成集合，从集合中逐个取出任务，进行一次如下操作：在不添加其它货架任务也能够满足拣货台的商品需求的前提下，删除该任务，更新agv执行方案，生成候选解，将多个候选解与当前解比较，更新当前解。
[0081]
优选地，货架替换邻域算子的步骤如下：
[0082]
对于已有货架访问拣货台方案，随机选择n个货架任务构成集合，从集合中逐个取出任务，进行一次如下操作：用一个货架替换该任务中的目标货架，形成新的货架访问拣货台方案，生成候选解，将多个候选解与当前解比较，更新当前解，货架换入时根据新的货架访问序列能否满足拣货台的商品需求，更新货架任务和agv任务分配方案。
[0083]
由上述本发明的实施例提供的技术方案可以看出，本发明实施例以订单、货架和agv为主要研究对象，以缩短拣选时间为目标，研究移动机器人履行系统中的订单拣选活动，为现实中配送中心制定订单拣选方案、agv调度计划提供参考，以到达降本增效的目的。
[0084]
本发明附加的方面和优点将在下面的描述中部分给出，这些将从下面的描述中变得明显，或通过本发明的实践了解到。
附图说明
[0085]
为了更清楚地说明本发明实施例的技术方案，下面将对实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
[0086]
图1为本发明实施例提供的一种订单分配和agv调度方案示意图；
[0087]
图2为本发明实施例提供的一种通过坐标系将仓库中的车场、货架与拣货台转换化坐标系中的点的示意图；
[0088]
图3为本发明实施例提供的一种agv执行任务网络示意图；
[0089]
图4为本发明实施例提供的一种拣货台任务访问队列示意图；
[0090]
图5为本发明实施例提供的一种订单交换示例示意图；
[0091]
图6为本发明实施例提供的一种订单重新分配示例图；
[0092]
图7为本发明实施例提供的一种货架供应商品种类减少示意图；
[0093]
图8为本发明实施例提供的一种货架任务交换示例示意图；
[0094]
图9为本发明实施例提供的一种货架任务重新分配示例示意图；
[0095]
图10为本发明实施例提供的一种货架任务删除示例示意图；
[0096]
图11为本发明实施例提供的一种货架替换示例示意图；
[0097]
图12为本发明实施例提供的一种邻域变换过程示意图；
[0098]
图13为本发明实施例提供的一种vnsii算法的流程图；
[0099]
图14为本发明实施例提供的一种小规模算例的仓库环境示意图；
[0100]
图15为本发明实施例提供的一种大规模算例的仓库环境示意图；
[0101]
图16为本发明实施例提供的一种vnsii算法求解li13算例的迭代、收敛过程示意图；
具体实施方式
[0102]
下面详细描述本发明的实施方式，所述实施方式的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施方式是示例性的，仅用于解释本发明，而不能解释为对本发明的限制。
[0103]
本技术领域技术人员可以理解，除非特意声明，这里使用的单数形式“一”、“一个”、“所述”和“该”也可包括复数形式。应该进一步理解的是，本发明的说明书中使用的措辞“包括”是指存在所述特征、整数、步骤、操作、元件和/或组件，但是并不排除存在或添加一个或多个其他特征、整数、步骤、操作、元件、组件和/或它们的组。应该理解，当我们称元件被“连接”或“耦接”到另一元件时，它可以直接连接或耦接到其他元件，或者也可以存在中间元件。此外，这里使用的“连接”或“耦接”可以包括无线连接或耦接。这里使用的措辞“和/或”包括一个或更多个相关联的列出项的任一单元和全部组合。
[0104]
本技术领域技术人员可以理解，除非另外定义，这里使用的所有术语(包括技术术语和科学术语)具有与本发明所属领域中的普通技术人员的一般理解相同的意义。还应该理解的是，诸如通用字典中定义的那些术语应该被理解为具有与现有技术的上下文中的意义一致的意义，并且除非像这里一样定义，不会用理想化或过于正式的含义来解释。
[0105]
为便于对本发明实施例的理解，下面将结合附图以几个具体实施例为例做进一步的解释说明，且各个实施例并不构成对本发明实施例的限定。
[0106]
本发明通过以下技术方案实现，对rmfs中订单分配和agv调度联合优化问题(integrated order allocation and robot scheduling problem，ioarsp)建立了该问题的混合整数规划模型，包括目标函数及相应的约束条件。设计了用于求解ioarsp问题的变邻域搜索算法vnsii(variable neighborhood search algorithm)，设计订单批次先匹配货架再分到拣货台的初始解生成算法，以及计算ioarsp问题系统完工时间计算的算法。然后结合问题的特点，设计了两种扰动邻域：拣货台订单交换和拣货台订单重新分配，以及设计了五种局部搜索邻域：货架任务交换、货架任务重新分配、货架任务删除、货架供应商品种类减少和货架替换，并且给出了邻域变换的规则和顺序。
[0107]
ioarsp问题可以描述为：在一个使用rmfs的物流仓库中，有一定数量的货架、拣货台和agv小车，以及一批待拣选的订单。已知订单的商品种类和数量以及货架上储存商品的种类和数量，将订单分配给拣货台，并且指派agv有序搬运能够满足订单需求的货架访问拣货台以进行拣选。订单不可拆分，一个货架可以连续访问多个拣货台。每个拣货台在调度期内能处理的订单数量有限。每个拣货台是一个单服务台排队系统，任意时刻只允许一个货架访问，并且服务不可中断。携带货架的agv按照先到先服务(fifo)的原则排队访问拣货台。所有agv均从车场出发，执行完所有任务后均回到车场。当所有的agv回到车场时，代表着这一批订单的拣选结束，以最后一个回到车场的agv的到达时间作为系统完工时间。ioarsp问题的优化目标是最小化系统完工时间。
[0108]
图1举例说明了订单分配方案和agv调度方案的生成：现有一批订单需要拣选，编号1～9，图1中给出了一种分配方案，即把订单1、5、6分给拣货台a，订单2、3、9分配给拣货台b，订单4、7、8分配给拣货台c。然后，将订单需求汇总，得到每个拣货台的商品拣选需求，在此基础上从货架群中选取货架访问拣货台。每个拣货台下方的方框内给出了一个满足其拣货需求的货架访问集合，即61、53、44号货架访问拣货台a，50、44号货架访问拣货台b，47、
50、55号货架访问拣货台c。最后，根据上述的货架访问拣货台方案，将搬运货架的任务指派给agv并确定执行顺序，形成agv任务序列。
[0109]
根据任务序列，agv有序执行货架任务，一个agv至多只能携带一个货架。
[0110]
拣货台任意时刻只允许一个货架访问，服务不可中断。货架访问拣货台的顺序取决于携带货架的agv到达拣货台的先后顺序，当agv携带货架到达拣货台时，如果拣货台处于空闲状态，货架直接访问拣货台开始服务；如果拣货台正在服务其它货架，agv按照fifo的原则排队依次访问。因此agv的工作时间除了行驶时间和服务时间外，还有等待时间。
[0111]
对于一个拣货台来说，满足其拣选需求的货架访问集合指的是，集合中所有货架储存的各商品数量之和能够满足拣货台的商品拣选需求。基本假设：
[0112]
(1)假设仓库采取分散储存策略，即同一个sku(stock keeping unit，最小存货单位)分散储存在多个货架上。这种策略增加了单个货架上的商品种类，可以满足更多样的需求，并且在多个拣货台对单个商品的需求同时发生时，可以通过指派多个储存了该商品的货架去访问拣货台，更迅速的完成拣选。
[0113]
(2)假设一批订单中所有商品的需求量小于仓库中商品的储存量，不考虑缺货的情况。需要明确的是，单个货架可能不能满足拣货台某种商品的需求，但至少会有一个可行的货架访问集合。
[0114]
(3)假设agv以恒定速度行驶，路网中每个通道均设置双向两车道。不考虑agv在仓库中移动时，在交叉口或拥堵路段的等待时间。在rmfs中，多agv小车在仓库中走行时会自动避让，产生等待时间。本发明的研究侧重于订单分配和调度，不考虑多agv的无碰撞路径规划。
[0115]
(4)一批订单的拣选持续时间一般都较短，而agv在充满电的情况下能连续运转数小时，因此不考虑agv的充电问题。未来将模型扩展到多批订单、动态拣选的情形下，则需要考虑agv的电量问题。
[0116]
(5)假设在一批订单的拣选过程种，一个货架只会被一个agv搬运一次，访问一个或多个拣货台。当有多个拣货台需要同一个货架访问时，采用一个agv搬运该货架连续访问多个拣货台，agv行驶距离更短，更符合仓库中的实际情况。
[0117]
(6)假设拣货员从货架上拣选商品所花费的时间由固定时间和可变时间组成，固定时间描述的是拣货员操作货架换入换出的时间，可变时间描述的是拣取n种商品的时间，由n乘以一个常数得到。
[0118]
路径网络构建与时间参数计算
[0119]
1：agv的行驶距离
[0120]
agv在仓库中的行驶分为两种情况，不携带货架的空载行驶和携带货架的载重行驶。当agv处于空载状态时，agv小车可以在通道内、货架下方行驶；当agv处于负载状态时，agv小车只能在通道内行驶。在本发明考虑的场景中，仓库内的通道都是双向两车道，图5为本发明实施例提供的一种通过坐标系将仓库中的车场、货架与拣货台转换化坐标系中的点的示意图，如图2所示，可建立坐标系将仓库中的车场、货架与拣货台转换化坐标系中的点。
[0121]
如果是空载行驶，agv从点(x1,y1)到点(x2,y2)之间的移动距离可通过计算曼哈顿距离的公式(1)得出：
[0122]
d＝|x
1-x2|+|y
1-y2|
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(1)
[0123]
如果是负载行驶，agv从点(x1,y1)到点(x2,y2)之间的移动距离不是简单的曼哈顿距离，agv从货架位置到通道以及从通道到货架位置都需要进行一小段位移，在此需要设置一个偏移点辅助计算行驶距离。例如图2中的1号货架左侧方块就为1号货架的偏移点。用货架位置对应的通道偏移点(x0,y0)代替货架位置(x1,y1)计算欧式距离，再加上横向的偏移量|x
1-x0|，即为两点之间的距离，计算公式为式(2)：
[0124]
d＝|x
0-x2|+|y
0-y2|+|x
1-x0|
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(2)
[0125]
通道偏移点可通过以下规则得到：当货架位置(x1,y1)的横坐标x1为奇数时，对应的通道偏移点为(x
1-1,y1)；当货架位置(x1,y1)的横坐标x1为偶数时，对应的通道偏移点为(x1+1,y1)。
[0126]
2：agv的走行时间
[0127]
agv在仓库中的走行时间需要考虑agv的行为。本发明假设agv的行驶速度、提升货架时间和放下货架时间是固定的，agv走行距离可以根据上一节所述方法得出。用距离除以速度得到移动时间，再加上agv执行特定动作需要花费的时间，就可以得到agv的走行时间。对于本发明描述的问题，根据走行路径起终点的不同，将agv走行情形分为三种：
[0128]
第一种情况是起点任务到货架任务。agv从车场出发，执行第一个货架任务，agv走到货架位置，提升货架，并搬运其访问拣货台，路线为：
[0129]
{车场——当前货架原位置——目标拣货台}
[0130]
第二种情况是货架任务到货架任务。agv携带货架访问完拣货台后，执行下一个货架任务。此时需要判断当前携带的货架，是否为下一个任务的目标货架，如果是的话，直接去往目标拣货台，路线为：
[0131]
{当前所在拣货台——目标拣货台}
[0132]
如果不是的话，则先将携带的货架回到原位置，放下货架，再去往下一任务的目标货架位置，提升货架，并搬运其访问拣货台，路线为：
[0133]
{当前所在拣货台——当前货架原位置——目标货架位置——目标拣货台}
[0134]
三种情况是货架任务到终点任务。agv执行最后一个货架任务，携带货架访问完拣货台后，将货架运回原位置并放下，后返回车场，路线为：
[0135]
{当前所在拣货台——当前货架原位置——车场}
[0136]
接下来，我们将用数学公式表示出这三种情形下的走行时间。首先对需要用到的参数进行说明，m表示货架，s表示拣货台，o和d表示车场，(m,s)、(m
′
,s
′
)表示货架任务，(o,o)表示离开车场的起点任务，(d,d)表示返回车场的终点任务，l
ij
表示从节点i到节点j的距离，v0表示agv空载行驶速度，v表示agv载重行驶速度，t
lp
表示agv提升货架所需时间，t
dp
表示agv放下货架所需时间。
[0137]
第一种情况，起点任务到货架任务，走行时间的计算见式(3)
[0138][0139]
第二种情况，货架任务到货架任务，走行时间的计算见式(4)
[0140]
[0141]
第三种情况，货架任务到终点任务，走行时间的计算见式(5)
[0142][0143]
下面建立以系统完工时间最小为目标的ioarsp问题的数学模型。
[0144]
集合、参数与决策变量模型的相关集合、参数和决策变量如表1，2和3所示。
[0145]
表1模型集合tab.1sets of model
[0146][0147]
表2模型参数tab.2parameters of model
[0148][0149]
表3模型决策变量tab.3decision variables of model
[0150][0151]
[0152]
其中，起点任务的到达时间g
oo
、开始时间t
oo
、结束时间e
oo
的值为常数0。q
mm
′s是一个分离变量，用于显式建模货架访问拣货台的冲突避免。
[0153]
目标函数与约束条件
[0154]
ioarsp问题的目标是最小化系统完工时间。目标函数见式(6)，其中u表示系统完工时间。
[0155]
minimizeu
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(6)
[0156]
模型包括四类约束条件：拣货台订单分配约束、货架与拣货台商品供需约束、agv执行货架任务约束以及时间约束。
[0157]
(1)拣货台订单分配约束
[0158]
订单需要分配到拣货台，按照订单商品需求进行拣选。
[0159][0160][0161]
式(7)表示每个订单都有且只被分配到一个拣货台，式(8)表示每个拣货台处理的订单数量有限制。
[0162]
(2)货架与拣货台商品供需约束
[0163]
货架访问拣货台进行拣选时，商品的供应与需求需要平衡。
[0164][0165][0166][0167]
式(9)表示货架访问拣货台就会供应商品，如果不供应商品，货架就不访问拣货台。式(10)表示任一货架供应所有拣货台的任一商品的数量不能超过其库存量。式(11)表示所有货架供应任一拣货台的任一商品的数量之和正好等于其需求量，其中表示分配到拣货台s的所有订单中商品i的需求量之和。
[0168]
(3)agv执行货架任务约束
[0169]
货架任务需要分配给agv，agv执行货架任务需要有顺序。
[0170][0171][0172][0173][0174][0175]
[0176][0177]
式(12)表示每一个货架访问拣货台的任务都需要一台agv完成，且仅能由一台agv完成。式(13)表示每一个agv执行的任务数量有限制。式(14)表示搬运同一货架的不同任务不能被分配给不同的agv，只能分配给同一台agv。式(15)和(16)表示分配到任务的agv都从车场出发去执行任务，执行完任务后都要回到车场，没有任务的agv则一直待在车场。式(17)和(18)表示分配到agv的每一个任务都有前序任务和后序任务，前序任务中包含离开车场任务，后序任务中包含回到车场任务。由于后面建立了时间约束，agv执行任务顺序中不会出现子回路，无需建立破除子回路的相关约束。
[0178]
(4)时间约束
[0179]
时间约束包括货架任务相关时间和agv返回车场时间的约束。
[0180][0181][0182][0183][0184][0185][0186][0187][0188][0189][0190][0191]
式(19)表示搬运同一货架的不同任务是连续的。式(20)表示货架任务在拣货台的拣货结束时间为拣货开始时间加上拣货时间，其中拣货时间由固定拣货时间b和固定拣取一种商品的时间a与货架供应商品种类的乘积组成。式(21)表示货架到达之后才能开始拣货。式(22)表示货架到达拣货台的时间点要大于搬运该货架的agv上一任务的结束时间与两任务之间的走行时间之和。式(23)和式(24)表示先到达拣货台的货架任务先服务。式(25)保证了货架访问顺序的唯一性。式(26)表示拣货台不能同时处理多个货架任务且每个货架任务的处理是连续、不可中断的，并且先服务的货架任务先离开。式
[0192]
(27)表示当货架不访问拣货台时，此货架任务的到达、开始服务、结束时间均为0。式(28)表示每个agv回到车场的时间点大于该agv上一任务的结束时间与两任务之间的走行时间之和。式(29)表示系统完工时间大于任意一个agv回到车场的时间。
[0193]
本发明实施例提供的vnsii算法的具体框架和步骤如下：
[0194]
初始方案生成算法
[0195]
初始化算法由四个部分组成，订单分批、货架选择、订单批次指派和agv任务分配。整体思路是先将相似度高的订单打包成批次，选取较少的货架满足批次，随后在考虑货架
到拣货台距离的基础上将批次分配到拣货台，最后随机将货架搬运任务分配给agv，得到初始解。
[0196]
(1)订单分批算法
[0197]
订单需要分配到拣货台，它的商品需求最终会汇总在拣货台的商品需求上，由多个货架共同满足这些需求。如果分配到拣货台的订单所包含的商品更多的出现在相同的货架上，那么就可以用数量更少的货架来访问拣货台。本发明将订单分配到拣货台的动作拆分为订单的分批和批次分配到拣货台两个动作，可以在子动作上设计更有针对性的算法，如考虑货架到拣货台的距离。下面阐述订单分批这个子动作的算法。
[0198]
订单关联度oa(o1,o2)，表示两个订单o1和o2的关联程度，商品关联度ia(i1,i2)，表示两个商品i1和i2是否存储在同一货架上。计算公式见式(30)。两个订单中所有商品对(来自不同订单)的关联度之和即为订单关联度。两个订单之间出现在同一货架上的商品对越多，它们之间的关联度越大。
[0199][0200]
在商品关联度和订单关联度的基础上，本发明定义了订单对与批次关联度oba((o1,o2),b)，计算公式见式(31)。订单对中的两个订单与批次包含的所有订单，两两组合的订单关联度之和即为订单对与批次关联度。
[0201][0202]
本发明设计的订单分批算法，按订单关联度的大小，逐一处理订单对。如果订单对中的两个订单都还未被分配到批次，计算该订单对与各批次的关联度，将它们同时分配给关联度最大的批次；如果有一个订单已经分配到批次，并且批次还可以容纳新订单，将未分配的订单分配到该批次。批次的数量与拣货台数量相同。
[0203]
(2)货架选择算法
[0204]
通过采用上文提到的订单分批算法将订单分配到批次以后，就可以汇总订单的商品需求，得到批次的商品需求。对于每一个批次，需要选择能够满足其商品需求的货架集合，同时还要考虑到一个货架可能会匹配多个批次，当货架供应一个批次后，货架库存已经减少了。
[0205]
在此，本发明定义了货架满足度rbs(r,b)，表示货架r能够供应批次b的商品数量，计算公式见式(32)。指定货架和批次，对于每一个商品i，取货架库存inv(r,i)和批次需求量dem(b,i)之间的较小值，然后对所有商品求和。
[0206][0207]
本发明设计的货架选择算法，首先计算货架满足度，找到满足度最大的一对货架和批次，形成匹配关系，然后更新货架的库存，重新计算货架的满足度。重复上述操作，直至货架满足度最大的值为0。
[0208]
(3)订单批次指派算法
[0209]
为使agv顶起货架行驶到拣货台的时间更短，拣货台的空闲时间更少，提高系统运行效率，本发明在考虑各订单批次的货架访问集合与各拣货台之间的距离的基础上，将各订单批次指派给各个拣货台。
[0210]
在此，本发明定义了批次到拣货台的距离bds(b,s)，计算公式见式(33)。对于选定的批次b和拣货台s，对该批次的货架访问集合r(b)中每一个货架到拣货台的距离d(r,s)进行求和，得到的结果即表示批次到拣货台的距离。
[0211][0212]
本发明设计的批次分到拣货台算法，首先计算各批次到各拣货台的距离，找到距离最小的一对批次和拣货台，根据订单分批和货架选择的计算结果，将批次中的订单和对应的货架访问集合全部指派给该拣货台，重复上述操作，直至所有批次都匹配上拣货台。经过上述过程，订单分配给了拣货台，同时确定了拣货台的货架访问方案。
[0213]
(4)任务分配算法
[0214]
当订单已经分到拣货台，访问拣货台的货架已经确定，剩下的就是将搬运货架访问拣货台的任务分配给agv，以及给出agv以何种顺序执行分配给它们的任务。由于任务分配对于目标值的影响有较强的不确定性，因此在这一阶段，本发明采用随机将任务分配给agv的方法来给出初始的任务分配方案。
[0215]
(5)初始化算法框架
[0216]
本发明先进行订单分批，再将货架与批次匹配上，然后一起打包分配给拣货台，最后将货架任务分配给agv。本发明实施例提供的一种初始化算法具体步骤如下：
[0217]
step1：订单分批算法。以拣货台数量为批次数量，将订单分批打包。
[0218]
step2：货架选择算法。为每一个批次确定需要哪些货架来访问。
[0219]
step3：批次分到拣货台算法。以货架到拣货台的距离为参考，将批次分给拣货台，一一对应。
[0220]
step4：任务分配算法。将货架访问拣货台的任务分配给agv。
[0221]
系统完工时间计算
[0222]
ioarsp问题的系统完工时间是agv完工时间，即最后一个agv回到车场的时间。agv在执行任务的过程中会遇到在拣货台排队等待访问的情况，等待时间受到访问相同拣货台的前序任务影响，同时任务到达拣货台的时间受到相同agv的前序任务的影响，因此agv的工作时间并不能通过简单的加和计算得出。
[0223]
agv执行任务的过程可以建立成有向网络，离开车场任务是有向网络的起点，回到车场任务是有向网络的终点，货架访问拣货台的任务是中间节点。在这个网络中的边表示两个任务由同一个agv执行，方向表示任务执行顺序，从任务分配方案里可以直接得到。每个节点都有一个权值，表示的是货架访问拣货台时的拣选时间；每条边也有一个权值，表示两个任务之间的走行时间。图3为本发明实施例提供的一种agv执行任务网络示意图，如图3所示，有三个agv搬运货架访问两个拣货台，l表示的是任务之间的走行时间，节点内的数字表示的分别是(货架，拣货台)和拣选所需时间t。
[0224]
此外，还需要建立队列记录货架到达拣货台的顺序，队列不能直接从agv任务分配方案中得到。假设拣货台任务访问队列如图4所示，拣货台1的队列表示货架11先到达拣货台1，货架15后到达拣货台1。结合图3与图4可知，货架任务(15，1)的开始服务时间既受到agv任务网络中前序任务(3，2)的限制，又受到拣货台任务访问队列前序任务(11，1)的限制。
[0225]
每一个货架访问拣货台任务都有三个需要计算的参数：货架到达拣货台时间g、开始拣选时间t和离开拣货台时间e。这三个参数的计算公式见式(34)、(35)和(36)。
[0226]
g＝agv执行任务网络中上一节点的离开时间e+l(34)
[0227]
t＝max{g,拣货台任务队列中上一任务的离开时间e}(35)
[0228]
e＝t+t(36)
[0229]
本发明设计了一种算法来确定agv访问拣货台的顺序和开始服务时间，并计算系统完工时间。整体思路是对每一个拣货台建立一个任务访问队列(如图4)，根据网络图中agv执行任务的到达时间(如图3)，添加最早到达的任务到访问队列中，然后在网络图中更新任务的开始时间、结束时间，如此循环，最终得出最后一个agv回到车场的时间。算法的具体步骤如下。
[0230]
step1：初始化每个拣货台任务队列中上一任务离开时间为0，离开车场任务的e值为0，其余任务的e值为一个足够大的数g。删除没有货架任务的agv，更新每个agv的第一个任务为当前任务，并计算它们的g值。
[0231]
step2：比较每个agv当前任务的g值，找到g值最小的任务t(m,s)和对应的小车k，将任务t添加到拣货台s的访问队列中，更新任务t的开始拣选时间t和离开拣货台时间e。
[0232]
step3：判断小车k的下一任务是否是终点任务，若为否，则将小车k的下一任务更新为当前任务，并计算其g值，执行step2；若为是，则计算终点任务的g值，删除小车k，并判断是否所有任务都已完成，如果所有任务都已完成，执行step4，否则执行step2。
[0233]
step4：所有agv都已回到车场，终点任务的g值，即最后一个agv回到车场的时间，也是问题的系统完工时间。
[0234]
邻域结构设计
[0235]
变邻域搜索算法中的邻域变换是为了扩大搜索空间，搜索更优的解。在扰动阶段和局部搜索阶段，都会用到邻域，这两个阶段的邻域可以是相同的，也可以是不同的。vnsii包含两个用于扰动的邻域和五个用于局部搜索的邻域。
[0236]
(1)扰动阶段邻域设计
[0237]
扰动阶段主要是调整订单分配到拣货台方案，更改订单所属的拣货台。为此，分别设计了订单交换和订单重新分配两个邻域。
[0238]
1)拣货台订单交换
[0239]
针对已有的订单分配方案，随机选择两个不属于同一拣货台的订单，交换它们所属的拣货台，形成新的订单分配方案。接着重新计算这两个拣货台的商品需求，因为拣货台的商品需求发生了改变，所以需要先剔除多余的货架，然后判断现有的货架序列能不能满足需求，如果不能满足需求，加入新货架；如果能够满足商品需求，则不再加入新货架。最后，将新的货架访问拣货台任务插入到现有的agv任务分配方案中，最终形成一个新的解。图5为本发明实施例提供的一种订单交换示例示意图，图5所示，左边表示一种订单分配到拣货台的方案，右边表示交换箭头所指的两个订单所属的拣货台后得到的订单分配方案。
[0240]
2)拣货台订单重新分配
[0241]
针对已有的订单分配方案，随机选择两个拣货台，将其中一个拣货台的任一订单从该拣货台中移除，再分配到另外一个拣货台。接着重新计算这两个拣货台的商品需求，对于订单数减少的拣货台，剔除多余的货架即可；对于有新增订单的拣货台，判断已有货架方
案是否能满足拣货台需求，如果可以满足，则无需加入其它货架，如果不能满足，则需要选择合适的货架加入访问序列。最后再更新agv任务分配方案，形成一个新的解。图6为本发明实施例提供的一种订单重新分配示例图，如图6所示，左边表示一种订单分配到拣货台的方案，右边是8号订单重新分配到其它拣货台后，得到的订单分配方案。
[0242]
(2)局部搜索阶段邻域设计
[0243]
局部搜索阶段主要是在固定的订单分配方案下，通过改变访问拣货台的货架、agv任务分配方案来找出该订单分配方案下的局部最优解。为此设计了以下五种邻域。
[0244]
1)货架供应商品种类减少
[0245]
基于当前的货架访问拣货台方案，随机选择n个货架任务形成任务集合，从集合中逐个取出货架任务，进行一次如下操作：删除任务中任意一种商品的供应量，分由其他访问相同拣货台的货架来供应，得到一个候选解。如果不能剔除任务中任何一种商品的供应量，则跳过该任务。最后将候选解与当前解比较，更新当前解。
[0246]
该邻域算子一般不改变货架任务，只改变货架供应商品种类数量，减少货架供应拣货台的商品种类数可以缩短任务服务时间，让后续的任务更早的开始。图7为本发明实施例提供的一种货架供应商品种类减少示意图，如图7所示，左边表示原方案中的货架商品储存情况(供应后)和供应方案，10号货架供应1号拣货台a商品的数量为4，可以由9号和21号货架替换10号货架满足1号拣货台a商品的需求，右边为替换后的货架商品储存情况和供应方案。
[0247]
2)货架任务交换
[0248]
基于当前的agv任务分配方案，随机选择n个不重复的agv任务对(两个任务可以是由同一个agv，也可以是由不同agv执行)构成集合，从集合中逐个取出任务对，进行一次如下操作：将两任务的位置交换一次，生成候选解。最后将多个候选解与当前解比较，更新当前解。选中的货架任务的目标货架可能不止访问一个拣货台，为了满足一个货架的访问任务只能由一个agv执行且连续的条件，需将相同货架的任务打包后进行交换。图8为本发明实施例提供的一种货架任务交换示例示意图，如图8所示，左边表示原有的agv任务分配方案，右边表示的是交换箭头所指的两个货架任务后的agv任务分配方案。
[0249]
本发明设计了一个用于寻找agv任务序列中相同货架任务及其起终位置的算法，在交换货架任务、插入货架任务时都会用到，伪代码如表11所示。
[0250]
表11相同货架的任务序列算法步骤tab.11procedure of tasks sequence for same rack algorithm
[0251][0252]
3)货架任务重新分配
[0253]
基于当前的agv任务分配方案，随机选择n个agv任务构成集合，从集合中逐个取出任务，进行一次如下操作：将任务重新分配给另一个agv，生成候选解。最后将多个候选解与当前解比较，更新当前解。为满足相同货架任务需由一个agv连续执行的条件，重新分配的时候同样需要先找出相同货架序列。图9为本发明实施例提供的一种货架任务重新分配示例示意图，如图9所示，左边表示原有的agv任务分配方案，右边表示的是交换53号的货架任务序列后的新agv任务分配方案。
[0254]
4)货架任务删除
[0255]
基于当前的货架访问拣货台方案，随机选择n个货架任务构成集合，从集合中逐个取出任务，进行一次如下操作：在不添加其它货架任务也能够满足拣货台的商品需求的前提下，删除该任务，更新agv执行方案，生成候选解。最后将多个候选解与当前解比较，更新当前解。图10为本发明实施例提供的一种货架任务删除示例示意图，如图10，左边是原始的货架访问、agv执行方案，右边是去掉10号货架任务后的货架访问、agv执行方案。
[0256]
5)货架替换
[0257]
对于已有货架访问拣货台方案，随机选择n个货架任务构成集合，从集合中逐个取出任务，进行一次如下操作：用一个货架替换该任务中的目标货架，形成新的货架访问拣货台方案，生成候选解。最后将多个候选解与当前解比较，更新当前解。货架换入时需要考虑这一新的货架访问序列能否满足拣货台的商品需求，进一步还要更新货架任务和agv任务分配方案。图11为本发明实施例提供的一种货架替换示例示意图，如图11所示，左边时原有的货架访问、agv执行方案，右边是用22号货架替换掉9号货架防访问2号拣货台后的货架访问、agv执行方案。
[0258]
邻域搜索策略
[0259]
本发明在扰动邻域内采用随机搜索策略，避免陷入局部最优，并采用执行同一个扰动邻域算子多次的方法以达到更好的扰动效果。对于ioarsp问题来说，每次调整解方案后都需要重新计算系统完工时间，计算系统完工时间的算法时间复杂度为o(n
×
m)(n为货架任务数量,m为agv数量)。同时每个局部搜索邻域的搜索空间也较大。如果采用全局搜索策略，求解时间过长。为了保证算法的效率，在局部搜索邻域内也采用随机搜索策略，但不
是随机一次，而是随机搜索多次得到多个候选解。
[0260]
邻域变换规则及顺序
[0261]
vnsii算法的邻域变换规则以vnd框架为基础，并增加了扰动阶段。邻域变换规则如下：按顺序在每个邻域里进行局部搜索，一旦找到更优的解，就返回第一个邻域继续搜索，否则跳转到下一个邻域搜索。如果在最后一个邻域里没有搜索到更优的解，并且没有到达终止条件，则记录下当前解，进入到扰动邻域扰动生成新解，然后回到第一个邻域继续搜索。
[0262]
在变换邻域搜索的过程中，搜索顺序靠前的邻域的搜索次数更多，先搜索空间较小的邻域有助于减少搜索时间。另外，应该将改进解可能性更大的邻域排在前面，可以避免不必要的搜索。对于本发明研究的问题，同一货架访问方案下有多种货架供应拣货台商品的方案，以及多种agv任务分配方案。先进行改变货架供应商品种类和agv任务分配的邻域搜索，有助于在该货架访问方案下充分搜索出更优的解。另一方面，货架供应商品种类减少邻域的搜索空间较小。综上，邻域访问顺序的设置是货架供应商品种类减少、货架任务删除、货架任务重新分配、货架任务交换和货架替换。最终，本发明实施例提供的一种邻域变换过程示意图如图12所示。
[0263]
求解方法步骤
[0264]
本发明设计的vnsii算法在基本变邻域搜索算法的基础上，结合ioarsp问题的特点，基于vnd框架对邻域变换规则进行了一定的改进，设计了五种局部优化邻域对当前解进行优化，同时设计了两种扰动邻域对当前解进行扰动。本发明实施例提供的一种vnsii算法的流程图如图13所示，其中n代次数，具体步骤如下：
[0265]
step1：初始化参数。
[0266]
输入订单数据d
pi
、货架库存数据c
mi
、货台订单处理上限e、agv任务数量上限l选时间计算参数、任务之间的走行时间t
msm
′s′
域算子输入常数、扰动次数k大迭代次数n
max
。
[0267]
step2：生成初始解，令迭代次数n＝0依次执行订单分批、选取货架访问批次、批次分到拣货台和给agv分配任务算法，得到订单分配方案、货架访问方案和agv任务分配方案。将初始解同时赋给当前最优解obj和局部最优解obj
max
。
[0268]
step3：变换邻域搜索局部最优解。
[0269]
以obj输入，依次在货架供应商品种类减少、货架任务删除、货架任务重新分配、货架任务交换和货架替换五个邻域中进行局部搜索，不断的改进当前最优解obj域变换规则。当在货架替换邻域搜索中找不到更优的解时，转入下一步。
[0270]
step4：判断obj优于obj
max
果是的话，令obj
max
＝obj入下一步；否则直接转入下一步。
[0271]
step5：判断是否迭代次数n n
max
果是的话，输出obj
max
法终止；否则令n＝n+1入下一步
[0272]
step6：在邻域内扰动生成新的解，以扩大搜索空间。
[0273]
首先在1～e随机生成一个整数赋给扰动次数k后随机选择一个扰动邻域，以obj
max
输入，执行邻域算子k生成新解并赋给obj入step3。
[0274]
实验设计
[0275]
为验证本发明所提出的vnsii算法的性能，根据某仓库rmfs系统的实际参数，结合
拣货台布局策略、拣货台数量、agv数量等多种因素构建了算例集。其中，小规模算例15个，大规模算例27个。本发明实施例提供的一种小规模算例的仓库环境如图14所示，本发明实施例提供的一种大规模算例的仓库环境如图15所示，均以车场为坐标原点建立直角坐标系。
[0276]
在大规模算例中，本发明考虑了三种拣货台布局方式，分别是i型布局、l型布局和u型，并结合不同的拣货台数量、agv数量形成了不同类型的算例。由于小规模算例拣货台数量较少，均设置为i型布局。所有算例的商品储存策略都是随机储存策略。每个货架上储存的商品种类数为1～5之间的随机数。每个订单包含的商品种类数为1或2，商品数量为1～3之间的随机数。算例参数说明见表15，算例编号和具体参数见表16。
[0277]
表15算例参数tab.15parameters of example
[0278][0279]
表16算例参数值设置tab.16parameter value settings for examples
[0280][0281]
本发明设计了3个实验。实验一用于验证vnsii算法的可行性、有效性和稳定性。实验二用于探究不同拣货台布局和不同拣货台数量、agv数量对订单拣选效率的影响，为配送中心的布局和设施布置提供决策依据。实验三用于探究订单分配对agv调度优化的影响，验证联合订单分配进行agv调度优化的必要性和优越性。
[0282]
实验参数设置
[0283]
本发明设计的实验相关实验参数如表17所示。此外在五个局部搜索邻域中的输入常数n都为10。
[0284]
表17实验参数tab.17parameters of experiment
[0285][0286]
实验配置与步骤
[0287]
本发明的实验环境为windows10操作系统的电脑，其中cpu为频率1.6ghz的i5-10210u，内存为16gb。变邻域搜索算法采用python语言编程实现，编程环境为pycharm。ioarsp混合整数规划模型采用cplex12.10进行求解。
[0288]
本发明实验所测试的算法有三种，分别是vnsi、vns-as和vnsii。vnsi中的局部搜索邻域只包含货架供应商品种类减少邻域(ls-i)、货架任务插入邻域(ls-iii)、货架任务交换邻域(ls-iv)和货架替换邻域(ls-v)，不包含货架任务删除邻域(ls-ii)。vns-as包含全部五种局部搜索邻域，但不进行扰动。vnsii包含全部五种局部搜索邻域和两种扰动邻域。
[0289]
具体实验步骤如下：
[0290]
step1：将算法相关实验参数写入代码，包括agv行驶速度、agv执行动作花费时间、最大迭代次数、拣选商品时间参数等。
[0291]
step2：读取算例中的数据，包括拣货台位置坐标、货架位置坐标和库存数据、订单需求数据、agv数量等。
[0292]
step3：运行程序并记录结果。对每个算例，分别运行vnsi、vnsii和vns-as各10次。记录订单分配、货架访问拣货台方案、agv任务分配方案、目标值、算法运行时间等信息。
[0293]
step4：根据记录的数据，经过整理后得到每种算法的目标函数平均值和平均运行时间。
[0294]
step5：计算解的改进率、不同算法目标值的平均相对误差。改进率的计算公式如式(37)所示：
[0295]
air＝(obj
init-obji)/obj
init
ꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(37)
[0296]
上式中，air表示目标函数值的平均改进率，obj
init
表示采用初始化算法得到的初始解的目标函数值，obji表示采用算法i求解得到的目标函数值。
[0297]
平均相对误差的计算公式如式(38)所示：
[0298]
arg＝(obj
i-objj)/objiꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀꢀ
(38)
[0299]
上式中，arg表示目标函数值的平均相对误差，obji、objj分别表示采用算法i，算法j求解得到的目标函数值。
[0300]
实验一
[0301]
设计小规模算例和大规模算例实验，验证vnsii算法的可行性和有效性，以及vnsii所包含的邻域的有效性。
[0302]
1)小规模算例实验结果及分析
[0303]
小规模算例实验对s03、s04、s05、s06和s07，5种类型共计15个算例进行测试。算例参数中货架数量为3～7，商品种类数量为5、7、8或9，订单数量为6、8或10，拣货台与agv数量为2或3。
[0304]
(2)7种局部搜索邻域的有效性分析
[0305]
将用于进行扰动的两个邻域拣货台订单交换和拣货台订单重新分配也加入到局部搜索的过程中，同时保持算法框架、参数不变进行实验，验证局部搜索邻域的有效性。算法运行10次，记录每次每个邻域优化当前解的次数，再取平均值得到平均优化次数，结果如表19所示，表中的ls-vi和ls-vii分别表示拣货台订单交换邻域和拣货台订单重新分配邻域。
[0306]
由表19可知，ls-i、ls-ii、ls-iii、ls-iv和ls-v均展现了不同程度的局部优化能力。其中ls-iv从当前解出发找到更优解的平均次数最多，因为相比其它邻域，它的搜索空间要更大，寻优的可能性更高。ls-i的平均优化次数也比较多，达到了26.6次，虽然它的搜索空间不大但它的搜索顺序是第一位，搜索次数最多。ls-vi和ls-vii均不能从当前解出发找到更优解，可能的原因是订单的拣选位置变动后需要对解进行多重调整，难以优于之前不同订单分配方案下经过局部优化的当前解，从另一个方面来说，将ls-vi和ls-vii放在扰动阶段有利于跳出局部最优。
[0307]
表19邻域算子平均优化次数
[0308]
tab.19 average number of optimizations of neighborhood operator
[0309][0310][0311]
为了更进一步说明邻域的有效性，将小规模算例按货架个数分为3类，分别是s-34、s-56以及s07，其中s-34由s03和s04类算例组成，s-56由s05和s06类算例组成，统计每一类算例中各邻域的平均优化次数，再取平均值，得到表20。
[0312]
表20不同算例类型中邻域算子平均优化次数
[0313]
tab.20average number of optimizations of neighborhood operator for different
[0314]
example types
[0315][0316]
由表20可知，随着算例规模的增大，邻域算子的平均优化次数呈现增加的趋势。相比s-34类算例，在s-56和s07类算例中ls-iv的平均优化次数明显上升，原因可能是随着货架任务的增多，货架任务的分配、排序规模呈指数型增长。在s-34类算例中优化次数较低的ls-iii和ls-v，在s07类算例中的平均优化次数明显增多了，虽然这两个邻域的搜索空间相对较小，但它们具备一定的寻优能力，同时较小的搜索空间意味着较短的搜索时间，并不会对算法运行时间产生太大的影响。
[0317]
2)大规模算例实验结果及分析
[0318]
大规模算例实验对li1、li2、li3、ll1、ll2、ll3、lr1、lr2和lr3，九种类型共计27个算例进行测试。算例参数中货架数量为180，商品种类数量为300，订单数量为100，拣货台数量为9、12、15，对应的agv数量为12、15、20。
[0319]
分别采用vnsi和vnsii运行大规模算例，vnsi的平均运行时间为239.6s，vnsii的平均运行时间为271.0s。运行结果如表22所示。
[0320]
表22大规模算例vnsi算法与vnsii算法对比
[0321]
tab.22comparisons between vnsi algorithm and vnsii algorithm for large
[0322]
examples
[0323]
[0324][0325]
由表22可知，相比初始解，vnsii和vnsi的平均改进率都达到了30％以上。不论拣货台布局、agv数量和拣货台数量如何，vnsii总比vnsi求得的解更好，两者的平均相对误差为2.1％，进一步验证了货架任务删除邻域的有效性。
[0326]
图16展示了vnsii算法求解li13算例的迭代、收敛过程。每次迭代结束时，得到局部优化值，并更新最优值，再进行扰动得到扰动值，然后进入下一次迭代。第一次迭代的扰动值是初始解的值。图中最优值多次下降，说明了扰动阶段可以跳出局部最优，以及局部优化是有效的。
[0327]
实验二
[0328]
探究不同拣货台布局和不同拣货台、agv数量对订单拣选效率的影响。拣货台布局分为i型，l型和u型，拣货台数量为9、12、15，对应的agv数量为12、15、20。
[0329]
(1)不同拣货台布局对拣选效率的影响
[0330]
根据大规模算例的运行结果，统计li、ll、lu三大类算例运行结果的平均值，得到表23。其中i型布局的拣选时间最短，l型布局下拣选时间增加了11.4％，u型布局下拣选时间增加了16.1％。原因可能是货架需要访问多个拣货台，而i型布局下拣货台与拣货台之间相距较近，所以拣选时间较短。
[0331]
表23不同拣货台布局对比tab.23compari sons of different picking station layouts
[0332][0333]
(2)不同拣货台、agv数量对拣选效率的影响
[0334]
根据大规模算例的运行结果，统计不同拣货台、agv数量的算例运行结果的平均值，得到表24。随着拣货台、agv数量的增加，拣选时间也更短。另外相比拣货台布局来说，拣选时间对拣货台、agv数量的变化更敏感。
[0335]
表24不同拣货台、agv数量对比tab.24comparisons of the number of different picking stations and agv
[0336][0337]
实验三
[0338]
为了探究订单分配对于agv调度的影响，本发明采用初始解生成得到的订单方案作为固定分配方案，在不进行扰动(不改变订单分配)的情况下进行局部搜索邻域变换、迭代寻优，与可调整订单分配下的agv调度优化结果进行比较，对应的算法分别是vns-as与vnsii。统计每类算例的运行结果取平均值，结果如表25所示，arg表示vns-as与vnsii求得解的平均相对误差。
[0339]
表25不同算例vns-as算法与vnsii算法对比
[0340]
tab.25comparisons between vns-as algorithm and vnsii algorithm for different
[0341]
examples
[0342][0343]
由表25可知，在所有算例中vnsii求得的解比vns-as求得的解更好，拣选时间平均缩短了20％。vns-as相较于初始解的平均改进率为16.9％，说明仅调整agv调度方案也可以
提高拣选效率，但在大规模算例中改进率明显低于平均值，同时与vnsii的结果相比也有了更加明显的差距。综上可以说明固定订单分配方案下进行agv调度优化的局限性，且订单处理量越大，同时考虑订单分配与agv调度的效果越好。
[0344]
本发明针对ioarsp问题设置了大规模算例27个，算例参数在不同维度上均有区别。以cplex求解器、vnsi算法、vns-as算法作为对照，进行了多组对比实验。
[0345]
综上所述，本发明实施例的方法具有如下的有益效果：
[0346]
1)本发明设计的vnsii算法，以及该算法包含的五种局部搜索邻域和扰动过程是有效、可行和稳定的。
[0347]
(2)货架任务减少邻域有助于提高解的质量。从侧面说明了减少货架任务数量，可以缩短拣选时间，提高拣选效率。
[0348]
(3)相比l型和u型布局，i型布局更适用于货架连续访问拣货台的场景。
[0349]
(4)随着拣货台数量、agv数量的增多，订单拣选时间缩短。相比拣货台布局，拣货台数量、agv数量对拣选效率的影响更显著。
[0350]
(5)单一的订单分配方案会限制agv调度的优化空间，将两者联合优化，效果更佳。订单分配和agv调度联合优化；
[0351]
(6)模型与算法能够得到最小化系统完工时间；邻域搜索算法vnsii包含七种分别用于扰动和局部搜索的邻域；结合仓储布局制作算例，通过实验验证了vnsii算法的有效性、稳定性和可行性。
[0352]
本领域普通技术人员可以理解：附图只是一个实施例的示意图，附图中的模块或流程并不一定是实施本发明所必须的。
[0353]
通过以上的实施方式的描述可知，本领域的技术人员可以清楚地了解到本发明可借助软件加必需的通用硬件平台的方式来实现。基于这样的理解，本发明的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在存储介质中，如rom/ram、磁碟、光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本发明各个实施例或者实施例的某些部分所述的方法。
[0354]
本说明书中的各个实施例均采用递进的方式描述，各个实施例之间相同相似的部分互相参见即可，每个实施例重点说明的都是与其他实施例的不同之处。尤其，对于装置或系统实施例而言，由于其基本相似于方法实施例，所以描述得比较简单，相关之处参见方法实施例的部分说明即可。以上所描述的装置及系统实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本实施例方案的目的。本领域普通技术人员在不付出创造性劳动的情况下，即可以理解并实施。
[0355]
以上所述，仅为本发明较佳的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求的保护范围为准。

技术特征：
1.一种移动机器人履行系统中订单分配和agv调度联合优化方法，其特征在于，包括：step1：初始化参数，输入订单数据d
pi
、货架库存数据c
mi
、货台订单处理上限e、agv任务数量上限l、时间计算参数、任务之间的走行时间t
msm
′
s
′
、域算子输入常数、扰动次数k和迭代次数上限n
max
；step2：生成初始解，令迭代次数n＝0，依次执行订单分批算法、货架选择算法、订单批次指派算法和给移动机器人agv分配任务算法得到订单分配方案、货架访问方案和agv任务分配方案的初始解，将所述初始解同时赋给当前最优解obj和局部最优解obj
max
；step3：变换邻域搜索局部最优解，以obj为输入，依次在货架供应商品种类减少、货架任务删除、货架任务重新分配、货架任务交换和货架替换五个邻域中进行局部搜索，不断的改进当前最优解obj域变换规则，当在货架替换邻域搜索中找不到更优的解时，转入step4；step4：判断obj是否优于obj
max
，如果是，令obj
max
＝obj，转入step5；否则，直接转入step5；step5：判断迭代次数n是否大于或者等于n
max
，如果是，输出obj
max
，算法终止；否则令n＝n+1，转入step6；step6：在邻域内扰动生成新的解，以扩大搜索空间；在1～e随机生成一个整数，将整数赋给扰动次数k后随机选择一个扰动邻域，以obj
max
输入，执行邻域算子k生成新解并赋给obj，转入step3。2.根据权利要求1所述的方法，其特征在于，所述方法相关集合、参数和决策变量如表1，2和3所示：表1模型集合表2模型参数
表3模型决策变量其中，起点任务的到达时间g
oo
、开始时间t
oo
、结束时间e
oo
的值为常数0，q
mm
′
s
是一个分离变量，用于显式建模货架访问拣货台的冲突避免；目标函数与约束条件ioarsp问题的目标是最小化系统完工时间，目标函数见式(6)，其中u表示系统完工时间；minimizeu(6)模型包括四类约束条件：拣货台订单分配约束、货架与拣货台商品供需约束、agv执行货架任务约束以及时间约束；(1)拣货台订单分配约束订单需要分配到拣货台，按照订单商品需求进行拣选；按照订单商品需求进行拣选；式(7)表示每个订单都有且只被分配到一个拣货台，式(8)表示每个拣货台处理的订单数量有限制；(2)货架与拣货台商品供需约束货架访问拣货台进行拣选时，商品的供应与需求需要平衡；商品的供应与需求需要平衡；商品的供应与需求需要平衡；式(9)表示货架访问拣货台就会供应商品，如果不供应商品，货架就不访问拣货台，式(10)表示任一货架供应所有拣货台的任一商品的数量不能超过其库存量，式(11)表示所有
货架供应任一拣货台的任一商品的数量之和正好等于其需求量，其中表示分配到拣货台s的所有订单中商品i的需求量之和；(3)agv执行货架任务约束货架任务需要分配给agv，agv执行货架任务需要有顺序；agv执行货架任务需要有顺序；agv执行货架任务需要有顺序；agv执行货架任务需要有顺序；agv执行货架任务需要有顺序；agv执行货架任务需要有顺序；agv执行货架任务需要有顺序；式(12)表示每一个货架访问拣货台的任务都需要一台agv完成，且仅能由一台agv完成，式(13)表示每一个agv执行的任务数量有限制，式(14)表示搬运同一货架的不同任务不能被分配给不同的agv，只能分配给同一台agv，式(15)和(16)表示分配到任务的agv都从车场出发去执行任务，执行完任务后都要回到车场，没有任务的agv则一直待在车场，式(17)和(18)表示分配到agv的每一个任务都有前序任务和后序任务，前序任务中包含离开车场任务，后序任务中包含回到车场任务；(4)时间约束时间约束包括货架任务相关时间和agv返回车场时间的约束；时间约束包括货架任务相关时间和agv返回车场时间的约束；时间约束包括货架任务相关时间和agv返回车场时间的约束；时间约束包括货架任务相关时间和agv返回车场时间的约束；时间约束包括货架任务相关时间和agv返回车场时间的约束；时间约束包括货架任务相关时间和agv返回车场时间的约束；时间约束包括货架任务相关时间和agv返回车场时间的约束；时间约束包括货架任务相关时间和agv返回车场时间的约束；时间约束包括货架任务相关时间和agv返回车场时间的约束；时间约束包括货架任务相关时间和agv返回车场时间的约束；时间约束包括货架任务相关时间和agv返回车场时间的约束；
式(19)表示搬运同一货架的不同任务是连续的，式(20)表示货架任务在拣货台的拣货结束时间为拣货开始时间加上拣货时间，其中拣货时间由固定拣货时间b和固定拣取一种商品的时间a与货架供应商品种类的乘积组成，式(21)表示货架到达之后才能开始拣货，式(22)表示货架到达拣货台的时间点要大于搬运该货架的agv上一任务的结束时间与两任务之间的走行时间之和，式(23)和式(24)表示先到达拣货台的货架任务先服务，式(25)保证了货架访问顺序的唯一性，式(26)表示拣货台不能同时处理多个货架任务且每个货架任务的处理是连续、不可中断的，并且先服务的货架任务先离开，式(27)表示当货架不访问拣货台时，此货架任务的到达、开始服务、结束时间均为0，式(28)表示每个agv回到车场的时间点大于该agv上一任务的结束时间与两任务之间的走行时间之和，式(29)表示系统完工时间大于任意一个agv回到车场的时间。3.根据权利要求1或者2所述的方法，其特征在于，所述货架选择算法的步骤如下：首先计算货架满足度，找到满足度最大的一对货架和批次，将该货架和批次形成匹配关系，然后更新货架的库存，重新计算货架的满足度，重复上述操作，直至货架满足度最大的值为0，货架选择方案记录的是货架是否访问批次以及供应的商品种类数，货架满足方案记录的是货架供给哪个批次哪种货物的数量。4.根据权利要求1所述的方法，其特征在于，所述订单批次指派算法的步骤如下：首先计算各批次到各拣货台的距离，找到距离最小的一对批次和拣货台，根据订单分批和货架选择的计算结果，将批次中的订单和对应的货架访问集合全部指派给该拣货台，重复上述操作，直至所有批次都匹配上拣货台，经过上述过程，订单分配给了拣货台，同时确定了拣货台的货架访问方案。5.根据权利要求1或者2所述的方法，其特征在于，所述系统完工时间的计算过程如下：step1：初始化每个拣货台任务队列中上一任务离开时间为0，离开车场任务的e值为0，其余任务的e值为一个足够大的数g，删除没有货架任务的agv，更新每个agv的第一个任务为当前任务，并计算它们的g值；step2：比较每个agv当前任务的g值，找到g值最小的任务t(m,s)和对应的小车k，将任务t添加到拣货台s的访问队列中，更新任务t的开始拣选时间t和离开拣货台时间e；step3：判断小车k的下一任务是否是终点任务，若为否，则将小车k的下一任务更新为当前任务，并计算其g值，执行step2；若为是，则计算终点任务的g值，删除小车k，并判断是否所有任务都已完成，如果所有任务都已完成，执行step4，否则执行step2；step4：所有agv都已回到车场，终点任务的g值，即最后一个agv回到车场的时间，也是问题的系统完工时间。6.根据权利要求1或者2所述的方法，其特征在于，拣货台订单重新分配邻域算子的步骤如下：针对已有的订单分配方案，随机选择两个拣货台，将其中一个拣货台的任一订单从该拣货台中移除，再分配到另外一个拣货台，重新计算这两个拣货台的商品需求，对于订单数减少的拣货台，剔除多余的货架；对于有新增订单的拣货台，判断已有货架方案是否能满足拣货台需求，如果可以满足，则无需加入其它货架，如果不能满足，则需要选择合适的货架加入访问序列，再更新agv任务分配方案，形成一个新的解。7.根据权利要求1或者2所述的方法，其特征在于，货架供应商品种类减少邻域算子的
步骤如下：基于当前的货架访问拣货台方案，随机选择n个货架任务形成任务集合，从任务集合中逐个取出货架任务，进行一次如下操作：删除任务中任意一种商品的供应量，分由其他访问相同拣货台的货架来供应，得到一个候选解，如果不能剔除任务中任何一种商品的供应量，则跳过该任务，最后将候选解与当前解比较，更新当前解。8.根据权利要求1或者2所述的方法，其特征在于，货架任务交换邻域算子的步骤如下：基于当前的agv任务分配方案，随机选择n个不重复的agv任务对构成集合，从集合中逐个取出任务对，进行一次如下操作：将两任务的位置交换一次，生成候选解，将多个候选解与当前解比较，更新当前解，将相同货架的任务打包后进行交换，一个货架的访问任务通过一个agv执行。9.根据权利要求1或者2所述的方法，其特征在于，货架任务删除邻域算子的步骤如下：基于当前的货架访问拣货台方案，随机选择n个货架任务构成集合，从集合中逐个取出任务，进行一次如下操作：在不添加其它货架任务也能够满足拣货台的商品需求的前提下，删除该任务，更新agv执行方案，生成候选解将多个候选解与当前解比较，更新当前解。10.根据权利要求1或者2所述的方法，其特征在于，货架替换邻域算子的步骤如下：对于已有货架访问拣货台方案，随机选择n个货架任务构成集合，从集合中逐个取出任务，进行一次如下操作：用一个货架替换该任务中的目标货架，形成新的货架访问拣货台方案，生成候选解，将多个候选解与当前解比较，更新当前解，货架换入时根据新的货架访问序列能否满足拣货台的商品需求，更新货架任务和agv任务分配方案。

技术总结
本发明提供了一种移动机器人履行系统中订单分配和AGV调度联合优化方法。本发明对RMFS中订单分配和AGV调度联合优化问题建立包括目标函数和约束条件的数学模型，设计变邻域搜索算法求解IOARSP问题。初始解生成算法包括订单分批、货架选择、订单批次指派和AGV任务分配四个部分，并设计计算IOARSP问题系统完工时间的算法。设计了两个扰动邻域：拣货台订单交换和拣货台订单重新分配；五个局部搜索邻域：货架任务交换、货架任务重新分配、货架任务删除、货架供应商品种类减少和货架替换，给出邻域变换的规则和顺序。本发明研究移动机器人履行系统中的订单拣选活动，为现实中配送中心制定订单拣选方案、AGV调度计划提供参考，以到达降本增效的目的。降本增效的目的。降本增效的目的。


技术研发人员：刘志硕
受保护的技术使用者：北京交通大学
技术研发日：2023.03.30
技术公布日：2023/8/5