基于多智能体算法的智慧无人仓布局设计及 AGV 调度优化研究论文

　　【关键词】无人仓布局,AGV调度,ALNS,基于冲突搜索
 

　　Research on Intelligent Unmanned Warehouse Layout Design and AGV Scheduling
 

　    ZHAO Bo-m,eBi,,tZi,ZHANG Kang
 

　　(School of Economics&Management,Southeast University,Nanjing 211189,China)
 

　　【Abstract】Intelligent logistics is one of the major themes of Industry 4.0,while intelligent unmanned warehouse based on AGV system is a possible form of storage intelligentization under the existing technology.Among them,unmanned warehouse layout and AGV scheduling strategy are important factors that affect the maturity of unmanned warehouse technology.Taking into account the characteristic that unmanned warehouse layout and AGV scheduling strategy affect each other,the experiment studied the effect of layout elements such as aisle on the throughput efficiency of unmanned warehouses through the AGV scheduling strategy which is designed by combining the research findings of MAPF problem with ALNS algorithm.The experimental results show that layout with ingenious aisles is beneficial to improve the operational efficiency of AGV in unmanned warehouse.
 

　　【Key words】unmanned warehouse layout;AGV scheduling;ALNS;conflict-based search;multi-agent algorithm
 

　　工业4.0是智能化的时代，而智能化旨在利用信息化技术促进产业变革。智能物流是工业4.0的几大主题之一，强调利用物联网、大数据、人工智能等先进技术整合物流资源，提高物流效率，同时，也为需求方提供更强的物流支持。基于AGV系统的智能无人仓就是现有技术支持下，物流仓储阶段智能化的一种可能形式。对此，亚马逊、京东、菜鸟等物流巨头均表现出了强烈的兴趣，并拿出了kiva、亚洲一号等智能仓储系统。

 

　　AGV(Automated Guided Vehicle)是一种搬运机器人，此类机器人需要在具有特定地标的栅格无人仓中，在中控系统的指引下运行，这种特点自然而然地带来了无人仓布局设计和多AGV调度问题。无人仓布局对于仓库效率通常都有影响，Roodbergen,Koster[1]验证了I/O点位置不同的情况下，插入正交通道在I/O点异侧的情况下确实会提高吞吐效率。Gue等[2]验证了一些非传统鱼骨型的布局也有益于提高无人仓效率。多AGV调度在运筹优化领域主要考虑任务分配和路径规划两个问题，任务分配是研究合理地将任务分配给多个AGV的问题，路径规划则是为多个AGV规划无冲突路径。设计良好的AGV调度策略是实验研究无人仓布局要素对于无人仓效率影响的前提。
 

　　1研究现状
 

　　一些学者通过分别考虑两项任务，对该问题提出了AGV调度策略。丁一等[3]使用模拟退火算法进行任务分配，时空网络算法执行无冲突路径的规划。范厚明等[4]设计自适应遗传算法实现任务分配，使用Dijkstra算法执行路径规划。一些学者在任务分配环节就考虑规避AGV间的冲突，因而提出了Krishnamurthy等[5]建立了该问题的混合整数规划模型，并使用列生成算法进行求解。Correa等[6]将任务分配问题建模为主问题，将无冲突路径规划建模为子问题，并使用CPLEX求解了小规模的算例。王鹤南，张新敏[7]使用Dijkstra算法为单个AGV规划路径，当路径发生冲突时则使用带约束的遗传算法为多个AGV规划路径。陈志刚，卢山[8]则基于概率模型求解带时间窗约束的多智能体路径规划问题。
 

　　是从智能无人仓当中抽象出来的问题，其主流求解方法主要包含四类，即Astar算法、代价增长树、规约算法以及冲突搜索算法。此处提到的Astar算法是指为多AGV规划路径的Astar算法，因为基础的Astar算法构建的搜索空间非常大，难以求解大规模的问题。Standley[9]提出使用算子分解和独立检测来提高效率。Goldenberg等[10]提出的EPEAstar仅会将部分更有潜力的节点纳入到进一步的搜索过程中。代价增长树(ICTS)算法是一种两层算法，该算法首先指定目标成本，然后在目标成本下搜索可行解，当可行解不存在时放宽成本限制进行迭代搜索，直到找到最小成本的可行解。规约算法通常是将问题建模为规划模型，然后使用对应方法进行求解。
 

　　冲突搜索算法(CBS)是比较热门的无冲突路径搜索算法，其基本思路是使用Astar或者Dijkstra算法为单个AGV规划路径，然后由上层算法检查冲突，上层算法会在检查到冲突后对下层算法提供约束并进行重新规划，如此迭代直到找到最优路径。针对CBS算法在拥挤时易发生大量次生冲突导致效率降低的问题，Sharon等[11]提出了MACBS算法，该算法实际上是将Astar算法引入了CBS算法，具体做法是当某些AGV之间冲突超过限度时，将这些AGV合并为MetaAGV并使用先前的Astar算法规划路径。Boyarski等[12]提出了ICBS算法，该算法在前人基础上进一步提出了对冲突进行分类处理的思路。
 

　　MAPF问题虽然脱胎于智能无人仓，如今却较少被应用于智能无人仓当中进行路径规划，因此，本文基于任务分配和路径规划两阶段考虑AGV调度问题，将MAPF算法研究成果应用于路径规划，并结合自适应大邻域搜索算法设计AGV调度策略，从而支持实验研究无人仓布局要素对于AGV运行效率的影响。
 

　　2 AGV调度策略

       2.1路径规划
 

　　MAPF问题与最短路问题的主要差别在于如何处理AGV间的冲突。多智能体Astar算法在搜索邻居节点的时候，对每个AGV的邻域节点集合求笛卡尔积，并排除冲突节点构成多智能体的无冲突通行空间。由于冲突搜索算法是一个两阶段的算法，下层算法在不考虑冲突的前提下为单个AGV规划路径，随后上层算法在其中搜索冲突，当上层算法搜索到冲突以后，会通过对冲突双方分别施加约束进行分支，其中，叶子节点会不断继承父节点所记录的冲突，如此反复，直到搜索到最小成本无冲突路径。
 

　　通过分析发现，前述算法处理冲突的思想是记录AGV的时空位置，然后令寻路算法在搜索路径的时候避免那些会发生冲突的路径。基于此思想，提出一种无冲突路径搜索算法。第一步，使用Astar、Dijkstra等算法为单个AGV搜索路径；第二步，记录AGV每一步移动的时空位置；第三步，为下一个AGV搜索路径，同时，根据第二步记录的时空位置避免在搜索路径时发生冲突，反复迭代直到所有AGV的路径都规划完毕。该算法解决了多AGV无冲突的路径搜索问题，但是还需要借助任务分配策略才能得知AGV行动的起点与终点。
 

　　2.2任务分配
 

　　任务分配问题形似组合优化问题，只是目标函数值需要借助路径规划算法求得。对于此类问题，邻域搜索算法是比较常用的启发式算法。经典的模拟退火算法只能探索一种邻域，于是变邻域搜索(VNS)被提出，其允许使用多个算子来探索多种邻域，但不同的算子对于特定问题的适用性可能有所不同，VNS在选择算子上比较盲目，因此，自适应大邻域搜索(ALNS)就被提出。该算法在VNS的基础上增加了一套打分机制来评估每次迭代中算子的表现，并允许那些表现更好的算子被更加频繁地使用。因为ALNS的结构比较完善，同时允许通过添加算子来实现算法的进一步完善，于是被用来求解任务分配问题。
 

　　ALNS主要包含初始化、算子执行和算子打分三个步骤：①初始化。算法按照一定的规则构造初始解，例如，将所有任务均匀打乱并分配给所有的AGV;②算子执行。算法会将算子的初始权重视为概率，使用轮盘赌的方式随机选择算子并执行得到当前解；③打分。打分机制会按照当前解的四种表现，即超过历史最优、超过当前解、劣解被接受、劣解未接受给出递减的分数，分数会影响算子的权重，进而影响到算子被选择到的概率。这种影响过程通过权重更新公式描述，权重更新的速度与更新系数和保留系数有关，更新系数越大，保留系数就相应越小，权重的更新速度就越快。权重更新的部分等于算子得分与算子使用次数之比，作比的好处是得到了算子每次执行的平均分而非累计分数，以防止算子表现较差，但因为被选择次数较多就得到更多权重的问题。算法不断迭代这三个步骤，直到达到终止条件，其中，每次迭代就是一次退火过程，算子均有一个与温度相关的概率接受劣解，以防止基于启发式规则的算子局限在某个局部最优解上。
 

　　算子设计对于该算法的性能有较大影响，该算法通过允许多种算子设计的方式，实际上集成了多种搜索规则，这些规则定义了多种不同的搜索邻域，使得在一种邻域当中存在的局部最优问题在另一种邻域视角看来可能并不造成阻碍。随机算子和平衡算子都是比较经典的算子，随机算子随机将某个AGV的任务转移给另一个AGV,平衡算子则将完成任务耗时最长的AGV转移给完成任务耗时最少的AGV。将ALNS与路径规划结合，就得到了AGV调度策略。
 

　　3实验研究
 

　　3.1场景描述
 

　　第十二届MathorCup数学建模挑战赛B题提供了一个具有32×22大小的无人仓场景，该场景为本实验的开展提供了良好的算例。算例地图中包含148个储位节点，6个I/O点和两个托盘回收处，任务要求将所有货物按照订单要求送至目标I/O点，仓库中的货物多于订单的需求。场景中，每一个货架都固定在地面上，托盘放置在货架上，AGV空载时能够穿行于货架中，或者将货架上的托盘抬起，但当AGV负载托盘时则不能经过任何储位节点，否则，托盘会与货架发生撞击，导致货物散落在仓库中，进一步影响AGV系统的运行。相应的，由于结构原因，AGV也仅能在货架处或者托盘回收点卸下托盘。AGV完成搬运任务需要经过取货、送货以及返回三个步骤，取货是取得目标托盘，送货是将托盘送至目标I/O点，返回根据托盘是否为空分为回收和回库，回收是指将空托盘运送至托盘回收点，回库则是将非空托盘送回仓库。
 

　　3.2实验设计
 

　　对于通道的研究比较丰富，通道的设计要素包括通道的数量、通道的形状等。通道与过道的不同在于通道通常是指方向区别于平行货架的过道的路径。在无人仓面积允许的前提下，无人仓可以设置任意无限多条通道，但是不难想象过多的通道也会占用过多的仓库面积而仅仅发挥有限的作用。通道的形状要素与前述布局研究文献有关[1-2],这些文献中作者设计了例如折线形等异形通道并提高了无人仓的效率，本文也设计实验探究具有异形通道的布局是否会对所述场景带来效率上的提升。
 

　　如图1所示，图中灰色表示可通行节点，中间的节点表示存储节点，上边、下边和右边都均匀分布两个I/O点，左下和右上的节点表示托盘回收处，后续布局也类似表示。在各个实验中，I/O点和托盘回收处的位置保持一致，通过控制变量来探究货架的各个布局要素对于无人仓效率的影响。

 

 

　　第一个和第二个实验分别探索通道的数量和形状对于无人仓效率的影响。第一个实验如图1所示，图1（左）表示无通道布局，图1（中）表示居中单通道布局，图1（右）表示均匀双通道布局。第二个实验探究通道的形状对于无人仓布局的影响。图2（左）表示直线通道布局，图2（中）表示斜线通道布局，图2（右）表示折线通道布局。
 

　　4实验结果
 

　　4.1实验数据
 

　　AGV系统在第一个实验当中完成任务分别花费了22040、21164、20799步。相比之下，单过道布局比无过道布局节约了AGV系统4.14%的步数，双过道布局又比单过道布局节约了AGV系统1.85%的步数，即双过道布局比无过道布局节约了6.07%的步数。
 

　　AGV系统在第二个实验当中完成任务分别花费了21165、22098、22236步。相比之下，AGV系统在斜线布局中花费的步数比直线布局中多4.41%,在折线布局中花费的步数则比在直线布局中多5.06%。显然，异形的通道降低了通道的作用。
 

　　4.2结果分析
 

　　结果表明，好的通道确实具有提高无人仓效率的作用。结合Boyarski等[12]的工作，关于通道能够提高无人仓效率的机理，一种可能的解释是通道为AGV系统提供了更多的选择以避免重要冲突(Cardinal Conflict,CC)。重要冲突是一类无法经过等曼哈顿距离路径绕行而避免的冲突，这种冲突的发生一定会降低无人仓效率，如果仓库更加空旷或是有更多通道，那么AGV实际上会拥有更多的等曼哈顿距离路径，也就降低了冲突对于无人仓效率的影响。
 

　　5研究展望
 

　　本文结合MAPF的研究成果与ALNS算法设计了AGV调度策略，采取实验研究的方式探究了过道的数量和形状对于无人仓效率的影响，结果表明提高通道数量对于无人仓的效率有提升的作用。随后，本文结合其他学者的工作对于这些布局要素影响无人仓效率的可能机理进行了分析讨论。后续的研究者可以使用更多的算例来验证这一结果，以探索结论在更广泛的场景中的适用性。另外，本文基于算例规模考虑采取了启发式的AGV调度策略，这一策略也有待于进一步优化来适应更加精确或者是更大规模算例的实验研究。
 

　　［参考文献］
 

　　[1]Roodbergen K J,Koster R.Routing order pickers in a warehouse with a middle aisle[J].European Journal of Operational Research,2001,133(1):32-43.
 

　    [2] Gue K , Ivanoviĉ G, Meller R. A unit - load warehouse with multiple pickup and deposit points and non-traditional aisles[J].Transportation Research Part E:Logistics and Transportation Review,2012,48(4):795-806.
 

　　[3]丁一，袁浩，方怀瑾，等．考虑冲突规避的自动化集装箱码头AGV优化调度方法[J].交通信息与安全，2022,40(3):96-107.
 

　　[4]范厚明，牟爽，岳丽君．考虑冲突和拥堵的自动导引车调度与路径规划协同优化[J].计算机应用，2022,42(7):2281-2291.

       [5]Krishnamurthy N,Batta R,Karwan M.Developing conflict-free routes for automated guided vehicles[J].Operations Research,1993,41(6):1077-1090.
 

　　[6]Correa A I,Andre L,Louis R.Scheduling and routing of automated guided vehicles:A hybrid approach[J].Computers&Operations Research,2007,34(6):1688-1707.
 

　　[7]王鹤南，张新敏．人机混合环境下的多AGV系统路径规划研究[J].物流工程与管理，2018,40(06):88-90.
 

　　[8]陈志刚，卢山．时间窗约束下基于概率模型的AGV路径研究[J].物流工程与管理，2017,39(10):65-67+32.
 

　　[9]Standley T.Finding Optimal Solutions to Cooperative Pathfinding Problems[C].Proceedings of the 24th AAAIConference on Artificial Intelligence,Los Angeles,Associa-tion for the Advancement of Artificial Intelligence,2010.
 

　　[10]Goldenberg M,Felner A,Stern R,et al.Enhanced partial expansion A[J].Journal of Artificial Intelligence Research,2014,50(2):141-187.

       [11] Sharon G, Stern R , Felner A , et al. Conflict - based search for optimal multi-agent pathfinding[J].Artificial Intelligence ,2015 ,219 :40 - 66.
 

　　[12]Boyarski E,Felner A,Stern R,et al.ICBS:improved conflict-based search algorithm for multi-agent pathfinding[C].Proceedings of the 24th International Conference on Artificial Intelligence.Argentina,The International Joint Conferences on Artificial Intelligence,Inc.2015.