作者:

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

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

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

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

编者按

众所周知,交通供需存在时间和空间上的不匹配的现象,某一时刻城市内一部分地区车辆供过于求的同时,另一部分地区可能存在车辆空驶的状况。随着近年来全球定位系统(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滴滴:基于最小车队的动态车辆调度

相关资讯

  • 货车司机频见阳性!防护指南来了!

    货车司机频见阳性!防护指南来了!

    期有多地发现货车司机新冠阳性病例。货车司机长期奔波在不同的城市,有一定的感染风险。记者邀请南京疾控专家科普货车司机怎样做防护。 01 上岗工作前:全程接种新冠疫苗,健康监测做到位 开展自我健康监测,配合核酸检测,自我核查健康码和行程码;按规定全程接种新冠病毒疫苗,符合条件的需尽快完成同源加强免疫或序…

    行业资讯 2022年4月13日
  • 最懂商用车的狮桥,在智慧物流上下了一盘什么棋?

    最懂商用车的狮桥,在智慧物流上下了一盘什么棋?

    智慧物流要由量变走向质变,离不开相关技术的突破,比如5G、大数据、人工智能等,尤其是干线物流中的自动驾驶货车、支线物流中无人机送货等何时能大批量商业化落地,或将成为整个行业质变的一个关键点,而如今这一场景正在加速到来。 12月8日,商用车智慧服务平台狮桥联合百度,一起推出自动驾驶货车领域技术平台新公…

    行业资讯 2022年9月15日
  • 特斯拉 FleetAPI 新增支持 Powerwall 能源系统等产品,便于开发者创建第三方应用

    特斯拉 FleetAPI 新增支持 Powerwall 能源系统等产品,便于开发者创建第三方应用

    特斯拉 Tesla Energy 近期在 X 平台发布贴文,宣布 FleetAPI 现已支持 Powerwall 能源系统、solar 太阳能板及 Wall Connector 壁挂式连接器。 IT之家此前报道,特斯拉在…

    行业资讯 2024年1月11日
  • 车队主管的一天

    车队主管的一天

      “以车队为家,以服务为乐”是昆明官渡环卫一体化项目车队主管李崇云的工作写照。从业10多年,李崇云从一线驾驶员做起,全心投入到官渡区的城市服务工作中,多次荣获“城市美容师”“先进个人”等称号。   01   24小时待机,一片公心成车队“管家”   李崇云负责侨银股份昆明官渡环卫一体化项目官渡片区…

    行业资讯 2022年6月24日
  • 面向下一代移动出行,采埃孚在全球技术日上发布多款创新技术

    面向下一代移动出行,采埃孚在全球技术日上发布多款创新技术

    为更好推动“下一代出行”战略的实施,采埃孚正通过技术和产品组合的多元化,加速新技术布局。完成对威伯科的整合之后,采埃孚也期望打通不同细分市场,在乘用车和商用车领域实现技术共享。 不久前,采埃孚在其德国简孚森(Jeversen)测试场举办了全球技术日。采埃孚集团首席执行官沃夫翰宁·施艾德 (Wolf-…

    行业资讯 2022年7月29日
  • Wejo与丰田达成数据协议

    Wejo与丰田达成数据协议

    据外媒报道,互联、电动和自动驾驶汽车(AV)数据的云和软件分析公司Wejo Group Limited(Wejo)宣布与丰田北美公司(Toyota Motor North America)达成数据协议。凭借该协议,Wejo将为美国云连接车队车辆提供个性化的互联车辆数据服务。 Wejo将收集丰田车队互…

    行业资讯 2023年1月12日
联系我们

联系我们

025-52349561

邮件:market@jsecode.com

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

申请体验
TOP
XML 地图 | Sitemap 地图

欧洲杯买球官方官网