仓库拣货员多任务路径优化

杨东起,骆心怡,毛 鹏†

(1. 南京林业大学轻工与食品学院, 江苏 南京 210037;2. 南京林业大学土木工程学院, 江苏 南京 210037)

1 引言

随着大数据、智慧供应链的兴起和科学技术的快速发展,众多企业的商务模式与供应链运营相互作用,产生了新业态[1]。为了提升企业核心竞争力,以期能更好地调控供应链运营中的费用,仓库的成本管理十分非常重要[2]。越来越多的企业为了使仓库施行更有效的库存信息化管理和提高货物的搬运效率,纷纷建立智能仓库进行仓储管理[3]。仓库的取货最优路径是使仓库管理高效运行的核心[4],因此,为了使仓库的管理更加智能化,提高拣货员的工作效率,众多学者进行了仓库取货的路径规划研究。

路径规划的算法主要有传统算法、智能优化算法[5]。现大多数学者在原先的算法上进行改进,引入模型得出路径调度的进一步优化。如Xing等人[6]对禁忌搜索(NTS)算法进行改进,在邻域搜索过程中设计了重定位和交换操作,优化了取货点的顺序,从而提高了拣货的工作效率。传统的A星算法存在计算量大的缺点[7],为此,Zhang等人[8]先基于A星算法得到初始路径,采用关键点选择策略进行二次规划,以去除路径中冗余的拐点和节点,提供更有效的仓库路径规划。上述的两种算法均属于传统的路径规划算法,智能优化算法中,由于遗传算法具有较好的鲁棒性和并行性,能够获得满足特定要求的最优解,被广泛应用于仓库的路径规划中[9],改进遗传算法以解决仓库的路径规划问题受到了大量学者的关注。如Zhu等人[10]提出了一种平均分布遗传算法,预先调整随机输入的染色体,以生成更合理的染色体,使迭代过程可以更高效地进行,同时避免早熟收敛,有效地处理了拣货调度问题。Paraskevi等人[11]将遗传算法与仓库拣货的距离和容量的模糊模型相结合,给出了不同情况下的路径调度最优解。Liu等人[12]将两种自适应遗传算法和一种多自适应遗传算法相结合,优化拣货的任务调度,具有较强的全局搜索能力和较快的优化速度。

然而上述文献均只考虑了拣货员执行一个任务时的路径优化,在实际生活中,由于拣货员数量有限,他们常常需要连续执行多个任务。此外,上述文献中提及的仓库规模较小,当仓库规模较大时,现有的方法难以满足需求。

针对上述问题,本文将拣货员的多任务拆分为若干个单任务,依次利用改进的遗传算法求解其最短路径。为了解决因大量计算两点间的距离而导致求解过程耗时的问题,本文创新性的总结了拣货员从当前位置运动到下一位置的路程计算公式,并引入了距离查找表。

2 问题描述

本文的仓库模型由货架和复核台组成,其规模较大。货架共4排,每排25组,每组2列,每列货架包含15个货格。货格共3000个。复核台共13个,位于货架外围,成直角分布于仓库左下角,纵5横8。任意两组水平方向相邻的货架之间的距离为1500mm,任意两组竖直方向相邻的货架之间的距离为2000mm。货格长宽均为800mm,复核台长宽均为1000mm。除货架和复核台,仓库其它地方皆可通行。图1为仓库的局部(仓库的左下角),包含1排7组,其每组2列,每列货架包含15个货格。

图1 仓库局部示意图

在拣货过程中,拣货员执行单任务的路径是由起始复核台、若干货格和终止复核台构成,可表示为

T={Sstart,L1,…,Li,…,Ln,Send}

(1)

其中,Sstart表示起始复核台,Send表示终止复核台,Li表示第i个货格。

实际生活中,一个拣货员会接到多个任务,拣货员每完成一个任务时,必须到复核台核对。此时,拣货员接到的多任务表示为

P={T1,…,Tj,Tj+1,…,Tm}

(2)

其中,Tj为拣货员的第j个单任务。Tj+1的起始复核台为Tj的终止复核台。

3 货格/复核台间距离计算

拣货员从当前位置(xi,yi)运动到下一位置(xi+1,yi+1)时,如果其中的某段路程同时满足:(1)连续两次转向,且方向相同(同为顺时针或者逆时针转向);(2)包含当前位置(xi,yi)或者下一位置(xi+1,yi+1),那么称它为“N”型路程,如图2中的路线ABCD。拣货员运动时通过偏移量才能绕过货架或复核台。图2中,线段AB、CD、EF和GH为横向偏移量,CI和FJ为纵向偏移量。所有的偏移量均记为bias=750mm。

图2 两货格间的路径示意图

当计算拣货员从当前位置(xi,yi)运动到下一位置(xi+1,yi+1)的路程时,如果拣货员无需绕过货架,如图3所示,那么当前位置和下一位置满足以下条件之一:

图3 拣货员从当前位置运动到下一位置的路径示意图

1)当前位置和下一位置分布在同一过道的一侧或两侧

2)当前位置和下一位置不在同一排货架。

此时,拣货员的路程可表示为:

D(i,i+1)=|xi-xi+1|+|yi-yi+1|+2n×bias

(3)

其中,n为“N”型路程的个数。

当计算拣货员从当前位置(xi,yi)运动到下一位置(xi+1,yi+1)的路程时,如果拣货员需要绕过货架,如图4所示,那么当前位置和下一位置同时满足以下条件:①当前位置和下一位置在同一排;②当前位置和下一位置不在同一竖直过道的一侧或两侧。

图4 拣货员从当前位置运动到下一位置的路径示意图

由于拣货员在绕过货架时,可从货架上方绕过,也可从货架下方绕过,所以选择它们中最短的路程。此时,拣货员的路程可表示为:

D(i,i+1)=|xi-xi+1|+min{ytop,ybottom}+(2n+2)×bias

(4)

其中,n为“N”型路线的个数;ytop和ybottom分别为从货架上方绕过和从货架下方绕过的总纵向距离,且满足以下关系:

(5)

其中,ymax和ymin分别表示货格所在货架的最大和最小纵坐标。

4 拣货员路径优化

4.1 改进的遗传算法

由于本文的仓库规模较大,直接从全部货格和复核台中查找拣货员当前位置和下一位置并计算二者之间的距离,这将导致求解过程中消耗大量时间。为此,本文在计算适应度时,引入了距离查找表来缩短程序运行时间。具体的过程如下:

1)编码

对于单任务而言,随机起始复核台和终止复核台,分别置于染色体的首部和尾部,任务涉及到的货格随机置于染色体的中间,以此作为该任务的潜在路径,如图5所示。对于多任务而言,将多个任务的染色体依次拼接作为一个染色体即可,如图6所示。

复核台货格1…货格n复核台

图6 多任务的编码

2)查找表

本文提及的仓库模型共包含3000个货格和13个复核台,仓库规模较大。计算拣货员从当前位置到下一位置的路程时,如果采用先从整个仓库模型中查取当前位置和下一位置的坐标,再计算二者之间的距离这一策略,那么这将消耗大量的时间。为了避免上述问题,本文先将拣货员任务中所涉及的货格和复核台选出,然后计算任意货格与货格、货格与复核台之间的距离,最后以此建立相应的距离查找表。

3)适应度

对染色体的优劣进行评价时,本文采用的衡量标准如下

(6)

其中,n为染色体的长度,即该路径中复核台和货架的总数;D(i,i+1) 为第i个复核台或者货格和第i+1个复核台或者货格间的距离,该距离从距离查找表中获得。

4)选择

利用选择操作中传统的轮盘赌,选择出适应度小的染色体作为子代。

5)交叉

交叉分为两种情况:(1)针对一个染色体,对一个任务内的随机的两个货格进行换位;(2)针对不同染色体,对应位置的复核台进行交叉。本文通过交叉阈值来决定染色体交叉时,会发生上述情况中的哪一种。

6)变异

通过变异阈值,决定染色体是否发生变异。如果染色体发生变异,那么用重新初始化的染色体替代该染色体。

4.2 仓库拣货员多任务路径优化策略

假设一个拣货员执行一次任务需要访问2个复核台和n个货格。以上述遗传算法为基础,本文提出以下三种策略来求解一个拣货员的m个任务的最短路径:

方法1:采用m次单目标规划。采用上述遗传算法的单任务编码,染色体长度为n+2,含有1个适应度,共执行m次;

方法2:采用单目标规划。采用上述遗传算法的多任务编码,染色体长度为m(n+1)+1,含有1个适应度,共执行1次;

方法3:采用多目标规划。采用NSGA-Ⅱ算法,编码方式为多任务编码,染色体长度为m(n+1)+1,含有m个适应度,共执行1次。

5 实验结果

本文选取了3个拣货员作为实验对象,并设定每个拣货员共执行3个任务,每个任务包含2个复核台和20个货格。为了简化实验,假设只有复核台FH03和FH11正常工作。实验所需原数据如表1所示。

表1 实验数据

表2为利用遗传算法求解拣货员单任务时是否采用距离查找表迭500次的耗时结果。从该表可以看出,采用距离查找表后,可将求解耗时缩小100多倍。

表2 是否采用距离查找表的耗时比较

对于上述求解仓库拣货员多任务路径的三种策略所涉及到的参数均相同:运行一次算法的最大迭代次数为1500次,变异阈值为0.1,交叉阈值为0.5。此外,三种策略在计算适应度时,均采用了距离查找表,且它们的选择、交叉、变异方式相同。三种策略求得的最短距离和耗时如表3所示。

表3 不同策略下的实验结果比较

从表3可以看出,对于3个拣货员而言,方法1虽然耗时较长,但是它更利于发现拣货员多任务时的最短路径。为了探究其原因,本文将3个拣货员在不同策略下的求解过程可视化,如图7所示。以拣货员P001为例,方法1收敛速度较快;方法2由于染色体的长度太长,所以收敛的速度较慢;方法3很难同时找到三个任务的最短路径,对于任务T0001迭代了1500次后,仍未收敛,这导致了该方法所得到的结果最差。其他拣货员亦是如此。方法1所求的最短路径如表4所示。

表4 基于方法1的拣货员的最短路径

图7 基于三种方法的3位接货员最短路径求解过程

6 结束语

本文总结了拣货员拣货时从当前位置运动到下一位置时的路程计算的基本规律。对于较大的仓库,为了避免因查找位置坐标而导致计算两点间的距离消耗大量时间,本文先将所涉及的位置坐标选出,计算任意两位置间的距离,然后建立了距离查找表。提出了利用遗传算法,采用多次单目标规划、单目标规划、多目标规划三种计算拣货员在多任务情况下最短路径的策略。最后,通过实验验证了多次单目标规划效果最优。本文所提的方案能有效解决实际中规模较大的仓库的路径优化问题。