管理配送网络：图数据库的应用案例

作为一家电子商务平台，takealot.com 最大的竞争优势之一在于我们拥有并不断扩展自己的物流网络。该网络使我们能够控制向客户交付商品的方式和时间，并且除其他方面外，还能确保 takealot.com 成为南非领先的电子商务平台。

在本文中，我将分析 takealot.com 在为客户提供可靠配送服务方面面临的独特问题，以及我们如何使用图数据库来提供高性能和可扩展的解决方案。

问题出在哪里？

有人可能会问，为什么 takealot.com 不使用南非的邮政服务和现有快递公司？答案很简单：可靠性不足。当地邮政服务无法提供准确的送达日期。这意味着，如果以邮政服务作为我们的物流主力，就无法为客户提供确切的送达时间。此外，现有快递公司会收取额外费用，这会增加成本，而这些成本最终大多会转嫁到客户身上。基于这一关键因素，维持我们自己的物流运营仍然是最佳选择。

然而，要发展物流网络以满足不断增长的全国性电子商务平台的需求，不可能一蹴而就。因此，我们必须确保与现有第三方快递公司保持整合。

因此，该系统的要求是建立以下功能：

1. 如何将订单送达客户。
2. 订单何时能送达客户手中？
3. 是否使用第三方快递公司或我们自己的配送网络来完成配送。

本文余下部分将重点讨论第一点，同时也会略微提及第二点。如果大家感兴趣，我会在后续文章中详细阐述第二点。

让我们一起实现造船梦想

在 takealot.com 平台上，向客户交付商品分为两个阶段：

1. 将包裹从仓库快递到离客户最近的分店。这可能涉及包裹在多个分店之间转运。
2. 将包裹从分店送至客户手中。

简而言之，takealot.com 需要确保订单以最短、最经济的方式从中央仓库或第三方市场卖家运送给客户。

这涉及到计算最短路径，这是一个经典的计算机问题。原则上，我们将分支视为一系列节点，可以表示如下：

当你用代表路线的边将它们全部连接起来，并运行图搜索算法时，我们就能快速交付成果，并用冰镇啤酒和击掌庆祝。

我们通过pgrouting和Yen 算法实现了上述功能。以下是该方法的延迟：

135毫秒内我们就能知道如何联系到客户。确定联系到客户的时间后，系统响应时间如下：

510毫秒后，我们将知道如何以及何时联系到您。成功！

然后我们需要扩展规模，结果发现了一个问题。配送网络的图表示仅仅是一个图：一堆节点通过一堆边连接起来。这意味着，诸如确保我们不用摩托车运送冰箱之类的配送约束，是在后期处理时在图之外完成的。

随着路线、快递员和分支机构的增加，性能下降到我们无法扩展配送能力的地步，因为这意味着客户需要等待几秒钟才能收到配送日期。

最终，这意味着无法持续整合第三方快递公司；除其他挑战外，该公司现在无法获得价格合理的农村快递服务。

属性图来帮忙

事实证明，我们需要的不是图，而是属性图。简而言之，属性图是一种图数据结构，它在图的边和顶点上添加了属性（键值对）。之前讨论的图模型从一堆相互连接的节点变成了：

每条边/顶点都具有以下属性：

这意味着我们可以将所有路由约束逻辑都下放到图结构中。在确定如何到达客户方面，无需任何后处理。我们利用JanusGraph作为数据层，并借助TinkerPop 和 Gremlin实现查询语言，从而简化了这一过程。这也意味着数百行后处理代码被简化为如下所示的简单Gremlin-Scala查询：

g.V().has(Keys.Vertex.LOOKUPID, lookupIDTo)
          .inE(LegType.LAST_MILE.toString)
              .has(Keys.Edge.PHYSMINWEIGHT, P.lte(attributes.physWeight))
              .has(Keys.Edge.PHYSMAXWEIGHT, P.gte(attributes.physWeight))
              //More property constraints
          .outV()
            .has(Keys.Vertex.HUBACTIVE, true)
          .repeat(
            _.inE(LegType.LINE_HAUL.toString)
              .has(Keys.Edge.PHYSMINWEIGHT, P.lte(attributes.physWeight))
              .has(Keys.Edge.PHYSMAXWEIGHT, P.gte(attributes.physWeight))
              //More property constraints
            .outV()
              .has(Keys.Vertex.HUBACTIVE, true)
            .simplePath()
            ).until(_.has(Keys.Vertex.LOOKUPID, lookupIDFrom)).limit(10).path

任何 Gremlin 的粉丝都会注意到我们是在反向遍历。假设我们能更好地理解边的度分布，那么边的标签就可以用于进一步的优化。

上述查询不仅检查我们如何到达客户处，还利用所递送包裹的详细信息（例如重量）来更快地排除路线。

现在，让我们再看一下下面的延迟图：

P95 响应时间仅为10 毫秒，性能提升了一个数量级。此外，随着 takealot.com 增加配送中心和快递员，性能并未下降（至少目前为止没有）。这是因为我们的搜索空间始终限制在LINE_HAUL现有边的数量范围内，而物流网络的大部分扩展都发生在LAST_MILE边层。属性图的另一个优势在于，它能够通过标签和属性对图的结构进行正式的分类和分层。

这种新的属性图结构使我们能够以结构化且可遍历的方式表示时间约束。然而，计算何时将货物送达客户的操作仍然在图之外进行。图上更自然的时间数据（而非逻辑）表示方式使我们能够在该层进行优化。最终，系统响应时间为：

150毫秒的P95响应时间是可以接受的。正如我所说，如果大家对这篇文章感兴趣，我可能会继续探讨该图表如何帮助我们优化交货日期计算。

这种新的属性图模型提供了许多其他与性能无关的好处，例如提高可观测性、更容易修改等等。

所以我们正在促成船舶项目的实现吗？

我希望我们做到了。这套系统让我们能够更准确地预测交货日期——当然，前提是它没有考虑到潜在的运营延误，例如供应商到货延迟、交通拥堵等等。如何应对配送路线上的潜在运营延误，可能是我们接下来需要解决的另一个挑战。

属性图是解决计算问题的万能灵药吗？不！绝对不是！就像你不会用马桶搋子来取出螺丝一样，你也不会用图数据库来建模购物车之类的东西。

然而，这种新的属性图模型引发了许多讨论，可能会带来更多面向客户的改进。

我们很高兴能进一步推进这项技术，看看我们能用它做什么：我们需要制造出更多这样的船舶。