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

Operations Research and Fuzziology 运筹与模糊学运筹与模糊学,2024,14(1),1106-1119 Published Online February 2024 in Hans.https:/www.hanspub.org/journal/orf https:/doi.org/10.12677/orf.2024.141102 文章引用文章引用:顾洋洋,袁柳洋.“货到人”拣选系统的两阶段随机规划模型J.运筹与模糊学,2024,14(1):1106-1119.DOI:10.12677/orf.2024.141102 “货到人”拣选系统的两阶段随机规划模型“货到人”拣选系统的两阶段随机规划模型 顾洋洋顾洋洋1，袁柳洋，袁柳洋1,2 1武汉科技大学理学院，湖北 武汉 2武汉科技大学冶金工业过程系统科学湖北省重点实验室，湖北 武汉 收稿日期：2024年1月1日；录用日期：2024年1月19日；发布日期：2024年2月29日 摘摘 要要 在“货到人”智能仓储拣选体系中，机器人的合理调度和任务分配影响着系统的效率与成本。为此本文在“货到人”智能仓储拣选体系中，机器人的合理调度和任务分配影响着系统的效率与成本。为此本文同时考虑“货到人”拣选系统中的机器人调度和任务分配，建立了机器人空闲时间不确定的两阶段随机同时考虑“货到人”拣选系统中的机器人调度和任务分配，建立了机器人空闲时间不确定的两阶段随机规划模型。第一阶段，对于给定的机器人数量，作出是否调度机器人的上层策略，使得机器人完成所有规划模型。第一阶段，对于给定的机器人数量，作出是否调度机器人的上层策略，使得机器人完成所有任务耗费的总期望成本最小；第二阶段，对于某个场景，作出如何合理地进行任务分配的下层策略，使任务耗费的总期望成本最小；第二阶段，对于某个场景，作出如何合理地进行任务分配的下层策略，使得机器人完成所有任务的空闲时间成本最小。然后利用遗传算法对此模型进行求解，并通过实例仿真验得机器人完成所有任务的空闲时间成本最小。然后利用遗传算法对此模型进行求解，并通过实例仿真验证了模型的可行性。证了模型的可行性。关键词关键词 “货到人”拣选系统，机器人调度“货到人”拣选系统，机器人调度，两阶段随机规划，遗传算法，两阶段随机规划，遗传算法 A Two-Stage Stochastic Programming Model for the“Goods to People”Picking System Yangyang Gu1,Liuyang Yuan1,2 1College of Science,Wuhan University of Science and Technology,Wuhan Hubei 2Hubei Key Laboratory of Metallurgical Industry Process System Science,Wuhan University of Science and Technology,Wuhan Hubei Received:Jan.1st,2024;accepted:Jan.19th,2024;published:Feb.29th,2024 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 con-siders both robot scheduling and task assignment in the“goods to people”picking system,and es-顾洋洋，袁柳洋 DOI:10.12677/orf.2024.141102 1107 运筹与模糊学 tablishes 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.Keywords“Goods to People”Picking System,Robot Scheduling,Two-Stage Stochastic Programming,Genetic Algorithm Copyright 2024 by author(s)and Hans Publishers Inc.This work is licensed under the Creative Commons Attribution International License(CC BY 4.0).http:/creativecommons.org/licenses/by/4.0/1.引言引言 随着互联网经济的发展，全球经济逐渐向数字经济转型，其中最具有代表性的一种表现就是电子商务的崛起。电子商务的繁荣发展促进了快递物流行业的兴起。如何提高物流体系的效率是电子商务企业现在最为关注的问题。在整个物流体系中，智能仓储系统是影响其效率的极为重要的一个部分1。美国亚马逊成功研发和应用 Kiva 机器人系统使整个仓储系统的存拣货效率有了大大的提高，它改变了传统的“人到货”拣选模式，提出一种新型的“货到人”拣选模式2。这种拣选模式中的任务分配是指机器人将系统接收到的每批订单的每个任务分别分配给系统中不同的搬运机器人，由机器人把订单包含的货物所在的货架搬运到拣选员工所在的拣选台的位置以供员工拣选。近几年，已有很多学者对“货到人”拣选系统中的机器人任务分配问题进行了研究。比如袁瑞萍等3以机器人完成所有任务的最短时间为任务目标，分别建立了机器人在同步和异步拣选模式下的任务调度模型，并采用改进的协同进化遗传算法进行求解，得出多个拣选平台同步拣选效果较好。石媛媛等4建立任务均衡分配以及路程代价最优双重目标模型，结合提出的一种平衡拍卖启发式算法，解决了智能仓储机器人的任务分配问题。Nielsen 等5研究了单个机器人的调度模型，并对其配送能力进行了约束，采用基于遗传算法的启发式算法求解机器人的配送任务数。谢永盛等6以机器人到任务位置路径最短为目标建立模型，利用改进的布谷鸟搜索算法，通过实例仿真，有效解决了机器人的任务分配以及路径规划。秦新立等7对机器人的电量、数目和任务载荷进行约束，以机器人的性能指标最优为任务目标，将多机器人的任务分配问题看作多旅行商问题，通过改进的蚁群算法很好的解决了多机器人的任务分配问题。王振庭等8以机器人执行任务时的转向次数、路程代价、最大任务等待时间为优化目标，采用遗传算法对机器人的任务进行分配，Q-learning 算法对机器人分配到的任务进行具体路径规划。在“货到人”拣选系统中，如何调度机器人也至关重要，已有学者对机器人的调度问题进行了研究。例如 Milica 等9构建了多目标机器人规划模型，提出了一种基于单移动机器人的多目标灰狼优化器方法，利用改进的遗传算法，解决了机器人的调度问题。Jia Ma 等10建立了最小化机器人执行任务总时间和最大化单个机器人执行任务时间的多目标规划模型，提出一种新的基于 Parcto 的 MOEA，在机器人的调度问题上取得了较好的结果。李腾等11考虑了机器人在完成任务的过程中行走距离的不确定性，建立鲁棒双层规划模型，通过遗传算法，解决了机器人的调度和任务分配问题。Open AccessOpen Access顾洋洋，袁柳洋 DOI:10.12677/orf.2024.141102 1108 运筹与模糊学 综上所述，现有文献绝大多数以时间或运行成本为优化目标，没有考虑机器人的空闲成本，并且都假设机器人在行走过程中是畅通的，但在实际情况中，机器人在行走过程中有可能发生堵塞和排队，这样会造成机器人运行时间的不确定性。因此本文同时考虑“货到人”拣选系统中的机器人调度及任务分配问题，建立了机器人空闲时间不确定的两阶段随机规划模型。第一阶段，对于给定的机器人数量，作出是否调度机器人的上层策略，使得机器人完成所有任务耗费的总期望成本最小；第二阶段，对于某个场景，作出如何合理地进行任务分配的下层策略，使得机器人完成所有任务的空闲时间成本最小。然后利用遗传算法对此模型进行求解，并通过实例仿真验证了模型的可行性。2.两阶段随机规划模型两阶段随机规划模型 2.1.问题描述问题描述“货到人”拣选系统仓库的平面布局通常用二维平面栅格化地图表示12，如图 1 所示，主要由货架、拣选台、机器人停车区组成。Figure 1.“Goods to people”picking system warehouse plan 图图 1.“货到人”拣选系统仓库平面图 机器人在接收到系统下发的任务分配信息时，先从初始位置移动到其被分配的第一个任务所对应的货架位置，然后将该货架搬运至拣选台前，等待工作人员在货架上挑选货物并打包，再将工作人员拣选完毕的货架搬运回货架原来的位置，并在该货架前等待下一个任务分配，以此循环，直到完成机器人被顾洋洋，袁柳洋 DOI:10.12677/orf.2024.141102 1109 运筹与模糊学 分配的所有任务。如果机器人在搬运货架的路途中发生堵塞，机器人可以选择等待或者改变路径。图 2为一个机器人完成任务的流程图。Figure 2.Flow chart of robot completing task 图图 2.机器人完成任务流程图 为了建立一个合理的模型，本文提出以下假设：1)在初始时刻，仓库中的所有机器人都处于闲置状态。2)所有机器人在运行过程中的电力始终充足。3)所有机器人都从相同的初始位置开始。4)仓库内所有货物均不短缺。5)机器人将货架移回原位后，在货架位置等待下一个任务的分配。6)不考虑机器人的固定购买成本。2.2.模型建立模型建立 符号含义如表 1 所示。顾洋洋，袁柳洋 DOI:10.12677/orf.2024.141102 1110 运筹与模糊学 Table 1.Symbol meaning table 表表 1.符号含义表 符号 定义 n 机器人的总数量 m 任务的总数量(),AiAixy 机器人iR的位置坐标(),BjBjxy 任务jZ的位置坐标(),QQxy 拣选台Q的位置坐标 AiBjd 机器人iR从初始位置到任务jZ行走的距离 BjQd 机器人iR从任务jZ到拣选台Q行走的距离 QBjd 机器人iR从拣选台Q到任务jZ行走的距离 rC 机器人行走单位距离所花费的成本 fC 单位时间每台机器人的空闲成本 C n个机器人完成m个任务花费的总成本 12,V V 机器人搬运货架时的速度和机器人空载时的速度 ijD 机器人iR完成任务jZ的行走总距离 iD 机器人iR完成所有任务的行走距离 (机器人调度)决策变量iY表示是否调度机器人iR来完成任务，则 1,0,iiRY=调度机器人否则(1)(任务分配)决策变量ijX表示机器人iR是否完成任务jZ，则 1,0,ijijRZX=机器人 完成任务否则(2)()ijkT为第k种场景下机器人iR完成任务jZ所花费的时间，121,2,kk=。记()ijkT为机器人iR完成任务jZ额外的时间增加值。假设机器人完成任务时行走距离不变，路径状况分为两种情况：第一种情况道路畅通无阻，即机器人在完成任务过程中不发生堵塞或排队，没有产生额外的时间损耗，即()10ijT=，那么机器人完成任务的时间是：()112BjQQBjAiBjijijdddTXVV+=+(3)第二种情况道路发生拥堵，即机器人在完成任务过程中发生堵塞或者在拣选台等候等情况，因本文假设发生这些情况时机器人不改变路径，而是在原地等待，直到可以通过，此时就会产生一个时间的增加值，即()20ijT，那么机器人完成任务的时间是：顾洋洋，袁柳洋 DOI:10.12677/orf.2024.141102 1111 运筹与模糊学 ()()2212BjQQBjAiBjijijijdddTTXVV+=+(4)()kT为第k种场景下所有机器人完成任务的总时间，也就是每一个订单批次中执行任务时间最长的机器人的执行时间，则 ()()1,2,.,1maxmkijkinjTT=(5)两阶段随机规划问题是随机规划问题的一个分支，是特殊的期望值模型13。本文考虑了机器人调度与机器人任务分配问题，建立了基于机器人空闲时间不确定的两阶段随机规划模型。第一阶段，从全局层面决定机器人是否被调度，对于给定的机器人数量，作出是否调度机器人的上层策略，使得机器人完成所有任务耗费的总期望成本最小。第一阶段模型：min C(6)()()()111,nnriifiiinriifiiC Y DECYC Y DECY=+=+.st 1niiYn=(7)0,1,1,2,iYin=(8)AiBjAiBjAiBjdxxyy=+(9)BjQQBjBjQBjQddxxyy=+(10)ijAiBjBjQQBjDddd=+(11)1miijijDDY=(12)其中目标函数将所有机器人完成任务所花费的总成本分为两个部分，1nriiiC YD=为机器人的行走成本。本文道路情况只考虑两种场景：堵塞和畅通，所以随机变量是离散的，只包含两个值，且分布律是已知的，()12,kPP P=，每种情况对应的时间值也是确定的，所以空闲时间的成本值可以用空闲时间成本的期望值来表达，即可以用()1,nfiiECY=来表达。堵塞情况下时间的增加值假设服从均值为，方差为的正态分布，且每个机器人完成任务的时间是相互独立的。式(7)表示调度机器人的数量不能超过系统中机器人的配置数量。第二阶段，从局部层面决定任务如何合理地分配给机器人，对于某个场景，作出如何合理地进行任务分配的下层策略，使得机器人完成所有任务的空闲时间成本最小。min(),fikCY(13)()()()()()()11,2,.,111maxmfikfikijkjmmfijkijkinjjCY TC Y TTCTT=+=顾洋洋，袁柳洋 DOI:10.12677/orf.2024.141102 1112 运筹与模糊学 .st 11,1,2,nijiXjm=(14)110,1,2,mijijXYin=(15)1,0,1,2,;1,2,ijXin jm=(16)121,2,kk=(17)其中，目标函数将机器人的空闲时间分为两个部分，()()1ikY T为没有被调度的机器人的等待时间，()()()1mikijkjY TT=为机器人在完成任务过程中由于堵塞排队所造成的空闲时间。式(14)表示一个任务只由一个机器人来完成。式(15)表示被调度的机器人至少需要完成一个任务。3.遗传算法遗传算法 为了消除时间不确定性对求解造成的困难，可将问题转化为常规的规划问题进行求解14，先将第一阶段期望值的表达形式具体化，再在约束的条件下，寻找解集，使目标函数达到最优。本文中时间的不确定性是由于道路情况的不确定性造成的，道路情况分为堵塞和畅通两种场景，根据两种场景发生的概率，写出期望总成本的表达式。即：min C(18)()()()()11121,2,.,111,maxnnriifiiinriiimmfkijkijkinkjjC Y DECYC Y DC PTT=+=+遗传算法是一种模拟生物自然选择和遗传进化过程的优化算法，它在初始种群中根据适应度函数选择最优个体，通过染色体的交叉变异按照优胜劣汰的原则更新种群，最终得到适应度值最高的染色体15。遗传算法适合用于求解组合优化问题16 17，机器人的调度与任务分配问题其实是一种组合优化问题，也就是 NP-hard 问题，因此本文选择与传统的遗传算法相结合，使用循环机器人个数的方式求解，先给定一个初始的机器人数量，再运用遗传算法。求解流程图如图 3 所示。具体步骤如下：步骤一：初始化种群参数。染色体的编码方式采用实数编码，如图 4 所示，实数编码可以明显观察到机器人与其完成的任务之间的对应关系。步骤二：计算适应度值。给定一个初始的机器人数量，运用遗传算法对模型进行求解，把期望总成本的倒数作为适应度函数，即：()()()()21,2,.,11111maxmaxnmmriifkijkijkinikjjf xC YDC PTT=+(19)步骤三：选择。将染色体按照适应度值的大小排序，适应度值越大，期望总成本就越小。用精英保留策略筛选适应度值较高的染色体作为父代染色体。步骤四：交叉和变异。按照交叉概率变异概率对选择个体进行变异，随机生成一个父代染色体的变异位置，变异时只将该位置的基因变异成所调度的其他机器人的编号。顾洋洋，袁柳洋 DOI:10.12677/orf.2024.141102 1113 运筹与模糊学 Figure 3.Flow chart of genetic algorithm 图图 3.遗传算法流程图 Figure 4.Chromosome coding example 图图 4.染色体编码示例 步骤五：输出机器人任务分配结果。设定种群最大迭代次数，当达到最大迭代次数时，停止计算，记录当前调度机器人数量下的历史最小期望总成本值以及任务分配结果。步骤六：循环。将调度机器人的数量加 1，再做一次遗传算法，直到调度机器人的数量等于系统中机器人的配置数量，停止循环，比较调度不同机器人数量的最小期望总成本，输出期望总成本最小的机器人调度数量以及任务分配结果。顾洋洋，袁柳洋 DOI:10.12677/orf.2024.141102 1114 运筹与模糊学 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.任务坐标 任务 Z1 Z2 Z3 Z4 Z5 Z6 Z7 Z8 Z9 Z10 位置(30,33)(17,35)(24,10)(10,18)(38,26)(24,46)(31,31)(43,41)(49,48)(19,15)任务 Z11 Z12 Z13 Z14 Z15 Z16 Z17 Z18 Z19 Z20 位置(10,17)(50,24)(5,6)(18,4)(22,42)(45,23)(41,32)(16,46)(33,14)(46,12)任务 Z21 Z22 Z23 Z24 Z25 Z26 Z27 Z28 Z29 Z30 位置(36,49)(39,25)(35,12)(21,23)(48,42)(32,4)(44,34)(46,36)(40,14)(30,34)任务 Z31 Z32 Z33 Z34 Z35 Z36 Z37 Z38 Z39 Z40 位置(22,39)(27,22)(13,33)(35,24)(34,6)(21,27)(27,35)(34,24)(11,34)(47,8)任务 Z41 Z42 Z43 Z44 Z45 Z46 Z47 Z48 Z49 Z50 位置(31,32)(33,27)(41,33)(10,31)(26,9)(12,28)(6,34)(21,15)(43,46)(25,12)任务 Z51 Z52 Z53 Z54 Z55 Z56 Z57 Z58 Z59 Z60 位置(12,10)(14,12)(14,20)(20,12)(18,26)(16,32)(24,34)(26,39)(28,38)(34,36)任务 Z61 Z62 Z63 Z64 Z65 Z66 Z67 Z68 Z69 Z70 位置(24,30)(28,24)(30,24)(30,30)(26,36)(22,36)(18,28)(18,42)(18,34)(32,34)任务 Z71 Z72 Z73 Z74 Z75 Z76 Z77 Z78 Z79 Z80 位置(24,24)(22,22)(20,20)(20,28)(20,30)(6,30)(6,6)(4,16)(8,16)(10,16)4.2.机器人任务分配结果分析机器人任务分配结果分析 对两阶段随机规划模型的机器人任务分配问题进行仿真，遗传算法参数中，初始种群个数设为 200个，最大迭代次数设为 5000 次，交叉概率和变异概率设为 0.8。随机从表 1 选取任务的数量分别为 40 个、50 个、60 个、70 个和 80 个，通过采用循环机器人数量的方式进行仿真，对比不同数量机器人的空闲时间成本、期望总时间成本和任务分配结果，以便选择调度最优机器人个数，考虑到任务数量比较多，初始调度机器人数量设为 4 个，最大机器人数量为 8 个，以下仿真实验的结果包括机器人的调度数量、总空闲时间成本、期望总成本和机器人任务分配结果。图 59 的纵坐标表示搬运任务所花费的期望总成本，横坐标表示机器人的数量，实验结果显示，对于搬运相同数量任务，调度机器人数量的不同，所花费的总期望成本也不同，并且可以看出在完成相同数量任务时，花费的期望总成本随机调度器人数量的增加呈波动上升的趋势，调度 8 个机器人时花费的期望总成本都是最多的。顾洋洋，袁柳洋 DOI:10.12677/orf.2024.141102 1115 运筹与模糊学 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 个任务所花费的最小成本 顾洋洋，袁柳洋 DOI:10.12677/orf.2024.141102 1116 运筹与模糊学 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 个任务所花费的最小成本 顾洋洋，袁柳洋 DOI:10.12677/orf.2024.141102 1117 运筹与模糊学 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 个任务时普通的两阶段规划模型的仿真实验的时间成本是多于基于空闲时间不确定性的两阶段随机规划模型的仿真实验的空闲时间成本，并且普通的两阶段规划模型的仿真实验的总成本都多于基于空闲时间不确定性的两阶段随机规划模型的仿真实验的期望总成本，由此可以表明，在搬运过程中，发生堵塞、排队等情况时，让机器人在原地等待比绕路更节约成本。顾洋洋，袁柳洋 DOI:10.12677/orf.2024.141102 1118 运筹与模糊学 Table 3.Robot scheduling,total idle time cost,expected total cost and task allocation results for different tasks 表表 3.完成不同数量任务的机器人调度、总空闲时间成本、期望总成本以及任务分配结果 任务数量/个 机器人数量/个 基于空闲时间不确定性的 两阶段随机规划模型调度结果 基于普通的两阶段规划模型调度结果 总空闲时间成本/元 期望总成本/元 任务分配结果 时间成本/元 总成本/元 任务分配结果 40 4 0.017 1.881 1-4-10-11-13-14-19-20-27-28-33-39 2-3-5-12-16-22-23-29-30-31-36-37 3-1-7-8-9-17-24-32-34-38 4-2-6-15-18-21-25-26-35-40 0.007 2.990 1-4-5-11-13-14-15-18-21-22-23-26-35-40 2-2-9-12-16-17-19-24-36-39 3-3-8-25-27-28-29-30-32-34-38 4-1-6-7-10-20-31-33-37 50 4 0.022 2.306 1-1-2-4-11-13-14-24-36-37-41-42-43-49 2-10-15-18-21-25-28-29-35-38-46-47 3-5-12-16-20-22-27-30-31-32-34-40-45-48-50 4-3-6-7-8-9-17-19-23-26-33-39-44 0.030 3.120 1-4-8-20-29-32-34-38-42-43-49 2-1-2-5-6-7-15-18-21-22-23-26-35-40-45-50 3-3-9-12-16-17-24-33-39-44-46-47 4-10-11-13-14-19-25-27-28-30-31-36-37-41-48 60 5 0.017 2.639 1-4-10-19-20-27-28-30-33-39-44-47 2-2-6-15-31-37-41-56-57-58-59-60 3-1-7-12-17-22-24-32-35-40-45-48-50-51-52-55 4-11-13-14-18-21-25-29-34-36-46-53-54 5-3-5-8-9-16-23-26-38-42-43-49 0.046 3.540 1-14-15-18-19-23-24-31-37-41-43-49 2-10-12-16-20-25-28-30-32-36-44-46-48-50-52-54 3-3-5-7-17-39-47-55-56-57-59-60 4-1-6-8-9-21-22-29-35-40-45-51-53 5-2-4-11-13-26-27-33-34-38-42-58 70 4 0.016 3.031 1-4-5-16-17-25-27-28-30-31-33-36-41-45-50-51-52-54-62 2-2-6-9-11-13-14-19-26-35-40-48-53-56-57-58-59-61-67-69 3-1-7-8-12-20-23-29-34-38-42-43-49-60-65-66-68 4-3-10-15-18-21-22-24-32-37-39-44-46-47-55-63-64-70 0.028 4.020 1-1-9-12-16-19-23-24-25-28-29-35-40-48-51-52-55-56-57-61-62-63 2-2-6-7-10-11-13-14-15-18-21-30-31-33-36-39-45-50-54 3-4-5-22-32-34-38-41-42-43-49-58-59-60-64-65-66 4-3-8-17-20-26-27-37-44-46-47-53-67-68-69-70 80 5 0.042 3.388 1-2-7-17-20-23-26-32-36-39-44-46-47-53-54-64-70 2-3-10-11-19-21-25-29-35-40-43-49-58-65-66-68 3-13-14-24-27-28-30-31-37-41-59-60-62-63-72-73-74-75 4-4-5-8-9-12-16-22-34-38-42-45-48-50-51-52-55-71 5-1-6-15-18-33-56-57-61-67-69-76-77-78-79-80 0.013 4.76 1-4-6-8-9-10-13-14-19-20-22-23-24-30-33-37-38-42-45-48-50-54-73 2-2-18-21-26-32-36-46-52-53-56-57-58-60-64-65-70 3-3-5-7-16-25-28-34-41-43-44-61-62-63-71-72-74-75 4-11-12-17-27-29-35-40-49-59-66-76-79-80 5-1-15-31-39-47-51-55-67-68-69-77-78 5.结论结论 本文考虑了机器人在完成任务过程中由于堵塞、排队等耗费的空闲时间的不确定因素，建立的基于空闲时间不确定性的两阶段随机规划模型为机器人调度和任务分配问题提供了一种新的解决思路，第一阶段，对于给定的机器人数量，作出是否调度机器人的上层策略，使得机器人完成所有任务耗费的总期望成本最小化；第二阶段，对于两种场景，作出如何合理地进行任务分配的下层策略，使得机器人完成所有任务的空闲时间成本最小化，通过结合遗传算法，成功地解决了模型的求解问题，实现了机器人的顾洋洋，袁柳洋 DOI:10.12677/orf.2024.141102 1119 运筹与模糊学 高效调度和任务分配。通过仿真实验结果显示，该模型具有很好的可行性和有效性，可以得到具体的机器人调度数量以及任务分配方案，搬运任务数量的增加不代表调度机器人的数量也跟着增加，在完成 40个任务至 80 个任务，调度 4 个或者 5 个机器人去搬运可以花费更少的成本，并且通过对比实验得出当机器人搬运过程中遇到堵塞、排队时，在原地等待再通过的方案比让机器人绕路避开的方案要更节省成本消耗。基金项目基金项目 湖北省教育厅科学研究计划资助青年项目(Q20211111)、冶金工业过程系统科学湖北省重点实验室开放基金项目(Y201905)、国家自然科学基金项目(12361064)。参考文献参考文献 1 杨杰.智能仓储系统中任务调度及路径规划研究D:硕士学位论文.西安:西安电子科技大学,2019.2 秦虎.仓库搬运机器人调度优化及仿真J.物流技术与应用,2022,27(5):120-123.3 袁瑞萍,王慧玲,孙利瑞,等.基于物流 AGV 的“货到人”订单拣选系统任务调度研究J.运筹与管理,2018,27(10):133-138.4 石媛媛,周罗伟,王江柳,等.适用于智能仓储多机器人任务分配的一种平衡启发式拍卖方法C/中国自动化学会系统仿真专业委员会,中国系统仿真学会仿真技术应用专业委员会,离散系统仿真专业委员会.系统仿真技术及其应用学术论文集(第 15 卷).南京:南京大学工程管理学院控制与系统工程系,2014:280-285.5 Nielsen,I.,Do,N.,Banaszak,Z.A.,et al.(2017)Material Supply Scheduling in a Ubiquitous Manufacturing System.Robotics and Computer-Integrated Manufacturing:An International Journal of Manufacturing and Product and Process Development,45,21-33.https:/doi.org/10.1016/j.rcim.2016.08.009 6 谢永盛,曾箫潇,冯文健.改进布谷鸟搜索算法在多机器人任务分配及路径规划中的应用J.计算机应用与软件,2021,38(2):285-290.7 秦新立,宗群,李晓瑜,等.基于改进蚁群算法的多机器人任务分配J.空间控制技术与应用,2018,44(5):55-59.8 王振庭,陈永府,刘田.智能仓储中的多机器人调度方法J.计算机与现代化,2020(7):65-70.9 Petrovi,M.,Joki,A.,Miljkovi,Z.and Kulesza,Z.(2022)Multi-Objective Scheduling of a Single Mobile Robot Based on the Grey Wolf Optimization Algorithm.Applied Soft Computing,131,Article ID:109784.https:/doi.org/10.1016/j.asoc.2022.109784 10 Ma,J.,Yang,S.and Jing,H.(2022)Intelligent Warehouse Robot Scheduling System Using a Modified Nondominated Sorting Algorithm.Discrete Dynamics in Nature and Society,2022,Article ID:2021535.https:/doi.org/10.1155/2022/2