本文摘要:摘要:为提高电商仓库的拣货作业效率,本文提出了基于聚类和动态规划的组合路径策略,实现了生成路径消耗时间和路径长度之间的平衡,并将这一策略成功地应用到多区型仓库。该策略分四步:首先,根据待拣储位分布特征,运用聚类分析法对其进行分类;然后,以各
摘要:为提高电商仓库的拣货作业效率,本文提出了基于聚类和动态规划的组合路径策略,实现了生成路径消耗时间和路径长度之间的平衡,并将这一策略成功地应用到多区型仓库。该策略分四步:首先,根据待拣储位分布特征,运用聚类分析法对其进行分类;然后,以各类的首末储位作为节点,运用动态规划法对已得分类进行排序,得到相应的类序;其次,得到各类内部路径;最后,依次拣取待拣商品,并返回出发点完成拣货作业。在提出新的路径策略后,通过仿真方法将新策略与三种传统路径策略(穿越策略、最大间隙策略和混合策略)和一种优质算法(蚁群算法)进行了对比分析,结果表明:该策略具备良好的适用性和实用性。
关键词:拣货路径;聚类分析;动态规划
电商论文范文:电商售后货物退换设计流程和步骤
这篇电子商务论文发表了电商售后货物退换设计流程和步骤,隨着电子商务经济模式不断发展和完善,网络购物逐渐成为人们日常消费的主要方式之一。论文分析了电商模式下货物退换的流程和步骤,绘制了电商模式下货物退换的流程设计图。
0引言
2018年全国邮政管理工作会议公布的数据显示,2017年,快递业务量完成401亿件,同比增长28%。中国电子商务研究中心物流行业分析师姚建芳指出,这意味着国内快递包裹分发已经进入日均一亿件时代。面对发展如此迅猛的电子商务,提高电商订单处理效率势在必行。相关研究表明[1~3],作为订单处理核心环节的拣货作业在仓库作业中耗时最长、耗力最多,成本比例高达65%。拣货作业由行走、寻找、拣取、放置和其他五部分组成。其中行走用时比例高达50%,由此可见,行走距离会直接影响到拣货员的拣货效率,是提高拣货效率首要改进目标。要想减小行走距离就要对拣货路径进行优化。拣货路径优化问题作为一种组合优化问题,当规模较小时,可通过精确算法求解,但随着规模的增大,求解的复杂度将以指数级别增长,这时就需借助启发式算法得到满意解[4,5]。
关于仓库拣货路径方法的研究主要有启发式路径策略、数学最优化方法和智能优化算法。传统的启发式路径策略有穿越策略(Sshape)、最大间隙策略(LargestGap)和混合策略(Combined)[6~9]。穿越策略的引导策略为:拣货员以S形路线穿越所有包含待拣商品的巷道(跳过不包含待拣商品的巷道)进行拣货作业,这一策略仅适用拣货密度较大的情况;最大间隙策略作为返回策略的一种改进策略,是指拣货员以避开两相邻拣货位之间、每个拣货位与相应横向通道之间的距离最大的间隙的方式进行拣货作业;混合路径策略是指通过将穿越策略与返回策略相结合,使两相邻巷道中最远的待拣货位置之间的距离最小化的方式进行拣货作业。
只有当拣货密度较大时,穿越策略优于最大间隙策略;当拣货密度较小时,最大间隙策略优于穿越策略;而总体上来说混合策略要优于其他两种策略。应用于仓库拣货路径研究的数学最优化方法主要是动态规划法[10,11],当拣货规模较小时,该方法可以得到最佳的拣货路径,但随着拣货规模的增加,方法的复杂度将呈现指数级的增加,而且其适用的仓库布局类型是有限的。受到人类智能、生物群体社会性或自然现象规律的启发,人们发明了很多智能优化算法来解决复杂的优化问题。应用于仓库拣货路径研究的智能优化算法[12~14]主要包括模拟退火算法(SimulatedAnnealing,SA)、遗传算法(GeneticAlgorithm,GA)、蚁群算法(AntColonyOptimization,ACO)以及针对这些算法的改进算法。这些智能优化算法通过反复迭代,在满足收敛条件时,得到较优的拣货路径,这些迭代必然要以消耗一定的资源为代价的,且随着拣货规模的增大,智能优化算法消耗的资源和时间是难以忍受的。
针对传统策略适用范围受限,且有时与最佳拣货路径差距较大,数学优化算法和智能优化算法适用的拣货规模受限的问题,本文提出了一种新的拣货路径策略:基于聚类分析[15~18]和动态规划[19,20]的组合路径策略(CADP),该策略首先根据待拣储位分布特征,对其进行分类;然后运用动态规划的方法对各类进行排序,得到相应的类序;接着确定各类内部路径;最后通过类序连接各子路径找到一个较优的启发式路径,将规模较大的拣货路径问题,简化成几个较小的子路径问题,达到了化繁为简的效果。
1问题的描述与模型的建立
1.1问题的描述
本文以人至物平面仓库作为研究背景,重点讨论双区型仓库和三区型仓库的拣货路径问题。仓库由若干条平行的巷道构成,巷道两侧为平行排列货架,集货区位于整个分拣区的左下角。包含三条横向通道的为双区型仓库,包含四条横向通道的为三区型仓库。其中,每个区块都有相应的前端横向通道和末端横向通道,以距离depot较近的横向通道作为前端横向通道,距离depot远的横向通道为末端横向通道。
depot是仓库的进出口,为简化计算默认其位于第一条横向通道和第一条巷道中心线的交汇处。以离depot最近的区块为第1区,由近及远,区块编号依次递增。其中巷道宽度为D1=1m,横向通道宽度为D2=2m。D3=3m为两条相邻巷道之间的宽度。每一方格代表一个储位(储位长度和宽度均为1m),且有对应的编号(B,A,S,R),其中B(正整数,且Bmin=2,Bmax=3)表示该储位所在的区块编号,A表示所在的巷道编号(Amin=1为第一条巷道编号,Amax为最大巷道编号),S表示位于该巷道的哪一侧(S=0表示左侧,S=1表示右侧),R表示当前区块的行数编号(Rmin=1为第一行编号,Rmax为最大行数编号)。
拣货员从depot出发依次拣取待拣储位上的商品,返回至depot完成当前的拣货任务。可以看出拣货路径问题是特殊的旅行商问题,其特殊之处在于当两待拣储位位于不同巷道时,拣货员在拣完当前储位后,需离开当前巷道,并通过相应的横向通道进入下一个待拣储位所在的巷道。以下就仓库中任意两个储位之间的距离计算进行说明:文中计算的储位之间、储位与巷道和储位与横向通道的距离均为中心线之间的距离。
2基于聚类和动态规划的组合路径策略
本文提出了基于聚类和动态规划的组合路径策略:首先,根据待拣储位的分布特征,对其进行聚类分析;其次,运用动态规划法得到相应的类序;接着,确定各类的子路径;最后,按照类序连接对应的子路径得到最终的启发式路径。
2.1聚类分析法在路径优化中的应用
以待拣储位间的两两距离为依据,对待拣储位进行聚类分析,将一个复杂的旅行商问题分解成几个简单路径问题。前期通过大量探索试验可知:当聚类数量p在[9,12]范围内取值时,聚类效果最佳。文本借助MATLAB编程,运用层次聚类分析法,对待拣储位进行聚类,具体的实现步骤如下:(1)首先计算两两坐标的最短距离cij,继而生成相应的距离矩阵C。(2)运用linkage函数(内部为最短距离算法)生成具有层次结构的聚类树Z。Z=Iinkage(C)(6)
2.2动态规划法在路径优化中的应用
由于参与动态规划的节点个数受待拣储位数和聚类分析影响,此处以q(pq2p)作为动态规划节点数进行讨论。通过引入动态规划算法,可以将一个包含|N|个节点的旅行商问题转化成一个包含q个节点的动态规划问题和p个小型路径问题。必须注意两点:第一,当某类包含多个待拣储位时,其首末待拣储位都将作为动态规划节点,此时,为保证聚类结果不被破坏,需将这两节点的距离设为d(0
2.3CADP策略的子路径策略
得到相应的类序后,需进一步确定各类相应的子路径,下面就子路径策略进行介绍说明:以当前类的首个待拣储位所在巷道为当前巷道,最后一个待拣储位所在巷道为终止巷道。从首个待拣储位出发,依次拣取当前巷道的其余未拣储位,当前巷道拣取完毕后,从下一巷道中最小行编号和最大行编号待拣储位中选择一个与当前储位距离最短的一个作为下一个待拣储位,在拣取该储位后,依次拣取该巷道其余未拣储位(当拣取的是最小行编号的储位时,按从小到大的顺序;当选取的是最大行编号的储位时,按从大到小的顺序),按照以上规则拣取类内所有待拣储位。
3应用实例分析
由于拣货员使用的推车容量(或载重量)有限,本文以一单一车[21]的方式拣取处理后的拣货单,即拣货单中的全部商品可以由一辆推车往返一次从仓库中全部取走,不会出现超过推车的最大容量(或载重量)的情况。本文就双区型仓库和三区型仓库拣货路径问题进行研究,针对不同的仓库随机生成包括20、25、30、35和40个待拣储位拣货单5组(每组包含100个拣货单),每组订单分别运用Sshape策略、LargestGap策略、Combined策略、CADP策略和ACO算法生成路径,并对路径长度和生成路径所需时间进行比较分析。
4结语
拣货作业是订单处理作业的核心环节,也是仓库作业中耗时耗力最多的作业,提高拣货作业效率,优化拣货路径可以达到降低物流配送中心运营成本,提高物流作业效率和提高客户满意度的效果。一个良好的拣货路径策略不仅要考虑生成的路径长度,而且还要考虑生成路径消耗的时间。本文提出的基于聚类和动态规划的组合路径策略(CADP),通过聚类分析法将一个复杂的旅行商问题转化成几个相对简单的子路径问题,通过动态规划以最短的距离将这些子问题连接,实现了化繁为简的效果。
通过大量实验,可以得出结论:第一,在时间消耗很少的情况下,CADP策略生成的拣货路径长度明显优于以往的传统路径长度;在路径长度差距较小的情况下,CADP路径的生成时间明显短于ACO算法路径的生成时间。CADP策略实现了生成拣货路径所需时间与优化路径长度之间的平衡;第二,本文将CADP策略应用于三区型仓库,试验结果表明,该策略在在三区型仓库具有良好的适用性,扩大了以往以二区型仓库为主的适用环境。同时,本文对于拣货路径问题的研究还有许多值得继续研究的地方,接下来的研究主要从以下两个方向拓展:(1)如何将CADP策略与现代化的信息化技术相结合,实现在生成拣货路径后快速识别并拣取待拣商品,进一步提高拣货速度的目标。(2)关于CADP策略中聚类数量的进一步探究和对子路径策略的进一步优化。
转载请注明来自发表学术论文网:http://www.fbxslw.com/dzlw/22145.html