Minimum Fleet Problem「建议收藏」

Minimum Fleet Problem「建议收藏」本文为MITSenseableCityLaboratory2018年5月23号发表于Nature杂志Addressingtheminimumfleetprobleminon-demandurbanmobility论文的学习笔记。问题定义给定一批出行需求,在出行需求被严格满足且最大空驶时间不超过δ分钟约束下,找到…

大家好,又见面了,我是你们的朋友全栈君。

本文为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,保证车辆调度效率)

clipboard.png

按照上述方式搭建的网络,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…

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/135268.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 使用SpringBoot上传文件并存储至数据库

    使用SpringBoot上传文件并存储至数据库springboot2.2.1.RELEASE <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId><…

  • onmousedown和onmouseup事件「建议收藏」

    onmousedown和onmouseup事件「建议收藏」在这个程序中为我们介绍两个鼠标事件onmousedown和onmouseup事件,这个两双鼠标事件分别是鼠标按下时候触发的事件和鼠标松开的时候触发的事件他r这样来设置文本的颜色们的是实现是通过调用javaScript脚本。我们在这个程序中还可以看到的一点对于文本颜色的一个处理,我们在这个文本颜色的处理的过程是getElementById().style.color

    2022年10月23日
  • BufferedWriter使用write方法如何换行

    BufferedWriter使用write方法如何换行BufferedWriter对象自带newline()方法可以换行,但如果在字符串中部换行,不想用newline()方法该如何做呢?使用\n是无法实现的,使用\n后,只会出现一个空格,并未实现换行,在想要实现换行的地方加入\r\n就可以了例如Filefile=newFile(“d:/ioPractice/text.txt”);Writerfw=newFileWrite

  • C语言输出格式控制符汇总

    C语言输出格式控制符汇总C语言输出格式控制符汇总标志][输出最小宽度][.精度][长度]类型

  • 并发编程之多线程

    一多线程的概念介绍threading模块介绍threading模块和multiprocessing模块在使用层面,有很大的相似性。二、开启多线程的两种方式11.创建线程的开销比创建进程的开销

  • 5G网络切片综述 — 1

    5G网络切片综述 — 1简介随着5G时代的来临,21年的SA在国内的全范围商用,现阶段人们对于5G的必要性认识还不足。主要是目前人们用的5G主要集中在eMBB(enhancedMobileBroadband)即增强型移动带宽的阶段,而大数据业务如在线直播、高清视频等在4G上都得到了很好的支持,所以带宽的继续增大对于用户体验的边际效应递减。5G所带来的真正改善并不仅仅是在于大带宽,而在于5G提供了在同一张物理5G网络的情况下,同时能够提供eMBB,URLLC(Ultra-ReliableLow-LatencyCommun

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号