日益复杂的路径选择算法下将你的快递送到家

如果你现在需要亲手寄送20个快递包裹,你将如何计划最佳的投递路线?

这是一个数学家和计算机科学家们长期以来一直都在讨论的问题,但是对你来说,你更加熟悉的情况可能是例如当你在当销售的时候的行销路线的问题。简单地说,这个问题的核心是:给定一系列的用户位置列表以及它们之间相距的距离,能经过所有点一次并且回到原点的最短的一条路线是什么?显而易见,解决这个问题对于任何电商企业来说都是非常有吸引力的,因为这就意味着它们能使用更少的运输燃料和更少的司机雇佣。

但是问题来了:上述这个问题会变得非常的困难,并且瞬息万变。温哥华的路线优化初创公司Routific的首席执行官Marc Kuo就解释过说:“如果一个司机必须经过到57个站点,那么我们通过计算可以算出可行的组合方式数量是10的75次方。” 对于现有的计算机来说,大约需要几天或几周来评估每条可能的路线。因此,为了取代这种遍历寻找路径的方法,企业应该尽可能的寻找一种方式来完善它们的路线规划。

世界上最大的几家快递公司好像都并不热衷于与我们谈论这个话题。不论是UPS还是DHL都不回应我们的采访要求。而FedEx快递公司没有给出具体的面谈时间,即使我们已经提前一周联系了它们。亚马逊的一位发言人表示称,公司与许多不同的交付服务提供商有合作,这些递送服务提供商都使用亚马逊提供的高端服务。除此之外,无可奉告。

幸运的是,一些小的运输公司对此并不那么谨慎,所以我们和他们交谈了一下。

在现实世界中投递交付优化在好几个层面上都比旅行推销员问题要更加的棘手。首先,两个交付地点之间的距离需要计算,对于任何一个使用Google地图导航的人都知道,一般从出发地开始往往都有若干条路径来抵达你所要去的目的地。Paragon的常务董事Will Salter在60个国家为英国超市巨头Tesco等客户提供了路由和时间规划软件,他说该公司的路径规划算法与传统的谷歌地图算法相比是“高度定制化”的。他们会将不同时间段的道路情况、交通流量纳入考虑的范畴,甚至对于在十字路口右转产生的边际收益也考虑了进来。

在这方面,有成百上千个约束条件需要被考虑进来。你可能会计算出一条能够经过所有途经点的惊人的路线,但是作为快递交付,你难道可以把所有的货物都放进货车的车厢么?装卸冷冻食品的时间要比装卸主食多出多长的时间?为了节省燃料,是否应该先送较重的物品?

但是世界上最大的在线杂货零售商Ocado的总裁James Lohr解释说到,它的系统一开始在给定区域内随机的给配送货车分配配送点,然后计算出这些交付过程需要花费多长的时间。然后循序渐进的对配送过程进行改变,从切换两个包裹投递点的顺序到切换车辆的整块投递区域—— 每次改变都需要评估投递过程是否有改进。通过四百万次每秒的改变并且跟踪数据变化来寻找最佳的解决方案,这样一来结果将逐渐接近我们所需要的最佳路线。

除了这种大型公司才能负担得起的复杂数据计算外,一些公司也正在开发一些针对小型企业的系统。举例来说,Routific的Kuo声称他的公司希望通过基于云服务的计算来规划路线,这些结果都能够通过快递司机的手机去访问。他说:“这听上去有点令人震惊,但至今许多司机仍然采用纸和笔来进行规划路线。他的公司的算法也对路线进行逐渐的改变,但是对于这种一个小改变会造成大影响的项目,注意力集中在投递掉包裹以寻求最大化进步,然后继续使用算法进行计算。Routific称其服务可缩短至少40%的运送路线。

你已经与这些算法打过交道了,只是你并没有意识它的存在,这是一个很好的机会。Paragon(代表宜家Ikea和零售商Argos)以及Ocado都在给客户提供在线购物的”橱窗到客户”的服务中不断地搜集数据。它们能够给出适合当前计划任务的最佳的路线。

但是对于快递司机来说,这些路径最有算法并不是特别管用。Paragon,Ocado和Routific都经历过一些文化的交流问题——当他们在说服经验丰富的送货司机说他们公司的算法比他们多年的送货经验更厉害的时候。Ocado公司的Lohr说:“如果哪天你去了那些送货司机聚集吃午饭的地方说你是路线规划师,那么它们可能会说到让你怀疑人生。“当然,这有些夸张了,但是在政策上确实很困难。”

同时,更多的方面的影响因素在不断的加入路径优化的问题,而且看起来永无止境。Paragon的Salter告诉我们,客户的要求在不断增加,例如要求使用能够减少二氧化碳排放的路线就是最受欢迎的一项。他说:“每年我们都在考虑增加越来越多的限制因素,我认为我们不可能找到一个真正的最优的路径规划方案。”

本文的版权归 KX_WEN 所有,如需转载请联系作者。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏老九学堂

【干货】大学生求职面试12个误区,千万不要再犯错

误区一 简历要精美漂亮? 很多人认为,简历就是面试者的形象,一定要精美漂亮。其实不然,如果你不是学设计的,就不用把简历搞得像彩色连环画,只要保证简历在交给面试...

30160
来自专栏新智元

【论文】UC 伯克利教授:如何获得 AI 好处,不闯大祸?

如果自动驾驶汽车的上路,将美国每年大约40000例致死交通事故减少到一半,那么汽车厂商们可能不但不会收到20000封感谢信,反而会收到20000张法院传...

403120
来自专栏程序员宝库

程序员为什么要时刻保持危机感?

假期回来,第一天上班,领导找我说,你的人都划入各个事业部,管理权也都放在各事业部,于是我就成了一个光杆司令,后续未知。

9210
来自专栏Android工程师的修仙之旅

在腾讯实习一年,我学到了什么

6月底,我欣然前去,到现在刚好一年时间,马上要回学校了,我觉得该写点什么,因为这是一个很特殊的时间点,我站在学校和社会的交界处,对校园生活保持着最鲜活的记忆,对...

8K110
来自专栏新智元

BAT 机器人落地,人工智能应如何崛起?

人工智能需要拥有与我们一样的三观。 新智元点评 2015 百度世界大会的报道引发全球关注,今天英国金融时报 FT 的记者也通过【新智元】的相关报道针对中国人工...

38690
来自专栏华章科技

分享Google的42条军规,别说你懂职场

本文是谷歌产品高级副总裁Jonathan Rosenberg在其母校克莱蒙特·麦肯纳学院向毕业生分享的他自己多年的职场经验,包括沟通、文化、团队建设、决策、创新...

11820
来自专栏PaddlePaddle

【AI资讯】深度学习的成果如何验证?

据悉,NVIDIA的研究人员已经创建了一个深度学习系统,可以通过观察人类的动作来教机器人。研究人员训练了Nvidia的TIAN X GPU供电的神经网络。神经网...

13180
来自专栏黄成甲

如何提出好的问题

上世纪60年代,有个普林斯顿大学的学生,得到了一次采访爱因斯坦的机会。这可是采访世界上最智慧的科学家,这个学生花了很长时间思考该怎么提问。采访那天,他向爱因斯坦...

17040
来自专栏铭毅天下

论项目管理中当面沟通的重要性

0、沟通问题的由来 近段时间,团队中出现了管理方面的这样、那样的问题。团队领导不去直面问题,与当事人直接当面沟通。而是采取了“旁敲侧击”的方式,找相关人员沟通。...

37370
来自专栏数据科学与人工智能

【数据思维】明略数据吴明辉:忘掉你的大数据,数据思维才最重要

10月11日晚,北京明略软件系统有限公司董事长吴明辉先生结合自身丰厚的实战经验以及车品觉老师书作《决战大数据》就大数据实战应用为庐客汇“12+50”会员带来了一...

25660

扫码关注云+社区

领取腾讯云代金券