作者:

张文琦(北京邮电大学博士研究生)

李晶晶(北京邮电大学硕士研究生)

王强(北京邮电大学副教授,博导),研究方向:移动网络、信息理论、机器学习和智能决策系统

石东海,滴滴惠普产品技术负责人、高级技术总监

编者按

众所周知,交通供需存在时间和空间上的不匹配的现象,某一时刻城市内一部分地区车辆供过于求的同时,另一部分地区可能存在车辆空驶的状况。随着近年来全球定位系统(GPS)、无线通讯工具以及人工智能技术的发展,我们是否可以进行更好的规划,在维持车队规模一定的情况下,对这些空驶车辆进行有效指引以减少空闲率、提高司机收入并改善用户体验呢?滴滴出行惠普产品的石东海团队以及北极邮电大学王强团队对此合作探讨,结合强化学习算法进行调度优化,仿真验证显示效果显著。

由于交通供需之间的不匹配,大城市的车辆共享平台效率有很大提升空间。随着全球定位系统(GPS)和无线通信工具的发展,车辆共享平台可以充分利用空闲车辆来缓解供需之间的差距。

针对如何对空驶车辆有效指引以减少空闲率,同时研究城市承运中不同车队规模时的效率,滴滴出行普惠产品技术部负责人石东海团队和北京邮电大学王强副教授合作探讨,联合提出了一种基于最小车队的动态车辆调度方法,模拟实验得到了AI Labs的环境支持。

首先,在已知车辆共享网络情况下,采用二部图匹配算法获得所需的最小车辆数。然后,为了平衡实时交通中交通供需之间的失配,提出了深度强化学习算法DDQN(Dueling Deep Q-Network ),以有效地使用有限的车辆。DDQN能够估算供需之间复杂的动态关系,因此可以根据DDQN的调度政策将可用车辆调度到需求量大的地方,从而缓解供需之间的差距。最后,我们设计了一个模拟器来训练和测试决斗的深度强化学习算法。仿真结果证明算法在订单响应率和司机计费时长占比方面有显著改进,可以提升司机收入、改善用户体验。

1 研究背景

在线乘车共享服务由于其便利性和灵活性而受到了许多研究者的追捧。随着全球定位系统(GPS)和无线通信工具的发展,车辆共享平台能够充分利用道路上的车辆,这不仅能提高交通资源的利用率,还能够有效缓解交通拥堵和交通供需之间的差距。因此如何最好的规划和管理共享平台中的车辆就变得尤为重要。在已知车辆共享网络的情况下,采用二部图匹配算法最小化所需车辆数,并提出DDQN算法来将可用车辆分配到实时交通需求较大的地点已达到缓解供需之间差距的目的。

2 问题挑战

在当前的研究背景下,本论文提出了一种深度强化学习算法DDQN。在算法设计的过程中,我们面临的挑战主要是如何有效地分配有限的车辆,以满足更多需求。由于在车队管理过程中,调度政策的变化将很大程度上影响到未来的供需情况,我们需要保证调度的有效性。

3 解决方案

本论文基于滴滴平台中真实的数据,包括道路信息、时间估计以及订单数据,设计基于 DDQN的强化学习算法对车辆进行动态的调度策略。

本论文主要解决两个方面的问题,1)最小车队问题,在订单信息已知的情况下最大程度地减少所需车辆的数量;2)可用车辆调度问题,根据深度强化学习的策略,将可用车辆派往需求量大的地点来最大程度地提高响应率。

1 最小车队问题

根据订单数据,构建一个车辆共享网络,由于时间的方向性,它是一个有向无环图。图中的每个节点代表一个行程,图中的边表示两行程之间的可连接。由于是个有向无环图,我们可以将图分解为一个二部图,此时最小车队问题就转化为二部图最大匹配问题。通过二部图匹配算法就可以得到车辆共享网络的最小车队数量,图1展示了执行算法后得到的最小车队数和真实情况的对比,可以看到所需的车队数量有了明显的减少。

北邮X滴滴:基于最小车队的动态车辆调度
图1 每小时完成所有订单所需的最少车辆数量
北邮X滴滴:基于最小车队的动态车辆调度
图2 乘客忍耐时间与所需最小车辆的关系

2 可用车辆调度问题

在一个调度的时间线里,首先根据历史信息生成订单,其次更新可调度车辆分布,再次根据决策策略进行空闲司机调度,最后进行派单。调度的时间线流程如图3所示。

北邮X滴滴:基于最小车队的动态车辆调度
图3 调度时间线

我们使用DDQN模型来对共享网络中的可用车辆进行合理的调度和管理。在DDQN模型中, DDQN由状态、动作、奖励和状态-动作值(Q值)组成,空闲驾驶员(可用车辆)作为代理人。DDQN的目标是从初始状态开始获得最大化长期累积报酬的最优策略。在每次调度的过程中,每个空闲驾驶员都从状态空间观察一个状态,然后根据策略,每个空闲驾驶员都从动作空间选择一个动作执行。具体动态过程如图4所示。在DDQN中,我们采用Dueling结构对各个状态进行动作选择,这样可以提高算法的稳定性。

北邮X滴滴:基于最小车队的动态车辆调度
图4 调度/管理可用车辆的动态过程

4 实验与结果

在该实验中,本论文的数据集来源于滴滴出行的脱敏数据,可用车辆调度的实验数据包括北京核心区连续三周的车辆和订单数据。订单数据集包含上/落客时间和上/落客位置(经纬度)。车辆数据包含每几秒钟更新的位置(经纬度)和状态(在线和离线)信息。通过对比模拟器方法、随机方法和Q-Learning的方法,证明了我们提出的方法在订单响应率和司机计费持续时间占空比方面有显着改进,如表1所示。

北邮X滴滴:基于最小车队的动态车辆调度
表1 模型的实验结果对比

论文核心贡献者

北邮X滴滴:基于最小车队的动态车辆调度
北邮X滴滴:基于最小车队的动态车辆调度

相关资讯

  • 破解管理难题!共享单车管理系统上线 轻点鼠标让骑行更顺畅

    破解管理难题!共享单车管理系统上线 轻点鼠标让骑行更顺畅

    乱停乱放影响通行,停车点车辆超标停不下……共享单车在方便行人出行的同时,也因单车的乱停乱放为城市管理工作带来了挑战。为了整治共享单车无序停放、合理投放等问题,市城管局与第三方单车管理公司合作,上线了共享单车管理系统,通过智慧化监管,提升共享单车治理水平,让市民骑行更加顺畅。 “运营车辆总数14099…

    行业资讯 2022年5月26日
  • 政府工作报告5次提到汽车,新能源汽车产销量占全球比重超60% | 两会·最关注

    政府工作报告5次提到汽车,新能源汽车产销量占全球比重超60% | 两会·最关注

    3月5日,国务院总理李强在向十四届全国人大二次会议作政府工作报告时,五次直接提到汽车。 总理指出,过去一年来,我国加大宏观调控力度,推动经济运行持续好转。针对严峻挑战和疫后经济恢复特点,我们统筹稳增长和增后劲,突出固本培元,注重精准施策,出台支持汽车、家居、电子产品、旅游等消费政策,大宗消费稳步回升…

    行业资讯 2024年3月5日
  • 国家数据局等部门关于印发《“数据要素×”三年行动计划(2024—2026年)》的通知

    国家数据局等部门关于印发《“数据要素×”三年行动计划(2024—2026年)》的通知

    国家数据局等部门关于印发《“数据要素×”三年行动计划(2024—2026年)》的通知 国数政策〔2023〕11号各省、自治区、直辖市及计划单列市、新疆生产建设兵团数据管理部门、党委网信办、科学技术厅(委、局)、工业和信息化主管部门、交通运输厅(局、委)、农业农村(农牧)厅(局、委)、商务主管部门、文…

    行业资讯 2024年1月5日
  • 上海互联网50强 一嗨出行用数字化管理赋能线上线下实体经济

    上海互联网50强 一嗨出行用数字化管理赋能线上线下实体经济

    随着近年来互联网科技的深入普及,体现在出行领域可以说直接推动了服务体验的升级,融入数字化、移动网络技术的互联网出行方式,越来越受到更多人欢迎。作为国内汽车出行服务行业的领航者,以及数字化应用的先行者、倡导者,一嗨出行多年来持续布局“双智”平台建设,打造智能出行新生态,引领了行业完成数字化转型。日前,…

    行业资讯 2022年11月3日
  • 《道路旅客运输企业安全管理规范》修订 六大不同看过来

    《道路旅客运输企业安全管理规范》修订 六大不同看过来

    交通运输部于2023年11月23日举行11月份例行新闻发布会,介绍党的十八大以来,加快构建现代化公路基础设施体系有关情况。交通运输部新闻发言人、政策研究室副主任孙文剑主持发布会,部公路局副局长郭胜、部运输服务司副司长韩敬华共同出席,并回答记者提问。此次发布会重点介绍了“党的十八大以来,加快构建现代化…

    行业资讯 2023年11月15日
  • 关于惯性导航的 7 大误解

    关于惯性导航的 7 大误解

    作者:Mathias Vetter u-blox 消费与工业追踪应用首席产品经理 在全球范围内,越来越多的智能出行解决方案凭借可靠的定位技术可更好地应用于城市道路,精准的定位技术正在重塑传统的出行市场,例如租车、车队管理和车辆保险,以及其他共享单车、网约车和道路计程收费的新型应用。 针对这些普及速度…

    行业资讯 2022年9月12日
联系我们

联系我们

025-52349561

邮件:market@jsecode.com

时间: 8:30-18:00(工作日)

申请体验
TOP