论文部分内容阅读
摘要:合理优化器材的拣选路径是提高自动化立体仓库作业效率的一种有效方法,通过分析自动化立体器材仓库的拣选特点,建立了比较符合实际情况的目标优化模型,在用传统节约算法对该模型进行求解的基础上,分析了传统节约算法的不足,并进行了改进,使得拣选次数更少、拣选距离更短。
关键词:自动化立体仓库;拣选路径;改进节约算法
中图分类号:E237文献标识码:A
Abstract: Optimizing the order picking is effective on advancing the working efficiency of automatic materials warehouse. According to the characters of picking working in automatic warehouse, a reasonable model was proposed. A classical saving method was presented to solve the model. But it has some limitations in application. The paper puts forward an improved method, which can resolve the materials picking problem with less times and less distance.
Key words: automatic warehouse; order picking; improved saving method
0引言
军械维修器材(以下简称器材)仓库是器材组织储备、管理的重要机构,是我军赖以完成各项战备、训练任务,进行军事作战的供应保障基地,是器材物流管理过程中的重要组成部分,随着现代化战争高效化的需要和科学技术的发展,自动化立体器材仓库逐渐出现在我军的器材仓库中。在器材收发作业过程中,拣选作业是其中非常重要的一个环节,占总作业时间的60%左右。可以说器材收发作业的效率严重受到拣选作业瓶颈的钳制。美国仓储教育和研究协会早在1986年就将拣选作业定为提高仓库运作效率的首要研究领域[1]。自动化立体器材库中,相邻两排货架间有一条巷道,每条巷道内有一台巷道车进出巷道进行器材取放,巷道车可同时沿巷道水平方向和垂直方向运动。调拨器材的货位、拣选的先后次序、周转货箱的容积等因素直接影响到拣选任务完成的时间、巷道车行走的距离以及循环拣选的次数。
目前国内外关于拣选路径优化问题的研究基本上都是基于一张调拨单、拣货品不超过周转货箱容量、一种物品只有一个拣取位置、每个货位只拣选一次等确定性条件[2-3],对于器材仓库来说器材种类繁多、一物多位、一位多物、一个货位分多次拣的等情况都有可能,文献中的方法不能完全套用,需要进一步改进。
1拣选作业的数学模型
假设:(1)货位间距为常数,h为货位高度,b为货位宽度,长度忽略不计。(2)器材外形规则,周转货箱装箱能力仅与待装器材体积有关。(3)器材摆放位置可视为货格的中心点上,货位坐标为x,y,表示位于第x层第y列。(4)货箱容积大于任一货位内器材的体积。
符号:x■,y■——第l次取货,第k步巷道车停留在货架的第x■层第y■列;Ai,j,m——货架第i层第j列第m种器材库存数量(已知);Bx■,y■,m——第l次取货,第k步拣选第m种器材的数量;d■——调拨单中需要调拨的第m种器材的数量(已知);v■——第m种器材的体积(已知);V■——货箱的容积(已知)。
假设巷道车在横向和纵向的速度是恒定的,影响拣选作业效率的主要因素就是巷道车行走距离的多少,所以优化的目标就是寻求一条最短的拣选路径。当拣选器材较多时,受拣货箱容积和承重的限制(对于小件器材一般只考虑货箱容积的限制),可能无法一次完成拣选作业,需要分多次进行,因此,巷道车在整个拣选作业过程中所行走的距离就是进行每一次拣选路径的距离之和。
目标函数:
S=min■S■=min■■x■-x■b+y■-y■h (1)
式(1)中,S代表巷道车行走的最短距离,S■表示第l次取货时,巷道车所走的距离,x■-x■b表示巷道车第l次第k步取货,由货位x■,y■移动到货位x■,y■时横向行走的距离,同理y■-y■h表示纵向的行走距离。由于巷道车一般有两个电机驱动,一个负责横向移动,另外一个负责纵向移动,所以这里认为巷道车行走的距离就是巷道车在横向和纵向行走的距离之和。
约束条件:
每次拣选的器材体积之和小于等于货箱的容积,即:
■Bx■,y■,mv■≤V■(2)
拣选第m种器材的数量之和等于调拨单中第m种器材的数量,即:
■■Bx■,y■,m=d■(3)
对第i层第j列拣选的第m种器材的数量小于等于该货位上存放的第m种的数量,即:
■■Bi,j,m≤Ai,j,m (4)
货架存放的第m种器材的数量大于等于调拨单中该种器材的数量,即:
■■Ai,j,m≥d■(5)
2节约算法求解
拣选路径最优问题,已被证明是NP-难问题[2],精确算法的计算量太大,一般采用近似算法或启发式算法,节约算法是一种常见的启发式算法,由于它简单实用在配送领域的路线规划上被广泛应用,本文将其引入到器材拣选作业中,以求得路径优化的满意解(不一定是最优解)。
2.1节约量公式
设巷道口为P■,N个货位分别是P■,P■,…,P■,已知其中任意两个货位P■和P■之间的距离为d■d■=x■-x■b+y■-y■h,x■,y■、x■,y■分别为P■和P■的坐标。从巷道口开始拣选货位P■和P■,有两种方案,一是一次性完成两个货位的拣选后回到巷道口,二是往返两次分别拣选这两个货位,前者比后者行走距离的节约量为:
D■=d■+d■-d■=x■+x■b+y■+y■h-x■-x■b+y■-y■h=2minx■,x■b+miny■,y■h (6)
式(6)就是著名的节约量公式。由推导结果可知,D■≥0。
2.2节约算法的思路
由于同一种器材可能存放于多个货位,入库年份也可能不同,如果随机拣选,入库较早的器材可能一直不被拣选到,随时间推移,器材过了保质期就难免报废,造成浪费。所以,首先要根据“先进先出”(或“用旧存新”)原则及式(3)确定好待拣货位及数量,其次是将所有待拣货位两两组对,并计算其行走距离节约量,将节约量按由大到小顺序排列,选择节约量最大的两个货位,判断这两个货位待拣器材体积之和是否超过货箱的容积,如果不超过货箱的容积,则将这两个货位合并为一次拣选,如果超过货箱的容积,则不合并这两个货位,转而判断节约量稍小的另两个货位能否合并为一次拣选。直到所有可能合并为一次拣选的货位全部合并,最终得到巷道车行走距离优化的满意解。节约算法流程如图1所示。
根据节约算法,3算例分析中的算例可得最终的拣选路线(见表4)为:r■=0→16→17→7→5→0;r■
=0→8→15→6→0;r■=0→4→14→11→0;r■=0→2→3→0;r■=0→12→13→9→10→0;r■=0→1→0。可以看出一共分6次拣选,巷道车行走总距离为534米。
2.3节约算法的不足及改进
由3算例分析中的计算过程可以看出节约算法应用在器材拣选中还存在一些缺陷,需要改进。一是每个货位内的待拣器材数量不允许分割必须一次性拣完,这可能导致货箱不能装满,影响货箱容积的利用率,从而使拣选次数增加;二是每次拣选路线,货位都是按节约量的大小和货位序号进行排列的,货位的前后左右的位置可能较乱,造成巷道车在一次拣选过程中往复行走,使得行走距离增加,如算例中第1次拣选路线:r■
=0→16→17→7→5→0,巷道车行走的距离为178米,如果按照0→7→17→16→5→0顺序拣选,则巷道车行走的距离为166米。所以需要对以上两点不足进行改进。
针对货位存放的待拣器材数量不能分割问题,本文提出以下改进思路:将待拣货位两两组合,并计算其节约量,选择节约量最大的两个货位:①如果它们存放的待拣器材体积之和小于货箱容积,则合并它们一次拣选,并进一步寻找与这两个货位之一合并带来最大节约量的货位,把这个货位也合并到当前次拣选路线上,直到该线路上待拣器材的体积之和等于或大于货箱容积,合并最后一个货位使得货箱刚好满载或不能再装其他器材。②如果这两个货位器材体积之和等于货箱的容积,则合并它们在一条线路上拣选。③如果这两个货位器材体积之和大于货箱容积,则合并它们在一条线路上拣选,并使货箱满载或不能再装其他器材,将剩余的器材和其他待拣货位组成一个新的拣选决策问题,重复上述方法,直到所有货位全部被合并。
针对巷道车在一次拣选过程可能多次往复问题,本文提出以下改进方法:对于M层N列的固定货架,令r为不大于M/2的最大整数;将1~r层货位按列号从小到大排序;将r+1~M层货位按列号从大到小排序;在每一次拣选过程中先拣选1~r层货位再拣选r+1~M层货位,则可避免巷道车往复问题。
改进的节约算法相比传统的节约算法:一是允许货位存放的待拣器材分多次拣选,提高货箱利用率;二是将每一次要拣选的货位进行排序,避免巷道车多次往复,减少其行走的距离。改进的节约算法具体流程如图2所示。
按改进的节约算法,再计算3算例分析中的实例,如表5所示,可得以下拣选路线:
r■=0→8→7→17→16→0;r■=0→15→8→5→4→0;r■=0→6→4→14→11→12→13→0;r■
=0→3→2→13→0;r■=0→1→13→9→10→0,共分5次拣选,巷道车行走的总距离为492米。
3算例分析
自动化立体器材仓库某一巷道货架共10行(层)72列,货位高和宽均为1m,货箱容积为20dm3,根据器材调拨单要拣选5种器材,随机产生调拨单和器材货位对照表如表1所示(为简化计算这里认为器材体积可直接相加)。要求制定拣选计划,使得拣选距离最短。
3.1确定待拣货位
根据“先进先出”原则和调拨单数量要求,可确定以下待拣货位及数量如表2所示。
3.2计算节约量
将待拣货位两两组对,计算距离节约量如表3所示。
3.3节约算法求解
按照图1所示的节约算法流程及已确定的待拣货位和数量,可得表4所示决策结果(具体步骤略)。
3.4改进节约算法求解
利用改进节约算法进行求解,具体步骤如下。
(1)选择节约量最大的16、17货位,器材体积为1×4+1×4=8,拣货箱未装满,在与货位16和货位17有关的组合中查找最大节约量为16、7货位(或16、8,17、7,17、8),将货位7加入当前拣选序列,此时器材体积为8+2×3=14,拣货箱仍未装满,在货位16、17、7有关的组合中查找最大节约量为16、8货位,将货位8加入当前拣选序列,此时拣货箱只能再拣选货位8内2个器材就装满,巷道车返回巷道口,此时货位8还剩余1个器材等待拣选。这样可以确定第一次拣选的货位(数量)为72、82、161、171。
(2)将已经拣选完成的货位7、16、17从待拣选货位中删除,重复步骤(1),此时应注意货位8内器材数量为1,应保留与剩余的待拣货位组成新的拣选决策问题,按照(1)中的步骤进行,直至所有待拣货位全部合并,可以确定第二次拣选的货位(数量)为45、54、81、152;第三次为41、63、112、121、131、146;第四次为25、34、132;第五次为13、92、101、133。
(3)对每次拣选的货位进行排序,由题知r=?骔10/2」=5,1~5行按列号从小到大排列先拣选,6~10行按列号从大到小排列后拣选。第一次拣选货位排序为8、7、17、16;第二次拣选货位排序为15、8、5、4;第三次拣选货位排序为6、4、14、11、12、13;第四次拣选货位排序为3、2、13;第五次拣选货位排序为1,13,9,10。
经过以上三步分析计算,可得拣选决策结果,如表5所示。
3.5结果分析
由计算结果可以看出,在拣选作业决策上,利用改进节约式算法比传统的节约算法更能减少拣选次数和巷道车的行走距离,说明在拣选作业中利用改进的节约式算法方法是可行和正确的。
4结论
本文首先建立了的器材拣选作业的路径优化模型,利用传统节约算法计进行货位拣选的安排决策,分析了传统节约算法用于器材拣选作业中存在的不足,并针对两点不足进行了改进,使得拣选次数更少,拣选行走距离更短,为自动化立体器材仓库的拣选优化问题提供了一种新的思路。
参考文献:
[1] 李诗珍. 配送中心拣货作业优化设计与控制研究[D]. 成都:西南交通大学(博士学位论文),2008:2-4.
[2] 常发亮,刘増晓,辛征,等. 自动化立体仓库拣选作业路径优化问题研究[J]. 系统工程理论与实践,2007(2):139-143.
[3] 于洁,苏志忠,孙燕飞. 蚁群算法在拣货路径优化中的应用研究[J]. 电脑知识与技术,2008(4):466-467.
[4] 陈一永,许力. C-K节约算法在配载车辆调度问题上的应用研究[J]. 商场现代化,2009(562):149.
关键词:自动化立体仓库;拣选路径;改进节约算法
中图分类号:E237文献标识码:A
Abstract: Optimizing the order picking is effective on advancing the working efficiency of automatic materials warehouse. According to the characters of picking working in automatic warehouse, a reasonable model was proposed. A classical saving method was presented to solve the model. But it has some limitations in application. The paper puts forward an improved method, which can resolve the materials picking problem with less times and less distance.
Key words: automatic warehouse; order picking; improved saving method
0引言
军械维修器材(以下简称器材)仓库是器材组织储备、管理的重要机构,是我军赖以完成各项战备、训练任务,进行军事作战的供应保障基地,是器材物流管理过程中的重要组成部分,随着现代化战争高效化的需要和科学技术的发展,自动化立体器材仓库逐渐出现在我军的器材仓库中。在器材收发作业过程中,拣选作业是其中非常重要的一个环节,占总作业时间的60%左右。可以说器材收发作业的效率严重受到拣选作业瓶颈的钳制。美国仓储教育和研究协会早在1986年就将拣选作业定为提高仓库运作效率的首要研究领域[1]。自动化立体器材库中,相邻两排货架间有一条巷道,每条巷道内有一台巷道车进出巷道进行器材取放,巷道车可同时沿巷道水平方向和垂直方向运动。调拨器材的货位、拣选的先后次序、周转货箱的容积等因素直接影响到拣选任务完成的时间、巷道车行走的距离以及循环拣选的次数。
目前国内外关于拣选路径优化问题的研究基本上都是基于一张调拨单、拣货品不超过周转货箱容量、一种物品只有一个拣取位置、每个货位只拣选一次等确定性条件[2-3],对于器材仓库来说器材种类繁多、一物多位、一位多物、一个货位分多次拣的等情况都有可能,文献中的方法不能完全套用,需要进一步改进。
1拣选作业的数学模型
假设:(1)货位间距为常数,h为货位高度,b为货位宽度,长度忽略不计。(2)器材外形规则,周转货箱装箱能力仅与待装器材体积有关。(3)器材摆放位置可视为货格的中心点上,货位坐标为x,y,表示位于第x层第y列。(4)货箱容积大于任一货位内器材的体积。
符号:x■,y■——第l次取货,第k步巷道车停留在货架的第x■层第y■列;Ai,j,m——货架第i层第j列第m种器材库存数量(已知);Bx■,y■,m——第l次取货,第k步拣选第m种器材的数量;d■——调拨单中需要调拨的第m种器材的数量(已知);v■——第m种器材的体积(已知);V■——货箱的容积(已知)。
假设巷道车在横向和纵向的速度是恒定的,影响拣选作业效率的主要因素就是巷道车行走距离的多少,所以优化的目标就是寻求一条最短的拣选路径。当拣选器材较多时,受拣货箱容积和承重的限制(对于小件器材一般只考虑货箱容积的限制),可能无法一次完成拣选作业,需要分多次进行,因此,巷道车在整个拣选作业过程中所行走的距离就是进行每一次拣选路径的距离之和。
目标函数:
S=min■S■=min■■x■-x■b+y■-y■h (1)
式(1)中,S代表巷道车行走的最短距离,S■表示第l次取货时,巷道车所走的距离,x■-x■b表示巷道车第l次第k步取货,由货位x■,y■移动到货位x■,y■时横向行走的距离,同理y■-y■h表示纵向的行走距离。由于巷道车一般有两个电机驱动,一个负责横向移动,另外一个负责纵向移动,所以这里认为巷道车行走的距离就是巷道车在横向和纵向行走的距离之和。
约束条件:
每次拣选的器材体积之和小于等于货箱的容积,即:
■Bx■,y■,mv■≤V■(2)
拣选第m种器材的数量之和等于调拨单中第m种器材的数量,即:
■■Bx■,y■,m=d■(3)
对第i层第j列拣选的第m种器材的数量小于等于该货位上存放的第m种的数量,即:
■■Bi,j,m≤Ai,j,m (4)
货架存放的第m种器材的数量大于等于调拨单中该种器材的数量,即:
■■Ai,j,m≥d■(5)
2节约算法求解
拣选路径最优问题,已被证明是NP-难问题[2],精确算法的计算量太大,一般采用近似算法或启发式算法,节约算法是一种常见的启发式算法,由于它简单实用在配送领域的路线规划上被广泛应用,本文将其引入到器材拣选作业中,以求得路径优化的满意解(不一定是最优解)。
2.1节约量公式
设巷道口为P■,N个货位分别是P■,P■,…,P■,已知其中任意两个货位P■和P■之间的距离为d■d■=x■-x■b+y■-y■h,x■,y■、x■,y■分别为P■和P■的坐标。从巷道口开始拣选货位P■和P■,有两种方案,一是一次性完成两个货位的拣选后回到巷道口,二是往返两次分别拣选这两个货位,前者比后者行走距离的节约量为:
D■=d■+d■-d■=x■+x■b+y■+y■h-x■-x■b+y■-y■h=2minx■,x■b+miny■,y■h (6)
式(6)就是著名的节约量公式。由推导结果可知,D■≥0。
2.2节约算法的思路
由于同一种器材可能存放于多个货位,入库年份也可能不同,如果随机拣选,入库较早的器材可能一直不被拣选到,随时间推移,器材过了保质期就难免报废,造成浪费。所以,首先要根据“先进先出”(或“用旧存新”)原则及式(3)确定好待拣货位及数量,其次是将所有待拣货位两两组对,并计算其行走距离节约量,将节约量按由大到小顺序排列,选择节约量最大的两个货位,判断这两个货位待拣器材体积之和是否超过货箱的容积,如果不超过货箱的容积,则将这两个货位合并为一次拣选,如果超过货箱的容积,则不合并这两个货位,转而判断节约量稍小的另两个货位能否合并为一次拣选。直到所有可能合并为一次拣选的货位全部合并,最终得到巷道车行走距离优化的满意解。节约算法流程如图1所示。
根据节约算法,3算例分析中的算例可得最终的拣选路线(见表4)为:r■=0→16→17→7→5→0;r■
=0→8→15→6→0;r■=0→4→14→11→0;r■=0→2→3→0;r■=0→12→13→9→10→0;r■=0→1→0。可以看出一共分6次拣选,巷道车行走总距离为534米。
2.3节约算法的不足及改进
由3算例分析中的计算过程可以看出节约算法应用在器材拣选中还存在一些缺陷,需要改进。一是每个货位内的待拣器材数量不允许分割必须一次性拣完,这可能导致货箱不能装满,影响货箱容积的利用率,从而使拣选次数增加;二是每次拣选路线,货位都是按节约量的大小和货位序号进行排列的,货位的前后左右的位置可能较乱,造成巷道车在一次拣选过程中往复行走,使得行走距离增加,如算例中第1次拣选路线:r■
=0→16→17→7→5→0,巷道车行走的距离为178米,如果按照0→7→17→16→5→0顺序拣选,则巷道车行走的距离为166米。所以需要对以上两点不足进行改进。
针对货位存放的待拣器材数量不能分割问题,本文提出以下改进思路:将待拣货位两两组合,并计算其节约量,选择节约量最大的两个货位:①如果它们存放的待拣器材体积之和小于货箱容积,则合并它们一次拣选,并进一步寻找与这两个货位之一合并带来最大节约量的货位,把这个货位也合并到当前次拣选路线上,直到该线路上待拣器材的体积之和等于或大于货箱容积,合并最后一个货位使得货箱刚好满载或不能再装其他器材。②如果这两个货位器材体积之和等于货箱的容积,则合并它们在一条线路上拣选。③如果这两个货位器材体积之和大于货箱容积,则合并它们在一条线路上拣选,并使货箱满载或不能再装其他器材,将剩余的器材和其他待拣货位组成一个新的拣选决策问题,重复上述方法,直到所有货位全部被合并。
针对巷道车在一次拣选过程可能多次往复问题,本文提出以下改进方法:对于M层N列的固定货架,令r为不大于M/2的最大整数;将1~r层货位按列号从小到大排序;将r+1~M层货位按列号从大到小排序;在每一次拣选过程中先拣选1~r层货位再拣选r+1~M层货位,则可避免巷道车往复问题。
改进的节约算法相比传统的节约算法:一是允许货位存放的待拣器材分多次拣选,提高货箱利用率;二是将每一次要拣选的货位进行排序,避免巷道车多次往复,减少其行走的距离。改进的节约算法具体流程如图2所示。
按改进的节约算法,再计算3算例分析中的实例,如表5所示,可得以下拣选路线:
r■=0→8→7→17→16→0;r■=0→15→8→5→4→0;r■=0→6→4→14→11→12→13→0;r■
=0→3→2→13→0;r■=0→1→13→9→10→0,共分5次拣选,巷道车行走的总距离为492米。
3算例分析
自动化立体器材仓库某一巷道货架共10行(层)72列,货位高和宽均为1m,货箱容积为20dm3,根据器材调拨单要拣选5种器材,随机产生调拨单和器材货位对照表如表1所示(为简化计算这里认为器材体积可直接相加)。要求制定拣选计划,使得拣选距离最短。
3.1确定待拣货位
根据“先进先出”原则和调拨单数量要求,可确定以下待拣货位及数量如表2所示。
3.2计算节约量
将待拣货位两两组对,计算距离节约量如表3所示。
3.3节约算法求解
按照图1所示的节约算法流程及已确定的待拣货位和数量,可得表4所示决策结果(具体步骤略)。
3.4改进节约算法求解
利用改进节约算法进行求解,具体步骤如下。
(1)选择节约量最大的16、17货位,器材体积为1×4+1×4=8,拣货箱未装满,在与货位16和货位17有关的组合中查找最大节约量为16、7货位(或16、8,17、7,17、8),将货位7加入当前拣选序列,此时器材体积为8+2×3=14,拣货箱仍未装满,在货位16、17、7有关的组合中查找最大节约量为16、8货位,将货位8加入当前拣选序列,此时拣货箱只能再拣选货位8内2个器材就装满,巷道车返回巷道口,此时货位8还剩余1个器材等待拣选。这样可以确定第一次拣选的货位(数量)为72、82、161、171。
(2)将已经拣选完成的货位7、16、17从待拣选货位中删除,重复步骤(1),此时应注意货位8内器材数量为1,应保留与剩余的待拣货位组成新的拣选决策问题,按照(1)中的步骤进行,直至所有待拣货位全部合并,可以确定第二次拣选的货位(数量)为45、54、81、152;第三次为41、63、112、121、131、146;第四次为25、34、132;第五次为13、92、101、133。
(3)对每次拣选的货位进行排序,由题知r=?骔10/2」=5,1~5行按列号从小到大排列先拣选,6~10行按列号从大到小排列后拣选。第一次拣选货位排序为8、7、17、16;第二次拣选货位排序为15、8、5、4;第三次拣选货位排序为6、4、14、11、12、13;第四次拣选货位排序为3、2、13;第五次拣选货位排序为1,13,9,10。
经过以上三步分析计算,可得拣选决策结果,如表5所示。
3.5结果分析
由计算结果可以看出,在拣选作业决策上,利用改进节约式算法比传统的节约算法更能减少拣选次数和巷道车的行走距离,说明在拣选作业中利用改进的节约式算法方法是可行和正确的。
4结论
本文首先建立了的器材拣选作业的路径优化模型,利用传统节约算法计进行货位拣选的安排决策,分析了传统节约算法用于器材拣选作业中存在的不足,并针对两点不足进行了改进,使得拣选次数更少,拣选行走距离更短,为自动化立体器材仓库的拣选优化问题提供了一种新的思路。
参考文献:
[1] 李诗珍. 配送中心拣货作业优化设计与控制研究[D]. 成都:西南交通大学(博士学位论文),2008:2-4.
[2] 常发亮,刘増晓,辛征,等. 自动化立体仓库拣选作业路径优化问题研究[J]. 系统工程理论与实践,2007(2):139-143.
[3] 于洁,苏志忠,孙燕飞. 蚁群算法在拣货路径优化中的应用研究[J]. 电脑知识与技术,2008(4):466-467.
[4] 陈一永,许力. C-K节约算法在配载车辆调度问题上的应用研究[J]. 商场现代化,2009(562):149.