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

如果你现在需要亲手寄送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告诉我们，客户的要求在不断增加，例如要求使用能够减少二氧化碳排放的路线就是最受欢迎的一项。他说：“每年我们都在考虑增加越来越多的限制因素，我认为我们不可能找到一个真正的最优的路径规划方案。”