在Ridesharing问题空间中解决Dispatch

Matchings and Graph Theory

匹配与图论

The concept of matching drivers to riders can be captured through the lens of graph theory. Thinking of ridesharing matching as a graph comes naturally as the problem inherently involves connecting two distinct groups — riders and drivers. It is also advantageous for several reasons; including the flexibility in modeling relationships (capturing factors like distance, time, and compatibility through weighted edges), as well as offering an armada of efficient and scalable algorithms to identify optimal structures.

通过图论视角可以刻画司机与乘客的匹配。将网约车匹配视为图问题非常自然，因为该问题本质上涉及连接两个不同群体——乘客和司机。这样做还有诸多优势：既能灵活建模各种关系（通过加权边体现距离、时间和兼容性等因素），又能利用大量高效且可扩展的算法来寻找最优结构。

One specific graph that captures the ridesharing settings (and more generally any two-sided marketplace setting) is the bipartite graph. Formally, a bipartite graph is a graph where the vertices can be divided into two disjoint sets such that all edges connect a vertex in one set to a vertex in another set. There are no edges between vertices within the same set.

一种能够刻画网约车场景（更一般地，任何双边市场场景）的特定图是二分图。形式上，二分图 是一种图，其顶点可划分为两个不相交的集合，使得所有边都连接一个集合中的顶点到另一个集合中的顶点；同一集合内的顶点之间没有边。

Zoom image will be displayed

将显示放大图像

Figure 1: Constructing a bipartite graph to connect drivers to riders

图 1：构建二分图以连接司机与乘客

In most cases, our matching graphs are bipartite because we match one rider to one driver. However, there exist more involved situations, like shared rides, where the graph does not satisfy this condition. For simplicity, we only focus on bipartite cases.

在大多数情况下，我们的匹配图是二分的，因为我们把一名乘客匹配给一名司机。然而，也存在更复杂的场景，例如拼车，此时图并不满足这一条件。为简化讨论，本文仅聚焦二分情形。

Another practical layer that can be added to the concept of bipartite graphs is weighted edges. For our purposes, a weight represents the benefit accrued from a particular match.

另一个可以添加到二分图概念中的实用层是加权边。就我们的目的而言，权重表示从特定匹配中获得的收益。

You might now be wondering: a graph seems like a fairly intuitive object, but what exactly is a matching? Given a bipartite graph, a matching is a subset of the edges for which every vertex belongs to exactly...