1、基金项目:国家自然科学基金资助项目(72071115);江苏省大学生创新创业训练重点项目(202010298065Z)收稿日期:2021-05-20 修回日期:2021-05-27 第 40 卷 第 4 期计 算 机 仿 真2023 年 4 月 文章编号:1006-9348(2023)04-0139-06仓库拣货员多任务路径优化杨东起1,骆心怡2,毛 鹏2(1.南京林业大学轻工与食品学院,江苏 南京 210037;2.南京林业大学土木工程学院,江苏 南京 210037)摘要:随着供应链思想在本世纪初的发展,越来越多的企业注意到仓库管理的重要性。为了有效提高仓库管理的工作效率,往往需要结合科学技
2、术来实现。聚焦于优化仓库中的拣货路径,探究当拣货员在仓库执行多任务时如何实现最优路径规划。总结了拣货员从当前位置运动到下一位置的路程计算公式;提出了利用遗传算法,采用多次单目标规划策略求解拣货员多任务时的最短路径;引入了距离查找表以解决因大量计算两点间的距离而导致求解过程耗时的问题。通过实验,对比验证了所提方法的可行性和有效性。关键词:仓库管理;路径优化;遗传算法;查找表中图分类号:TP391.9 文献标识码:BMulti-Task Path Optimization for Warehouse PickersYANG Dong-qi1,LUO Xin-yi2,MAO Peng2(1.Coll
3、ege of Light Industry&Food,Nanjing Forestry University,Nanjing Jiangsu 210037,China;2.College of Civil Engineering,Nanjing Forestry University,Nanjing Jiangsu 210037,China)ABSTRACT:With the development of supply chain theory at the beginning of this century,more and more entrepre-neurs pay attention
4、 to the importance of warehouse management.In order to better improve the efficiency of warehousemanagement,it always needs to be done in conjunction with science and technology.This paper focuses on exploringhow to achieve the optimal path when the pickers have multiple tasks in the warehouse.The d
5、istance formula betweenthe current position and the next position was summarized.The optimal path of the pickers multi-task was solvedbased on genetic algorithm as the single objective programming.The distance look-up table was proposed to solve theproblem of time-consuming solving process due to a
6、large amount of calculation of distance between two points.Final-ly,the feasibility and effectiveness of the proposed method were verified by experiments.KEYWORDS:Warehouse management;Path optimization;Genetic algorithm;Look-up table1 引言随着大数据、智慧供应链的兴起和科学技术的快速发展,众多企业的商务模式与供应链运营相互作用,产生了新业态1。为了提升企业核心竞争
7、力,以期能更好地调控供应链运营中的费用,仓库的成本管理十分非常重要2。越来越多的企业为了使仓库施行更有效的库存信息化管理和提高货物的搬运效率,纷纷建立智能仓库进行仓储管理3。仓库的取货最优路径是使仓库管理高效运行的核心4,因此,为了使仓库的管理更加智能化,提高拣货员的工作效率,众多学者进行了仓库取货的路径规划研究。路径规划的算法主要有传统算法、智能优化算法5。现大多数学者在原先的算法上进行改进,引入模型得出路径调度的进一步优化。如 Xing 等人6对禁忌搜索(NTS)算法进行改进,在邻域搜索过程中设计了重定位和交换操作,优化了取货点的顺序,从而提高了拣货的工作效率。传统的 A 星算法存在计算量
8、大的缺点7,为此,Zhang 等人8先基于 A星算法得到初始路径,采用关键点选择策略进行二次规划,以去除路径中冗余的拐点和节点,提供更有效的仓库路径规划。上述的两种算法均属于传统的路径规划算法,智能优化算法中,由于遗传算法具有较好的鲁棒性和并行性,能够获得满足特定要求的最优解,被广泛应用于仓库的路径规划中9,改进遗传算法以解决仓库的路径规划问题受到了大量931学者的关注。如 Zhu 等人10提出了一种平均分布遗传算法,预先调整随机输入的染色体,以生成更合理的染色体,使迭代过程可以更高效地进行,同时避免早熟收敛,有效地处理了拣货调度问题。Paraskevi 等人11将遗传算法与仓库拣货的距离和容
9、量的模糊模型相结合,给出了不同情况下的路径调度最优解。Liu 等人12将两种自适应遗传算法和一种多自适应遗传算法相结合,优化拣货的任务调度,具有较强的全局搜索能力和较快的优化速度。然而上述文献均只考虑了拣货员执行一个任务时的路径优化,在实际生活中,由于拣货员数量有限,他们常常需要连续执行多个任务。此外,上述文献中提及的仓库规模较小,当仓库规模较大时,现有的方法难以满足需求。针对上述问题,本文将拣货员的多任务拆分为若干个单任务,依次利用改进的遗传算法求解其最短路径。为了解决因大量计算两点间的距离而导致求解过程耗时的问题,本文创新性的总结了拣货员从当前位置运动到下一位置的路程计算公式,并引入了距离
10、查找表。2 问题描述本文的仓库模型由货架和复核台组成,其规模较大。货架共 4 排,每排 25 组,每组 2 列,每列货架包含 15 个货格。货格共 3000 个。复核台共 13 个,位于货架外围,成直角分布于仓库左下角,纵 5 横 8。任意两组水平方向相邻的货架之间的距离为 1500mm,任意两组竖直方向相邻的货架之间的距离为 2000mm。货格长宽均为 800mm,复核台长宽均为1000mm。除货架和复核台,仓库其它地方皆可通行。图 1为仓库的局部(仓库的左下角),包含 1 排 7 组,其每组 2 列,每列货架包含 15 个货格。在拣货过程中,拣货员执行单任务的路径是由起始复核台、若干货格和
11、终止复核台构成,可表示为T=Sstart,L1,Li,Ln,Send(1)其中,Sstart表示起始复核台,Send表示终止复核台,Li表示第 i个货格。实际生活中,一个拣货员会接到多个任务,拣货员每完成一个任务时,必须到复核台核对。此时,拣货员接到的多任务表示为P=T1,Tj,Tj+1,Tm(2)其中,Tj为拣货员的第 j 个单任务。Tj+1的起始复核台为 Tj的终止复核台。图 1 仓库局部示意图3 货格/复核台间距离计算拣货员从当前位置(xi,yi)运动到下一位置(xi+1,yi+1)时,如果其中的某段路程同时满足:(1)连续两次转向,且方向相同(同为顺时针或者逆时针转向);(2)包含当前
12、位置(xi,yi)或者下一位置(xi+1,yi+1),那么称它为“N”型路程,如图 2 中的路线 ABCD。拣货员运动时通过偏移量才能绕过货架或复核台。图 2 中,线段 AB、CD、EF 和 GH 为横向偏移量,CI 和 FJ 为纵向偏移量。所有的偏移量均记为 bias=750mm。当计算拣货员从当前位置(xi,yi)运动到下一位置(xi+1,yi+1)的路程时,如果拣货员无需绕过货架,如图 3 所示,那么当前位置和下一位置满足以下条件之一:图 2 两货格间的路径示意图1)当前位置和下一位置分布在同一过道的一侧或两侧2)当前位置和下一位置不在同一排货架。此时,拣货员的路程可表示为:041D(i
13、,i+1)=|xi-xi+1|+|yi-yi+1|+2n bias(3)其中,n 为“N”型路程的个数。图 3 拣货员从当前位置运动到下一位置的路径示意图当计算拣货员从当前位置(xi,yi)运动到下一位置(xi+1,yi+1)的路程时,如果拣货员需要绕过货架,如图 4 所示,那么当前位置和下一位置同时满足以下条件:当前位置和下一位置在同一排;当前位置和下一位置不在同一竖直过道的一侧或两侧。图 4 拣货员从当前位置运动到下一位置的路径示意图由于拣货员在绕过货架时,可从货架上方绕过,也可从货架下方绕过,所以选择它们中最短的路程。此时,拣货员的路程可表示为:D(i,i+1)=|xi-xi+1|+mi
14、nytop,ybottom+(2n+2)bias(4)其中,n 为“N”型路线的个数;ytop和 ybottom分别为从货架上方绕过和从货架下方绕过的总纵向距离,且满足以下关系:ytop=|ymax-yi|+|ymax-yi+1|ybottom=|yi-ymin|+|yi+1-ymin|(5)其中,ymax和 ymin分别表示货格所在货架的最大和最小纵坐标。4 拣货员路径优化4.1 改进的遗传算法由于本文的仓库规模较大,直接从全部货格和复核台中查找拣货员当前位置和下一位置并计算二者之间的距离,这将导致求解过程中消耗大量时间。为此,本文在计算适应度时,引入了距离查找表来缩短程序运行时间。具体的过
15、程如下:1)编码对于单任务而言,随机起始复核台和终止复核台,分别置于染色体的首部和尾部,任务涉及到的货格随机置于染色体的中间,以此作为该任务的潜在路径,如图 5 所示。对于多任务而言,将多个任务的染色体依次拼接作为一个染色体即可,如图 6 所示。复核台货格 1货格 n复核台图 5 单任务的编码图 6 多任务的编码2)查找表本文提及的仓库模型共包含 3000 个货格和 13 个复核台,仓库规模较大。计算拣货员从当前位置到下一位置的路程时,如果采用先从整个仓库模型中查取当前位置和下一位置的坐标,再计算二者之间的距离这一策略,那么这将消耗大量的时间。为了避免上述问题,本文先将拣货员任务中所涉及的货格
16、和复核台选出,然后计算任意货格与货格、货格与复核台之间的距离,最后以此建立相应的距离查找表。3)适应度对染色体的优劣进行评价时,本文采用的衡量标准如下S=n-1i=1D(i,i+1)(6)其中,n 为染色体的长度,即该路径中复核台和货架的总数;D(i,i+1)为第 i 个复核台或者货格和第 i+1 个复核台或者货格间的距离,该距离从距离查找表中获得。4)选择利用选择操作中传统的轮盘赌,选择出适应度小的染色体作为子代。5)交叉交叉分为两种情况:(1)针对一个染色体,对一个任务内的随机的两个货格进行换位;(2)针对不同染色体,对应位置的复核台进行交叉。本文通过交叉阈值来决定染色体交叉时,会发生上述情况中的哪一种。6)变异通过变异阈值,决定染色体是否发生变异。如果染色体发生变异,那么用重新初始化的染色体替代该染色体。4.2 仓库拣货员多任务路径优化策略假设一个拣货员执行一次任务需要访问 2 个复核台和 n个货格。以上述遗传算法为基础,本文提出以下三种策略来求解一个拣货员的 m 个任务的最短路径:141方法 1:采用 m 次单目标规划。采用上述遗传算法的单任务编码,染色体长度为 n+2,含有