详情

原文传递基于强化学习的网约车自适应匹配时间策略研究

论文题名：	基于强化学习的网约车自适应匹配时间策略研究
关键词：	空车调度;网约车;自适应匹配;强化学习;马尔可夫决策
摘要：	随着共享经济的发展，网约车已经成为人们出行的重要方式，市场中有多个网约车平台，如滴滴出行、Uber等，网约车平台如何提高收益是较为关键的问题。在网约车的订单匹配过程中，司机与乘客总是动态到达，所以待匹配的司机和乘客数量时刻都在变化，而待匹配的司机、乘客信息越多，就越可能找到高收益的匹配组合。若采用固定匹配时间间隔的策略，就忽略了匹配过程中的适当等待能带来更高收益的可能性。此外，由于不同区域的待匹配信息不同，如果整个区域采用统一的匹配时间，就会忽略各个区域之间的待匹配信息丰富程度的差异，同样也会降低平台的总收益。为了能够找到合适的匹配时间点来提高平台的总收益，本文对网约车的自适应匹配时间策略进行了探讨，首先将网约车订单分配过程建模为马尔可夫决策过程(MDP)，并基于强化学习设计匹配时间策略，根据环境状态的变化实时调整匹配时间点。其次，考虑到多个区域的待匹配司机、乘客信息的差异，本文将整个区域划分为多个互不重叠的区域，基于多智能体强化学习实现多个区域差异化的匹配决策，使每个区域自主决定匹配时间。本文的主要工作如下：　　（1）本文首先介绍了网约车环境的基本设定，包括对订单的分配流程进行描述，并对参与订单分配的司机、乘客和平台的交互流程进行说明，同时本文将司机和订单进行了符号化的描述，并给出了平台收益的计算公式。　　（2）为了实现在动态变化的环境中自主调整匹配时间，本文提出了动态匹配决策问题。因为每次待匹配的状态都是基于上一次的匹配状态而得到的，所以该问题是一个序贯决策问题，本文将其建模为马尔可夫决策过程，并基于强化学习设计了DynamicMatchingDecisionProcess(DMDP)算法来解决该问题。最后以平台总收益、订单应答率、接单距离和平均每单额外距离作为对比指标，与RestrictedQ-Learning(RQL)、GREEDY和UNIFORM三个算法进行对比来验证DMDP算法的有效性。通过实验结果发现DMDP算法在平台总收益这一指标上表现最好，高出RQL算法2.55%，比GREEDY算法和UNIFORM算法分别多了15.13%和20.53%，在其他三个指标上也有不错的表现。　　（3）不同区域中所含待匹配信息的丰富程度不同，为了使这些区域能够进行差异化匹配，进而获取更高的收益，本文提出了多区域差异化匹配决策问题。按照待匹配信息的丰富程度将整个区域划分为多个不重叠的区域，多个区域相互协作并自主决策。由于该问题同样是序贯决策问题，本文也将其建模为马尔可夫决策过程，并根据多智能体强化学习提出基于多区域的Multi-RegionalDifferentiatedMatchingDecisionProcess(MRDMDP)算法解决该问题。此外，划分区域可能会造成一些区域中出现空闲车辆，降低车辆资源的利用率，本文进一步地提出空车调度Repositioning(REPOS)算法，通过将空车调度算法与基于多区域的算法进行结合可以解决划分区域后空闲车辆过多的问题。本文设计了对比实验来验证MRDMDP算法的效果，将它与其他多区域算法进行对比。通过实验分析发现，相比于Multi-RegionalRQL算法、Multi-RegionalGREEDY算法和Multi-RegionalUNIFORM算法分别能提高4.33%、19.63%和31.15%的平台总收益。实验结果表明使用空车调度算法解决区域中的空闲车辆较多的问题后，平台收益还能得到进一步地提升，在多个结合调度的多区域算法中，MRDMDP_REPOS算法能够获得最高的平台总收益，比其他三个算法分别提高了3.41%、11.91%和22.69%。　　本文对网约车环境下匹配时间策略进行分析，提出了动态匹配决策问题并基于强化学习设计了DMDP算法，该算法能够根据环境的变化调整匹配时间，提高了平台的总收益。接着讨论对匹配信息不同的区域差异化匹配时间的问题，本文基于多智能体强化学习设计了MRDMDP算法实现多个区域的协同合作，对不同的区域进行差异化的匹配决策，更进一步地提高平台的总收益。本文工作将为网约车平台设计匹配时间策略提供一定的指导。
作者：	邓亚平
专业：	计算机科学与技术
导师：	石兵
授予学位：	硕士
授予学位单位：	武汉理工大学
学位年度：	2022