学术成果 | 基于强化学习方法优化出租车司机行驶策略

基于强化学习方法

优化出租车司机行驶策略

内容导读

出租车是大城市的一种重要的交通出行模式，但乘客与出租车在时空分布上的不匹配严重降低出租车的服务效率，也影响出租车司机的收益。尽管打车App软件和一些推荐方法可以帮助司机尽快找到乘客，但是出租车司机的运营是多次载客的长序列，当前一次“好”的载客却可能导致后续的长程空载。出租车司机的最终收入将取决于一个工作周期内总的载客里程。司机在任意时刻和位置上，根据当前状态都有载客、空驶和等客三种可能的选择，每次选择的结果不仅决定当前的收益，也将影响后续的一系列收益。因此，需要从整个工作周期内的全局累计收益出发，评价每次策略选择的价值，最终实现整体收益的最大化。

 本研究在“理性人”假设下，不涉及伦理道德，建立出租车司机行驶策略的最优化方法。将一个工作周期内司机的动作选择序列形式化为一个马尔可夫决策过程，以累计收益最大化为目标，采用强化学习方法从海量出租车轨迹数据中学习最优行驶策略。该方法将有益于提升出租车司机收入，改善出租车服务效率。

方法

本方法的目标，是通过出租车的运行轨迹和状态序列，寻找在任意位置和状态下具有最大期望收益的行车策略。其中，行车策略是出租车司机在当前位置和状态下的动作选择，包括载客、空驶和驻车等客三种选择。不同的动作选择会产生不同的即时收益，同时也决定后续行为（如行车方向），并转移到新的状态。每一个策略的价值并不仅仅由它带来的即时收益决定，也取决于该策略导致的下一状态对应的期望收益，而最终的目的是获取使总体收益回报最大的每一位置上的动作选择。

基于强化学习，智能主体（agent）是给定环境（environment）内的决策者，环境在任意时刻具有状态（state）。当主体基于当前状态从动作集中选择一个动作（action），环境转移到新的状态，并产生奖励（reward），主体基于新状态选择新的动作，据此迭代。通过最大化期望累计奖励，主体最终找到一个动作序列作为最优策略（policy）。

给定时刻t，策略π是状态s到动作a的选择概率的映射：

策略的期望价值由值函数（value function）评价。将动作序列表示为一个马尔可夫过程（MDP），t时刻的期望价值由当前的即时奖励和后续延迟奖励两部分构成：

其中a'是在后继状态s'下的动作，R为奖励，γ为奖励衰减系数。

寻找最大化值函数的策略为最优策略，基于MDP和Bellman公式，可以将其近似为状态-动作值的迭代过程：

其中，p(s',r|s,a)是在状态s下执行动作a时转变到状态s'并获得奖励r的概率，而即时奖励r表示为 R(s,a)=E[R_t+1|S_t=s, A_t=a]。

该最优化问题采用Q-learning算法求解，状态-动作值在学习率η∈[0,1]下迭代计算：

建模

基于强化学习方法，将研究区域离散化为规则格网，作为环境；出租车（司机）是在其中活动的智能主体；出租车司机在格网单元中的动作选择就是一种策略，产生的载客收入为收益回报或奖励；以1天为一个工作周期，出租车行驶过程表达为一条轨迹；每一次行车轨迹就是一次探索，对应的整体收益为这次探索的累计奖励。根据累计奖励，可以后推轨迹途经的格网单元上所采取的策略的价值。通过多次轨迹探索，不断修正格网的价值，直到稳定为止。最终，每个格网都有三个得分值，分别是选择空驶、选择载客和选择等客三种策略的期望累计奖励，得分越高的策略，长远来看收益也就越大。所以当出租车到达某一位置时，通过选择得分最高的策略，达到行驶和运营优化的目的。

(1) 状态描述

智能主体的状态包括出租车所处的空间位置和行车状态，前者由格网坐标表示，后者包括载客、空车和驻车三种状态，即{occupied,vacant,parking}。最终，环境中的出租车共有N×3种可能的状态，其中为N格网数目。

(2) 动作空间

环境内的智能主体在每个格网单元上有3种可能的动作选择：载客、空驶和等客，即{empty_driving,carrying_passengers,waiting}。主体的动作选择依赖其状态，并决定其后续行为和状态（如图1)。给定时刻t，出租车位于格网单元p，并具有当前状态s_t，则动作集依据两种情况定义：

I. 如果s_t∈{vacant, parking}，则出租车司机可以选择三种动作的任意一种：a) 如果选择empty_driving，那么其行驶方向可以是p的任意邻居{p1, p2, …}之一，则后续动作集为A₁={p₁, p₂, …|s_t+1=vacant}； b) 如果选择waiting，则位置不变，后续动作集为A₂={p|s_t+1=parking}；c) 如果选择carrying_passengers，那么下一个位置是乘客目的地p_d，则 A₃={p_d|s_t+1=occupied}。II. 如果s_t=occupied，司机在到达乘客目的地 p_d之前不能进行动作选择，则轨迹上每个位置的后续动作集都是A₄={p_d|s_t+1=occupied}。

图1 基于状态的动作集

(3) 奖励函数

奖励函数评价每个动作选择的即时奖励，模型最终的优化目标是最大化即时奖励的累计值。综合考虑载客收入和空载成本，定义有效行驶里程比作为即时奖励函数：

其中d_o为本段载客里程数，d_e为从上次载客结束到本次载客开始出租车累计空载里程数，即寻客里程。该指标能够直观的反映载客和空载所带来的影响，当一段较短的载客里程需要很长的寻客路程时，降低这次载客的奖励。如果司机在某一状态选择空驶或等客动作，有效行驶比为0，则即时奖励为0；选择载客动作，则即时奖励为R。

(4) 策略学习

假设出租车轨迹是彼此独立的，那么对环境的探索就是一系列独立轨迹的随机实验。在一个网格单元内，每条轨迹可能具有不同的状态。状态由相应的动作产生，即carrying_passengers产生occupied，empty_driving产生vacant，waiting产生parking。在学习阶段，对每条轨迹采用贪心搜索的方法，每个格网单元的状态-动作值是从当前位置到轨迹结束时的累计奖励。尽管每个出租车司机在给定位置的动作选择并一定是最优的，但经过足够数量的轨迹探索，该位置上某个动作的最终累计奖励值可以认为是对该动作收益的具有统计意义的有效估计。对于每个格网单元，使用Q-learning算法，分别迭代计算三种动作选择的累计奖励，直至基于给定阈值δ收敛：

在策略应用阶段，司机在初始位置依据状态选择具有最大累计收益的动作。(1) 如果选择empty_driving，将具有最大累计收益的相邻网格作为下一步的目标位置，并在新位置开始新一轮搜索。如果在这一个过程中有乘客打车，则会中断该过程，因为原则上不能拒载，于是状态转变为occupied后，开始新一轮搜索(2) 如果选择carrying_passengers，则直到到达乘客目的地后，再开始新一轮搜索。如果当前位置没有乘客，carrying_passengers无法执行，则选择次优动作。(3) 如果选择waiting，则出租车停留在原位置，直到因有乘客打车而改变状态，开始新的搜索。

应用实例

使用北京市2013年11月12,000辆出租车的GPS轨迹数据，其中出租车状态每分钟采样一次。将北京地区划分为500m×500m的均匀格网，然后删除没有道路通过的格网单元，最终剩余34,850个格网单元。出租车GPS轨迹经过预处理后，以天为单位划分轨迹，轨迹上的每个GPS点根据记录标记为occupied、vacant和parking三种状态之一，最终产生371,189条有效轨迹。

前20天的轨迹数据作为训练集，其他轨迹数据作为测试集，使用Q-learning算法计算每个位置上三种动作选择的累计奖励的评分值，如图2所示。

图2 三种动作选择评分的空间分布：

(a) empty_driving, (b) carrying_passengers, (c) waiting

在每个格网单元内，取评分最高的动作作为其最优策略，在测试集上的模拟实验验证该结果具有86.3%的精度。最优策略的空间分布如图3所示。城区内三种动作的评分都相对较高，其中载客策略在大部分区域都高于其他两种选择。空驶通常是外围环路和高速公路周围的最佳选择。优先等客的区域相对较少，主要分布在机场和交通枢纽附近。而在火车站周围，载客和等客具有相近的期望收益。在大多数区域，空车寻客比驻车等客具有更好的期望收益。

图3 最优策略的空间分布：(a) 北京，(b) 六环内区域

改变奖励函数的形式，可以使用该方法寻找其他优化目标的策略。以最小化空载为目标，定义即时奖励函数为R=-d_e，可以评价每个位置上潜在的累计空载里程，帮助司机评估后续空载的风险(图4a)。以最大化载客为目标，定义即时函数为R=d_o，可以评价每个位置上潜在的长程载客(图4b)。

图4 其他优化目标的策略：

(a) 最小空载里程期望的空间分布

(b)最大载客里程期望的空间分布

结语

基于强化学习方法优化出租车司机的行驶策略，既有益于改善出租车司机的运营收入，也有利于出租车服务供给和需求的时空平衡，进而提高城市交通运行效率。该方法目前并没有考虑出租车之间的交互和影响，也没有考虑环境状态实时动态变化下的策略调整，这些是需要进一步研究的问题。

参考文献

Yong Gao, Dan Jiang & Yan Xu (2018). Optimize taxi driving strategies based on reinforcement learning. International Journal of Geographical Information Science, 32:8, 1677-1696. 

DOI: 10.1080/13658816.2018.1458984

素材来源：S³-Lab

材料整理：高   勇

内容排版：王   晗

点击“阅读原文”查看相关文献