Minimum Fleet Problem「建议收藏」

本文为MIT Senseable City Laboratory 2018年5月23号发表于Nature杂志Addressing the minimum fleet problem in on-demand urban mobility论文的学习笔记。

问题定义

给定一批出行需求，在出行需求被严格满足且最大空驶时间不超过δ分钟约束下，找到最小车队数

解决方案

总体思路：minimum fleet -> path cover -> maximum cardinality bipartite matching

轨迹处理

每条出行轨迹简化为四个信息：

• 起点经纬度
• 终点经纬度
• 出发时刻
• 到达时刻

根据上述信息进行以下几个方面的处理：

• 地图匹配：使用OSM地图数据，以路口为节点，以道路为边，构建Graph，对起终点经纬度进行Map Matching，目的是抓到定位点100米内最近的路口上。
• ETA：参数是每条道路的旅行时间；根据起点经纬度和终点经纬度规划路线，将途经道路的旅行时间加起来得到路线总时间，作为预测值；真值为轨迹到达时刻-轨迹出发时刻；优化目标是最小化平均相对偏差，即ME。具体实现时，有两个细节操作，一是路况的考虑，文章的具体做法是按照小时进行分组；二是匹配后相同起终点的轨迹做了清洗，去除了起终点在相同地方的轨迹、旅行时间过快和过慢的轨迹
• 定义出行需求：一个需求用（起点经纬度、终点经纬度、出发时刻、预计送达时刻）四个信息进行描述

Vehicle-shareability Network与Path Cover

每一个节点代表一个出行需求（Trip），如果两个出行需求可以用同一辆车来满足，则在这两个节点之间添加一条边。判断节点i和节点j之间能不能添加边的条件如下：

节点i的预计送达时刻 + 节点i的终点位置到节点j的起点位置的预计旅行时间 <= 节点j的出发时刻 （保证用户实际需求不用等待）

节点j的出发时刻 – 节点i的预计送达时刻 <= 时间阈值（文章设置为15min，即车辆最大空驶时间为15min，保证车辆调度效率）

按照上述方式搭建的网络，minimum fleet size问题就变成了path cover问题，我们从网络中找到一组路径对图进行互斥的覆盖后，路径的数量就是最小车队的数量。

二分图最大匹配

Vehicle-shareability网络是一个有向无环图（DAG），因此path cover可以转化为一个二分图。二分图的两组节点都是Trip，如果在Vehicle-shareability里邮编，则二分图里也有对应的边。这样的话，path cover问题就转变为 maximum cardinality bipartite matching问题。使用算法在二分图中找到最大匹配后，任选二分图中一个节点集合，其中未匹配的节点数就是最小车队数。详情可参见附录的资料。

Hopcroft-Karp算法

二分图匹配的关键思想是找到一个增广路径（augmenting path）。假如一个二分图当前已经进行了匹配（不是最大匹配），在该二分图中，仍然存在两个未进行匹配但是存在连通路径（路径可以由一条或多条边组成）的点，且在该连通路径上，已经选取的的边与未选取的边交替出现，称为增广路径。这个路径有一个重要性质，把路径上已经选取的边变成未选取，未选取的边变为已选取，匹配节点数增加了1。因此只要存在增广路径，通过取反操作，就能增大匹配数；当不存在增广路径时，我们就找到了最大匹配。

基于增广路径这个思路最简单的算法是Ford–Fulkerson algorithm，按照节点进行遍历，挨个节点寻找增广路径。寻找一个增广路径最坏需要遍历E条边，共有V个节点，因此复杂度为O(VE)。

Hopcroft-Karp算法的基本思路是：每一轮同时对于所有未匹配顶点的增广轨查找时，然后同时找出所有合法的增广轨（当然，这些增广轨的未匹配部分不允许重合），我们采用之前的增广轨取反法，分别用合适的顶点去匹配这些增广轨，每次匹配都可以给匹配数加1。直到再也找不到可匹配的增广轨，得到的即为最大匹配。Hopcroft-Karp算法的复杂度是O(V^0.5E)

Hopcroft-Karp算法的示意图如下：

// Hopcroft-Karp伪代码
/* 
 G = U ∪ V ∪ {NIL}
 where U and V are partition of graph and NIL is a special null vertex
*/
  
function BFS ()
    // 所有未匹配点的label设置为0，加入队列Q；所有匹配点的label设置为无穷大；伪节点的label设置为无穷大
    for each u in U
        if Pair_U[u] == NIL
            Dist[u] = 0  
            Enqueue(Q,u)
        else
            Dist[u] = ∞
    Dist[NIL] = ∞
    while Empty(Q) == false
        // 取出label最小的未匹配节点
        u = Dequeue(Q)
        if Dist[u] < Dist[NIL] 
            for each v in Adj[u]
                // 遍历u的邻接节点v
                if Dist[ Pair_V[v] ] == ∞
                    // 当邻接节点的匹配点的距离为无穷大
                    // ==>已匹配，更新Pair_V[v]节点的距离，这样不是无穷大，不会再被更新，保证了增广路径不相交
                    // ==>NIL，找到增广路径，更新NIL的距离，第一次遍历到的NIL的距离，决定了本轮查找的增广路最大长度
                    Dist[ Pair_V[v] ] = Dist[u] + 1
                    Enqueue(Q,Pair_V[v])
    // NIL的长度不为无穷大，说明有增广路径，否则没有
    return Dist[NIL] != ∞

function DFS (u)
    if u != NIL
        for each v in Adj[u]
            if Dist[ Pair_V[v] ] == Dist[u] + 1
                if DFS(Pair_V[v]) == true
                    Pair_V[v] = u
                    Pair_U[u] = v
                    return true
        Dist[u] = ∞
        return false
    return true

function Hopcroft-Karp
    for each u in U
        Pair_U[u] = NIL
    for each v in V
        Pair_V[v] = NIL
    matching = 0
    while BFS() == true
        for each u in U
            if Pair_U[u] == NIL
                if DFS(u) == true
                    matching = matching + 1
    return matching

应用

根据海量历史请求，计算得到了最小车队数量Nmin。在线使用时，令N=1.2Nmin。然后对于实时发单的出行需求，使用以下两种模型进行派单：

On-the-fly：来一单，派一单，选择标准是使用户从发单到上车这段等待的时间最短

Batch：压单1min，对这一批运单构建司机和运单的有权二分图，边权重为用户发单到上车的等待时间，最大值设置为6min，然后使用maximum matching（如KM算法）求解

从上图可以看出，使用压单1min、最大等待时间6min这套参数的Batch派单模式，需求满足率平均可以达到92%，远远超过on-the-fly的模式。

附录

Matching问题：https://en.wikipedia.org/wiki…

Path Cover与二分图：https://stackoverflow.com/que…

二分图匹配算法：http://blog.sina.com.cn/s/blo…