如何规划设计物流配送最短路径思考.pdf

该【如何规划设计物流配送最短路径思考】是由【鼠标】上传分享，文档一共【6】页，该文档可以免费在线阅读，需要了解更多关于【如何规划设计物流配送最短路径思考】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。如何规划设计物流配送最短路径思考(?)以下?章来源于实践笔记?,作者荡漾哥在城市配送中或者快递员送货,都会存在?个问题,怎么跑路径最短。当然现实中送货都是靠司机的经验,或者看下地图?概就知道怎么跑了,没有?真的去算路径是不是最短。但是从物流管理者?度,还是有必须知道逻辑,这样才能合理决策。今天先分享下单环模型(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当成仓,画外围常识下认为最短的圈,再?解决?案假设?的逻辑来连线。逻辑上应该可以得出最短的路径。六、解决?案设想四穷举法,把各种可能性都列出来,当然这个就没有太?的意义,?法找到快速解决问题的?案。除?有?种?式能?动穷举,这样也是不错。关于物流?视界物流?视界为专注于智能物流领域的数字传播综合服务机构,为物流技术装备?户企业及供应商提供会议、沙龙、论坛、数字传播、培训相关资源整合服务,旨在让优秀的物流装备技术及解决?案找到落地场景,让场景找到优秀的物流装备技术及解决?案,促进社会供应链物流?质量?效率的发展----好的?章,值得分享----编辑转发只为传递更多信息,并不代表本号观点。如有侵权,请联删。如有侵权,请联删。