文章转自滴滴科技合作（ID: didioutreach），
原文链接：NeurIPS 2019论文解读 | 北邮X滴滴：基于最小车队的动态车辆调度
张文琦（北京邮电大学博士研究生）
李晶晶（北京邮电大学硕士研究生）
王强（北京邮电大学副教授，博导），研究方向：移动网络、信息理论、机器学习和智能决策系统
石东海，滴滴惠普产品技术负责人、高级技术总监
众所周知，交通供需存在时间和空间上的不匹配的现象，某一时刻城市内一部分地区车辆供过于求的同时，另一部分地区可能存在车辆空驶的状况。随着近年来全球定位系统（GPS）、无线通讯工具以及人工智能技术的发展，我们是否可以进行更好的规划，在维持车队规模一定的情况下，对这些空驶车辆进行有效指引以减少空闲率、提高司机收入并改善用户体验呢？滴滴出行惠普产品的石东海团队以及北极邮电大学王强团队对此合作探讨，结合强化学习算法进行调度优化，仿真验证显示效果显著。
由于交通供需之间的不匹配，大城市的车辆共享平台效率有很大提升空间。随着全球定位系统（GPS）和无线通信工具的发展，车辆共享平台可以充分利用空闲车辆来缓解供需之间的差距。
针对如何对空驶车辆有效指引以减少空闲率，同时研究城市承运中不同车队规模时的效率，滴滴出行普惠产品技术部负责人石东海团队和北京邮电大学王强副教授合作探讨，联合提出了一种基于最小车队的动态车辆调度方法，模拟实验得到了AI Labs的环境支持。
首先，在已知车辆共享网络情况下，采用二部图匹配算法获得所需的最小车辆数。然后，为了平衡实时交通中交通供需之间的失配，提出了深度强化学习算法DDQN（Dueling Deep Q-Network ），以有效地使用有限的车辆。DDQN能够估算供需之间复杂的动态关系，因此可以根据DDQN的调度政策将可用车辆调度到需求量大的地方，从而缓解供需之间的差距。最后，我们设计了一个模拟器来训练和测试决斗的深度强化学习算法。仿真结果证明算法在订单响应率和司机计费时长占比方面有显著改进，可以提升司机收入、改善用户体验。
1研究背景
在线乘车共享服务由于其便利性和灵活性而受到了许多研究者的追捧。随着全球定位系统（GPS）和无线通信工具的发展，车辆共享平台能够充分利用道路上的车辆，这不仅能提高交通资源的利用率，还能够有效缓解交通拥堵和交通供需之间的差距。因此如何最好的规划和管理共享平台中的车辆就变得尤为重要。在已知车辆共享网络的情况下，采用二部图匹配算法最小化所需车辆数，并提出DDQN算法来将可用车辆分配到实时交通需求较大的地点已达到缓解供需之间差距的目的。
2问题挑战
在当前的研究背景下，本论文提出了一种深度强化学习算法DDQN。在算法设计的过程中，我们面临的挑战主要是如何有效地分配有限的车辆，以满足更多需求。由于在车队管理过程中，调度政策的变化将很大程度上影响到未来的供需情况，我们需要保证调度的有效性。
3解决方案
本论文基于滴滴平台中真实的数据，包括道路信息、时间估计以及订单数据，设计基于 DDQN的强化学习算法对车辆进行动态的调度策略。
本论文主要解决两个方面的问题，1）最小车队问题，在订单信息已知的情况下最大程度地减少所需车辆的数量；2）可用车辆调度问题，根据深度强化学习的策略，将可用车辆派往需求量大的地点来最大程度地提高响应率。
1最小车队问题
根据订单数据，构建一个车辆共享网络，由于时间的方向性，它是一个有向无环图。图中的每个节点代表一个行程，图中的边表示两行程之间的可连接。由于是个有向无环图，我们可以将图分解为一个二部图，此时最小车队问题就转化为二部图最大匹配问题。通过二部图匹配算法就可以得到车辆共享网络的最小车队数量，图1展示了执行算法后得到的最小车队数和真实情况的对比，可以看到所需的车队数量有了明显的减少。
图1 每小时完成所有订单所需的最少车辆数量
图2 乘客忍耐时间与所需最小车辆的关系
2可用车辆调度问题
在一个调度的时间线里，首先根据历史信息生成订单，其次更新可调度车辆分布，再次根据决策策略进行空闲司机调度，最后进行派单。调度的时间线流程如图3所示。
图3 调度时间线
我们使用DDQN模型来对共享网络中的可用车辆进行合理的调度和管理。在DDQN模型中， DDQN由状态、动作、奖励和状态-动作值（Q值）组成，空闲驾驶员（可用车辆）作为代理人。DDQN的目标是从初始状态开始获得最大化长期累积报酬的最优策略。在每次调度的过程中，每个空闲驾驶员都从状态空间观察一个状态，然后根据策略，每个空闲驾驶员都从动作空间选择一个动作执行。具体动态过程如图4所示。在DDQN中，我们采用Dueling结构对各个状态进行动作选择，这样可以提高算法的稳定性。
图4 调度/管理可用车辆的动态过程
4实验与结果
在该实验中，本论文的数据集来源于滴滴出行的脱敏数据，可用车辆调度的实验数据包括北京核心区连续三周的车辆和订单数据。订单数据集包含上/落客时间和上/落客位置（经纬度）。车辆数据包含每几秒钟更新的位置（经纬度）和状态（在线和离线）信息。通过对比模拟器方法、随机方法和Q-Learning的方法，证明了我们提出的方法在订单响应率和司机计费持续时间占空比方面有显着改进，如表1所示。
表1 模型的实验结果对比
论文核心贡献者
张文琦
北京邮电大学博士研究生
王强
北京邮电大学副教授/博导
研究方向包括移动网络、信息理论、机器学习和智能决策系统
李晶晶
北京邮电大学硕士研究生
石东海
滴滴普惠产品技术负责人、高级技术总监
閱讀更多 運籌OR帷幄 的文章
