国际资讯|按需的最后一英里运输：在位置智能下的实时路线优化
点击图片上方蓝色字体“慧天地”即可订阅
英文原文来源：www.geospatialworld.net
中文编译整理：孙韬淳
校对者：王芙蓉、林逸文
转载需经【慧天地】许可。
近年来，我们看到了众多市场平台的出现，它们将顾客与多样的产品和服务联系在一起。其中Uber, Postmates和Stuart就是例子，它们允许你订购从搭车到食品、甚至小包裹在内的几乎任何东西的取货和送货服务，然后在不到一两个小时的时间内送货上门。
从物流的角度来看，有效地运行这项服务是一个挑战，而且在面对激烈的行业竞争时，它也变得愈发重要。传统的物流解决方案不再适合规划此类服务，因为本质上，这些服务背后的问题和标准物流公司有很大不同。如果我们看下任何正规的第三方物流（3PL）公司，它们通常在一定的截止时间内接受第二天的递送订单，这样它们可以有充足的时间计划第二天的递送路线。这不是一个按需服务的案例，因为按需服务是指一个新的订单需要（几乎）实时处理并分配新订单，并不考虑任何在未来将会收到的订单的服务。
这两个问题极难解决，尤其是如果我们想要确保我们的运营处于最佳状态，或者至少比我们的竞争对手更好的话。这就是空间数据科学可以发挥作用的地方，因为它可以建立数据模型，模拟现存条件，为我们提供关于现有约束、低效分配等方面的见解。
传统最后一英里运输问题VS按需最后一英里运输问题
虽然这两个问题都难以解决，但每个问题的复杂性都可以在非常不同的阶段被发现。传统的最后一英里运输问题是一个车辆路线问题（Vehicle routing problem, VRP），这是一个组合优化问题，以其算法设计和计算的复杂性而著称。实时按需运输问题的一个明显优点是预先就能知道订单和驱动程序可用性的所有信息，而通常不需立即给出处理方案。这样就更容易找到接近最优的解决方案。有几种算法被设计来解决这个问题，也有几种实现了这些算法的解决方案，既有商业的，也有开源的。
另一方面，因可用的信息较少，实时按需运输问题属于相对较小的问题，但这需要立即的响应。我们仅知道直到我们检查系统状态时候的系统发生了什么，大多数因其已被递送而无法改变。因为缺乏未来的信息以及无法更改过去的决策，导致了非常低效的路线规划。克服这一问题成为了主要的挑战。
下面的地图很好地体现了这种低可视性，我们只能看到每三分钟时间窗口下的订单。一旦三分钟过去，我们就不能改变分发计划，也无法预见未来的订单。
在关于物流的文献中，一个解决这类问题的共识是：增加决策的灵活度，试图得到尽可能多的未来信息。第一点需要尽可能拖延决策，做出可以轻易撤销或者改变的决策。第二点与其他数据科学技术的使用相关，比如通过预测拓展我们的视野。
这个问题很难归类到一个问题类别中，因为它取决于提供的服务的复杂度，也取决于我们想要在多大程度上优化我们的路线。它可以从“单一”分配问题（如果我们仅需考虑一个窄时间窗口的相关信息），到一个VRP问题（如果我们需要考虑算法在当前迭代之前驱动程序做了什么）。
接下来的主要挑战是能够计算所有的需求成本，设计出一种能在几秒内找到临近最优解的算法。同时也还有其他挑战需要克服，比如在开始一天的工作之前计算我们需要多少司机，需要多少车队，或者为接下来的几分钟/几小时预报。
这两种情况下需要解决的问题存在很大的差异，这使得采用传统的物流解决方案来解决随需应变的运输问题变得非常困难，甚至是不可能的。
设计并且改进一个最优化问题
接下来的例子展示了如何应用优化来解决按需运输问题，以及这么做的益处。下面是一个场景，我们将使用两种初始方法来解决这个问题。
下面的假设是为了增强演示的清晰度。但是，请记住，这个问题可能会变得更加复杂，这取决于我们在优化我们的功能方面想要走多远，以及后面描述的服务需求。
我们的目标是最小化距离，我们主要的度量标准是走过的总距离。这可以很容易的改成其他的标准，比如最小化递送时间和车队大小。
每个订单相互独立，比如，它们不能合并，基于一个骑手在完成当前单之前不能接下一单，除非他们空闲。
骑手不能接新单，直到他们空闲。
车队的类型对每位骑手是相同的。
在算法的每个迭代中，我们将一直有充足的闲置骑手来分配订单。当然，这在现实中是不可能的，而且会增加问题的复杂度。
在下面的地图上，我们可以看到星期四下午7点到7点05接到的订单。我们可以看到取货和送货的地点，为每个订单计算最优路径以及闲置状态，或在一定的时间窗口内计算某一点的可用骑手/车手。我们将聚焦在5分钟的时间窗口中，使其更容易展示和比较结果。
第一步：起点-终点矩阵（Origin-Destination Matrix，OD矩阵）
为了解决任何路径规划问题，我们需建立一个成本矩阵，代表从位置A到位置B的成本。在现有的例子中，指给一个点A的骑手在点B的订单的成本。在我们的例子中，这个OD矩阵是从骑手位置到订单位置的距离。
在按需传输问题中，这是个更大的挑战，因为需要实时计算这个矩阵。（相关具体算法可以参照原文）。
下一步
前面的两种算法只是在遇到这个问题时通常遵循的第一个自然步骤。然而，问题的复杂性通常需要更多的步骤。
如前文提到的，在问题的每一迭代周期中，扩展可用的信息量是很重要的。一个非常实用的步骤是分配任务，考虑在接下来的30到60分钟内会发生什么（甚至更多的时间取决于服务的时间长短）。预报未来有需求的地点也很有帮助——避免一个骑手远离高需求地区。除此之外，这些信息可以对骑手开放，让他们在空闲的时候知道他们应该去哪里，这样就可以分发更多的订单。
这张地图展示从现在开始一小时后预期需求的位置和闲置骑手。基于骑手们到高预期需求地区的距离，他们的分发任务会有不同的优先级。
除此之外，还有一些其他的提升方法能更有效、有质量的解决分发任务。这些改进很大程度上取决于所提供的服务类型。
优化标准：在我们的例子中我们选择距离作为标准来优化。然而，我们可能添加额外的标准。始终记住在算法的每个迭代中都必须要计算成本。一些例子可以是：
（1）时间；
（2）利用率，这对一些购买和养护车队昂贵的公司尤其重要；
（3）顾客和骑手的体验；
（4）就服务使用频率而言，匹配顾客；基于顾客意见和递送效率，匹配骑手；
（5）融合订单（举例，Uber pool）；
（6）通过尽可能推延分发任务，创建更大的分发批次。比如，递送小包裹，5分钟就很好。
从算法的角度来看，把这些标准合并到我们的模型中是一项复杂的任务。可视化由不同算法得出的步骤和决策对于一个耗时的任务而言是一个强有力的工具。
翻译整理者
校对者
点击文末“阅读原文”即可查看原文章
内容转载、商务活动、投稿等合作请联系
微信号：huitiandi321
邮箱：geomaticshtd@163.com
欢迎关注慧天地同名新浪微博：
ID：慧天地_geomaticser
国际资讯|Planet公司与NASA签署了价值数百万美元的协议
《慧天地》敬告
《慧天地》公众号聚焦国内外时空信息科技前沿、行业发展动态、跨界融合趋势，探索企业核心竞争力，传播测绘地理信息文化，为测绘、地信、遥感等相关专业的同学提供日常学习、考研就业一站式服务，旨在打造政产学研用精准对接的平台。
《慧天地》高度重视版权，对于原创、委托发布的稿件，会烦请作者、委托方亲自审核通过后オ正式推发；对于来自网站、期刊、书籍、微博、微信公众号等媒介的稿件，会在作者栏或者文章开头显著标明出处，以表达对作者和推文引用平台版权的充分尊重和感谢；对于来源于网络作者不明的优质作品，转载时如出现侵权，请后台留言，我们会及时删除。感谢大家一直以来对《慧天地》的关注和支持！
——《慧天地》运营团队