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)
blank

相关推荐

  • idea2021 激活码【中文破解版】

    (idea2021 激活码)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~S32P…

  • dao层和service层和control代码(Java简述抽象类和接口的区别)

    DAO层:DAO层叫数据访问层,全称为dataaccessobject,属于一种比较底层,比较基础的操作,具体到对于某个表的增删改查,也就是说某个DAO一定是和数据库的某一张表一一对应的,其中封装了增删改查基本操作,建议DAO只做原子操作,增删改查。Service层:Service层叫服务层,被称为服务,粗略的理解就是对一个或多个DAO进行的再次封装,封装成一个服务,所以这里也就不…

  • 6种不同画法画平行线_平行线的画法「建议收藏」

    6种不同画法画平行线_平行线的画法「建议收藏」课题平行线的画法主备人复备人教学目标1.掌握平行线的画法,并能用画平行线的方法检验两条直线是否互相平行。2.能运用画平行线的方法画长方形和正方形。3.通过动手画一画,知道两条平行线间的垂线的特点。教学重难点正确运用直尺和三角尺画平行线教学设计复备师:我们上一节课学习了画垂线,这节课我们来学习画平行线。你们觉得该用什么工具画呢?学生可能会说:生1:用尺子来画。生2:用格子来画。师:同学们都能利用手中…

  • Wireshark抓包详解[通俗易懂]

    Wireshark抓包详解[通俗易懂]简述wireshark是非常流行的网络封包分析工具,功能十分强大。可以截取各种网络封包,显示网络封包的详细信息。使用wireshark的人必须了解网络协议,否则就看不懂wireshark了。为了安全考虑,wireshark只能查看封包,而不能修改封包的内容,或者发送封包。 wireshark能获取HTTP,也能获取HTTPS,但是不能解密HTTPS,所以wireshar

  • crontab 用法(执行python文件)[通俗易懂]

    crontab 用法(执行python文件)[通俗易懂]前提:创建一个xxx.py的文件文件头为#!/usr/bin/python3#-*-conding=utf-8-*-print(‘helloworld’)更改权限chmod777xxx.py这样python文件就可以执行了ubuntu@VM-0-10-ubuntu:~/script$./test.pyhelloworldcrontab使用…

  • Git 指令集

    Git 指令集Git指令集Git是分散式的版本控制系統,從架設、簡易操作、設定,此篇主要是整理基本操作、遠端操作等.註:Git的範圍太廣了,把這篇當作是初學入門就好了.注意事項由project/.git/config可知:(若有更多,亦可由此得知)origin(remote)是Repository的版本master(branch)是

发表回复

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

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