基于混合遗传算法的多拣货小车路径规划研究

胡小建, 杨 智

(1.合肥工业大学 管理学院,安徽 合肥 230009; 2.合肥工业大学 过程优化与智能决策教育部重点实验室,安徽 合肥 230009)

0 引 言

在互联网和电子商务快速发展的背景下,各大电商企业都在建立立体仓库用来提升相对落后的物流系统。“人到货”的分拣指的是人配合拣货小车用RFID扫描进行拣货。分拣仓库中货物的分拣大多数还是“人到货”的分拣,如典型的京东亚洲一号仓库的分拣,本文主要研究“人到货”的分拣。分拣仓库中的拣货小车调度问题是分拣系统中一个重要研究问题,也是目前国内外学者研究的热点问题。合理的车辆调度方案可以为企业节省运输成本和时间,提高物流服务的效率,为企业提升竞争力,因此对该问题的研究很有价值。

拣货小车调度问题包括单车调度问题和多车调度问题。对于单车调度问题,文献[1]基于基因表达式编程挖掘出高效实时调度规则;文献[2]在柔性制造系统中研究了一辆自动导引车的调度问题,建立了混合整数线性规划模型,提出了最佳解决方案,并研究了一些管理规则以及经典假设的影响。对于多车调度问题,文献[3]研究了一个新的自动导引车辆调度问题,该问题涉及在具有多品种和小批量生产的矩阵制造车间中从货物处理中取货和交货,建立了一个多目标混合整数规划模型,并设计了一种有效的多目标进化算法来解决该问题;文献[4]解决了一个矩阵制造车间物料搬运过程中的多自动导引车调度问题,该问题旨在确定一种解决方案以使运输成本最小化,为此建立了混合整数线性规划模型,提出了一种离散的人工蜂群算法以及一些新的技术来解决该问题;文献[5]提出了基于软时间窗的自动导引车调度规则;文献[6-10]分别提出了改进的差分进化算法、混合禁忌蝙蝠算法、优化的模糊决策算法、改进的花授粉算法以及改进的混合遗传算法与粒子群算法;文献[11]研究了动态作业选择调度规则在2种不同规模柔性制造系统中同时调度多载自动导引车的性能。

在分拣仓库中,不仅要考虑拣货小车的调度还要考虑多辆拣货小车的路径规划以及防碰撞问题。针对拣货小车路径规划,文献[12]提出了一种混沌模拟退火粒子群优化算法解决鱼骨型仓库布局拣选路径优化问题;文献[13]提出了一种混合粒子群优化算法求解多车协同拣选调度优化模型。对于防碰撞问题,文献[14]提出了一种环路死锁搜索方法;文献[15]提出了一种动态加权地图的交通规则和基于预约表的改进A*算法。

分析以上文献可知,多车调度一般假定拣货小车不会发生冲突且搬运路径固定。本文综合考虑了拣货小车的调度、路径规划以及多车之间防碰撞,建立多车路径规划模型以最小化最大搬运完成时间为优化目标,并采用遗传算法和A*算法混合的混合遗传算法求解。通过比较优化后的路径与优化前的路径,计算出节约的时间比例。为验证算法的性能,进行了仿真实验,在数据实验中用HGA进行了12组实验并观察了关键问题参数的影响。

1 问题描述

本文采用的分拣仓库栅格地图如图1所示。

图1 分拣仓库栅格地图

分拣仓库栅格地图由以下6个部分构成:

(1)分拣台。位于栅格地图的最左侧即栅格地图中的第1列,用于存放已经打包完成的包裹。

(2)停靠区。用于空闲拣货小车和已经完成搬运任务拣货小车的停靠,所有拣货小车均从停靠区出发。图1中箭头所指停靠区为坐标起点(1,1)。

(3)道路。栅格地图中白色的部分,用于拣货小车的行驶。

(4)拣货小车。用于拣货作业中装载货物的车辆,在仓库道路上以匀速v行驶。

(5)货架。将栅格地图均匀分割出多个存货区,每个存货区有4个货架用于存放货物。图1中所指货架坐标为(3,15)且各个货架均用坐标标出。

(6)分拣目的地。分拣目的地与货架相对应,若货架坐标(3,15),则拣货小车需行驶至栅格(3,16)进行分拣。

本文考虑多个订单、多个目标货架、多辆拣货小车,根据订单进行目标货架的选择以及多车拣选的路径规划问题。一方面,在平仓里进行拣选时通常是多辆拣货小车同时进行拣选且由不同的货架存放不同的货物,此时需要提前根据订单规划好最优的路径,避免降低拣货效率;另一方面,多车同时进行拣选容易出现路径冲突现象即在相同时间出现在相同位置,此时会造成道路拥堵,降低拣货效率。从图1可以看出,第1辆拣货小车和第m辆拣货小车在相同时间、相同位置相遇就会产生路径冲突,在该分拣仓库进行拣货作业的拣货小车越多,拣货的复杂性就越大,产生路径冲突就越容易,拣货效率会降低,因此在路径规划时需要根据避碰规则里小车的优先级让优先级低的拣货小车停车等待,优先级高的拣货小车优先通过,以此来达到消除路径冲突的目的,最后根据实际的拣货状况动态调整拣货路径。下面介绍问题参数与假设条件。

问题参数如下:设G=(V,E)为分拣仓库赋权图,V={i|1,2,…,n}为货架集合,E为边集;各货架之间的距离为dij,已知(dij>0且i,j∈V),距离用曼哈顿距离dij=|xi-xj|+|yi-yj|;v为拣货小车的行驶速度;xijk为决策变量(0-1变量)表示拣货小车k从货架i到货架j为1,否则为0;k为拣货小车的编号;K为拣货小车编号集合,k∈K={1,2,…,m};Tk为拣货小车k搬运一次货物所需要的时间;tw为拣货小车一次停车等待的时间;Tmax为最大搬运完成时间;nkw为拣货小车k搬运货物停车等待次数。

问题假设如下:

(1)拣货小车在行驶的过程中保持匀速。

(2)拣货小车可以沿上下或左右在栅格上行驶,但不允许沿对角线穿越栅格。

(3)不考虑拣货小车的装货与卸货时间,即拣货小车的装货和卸货时间为0。

(4)不考虑包裹到达停靠区后的出库过程。

(5)本文所用仓库为传统的分拣仓库。

(6)所有货架上都有货物,所有拣货小车均可使用。

(7)拣货小车不考虑容积约束和载重约束。

2 多车路径规划模型

Tk、Tmax计算方法如下:

|yi-yj|)xijk]/v+twnkw

(1)

(2)

基于(1)式、(2)式可得最小化最大搬运完成时间目标函数为:

(3)

约束条件为:

(4)

(5)

∀S⊂V；k=1,…,m

(6)

xijk∈{0,1}，i=0,…,n;k=1,…,m

(7)

x01=1,xn0=1

(8)

tw>0

(9)

其中:目标函数(3)式表示最小化最大拣货小车搬运完成时间;(4)式、(5)式表示所有待取货点所在货架都被选取且仅一次;(6)式则保证没有任何子回路解产生;(7)式表示决策变量是0-1变量即拣货小车从货架i到货架j为1,否则为0;(8)式表示拣货小车进行拣选作业时从停靠区出发,拣选作业完成后返回停靠区;(9)式表示拣货小车单次停车等待的时间要大于0。

3 模型求解

3.1 混合遗传算法

本文研究的多拣货小车调度与路径规划问题类似于多旅行商问题(multiple traveling salesman problems,M-TSP),因此遗传算法是求解该问题有效的智能算法,而A*算法是搜索最短路径的启发式算法并且可以用来得出拣货小车相邻拣货任务之间的最短路径的路径坐标,本文将遗传算法和A*算法混合得到混合遗传算法(hybrid genetic algarithm,HGA)用于求解多车路径规划模型。

A*算法主要用求得出多辆拣货小车的最短路径的路径坐标,然后在遗传算法中根据多辆拣货小车的路径坐标计算停车等待次数nkw,再根据nkw计算各个个体的适应度值。

HGA求解多车路径规划模型基本步骤如下。

(1)染色体编码。个体编码方法采用实数编码，如图2所示。

图2 编码示意图

首先对分拣仓库内所有货架进行编码,在实数编码中引入0作为分隔符,用来区分不同拣货小车及其路径,同时用0作为停靠区的编码。1,2,3,…,s表示所有货架。因此，染色体为(0,64,25,6,33,18,0,12,8,27,55,34,0，…),其中(0,1,2,3,4,5,0)表示第1辆拣货小车从停靠区出发依次对货位64、货位25、货位6、货位33、货位18进行拣货,拣选完成后返回停靠区,以此类推,另外染色体中0的数量为m+1个。

(2)产生初始种群。初始化种群大小p、拣货点个数n(即染色体基因数)、算法迭代的次数I、交叉概率pc和变异概率pm等参数。

(3)根据路径坐标计算停车等待次数。首先根据A*算法得出拣货小车拣货的路径坐标;然后根据路径坐标计算停车等待次数nkw。

(4)适应度函数。在多车路径规划模型中,已知距离矩阵d,根据n个拣选点的随机排列(每个染色体)和拣货小车的行驶速度v可计算出总运输时间,比较多辆小车的总运输时间,将最大的总运输时间作为适应度函数,即最大的运输时间越短,适应度函数越好。

(5)选择运算。采用基于适应度比例的选择策略,即适应度越好的个体被选择的概率越大。

(6)交叉运算。采用2点交叉算子,在相互配对的2个染色体编码串中随机设置2个交叉点,交换2个交叉点中间的元素,产生新的个体,提高种群的多样性,如图3所示。

图3 交叉示意图

步骤如下:① 随机选择2个染色体作为父本;② 产生2个随机自然数r1、r2;③ 将2个父本染色体r1至r2之间的基因片段进行交换,得到2个子代染色体,并对得到的2个染色体进行修复处理,使得不发生冲突。修复方法为交叉后取交叉片段的补集重新随机排列到非交叉片段。

示例说明:2个父代染色体为(9,5,1,3,7,4,2,10,8,6)与(10,5,4,6,3,8,7,2,1,9)分别表示2辆拣货小车的拣货顺序,产生随机自然数r1=4、r2=7进行交叉修复操作,以得到新的2条染色体,选择最优的染色体组合,实现拣货路径最优。

(7)变异运算。采用2点互异进行变异操作，如图4所示,其中变异概率pm选择范围为[0.01～0.2],变异是为了产生新的拣货路径,对路径中的路段进行变异操作，可以提高算法的效率,保持种群的多样性。步骤如下:① 产生2个随机自然数r1、r2;② 交换第r1位和第r2位的基因,得到新的拣货顺序。

图4 变异示意图

示例说明:有染色体为(9,5,1,6,3,8,7,10,4,2)表示依次拣选货架9、5、1、6、3、8、7、10、4、2,产生随机自然数r1=4、r2=7进行变异运算即交换第4位和第7位的基因,得到新的拣货顺序为9、5、1、7、3、8、6、10、4、2,新的染色体为(9,5,1,7,3,8,6,10,4,2)。

3.2 避碰规则

根据拣货小车载货情况的不同,将拣货小车的属性分为拣选过程中的载货、返回过程中的载货和空车3种属性。本文根据拣货小车的不同属性给予不同的优先级,根据拣货小车优先级确定避碰规则。不同拣货小车属性优先级的比较见表1所列。

表1 不同拣货小车属性优先级的比较

当产生冲突的2辆拣货小车的属性不同时,判断2辆拣货小车的优先级,载货(拣选)的拣货小车优先级最高,载货(返回)的优先级其次,空车的优先级最低。

当产生冲突的2个拣货小车的属性相同时,根据载货的情况判断货物优先级,货物优先级高的拣货小车的优先级高;空车的,优先级相同。

HGA的算法流程如图5所示。

图5 混合遗传算法流程

4 数据实验

4.1 实验设计

仿真对象为分拣仓库,其各项参数取值参见1.1节问题参数与假设条件。本文中实验为多车路径规划实验。实验运行环境为Intel(R)Core(TM)i5-5200U CPU @2.20 GHz,仿真软件为Matlab R2016a。

为验证HGA的有效性和先进性,以分拣仓库模型为仿真实例进行实验。HGA中拣货小车行驶速度v=1 m/s,种群大小p=100,迭代次数I=100。

问题规模设置为:拣选点数n为10、20、30、40;拣货小车数m为2、5、10。实验共分为12组,每组随机生成10个算例。

4.2 实验结果分析

12组实验算法的求解结果即最小化最大搬运完成时间(minTmax)和算法运行时间(algorithm running time,TAR)见表2、表3所列。表2、表3中加粗的数值是每组实验中的最小值。

表2 12次实验的min Tmax和TAR(算例1～算例5)

表3 12次实验的min Tmax和TAR(算例6～算例10)

由表2、表3可知:

(1)minTmax越小,不代表TAR越小。

(2)最小的minTmax和最小TAR发生在10×10规模问题中,数值分别为16 s和4.19 s。

(3)最大的minTmax和最大TAR发生在40×2规模问题中,数值分别是174 s和146.51 s。

以10×2规模为例,优化后的拣货路径如图6所示。

图6 10×2规模问题下拣货路径优化示意图

以10个拣选点为例,优化前后路径和节约时间比例见表4所列。表4中:t1为优化前小车行驶的总时间;t2为优化后小车行驶的总时间;(t1-t2)/t1为节约时间的比例。从表4中可以看出，10×2规模下节约时间的比例最大,节约了24.19%。

表4 10个拣选点下优化前后路径和节约时间比例表

同理可知,在20个拣选点情况下,20×2规模下节约时间的比例最大,节约了31.56%;在30个拣选点情况下,30×10规模下节约时间的比例最大,节约了20.86%;在40个拣选点情况下,40×2规模下节约时间的比例最大,节约了16.75%。

4.3 问题参数分析

本文重点分析研究问题中参数拣选点数n和拣货小车数m对HGA性能的影响。

(1)本文采用HGA求得12个实验组的最小化最大搬运完成时间(minTmax)和算法运行时间,其平均值如图7、图8所示。

图7 不同拣选点数量下的最小化最大搬运完成时间

图8 不同拣选点数量下的算法运行时间

分析可得,当m分别为2、5、10时,随着n的增大,minTmax和算法运行时间基本呈线性增长趋势,说明HGA具有良好的稳定性和扩展性。

(2)通过拣选点数n为10、20、30、40且m为2、5、10的12组实验,分析拣货小车数m对HGA的影响,如图9所示,当n为10、20、30、40时,随着m的增大,minTmax呈下降趋势且下降的斜率逐渐减小。原因分析如下:增加拣货小车的数量虽能减少搬运完成时间,但拣货小车的停车等待次数增多了即总的时间增加了,降低了小车的利用率。因此,需要根据仓库的规模大小和拣选点数确定合适的拣货小车的数量,提升小车的利用率。

图9 不同拣货小车数量下的最小化最大搬运完成时间

(3)不同拣货小车数量下的算法运行时间如图10所示。从图10可以看出,n为10、20、30时,随着拣货小车数量的增加,算法运行时间呈下降趋势且下降斜率逐渐减小;n=40时、m=10的算法运行时间比n=40、m=5的算法运行时间还要长。

图10 不同拣货小车数量下的算法运行时间

原因分析如下:增加拣货小车的数量能减少算法运行时间,但随着任务规模的增大,增加拣货小车的数量会增加算法的时间复杂度和空间复杂度,增加算法的运行时间。

5 结 论

本文研究“人到货”分拣情形下的拣货小车的路径规划问题,提出了分拣仓库的栅格地图模型。在此基础上构建了多车路径规划模型,并采用HGA求解。经过计算发现优化后的路径比优化前的路径最大可节约31.56%的时间。最后进行了12组实验,每组实验10个算例,大量实验表明,HGA有良好的稳定性和可扩展性。根据问题参数的分析表明,当拣货小车数量超过一定值之后,最小化最大搬运完成时间减小幅度越来越小,表明拣货小车的利用率在下降，即多辆拣货小车容易造成资源的浪费,如何在现有的仓库容量下合理地确定拣货小车的数量,实现资源的有效利用是接下来研究的重点。