2023年7月30日发(作者：)

如何规划设计物流配送最短路径思考（⼀）以下⽂章来源于实践笔记 ，作者荡漾哥在城市配送中或者快递员送货，都会存在⼀个问题，怎么跑路径最短。当然现实中送货都是靠司机的经验，或者看下地图⼤概就知道怎么跑了，没有⼈真的去算路径是不是最短。但是从物流管理者⾓度，还是有必须知道逻辑，这样才能合理决策。今天先分享下单环模型（TSP），即就⼀辆车刚好装满，⼀辆车出去跑多个点送货，然后再回到起点。现实中更多是多辆车出发跑不同的点，即多环模型（VRP），多环模型出来后，具体到单个司机还是得⽤单环模型来设计路线。在如何设计距离最短，有个著名的原理⼤家⼀定要先懂，这个初中的时候都学过：三⾓形两边之和⼤于第三边。这个很好理解，因为已经是我们的常识了。但是⽴马想到跟最短路径关系，还是有点难度。我们做个简单的例⼦：从仓库出发送2-3个客户，然后回仓库。如下图：我们做个简单的判断：路径不能有交叉，交叉会产⽣三⾓形，就会存在两边之和⼤于第三边，即路径不是最短。我们把上⾯的判断当成⼀个原则，即要路径最短必须遵守这个原则。接下来再想想如何路径最短。⽬前流⾏的最简单算法是最近邻点法，这个算法很容易接受，也很容易感觉是对的（⼩编⼀段时间都觉得这个⽅法很好），但是不⼀定对的。它的做法就是从仓出发，先到最近的点，下⼀步判断还是最近的点，以此类推。就会给⼈⼀种每⼀步决策都是最短路径，所以加起来就是最短路径。但是，这结论实际有2个疑点：①每⼀步最短全程就是最短吗？②即使①是最短，最后⼀步回仓路径加进去也是最短吗？下⾯我们举例证明。我们可以随机画画⼀些点，⾃⼰画线串点就容易发现，以上不⼀定对。如下。从证明过程可以看出。最近邻点法，前⾯每⼀段都是最短不⼀定全程是最短的，它违背了上⾯所说的原则： 路径规划不能有交叉，否则就不是最短 。以上提供了2种案例，⽽这2种案例在现实中概率也挺⼤的。另外，最近邻点法还存在⼀个问题，就是当在⼀个点上，出现多个同样距离的点，如何做选择？以上，只是⼩编在⽤最近邻点法的时候发现的⼏个特例。⽬前关于最短路径的算法很多（Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法等都是听起来很⾼⼤上的算法，但是都没有找到能⽤简单的数学说明清楚的，也可能是我⾃⼰没有找到），⼤部分都是⾼等的数学计算，所以最近邻点法还是⽐较适合多数⼈简单的规划路径。那么具体如何操作呢？⼀、做个简单的各点相互之间的⾥程表。如下图：⼆、画个简单的坐标图（地图）更直观看到各点位置三、先随机画⼏种⽅案第1种就是⽤最近邻点法来画的是40步，第3张图是38步更短。这个只是⼩编随机画⼏个，看能否找到规律，结果证明最近邻点法还是不奏效。最近邻点法还是不奏效。四、解决⽅案设想⼀通过上图⼩编想了是否能画出的图的⾯积表⽰路径最短，这个好像计算更复杂，也不好数据证明这个猜想是对的（但是是否⽤直观感觉图3的⾯积更⼩，你⽤所有外围的点看成⼀个⾯积，这个是同样的⼤⼩，减去凹进去部分⾯积，凹进去⾯积⼤就说明画图的⾯积⼩）。五、解决⽅案设想⼆先把仓以外的所有点连成⼀个环，这个最短路径的步数肯定得⼤于这个周长步数，因为仓肯定得先到⼀个点，再从隔壁的⼀个点回去，这样他们的路径肯定⼤于这2个点的距离。那么接就就得算⼀个值，如果仓与相邻的2个点之间距离和减去这2个点之间的距离得出的值最⼩，说明是最短路径。这样就得再制作⼀个表格出来，才能快速看到这个结果。根据上述的猜测得出的2个线路图都是40步，其中⼀个跟最近邻点法结果⼀样。说明这个⽅案假设还是有不⾜之处，⽆法得出最短路径。但是这个逻辑上感觉还是能讲得通的，为什么不是最短？需要再验证下输⼊的条件是否对，逻辑是否对。①先说条件⼀：我画的36步的外环是不是最少步数的外环（这个证明要跟题⽬⼀样了）②条件⼆，再对⽐38步的那个图会发现，我们要移动框框的步数跟现实的直线算距离不⼀样，从38步图可以看出仓到F加上仓到H的距离是等于F和H的距离，所以才会出现这个图是最短（⼩编为了好体现距离，⽤了推箱⼦的步数来代替）。所以转了⼀圈感觉没有得出什么。这个逻辑的前提是我能知道不含仓的环是最短的，如果把其中的点当成仓就直接可以画出最短路径了。我把我要证明的东西当成前提了，然后再证明怎么做能得出它。五、解决⽅案设想三将错就错，为什么在解决⽅案假设⼆的时候我会感觉⾃⼰找到对的⽅法，因为常识不是逻辑，感觉很容易就可以画出⼀个圈，就是他们该有的距离（最短的圈）。如果我随机画的点没有H这个点，相信⼤家都觉得这个就是最短的⼀个圈了，那如果分步骤来做，先把H当成仓，画外围常识下认为最短的圈，再⽤解决⽅案假设⼆的逻辑来连线。逻辑上应该可以得出最短的路径。六、解决⽅案设想四穷举法，把各种可能性都列出来，当然这个就没有太⼤的意义，⽆法找到快速解决问题的⽅案。除⾮有⼀种⽅式能⾃动穷举，这样也是不错。关于物流⽂视界物流⽂视界为专注于智能物流领域的数字传播综合服务机构，为物流技术装备⽤户企业及供应商提供会议、沙龙、论坛、数字传播、培训相关资源整合服务，旨在让优秀的物流装备技术及解决⽅案找到落地场景，让场景找到优秀的物流装备技术及解决⽅案，促进社会供应链物流⾼质量⾼效率的发展----好的⽂章，值得分享----编辑转发只为传递更多信息，并不代表本号观点。如有侵权，请联删。如有侵权，请联删。