语言选择:中文 | English
快速导航
 
新闻中心当前位置:网站首页 >> 新闻中心

双旋转货架管拣货路径优化策略

浏览率: 发布时间:2014-04-15 22:14:49

 

 
 
 
 
【摘要】讨论了由一个拣货员负责的双旋转货架管系统,考虑栋货员每次拣取货物所需时间不同,目标是 寻找一种最优拣货顺序使得总拣货时间最小。该问题被证明为强NP-难问题,提出了几种启发式算法寻找 最优拣货顺序,并对相关模型及算法进行模拟测试以证明其有效性,为方法选择与应用提供了依据。
 
关键词:旋转货架管;拣货;启发式算法 
 
水平旋转货架管是一种常见的自动化旋转货架管, 有单旋转方向和双旋转方向旋转的2种不同的货架管
 
选品项更快到达拣货点。本文所考虑由1个拣货员 负责的双旋转货架管系统,2个货架管系统配置相同,货 架为双方向旋转,既可以顺时针旋转又可以逆时针 旋转。设该货架管系统为一维方向,即只考虑水平方 向待拣选品项之间的距离,垂直方向之间的距离忽 略不计,若垂直方向有多个品项待拣选,视为一个待 拣选点。这样考虑主要是因为,拣货员或拣货设备 在垂直方向上的速度远远大于旋转货架管水平旋转的 速度,可以忽略不计。同时假设当某一订单拣选完 后,旋转货架管即停在最后拣选的品项位置处,而不是固定停留在某个点处。
 
对旋转货架管的研究分为存储策略[19]和拣货优 化策略[1M5]2类。多数文献集中于讨论单旋转货架管 系统,对于多旋转货架管系统的研究较少[16_17],对双旋 转货架管问题,Hassini等[18]研究了由1个拣货员负 责2个旋转货架管的双旋转货架管系统的存储策略,并 提出一些启发式算法。寸论了单个拣货 员负责的双旋转货架管系统,拣货员轮流在两货架管中 拣选时的拣货效率。本文针对双旋转拣货系统,讨 论拣取时间不可忽略时的拣选路径优化算法。
 
1问题描述及相关假设
 
双旋转货架管如图1所示,拣货系统为由1个拣 货员负责2个相同的水平旋转货架管中品项的拣选, 拣货员在两货架管间来回穿梭以拣选订单要求的品 项。假设一个订单中共有m个品项存放在双旋转 货架管中,本文的目标是确定一拣货顺序使得拣货时 间最小化。显然,该问题不同于单旋转货架管系统,订 单中品项的拣货顺序将对拣货员在两货架管间的行走 时间、货架管旋转时间及拣货员的等待时间造成影响, 改变订单中各个品项的拣选顺序,将对应不同的拣 货路径,不同的拣货路径所对应的拣货作业时间将 不同。在双旋转货架管系统中,需要考虑如何安排品 项的存放及拣选次序(拣货路径规划问题),使得拣 货作业时间最短以提高拣货作业效率及配送中心整 体运行效益。
图1双旋转货架管拣选系统
因此,可将双旋转货架管拣货路径优化问题描述 为:给定w个待拣选货位点,在可行解集合F={m 个待拣选货位点的所有排列}中找出一条排列e F,使得对一切& F有£_(</)<“&),其中,排列 </称为该问题的最优解。
 
系统其他相关假设:
 
(1)两货架管的旋转速度相同且恒定,忽略加、减速度。
 
(2)每次拣选品项数量不会超过拣货员的可承 载量。品项均衡分布在两货架管中,每个货架管有多个 待栋选品项。
 
(3)拣货作业按订单到达顺序进行拣选,即遵 守先到先拣选的原则。拣货员或拣货设备在每一货 架拣选点拣选品项的时间为恒定常量,不会因为存 取顺序的改变而变化。
 
(4)拣货作业为按订单拣选,订单不进行分批, 拣货员每次只负责拣选一张订单,货架管有无限订单 需求,即一直有订单需要拣货员拣选。同时,客户订 单需求在一次拣货作业中执行完毕,不能分割,即拣 货员中途不能进行下一订单的拣货作业。
 
(5)待拣选品项为确定值,即在拣货作业开始 之前,已经确定了待拣选品项的数量及在货架管中储 位的分布。不允许缺货发生。
 
2拣货优化目标及算法设计
 
2.1相关参数
 
„一每个货架管货柜列数,每个货柜宽为丨个单位 mt—货架管k中包含的订单品项数,6 = 1,2, mi 十=m {[1],[2],…,[m]}—订单需求品项的可行 拣货顺序,其中,[_;]为拣货员第J次拣选的 品项
 
Utj 一表7K栋货员从品项i所在货架管彳了走到品 项^所在货架管需要的行走时间 —表示同一货架管中,由品项〖所在货柜在拣 货台前旋转到品项J所在货柜位于拣货 台前所需时间 a,,々.)一二维坐标,横坐标\表示品项)所在 的货架管号4表示品项7所在货架管中的 货柜号,t = l,2,l<Kn Lj * (々)]一表7K品项[)]执行前,第k个货架管最 后被执行的品项 —第L/]次拣选品项所需的拣取时间,即拣 货员在某一货位处开始拣选品项起到拣 货员拣选完该位置处的品项可以离开以 拣选下一品项(该品项与当前拣选的品项 不在同一货位)之间的时间,即拣取时间 包括一个货位处拣选多件品项所需花费 的时间
 
拣选完第D+]个品项到第D]个品项拣选 完所需的时间 r一拣货员在两货架管之间移动所用时间 ^ 一旋转一个货柜所需时间,考虑在实践中拣 货员在两货架管之间移动所用的时间往往大 于旋转一个货柜所需时间,在此将v与r 做归一化处理,令i=1,t>12.3算法设计
 
从上述分析可知在拣选过程中,品项位置坐标 (相对于拣选点)是动态变化的,拣取时间的长度影 响着等待时间的长度,使总作业时间随着拣选品项
顺序的不同而变化。此时,寻找双旋转货架管最优拣 货排列是一个特殊的TSP问题,属于NP-难 题[2°],可以采用传统方法即实践中常用的方法找到 可行解,但该解质量较差。在此,本文设计并比较了 几种启发式算法寻求较优解。算法设计过程中系统 环境为订单为按单拣选作业,拣货员(或拣货设备) 从集货点出发拣选完订单所有需求品项后才返回集 货点。
 
 
版权所有 © 2011 佛山压花管,货架管,异形管台脚,异形家具不锈钢管-美华不锈钢
(门市地址):佛山市顺德区陈村镇力源金属物流城H区10座11-15号        (工厂地址):佛山市顺德区陈村大都工业区
电话:0757 - 83311606 / 83312484        传真:0757 - 83313685        联系 :蔡小姐~13702908402

友情链接:卷闸机械 门框机 仙庙烧鸡 仙庙烧鸡加盟 卷闸机械 货架管 仙庙烧鸡 佛山卷闸门 拉闸门 不锈钢拉闸门 水晶闸 通花闸 佛山振动盘 佛山振动盘厂家