当前位置:100EC>电商物流>【物流研究】城市配送和快递送货中怎么跑路径最短
【物流研究】城市配送和快递送货中怎么跑路径最短
发布时间:2019年02月01日 10:39:42

(网经社讯)在城市配送中或者快递员送货,都会存在一个问题,怎么跑路径最短。当然现实中送货都是靠司机的经验,或者看下地图大概就知道怎么跑了,没有人真的去算路径是不是最短。但是从物流管理者角度,还是有必须知道逻辑,这样才能合理决策。                    

今天先分享下单环模型(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当成仓,画外围常识下认为最短的圈,再用解决方案假设二的逻辑来连线。逻辑上应该可以得出最短的路径。

七、解决方案设想四

穷举法,把各种可能性都列出来,当然这个就没有太大的意义,无法找到快速解决问题的方案。除非有一种方式能自动穷举,这样也是不错。(来源:罗戈网;编选:电子商务研究中心)


今年是《电子商务法》实施的第一个315“国际消费者权益日”。为此,网经社旗下电子商务消费纠纷调解平台发起“‘律’动网购,我在行动!”的“3·15”主题活动,为期一月。通过报告发布、榜单评级、案例披露、投诉曝光、绿色通道、法律援助、消费预警、专题聚焦、滚动播报、全媒体矩阵和3000+注册媒体记者通报等多种形式,对网络消费维权难点、热点和相关平台点名鞭策。平台“绿色通道”入驻持续开放中,包括京东、苏宁易购、拼多多、唯品会、国美、网易考拉和严选、宝宝树美囤妈妈、蜜芽、贝贝、亚马逊中国、聚美优品、途虎养车、蘑菇街、美丽说、当当、绿森数码、丰趣海淘、有赞、云集、楚楚推、寺库、本来生活、i百联、返利网、美团点评、飞猪、阿卡索外教网、携程、去哪儿、艺龙、驴妈妈、同程旅游、分期乐在内的36家电商平台已抢先入驻。

股票名称/代码
$/总资产
$/营收
$/净利润
  • 阿里巴巴BABA.US
  • 1092亿
  • 385亿
  • 94.5亿
  • 京东JD.US
  • 282.6亿
  • 557.4亿
  • 7.7亿
  • 唯品会VIPS.US
  • 583.2亿
  • 112.2亿
  • 0.4亿
  • 宝尊电商BZUN.US
  • 4.60亿
  • 6.40亿
  • 0.3亿
  • 聚美优品JMEI.US
  • 7.60亿
  • 8.90亿
  • -0.06亿
  • 寺库SECO.US
  • 3.60亿
  • 5.80亿
  • 0.03亿