现在位置: 首页 > 物流那些事 > 仓配 > 云仓 > 正文

拣选路径优化,怎样的算法是最合理的?

投稿人:  浏览: 4,700 次
5年前 (2019-09-11) 沙发

计算最优拣选路径需要让电脑明白仓库任何两个位置之间的最短距离(同时也跟行走路线是一致的)。我们所知道的仓库管理系统没有能管理一个明确的仓库几何布局数据模型,所以真正的拣选路径最优化当前并未实现。

最终仓库管理系统将拥有仓库的几何布局数据模型,并且电信通讯技术的发展使得可以更经济也更简单的给拣选员精确地行走指,然后将没有理由不去利用最优化拣选路径。

最优化拣选路径的基础结果应归于Ratliff & Rosenthal,他们给出了一个用于快速寻找仓库里货位集最短路线的算法。我们将通过他们算法的一个简化版本来阐述他们的思想,将生成近似最优拣选路径。该简化对允许的行走模式有所限制,拣选员被禁止重新到访之前已到访过的巷道。也就是说,我将找到服从约束的最短拣选路径,即不能超出巷道的自然排序的到访。因为这个限制建议的路径可能稍微比未约束的最佳效果要长些。但是:

这个算法和最佳查找算法的原理是一样的,但更简单并因此更容易编程实现和被人接受。

由非原路返回的限制所产生的不必要行走距离通常很小。

所生成的路径比最佳路径在结构上更简单,同时订单拣选员也更容易理解和接受。

下列我们通过动态编程生成一个拣选路径,这利用了一个事实,即最佳路径可以假设在每个巷道的末端只有有限的模式。我们的限制即拣选员不能重复到访一个巷道,可能的模式数量减少成只有两种,因此每个订单拣选员可被想像为遵守下面的规则。

从当前的巷道拣选所有的条目,再走向下一个巷道。

注意有两种方法走到下一个巷道:订单拣选员可以行走全程穿过当前巷道,按需要拣选;或者也可以进入巷道只根据需要尽可能在其中拣选所有要求的项目,然后再回到和进入巷道相同的巷道的末端。

拣选路径优化,怎样的算法是最合理的?

图1:在左边到访货位,设想一个决策点在每个巷道的末端。因为原路退回是禁的,订单拣选员必须到访巷道i+1之前到访巷道i。

如图1中所建议的决策点在每条巷道的末端,因为有非原路退回,拣选员必须从左到到行走穿过仓库,由此我们能够序列地考虑在每个巷道作出的决策。我们可以图形化地总结如同图10.9开始的一系列数字所做决策的顺序。

图6展示了最终图形总结的由订单拣选员做出的决策序列。图中的最短路径

依据通过仓库的有效拣选路径得来。(可以通过图论或离散数学的初级算法找出最短路径,参照附录C的解释)

拣选路径优化,怎样的算法是最合理的?

图2:从巷道1到巷道2路径的列举和总结。每个候选的路径被图中相同长度的边长所代表。

拣选路径优化,怎样的算法是最合理的?

图3:从巷道2到巷道3路径的列举和总结

拣选路径优化,怎样的算法是最合理的?

图4:从巷道3到巷道4路径的列举和总结

拣选路径优化,怎样的算法是最合理的?

图5:从巷道4到结束路径的列举和总结

拣选路径优化,怎样的算法是最合理的?

图6:关联图上的最短路径给出了仓库的一个有效拣选路径

拣选路径优化,怎样的算法是最合理的?

图7:只有沿图的每侧边线的长度需要更新响应出新的客户订单

注意网络的连结点只需要建立一次,随后使用只需要更新边线长度,如图7所示。这个方法可自然地推广到处理新增的穿过的巷道,然而解决的工作快速地增加。

来源:互联网
本文由物流报(www.56tim.com)平台用户攥写或转载并发布,转载目的在于传递更多信息,物流报仅提供信息发布平台。文章内容仅代表本文作者或原作者个人观点,不代表物流报立场。转载需注明来源及作者姓名。如内容(包含图片、视频、音频、文字)侵犯到您的权益,请来邮告知,并提供相关证明,经本平台核实后立即删除。E-mail:zhoulh@56tim.com

发表评论

邮箱地址不会被公开。