如何计算最短拣货路径,用于自动生成拣货波次?
修改需要考虑商品组合和货位间距两个维度,用什么算法合适?
作者:刘宇
来源:知乎
谢邀,好专业性的问题,只能按本人有限的知识面回答一下,而且,由于涉及高等数学一堆理论,我不能保证我举例的正确性,仅做方向性指导。如各位看官发现不对的地方,请理性指正。
你问的是根据货品属性和货位,计算最短路径的算法。然后,计算最短路径后,还要生成拣货波次,这几个问题细化后几乎涵盖了我所学的所有知识点。
首先,最优路径问题的算法介绍:
1.最基本的是离散数学中的图论:分无向图和有向图。然后通过矩阵变换求最优解某两点间的最短路径。
2.有了基本的图论概念后,可以尝试了解经典的数学理论:旅行商问题(Traveling Saleman Problem,TSP)。在仓库中从开始点出发,经过N个拣货点,最终到达交货区,可以视为一个TSP线路问题。对TSP问题解法大致可以分为以下8类:
1)线性规划方法
2)动态规划方法
3)分支定界算法
4)人工神经网络
5)人工神经网络?
6)禁忌搜索算法
7)蚁群算法
8)遗传算法
看到这里,如果还有兴趣深入了解的话,恭喜你,我会继续分析你的拣货波次的问题,向结果迈进:
3. 做过仓库的都应该了解“摘果法”和“播种法”这两种拣货方式,不懂自己百度去。
这里我将用“摘果法”波次拣货代入到“VRP”问题中,车辆路线问题(VRP)它是指一定数量的客户,各自有不同数量的货物需求,配送中心向客户提供货物,由一个车队负责分送货物,按适当的行车路线,目标是使得客户的需求得到满足,并能在一定的约束下,达到诸如路程最短、成本最小、耗费时间最少等目的。
对应到仓库中的 波次分配+拣货路径,假设为:订单量巨大,某几个订单合为一个波次,让拣货员按此波次沿最短路径拣货。
至此,我对此你的问题的一种假设推荐是:先根据订单量分波次,再排最优拣货路线。见下图示意:
解题思路:将车辆线路问题(VRP)转换成多个旅行商问题(TSP)进行求解。也就是说,在根据条件优化好本次拣货量后,再计算此次最优路径。
当然,你的这个TSP求解问题因为条件过于复杂,我们只能趋向于求到局部最优解(不知道你是否能理解,数学中不一定能求出一个唯一的答案,只能是特定条件下趋向于正确或最优)。
进阶算法:可以根据波次和最优路径进行建模计算出两者之间的最优解组合,这个是运筹学里东西。
作为一个IT人,我当然希望你甚至可以针对算法进行了计算机编程(以上提到的算法)求解,利用软件对真实的波次和货位进行随机需求量进行计算测试,以期得到理想的最优解。
以上,我也就在此瞎说说而已,期望听到您的好消息,一起交流提高^_^。
暂无评论