基于深度强化学习的网约车动态路径规划

郑渤龙 明岭峰 胡 琦 方一向 郑 凯 李国徽

1(华中科技大学计算机科学与技术学院 武汉 430074) 2(香港中文大学(深圳)数据科学学院 广东深圳 518172) 3(电子科技大学计算机科学与工程学院 成都 610054)

网约车平台，如滴滴出行和优步等，允许用户在手机app或小程序上发起打车请求，由平台通过智能算法将请求与空闲的网约车进行匹配，在近年来得到了快速发展.一方面，与传统的司机在街道上寻找乘客的模式相比，网约车平台有效地减少了网约车的空驶时间，提升了司机的收益，并大大减少了乘客打不到车的情况，提高了城市交通系统的运行效率.另一方面，这些网约车平台积累了大量的包含乘客的出行模式等信息的数据，例如轨迹数据和订单数据，这些数据可以进一步用于交通领域的许多应用，如需求预测、订单分派和车队管理.

作为网约车平台的核心模块，网约车路径规划需要管理城市中的所有网约车，为空闲网约车指派巡航路线，将其调度到潜在的乘客位置，同时又要协调各辆网约车，防止其相互之间竞争乘客，以充分利用有限的网约车资源，平衡网约车的供应与乘客的打车需求之间的差距.然而，现实情况是，尽管在需求端每天有数万请求通过网约车平台进行处理，但仍然有许多的打车请求由于附近没有空闲网约车而未能及时处理，或是需要等待很长的时间才能打到车.而在供应端，依然有相当一部分的网约车无法接到乘客，需要空驶很长一段时间才能找到合适的乘客.这种供需不平衡的现象在大城市中每天都在发生，这既降低了平台的收益，也影响了用户的体验，并进一步导致了交通拥堵和资源浪费.因此，有效的网约车路径规划对网约车平台有着重要的意义.

制定有效的网约车路径规划策略主要存在3项挑战：1)需要对动态变化的供需分布进行建模，以准确预测每个区域对网约车资源的需求；2)需要防止空闲网约车聚集在热门区域，而导致这些区域出现运力过剩，而其他区域又运力不足的情况；3)需要考虑处于偏僻区域的网约车，让其能更快驶离当前区域，从而减少无效的巡航时间.

现有方法通过对历史网约车数据进行建模来解决上述挑战.RHC通过构建供需模型调度网约车以应对静态交通环境.深度强化学习(deep reinforce-ment learning, DRL)算法可以处理动态的交通环境，具有更好的性能.但是DRL算法在建模时面临着简化设定的问题，例如，大多数DRL算法都假设所有空闲网约车同时进行调度，并且假设网约车能够在下一时间片到达调度终点，而这在实际交通环境中是不可能的.而本文的调度策略会在网约车空闲时立即对其进行路径规划，不存在不合理的假设，更贴近真实的交通环境.

相比基于值函数的算法(如deep Q-network, DQN)，actor-critic采用策略梯度的算法可以在连续动作空间或高维动作空间中选取合适的动作，而这是基于值函数的算法无法做到的；相比单纯策略梯度的算法，actor-critic采用类似DQN的策略评估算法，可以进行单步更新而不是回合更新，比单纯策略梯度的算法更有效.因此，本文基于actor-critic的算法，提出了一种供需感知的深度强化学习算法，用于网约车调度.首先，通过定义智能体、状态、动作和奖励，将网约车路径规划问题转化为一个Markov决策过程(Markov decision process, MDP).然后，设计了一个具有动作采样策略的执行者-评论者(actor-critic with action sampling policy, AS-AC)网络结构，以学习最佳的调度策略.

本文的主要贡献包括3个方面：

1) 提出了一个基于实时供需状态的动态网约车路径规划框架，实现高效的大规模空闲网约车调度，通过包含实时的供需信息来适应动态变化的环境.

2) 设计了一种带有动作采样的AS-AC算法来选择可行的动作，增加了动作选择的随机性，从而有效地防止竞争.

3) 使用真实的网约车订单数据进行了大量实验，实验结果表明提出的方法相比对比方法有着更低的请求拒绝率.

1 相关工作

1.1 车队管理

车队管理是网约车平台的一项主要决策任务，它包括确定车队的规模和配置、车队分配、车辆路线规划等，这些都广泛应用于交通运输中.其中网约车路径规划是车队管理问题的核心任务，许多研究致力于有效地解决此问题或其变体，例如车辆路由问题(vehicle routing problem, VRP)、最小车队问题(minimum fleet problem, MFP)和乘车问题.大多数方法首先将这些问题转换成经典的图论问题，然后采用组合优化的方法去求解.例如，Vazifeh等人将最小车队问题建模为二部图上的最大匹配问题，然后采用Hopcroft-Karp算法确定服务所有订单所需的最小车队的规模.

随着网约车服务的普及，调度城市中的空闲网约车以平衡不同位置的供需成为一个新的研究热点.许多工作对城市中的网约车供需进行建模，调度空闲网约车来平衡供需，以最大程度地减少乘客的等待时间和网约车的空驶时间.例如，文献[18]将网约车调度任务建模为最小费用流(minimum cost flow, MCF)问题，并使用组合优化的方法对其进行求解.后退水平控制模型根据供需模型和网约车的实时位置来调度网约车，以减少网约车空驶的距离.然而，这些基于模型的方法局限于预先确定的供需模型，因此难以适应车辆状态和出行请求都在不断变化的真实交通环境.

1.2 深度强化学习

深度强化学习将具有强大感知力的深度学习方法和具有优秀决策力的强化学习方法相结合，通过试错的方式来学习智能体在观测状态下应采取的最佳动作.DRL利用神经网络来估计状态动作值，并通过更新网络参数来学习最佳行为策略，已经在许多具有挑战性的领域取得了突破性的进展，例如，围棋、电子游戏和自动驾驶.然而，主流的深度强化学习算法，如DQN和Reinforce主要适用于低维度且样本容易获取的任务，而在高维和非静态的动作空间中表现不佳.本文通过实时的供需估计和巧妙的采样策略，运用深度强化学习算法来解决网约车路径规划问题.

1.3 基于深度强化学习的网约车路径规划

由于网约车路径规划这一决策任务可以很自然地建模为Markov决策问题，许多最近的研究都致力利用深度强化学习设计模型无关的方法来调度网约车.这些方法可以分为基于值函数的方法(如DQN)和基于策略梯度方法(如A3C).基于值函数的方法主要使用DQN来估计动作的价值，通过神经网络计算出动作价值，然后选择价值最大的动作.例如，MOVI通过卷积神经网络(convolutional neural network, CNN)来提取供需分布特征并采用分布式的DQN策略学习单独的车辆的最优调度动作.COX采用聚类算法将路网划分为许多用于网约车调度的区域，再通过环境感知的需求预测模型和实时的网约车状态来计算区域级别的供需，最后将这些供需信息加入到状态中，提高DQN的表现.与基于值函数的方法不同，策略梯度方法用神经网络来近似策略，采用梯度上升法来寻找最优策略.例如，CoRide将订单调度和车队管理概述为部分可观测Markov决策问题(partially observable Markov decision process, POMDP)，然后采用深度确定性策略梯度(deep deterministic policy gradient, DDPG)算法来学习订单匹配和车队管理的最优策略，以最大化累积司机收入(accumulated driver income, ADI)和订单应答率(order response rate, ORR).文献[11]在求解动作空间时考虑了地理环境和协作环境，消除了无效的网格从而减小了动作空间，并提出contextual actor-critic多智能体强化学习算法用于网约车学习行为策略.

尽管这些方法相比基于模型的方法有着更强大的能力以适应复杂动态的交通环境，它们仍然受限于不现实的问题设定.例如，大多数方法要求所有的网约车在每个时间片同时进行调度决策，并要求网约车能在下一时间片到达调度终点，这在现实的动态交通场景中很难保证.此外，只把邻居网格作为动作空间会使得处于偏僻区域的网约车很难尽快驶离这些区域.与现有的方法不同，本文不对所有的网约车进行统一调度，而是将每一辆网约车看作单独的同质智能体，共享网络参数和调度策略，当一辆网约车变为空闲状态时立即对其进行调度.此外，提出的供需感知的强化学习方法采用变化的动作空间来代替静态的动作空间，在以邻近网格作为可行调度动作的基础上加上了全局热门区域，并采用动作过滤和采样来平衡全局供需分布.本文的框架在网约车变为空闲时就为其分配搜索路线，并激励网约车在其到达调度终点前尽快被分配请求，更接近真实的交通场景.

2 网约车路径规划问题

本节将介绍网约车路径规划问题的背景，包括问题设置、问题定义和框架概述，并将该问题描述为一个Markov决策过程.表1总结了本文常用的符号.

Table 1 Summary of Notation

2.1 问题叙述

网约车路径规划问题由空间中的一组网约车车队、流形式的请求和一个管理所有网约车的调度中心所组成.

定义3.

调度中心

.

调度中心包括3个模块：车队管理模块、请求预测模块和调度策略模块

.

车队管理模块跟踪每辆网约车的实时位置和占用状态，并更新供应分布

.

请求预测模块根据历史订单信息预测未来的乘客请求分布

.

调度策略模块基于供需分布将空闲的网约车调度到未来请求可能出现的位置

.

(1)

给定一组网约车和一个乘客请求流，调度中心需要为空闲网约车规划巡航路线以使得其能够尽快服务潜在的请求，从而最小化请求拒绝率

.

2.2 框架总览

ST-GCSL模型将请求预测问题建模为图节点预测问题，采用图神经网络技术，同时提取短期与长期时空依赖关系，具有很高的预测精度.因此，在框架中，使用ST-GCSL作为请求预测模型.具体而言，使用Uber H3库将城市路网划分为一组六边形网格

G

={

g

,

g

,…,

g

||}；将一天划分为一个时间片序列，表示为

T

={

t

,

t

,…,

t

||}

.

如图1所示，车队管理模块跟踪网约车的实时位置，以获取下一个时间片网约车供应量，而请求预测模块则根据历史的请求时空分布，预测未来的网约车需求分布.供需感知的深度强化学习调度策略将供需结合起来，以确定空闲网约车的调度动作，然后网约车将会朝着调度终点巡航.对于收到的新请求，调度中心分配最近的空闲网约车为其服务.当网约车被分配给一个请求后，它会首先沿着最短路径前往请求的起点去接乘客，然后驶向请求的终点以完成服务.如果一个请求在其最长等待时间内都没有被分配给网约车，则该请求将被拒绝.

Fig. 1 Interaction between taxis and passengers with the dispatching center图1 网约车、乘客在调度中心下的交互

2.3 Markov决策过程的构建

本文将网约车路径规划问题建模为Markov决策过程(MDP).具体地，将网约车视为与外部环境交互的智能体，并将每次路线规划看作是一次决策.采用六边形网格划分空间对动作空间进行离散化.如图2所示，将空闲网约车调度到目标网格视为是一个动作.

Fig. 2 An example of MDP formulation图2 一个MDP叙述的例子

MDP包含状态、动作、奖励、回合、策略和状态-动作价值函数6个关键元素.

(2)

(3)

2) 动作

a

∈

A.

动作

a

=〈

g

〉是指将空闲网约车派往某个特定的目的网格

g

.

所有可行的动作组成了动作空间，用

A

表示

.A

包括当前区域的

k

-阶邻居区域中需求与供应之差大于当前区域的所有区域和全局的热门区域

.

因此对于不同的供需状态

s

，动作空间

A

也是不同的

.

值得注意的是，由于网约车在调度的执行过程中也可以接单，因此其并不一定能到达调度终点(中途被分配给请求)

.

3) 奖励

r

.

使用文献[8]中有效行驶比作为即时奖励，其定义为：

(4)

其中,

d

为调度过程的持续时间，该过程从网约车空闲开始到乘客下车结束；设

d

为调度过程中乘客乘坐网约车的持续时间

.

式(4)计算的奖励

r

考虑服务请求的收入和空闲巡航的成本

.

注意到较大的

r

表示网约车在短时间闲置后迅速分配给乘客，因此获得的奖励很高

.

如果网约车到达调度目的地时未分配任何请求，则奖励为0

.

4) 回合

.

在该问题设定中，一个回合是从8∶00到22∶00的繁忙时段

.

因此，时间

t

在22∶00之后的状态为终止状态

.

5) 策略

π

(

a

|

s

)

.

策略函数表示从状态到可行动作

A

的概率分布的映射

.

对于确定性的策略，输出是一个特定的动作

.

通过深入的与环境进行交互，代理旨在学习到一个最优的策略

π

，以最大化预期奖励

.

6) 状态-动作价值函数

Q

(

s

,

a

)

.

状态-动作价值函数是司机从状态

s

开始，执行调度动作

a

，并且之后按照策略

π

执行调度动作，直到回合结束能得到的奖励和的期望，由于使用有效性行驶比作为奖励，因此

Q

表示的是预期累积有效行驶比，定义为

(5)

其中,

t

表示当前时间片，考虑到短期的奖励的影响更大，估值也更准，这里加入参数

γ

作为未来奖励的折扣因子，以对长期的奖励进行衰减

.

更具体地，在图2中给出了上述MDP概述的一个例子

.

在时刻

t

，一辆处于状态

s

的空闲车辆被指派了一条从网格0到网格17的搜索路线，执行前往网格17的动作

.

当它行驶到网格6时，在网格16出现一个请求并且这辆车被分配给了这个请求

.

因此它前往该请求的位置去接乘客，然后驶向位于网格12的订单终点，获得对应的奖励

r

，并到达下一状态

s

′

.

3 供需感知的深度强化学习

本节介绍一种供需感知的深度强化学习算法，称为AS-AC算法.

3.1 动作空间的确定

首先，通过考虑以下2种类型的网格来初始化可行动作空间

A

：1) 地理邻居网格

.

为了确保合理的调度距离，选择当前网格的邻居网格

.

具体来说，在实验中选择了纽约数据集的三阶邻域和海口数据集的二阶邻域内的网格

.

2) 全局热门网格

.

在下一个时间片中预测请求数量最多的少数网格(纽约为5个网格，海口为3个网格)，因为大多数请求都出现在这些网格中

.

为了减少计算开销，需要从初始动作空间

A

中移除无效的动作

.

这是因为，如果当前网格的供需差大于调度目标网格的供需差，停留在当前网格更可能获得更高的奖励，并且可以减少调度开销

.

因此，可以从动作空间中删除这些调度动作

.

对于

A

中的每个网格

g

，首先根据式(2)(3)分别计算供应和需求，然后通过如式(6)计算供需差

ρ

：

(6)

最后，从动作空间

A

中移除供需差小于网约车当前网格的动作

.

3.2 AC模型

actor-critic(AC)算法结合了基于值函数的方法与基于策略梯度方法的优势，避免了低维度动作空间的限定，可扩展性更强.因此，使用AC模型学习得到空闲网约车的最佳调度策略，它通过调整策略网络的权重来适应动态变化的环境.不同于DQN采用价值函数来制订策略，AC采用一个叫做actor的策略网络来直接近似策略，用于选择动作，用一个称为critic的价值网络来评估所选择的动作.相比基于值函数的方法，它不仅能够实现更稳定的学习过程，还适用于高维度或连续的动作空间.

本文采用了2种技术来提升网络的性能：1)对于critic网络，类似DQN，采用原始和目标2个相同的价值网络来实现周期稳定更新；2)通过嵌入地理邻居和供需差来过滤无效动作使得能够调整策略以适应动态变化的动作空间.

出台《松江区关于推进公共图书馆总分馆制建设管理暂行办法》，整合区内公共阅读资源，实行总馆主导下的统一文献资源目录、统一编目、统一配送、通借通还和人员培训。总馆对分馆加强业务指导，分馆按照总馆服务标准，对辖区内基层服务点实施业务考核、绩效管理、采编目录等方面的统一管理。制定《松江区公共图书馆服务规范》，规范服务项目，完善内部制度，以区级公共文化“服务规范”，提升全区公共图书馆行业服务水平。

采用小批量反向传播算法训练网络，对于critic价值网络，如图3所示，根据贝尔曼方程得到时序差分误差，以此平方作为损失函数：

(7)

(8)

θ

←

θ

+

α

∇

L

(

θ

),

(9)

其中，

α

是critic网络的学习率

.

价值网络的输入为智能体的当前状态

s

，输出为常量

V

(

s

;

θ

)表示当前状态价值

.

Fig. 3 The structure of critic network图3 Critic价值网络结构

对于actor策略网络，如图4所示，采用第3.3节提到的动作采样策略替换传统actor网络最后的softmax层.为了减小动作选择的方差，引入了一个优势函数来代替critic网络中的原始回报，以衡量选取的动作值与所有动作平均值的好坏，用时序差分来近似优势函数，即：

A

(

s

,

a

)=

td

，那么策略网络的梯度为∇

J

(

θ

)=∇log

π

(

a

|

s

)

A

(

s

,

a

),

(10)

其中，

θ

是策略网络参数

.

根据计算得到的策略梯度，策略网络参数

θ

更新为

θ

←

θ

+

α

∇

J

(

θ

),

(11)

其中，

α

是actor网络的学习率

.

策略网络的输入为智能体的当前状态

s

，输出为数组

Q

(

s

;

a

)表示当前状态下执行所有动作对应的状态价值函数

.

Fig. 4 The structure of Actor network图4 Actor策略网络结构

① 初始化记忆库

M

的容量为

N

；

③ 初始化actor网络参数

θ

为随机值；④ for

m

=1 to

max

-

episodes

do⑤ 重置所有网约车为初始状态

s

；⑥ for

t

=1 to |

T

| do⑦ 对每辆空闲网约车生成并存储状态转移元组(

s

,

a

,

r

,

s

+1)到

M

；

⑧ end for

3.3 动作采样策略

在当前状态

s

下，为了得到具体的动作，基于状态-动作价值函数

Q

(

s

,

a

)从

A

中选择一个动作

.

然而，传统的“

ε

-贪婪”策略会以1-

ε

的概率选择价值最大的动作，导致大部分空闲出租车都前往热门区域，造成“羊群效应”，无法很好地对网约车进行协调

.

为了实现网约车之间的协调，采取了动作优先级采样策略，与文献[38]中基于时序差分误差的经验优先级采样策略不同，依据动作价值函数

Q

(

s

,

a

)对可行性动作进行采样

.

具体而言，对动作价值函数

Q

(

s

,

a

)做类似softmax处理，以确保动作被采样的概率与动作价值是单调递增的关系，同时确保最小价值的动作被采样的概率非零

.

具体地，第

i

个动作被采样的概率计算为

(12)

其中,

p

>0是

A

中第

i

个动作的优先级，而

τ

是确定使用多少优先级的参数，当

τ

=0时，对应于统一随机采样

.

对于优先级

p

，有如下2种变体：1) 比例优先级

.

其中

p

=

Q

(

s

,

a

)，它表示从

A

中根据状态价值成比例的采样动作

.

值得注意的是，由于基于排序的优先级对异常值不敏感，具有更好的鲁棒性，因此实验中默认选择其来制订采样策略，与对比方法进行比较，并且在实验中比较这2种变体

.

最终，根据动作采样策略从

A

中采样得到调度动作

.

3.4 调度地点确定

为了实现更加细粒度的供需平衡，使用文献[16]中供需分布不匹配度来确定每个空闲网约车的具体调度位置

.

对于调度位置

l

∈

a

.g

，令

x

(

l

)和

y

(

l

)分别为

l

处空闲网约车的数量和预测请求数量，则

l

处的供需分配不匹配度计算为

(13)

对于每次调度，从目的网格

a

.g

中贪婪地选择需求供应不匹配最小的位置作为调度目的地，然后网约车沿着最短路径前往目的地

.

当目的网格中没有空闲网约车时，选择该网格中心作为调度目的地，因为它能保证与网格中的其他位置距离不会过远

.

算法2中详细地介绍了AS-AC的执行过程

.

算法2.

AS-AC算法.输入：当前状态

s

；输出：一个调度动作

a

.

① 计算源动作价值

Q

(

s

,

a

),∀

i

=1,2,…,|

G

|；② 初始化动作空间

A

为地理邻居和全局热门网格；③ 从

A

移除无效的动作；④ 初始化大小为|

G

|的数组

F

，并设置

F

=1,∀

a

∈

A

；⑤ 通过状态-动作价值

Q

(

s

,

a

)×

F

对动作

a

∈

A

进行排序，并计算对应优先级；⑥ 根据式(12)采样一个动作

a

；⑦ return

a

.

4 实验与结果

解决交通问题的强化学习方法通常需要一个动态模拟环境用于训练模型和评估算法，采用并拓展了车队管理模拟器COMSET，以训练并评估调度策略.实验用Java实现调度策略和所有的对比方法，使用Python3.6和Tensorflow1.15.0来构建并训练模型，其中网络模型在一台装配有Nvidia Tesla P100 GPU和16 G内存的机器上训练.

4.1 环境模拟器与数据集

基于真实数据集，采用并拓展了能够模拟外部环境的COMSET模拟器训练DRL模型.该模拟器是对网约车平台如何管理网约车和处理乘客请求的整个过程进行建模.具体而言，在模拟开始时，根据输入的OSM JSON文件创建一个地图，并通过输入边界多边形对其进行裁剪.乘客请求从历史订单数据中读取，每一个请求对应一个历史订单记录，只保留上下车位置均在边界多边形范围内的请求，并按照上车时间的先后顺序以流的形式进入系统. 固定数量的网约车被部署在地图上的随机位置，并按照调度策略给出的搜索路线进行巡航.当请求进入系统后，控制中心为其分配最近的空闲网约车；网约车接受请求，前往请求起点接乘客，再将其送到请求终点，期间车辆都沿着最短路径行驶.更重要的，模拟器会通过历史订单数据校正每条路段的旅行速度，因此COMSET产生的平均旅行时间与真实数据基本一致.

本文采用纽约和海口2个真实网约车数据集评估模型，有关数据集的信息统计在表2中，值得注意的是每条订单记录包含起点与终点信息、订单类型、旅行时间、乘客数量等信息.

1) 纽约数据集.纽约黄色网约车订单数据包括了2016年1月到6月中上车和下车点均在纽约市的网约车订单，而路网数据来源于OpenStreetMap，其中包含了4 360个节点和9 542条边.选取2016年6月1日至21日数据用于训练模型，6月22日至28日数据用评估模型.

2) 海口数据集.海口数据来源于海口市2017年5月到10月的网约车订单记录，路网包含3 298个节点和8 034条边.选取2017年10月1日至21日数据用于训练，10月22日至28日数据用于评估模型.

Table 2 Dataset Statistics

4.2 对比算法与度量标准

通过实验对比以下6种算法的效果：

1) RD.从路网中随机选取一个节点作为目的地，选取从当前位置到目的地的最短路径作为搜索路线.

2) MCF-FM. MCF-FM根据权重采样的方法选择调度终点，并在每个时间片中对空闲司机进行统一调度.

3) FMU. FMU根据动态的节点权重进行采样，并为等待中的请求增加额外的权重.

4) Q-learing. 标准表格式的Q-learning学习一个含有“

ε

-贪婪”策略的

q

表

.

实验中，状态简化为只包含智能体的位置和时间，并设置

ε

=0

.

1

.

5) DQN. 状态、动作和奖励定义与本文一样，采取“

ε

-贪婪”策略选取

Q

(

s

,

a

)值最大的动作作为调度目的地，实验中

ε

=0

.

1

.

6) AS-AC. 本文提出的具有动作采样策略的供需感知的执行者-评论者方法.

为了评估上述算法，统一采用3种度量标准：

1) 拒绝率(reject rate,

RR

)，指被拒绝的请求数占请求总数的比例，它在所有度量标准中具有最高的优先级；2) 巡航时间(cruising time,

CT

)，指网约车从空闲状态到乘客上车的平均时间，由总的空闲行驶时间除以接收的请求数量得到；3) 等待时间(waiting time,

WT

)，指乘客从发出请求到司机到达上车点的平均等待时间，由总的等待时间除以请求数量.

4.3 实验参数与结果对比

由表2可知，纽约数据集的规模比海口数据集大很多，如果对海口数据集采用和纽约数据集相同的划分粒度，则每个分区的数据将十分稀疏.为了避免这一问题，根据数据集的规模调整时空划分的粒度.具体而言，在纽约和海口数据集上设定时间片长度分别为5 min和10 min；采用Uber H3库将纽约和海口路网分别划分为99和30个网格.每个请求的最大生命周期

t

=5 min，即乘客最多等待5 min，如果5 min内没有司机接单，则该请求被视为拒绝，并从系统中移除.对于提出的方法，其设定的参数如下：actor与critic网络(如图3、图4)均采用3层全连接层，每层包含128个隐藏单元，并采用ReLU激活函数.记忆库容量

N

=100 000，采样的批量大小

b

=64，critic中目标网络更新的周期

B

=1 000，折扣因子

γ

=0

.

9，学习率

α

=0

.

001，

α

=0.000 5.

为了验证方法的鲁棒性，在不同网约车数量下进行对比实验，实验结果如表3所示，其中每种度量标准的最佳结果用粗体表示.

Table 3 The Results on Two Real-World Datasets

续表3

Fig. 5 Comparison of variants on New York dataset图5 2种变体在纽约数据集上的比较

一般而言，网约车数量越多，可以服务越多请求，这样拒绝率(

RR

)、平均巡航时间(

CT

)以及平均等待时间(

WT

)都会降低.更具体些，可以从表3中得出以下4点结论：

1) MCF-FM和FMU相比于随机调度策略RD在所有的度量标准上都有很大的提升.这是因为MCF-FM和FMU均根据历史订单数据为节点分配合理的权重，直观上，热门区域具有较高的权重，再根据权重采样可以很好地平衡供应与需求.

2) 基于历史数据学习动作价值函数的Q-learning相比于RD也有所提升，但其提升的程度没有MCF-FM与FMU大，这是因为Q-learning的性能受限于确定性的状态空间，而由于交通环境的复杂性，实际产生的状态是无穷多的，所以表格式方法无法对其完整建模.

3) 虽然标准DQN算法也可以实现不错的效果，但是其采用的“ε-策略”会贪婪地调度车辆前往价值高的区域，这会导致大部分车辆前往热区，造成“羊群效应”，而在其他区域因车辆少而乘客请求得到不到服务，直至拒绝.所以其提升效果也受限.

4) 除了在网约车数量为1 000的海口数据集上，提出的AS-AC算法在所有度量标准上均实现了最佳的效果，提升程度最大.相比于MCF-FM,FMU和DQN等已有最佳方法，在不同数据集、不同网约车数量的情况下，AS-AC算法可以在拒绝率上最高提升0.3个百分点，巡航时间上减少0.1～4.6 s，乘客等待时间减少1.8～4.1 s.由于每天都有百万级别的订单产生，所以每一点提升都会带来巨大效益，可以大大减少能源消耗，减少交通拥堵现象，提升用户体验，提高平台收益.

4.4 动作采样策略的讨论

表3的实验结果表明了3.3节提出动作采样策略的有效性.同时，针对3.3节中提到的2种采样优先级变体，本节进行对比实验，以验证排序优先级的优越性.其中：

1) 采用比例优先级的AS-AC记为V1;

2) 采用排序优先级的AS-AC记为V2.

为了方便比较，将2个变体相对DQN的提升程度作为实验结果，如图5和图6所示.可以观察到：

Fig. 6 Comparison of variants on Haikou dataset图6 2种变体在海口数据集上的比较

1) 总体来说，对于每种变体，相比于DQN的提升程度随网约车数量的增加而增大，比如，在纽约数据集上，当车辆数量为3 000时，DQN的拒绝率为11.799%，而V1与V2相比于DQN分别提升0.453%和0.448%；当车辆数量增加到4 000时，DQN的拒绝率为2.485%，而V1与V2相比于DQN分别提升1.323%和1.383%.由此可以看出随着车辆数的增加，2种变体能更好实现车辆之间的协调；

2) 相比于变体V1，变体V2达到更好的效果.这是因为基于排序的优先级对异常值不敏感，具有更好的鲁棒性，因此其更加有效，并选取其作为默认的采样策略优先级.

5 结 论

本文提出了一种基于供需感知的深度强化学习模型用于网约车调度.该模型通过定义合适的智能体、状态、动作和奖励，将网约车路径规划问题转化为Markov决策过程，然后提出了一个具有动作采样策略的执行者-评论者网络结构(AS-AC)，以学习最佳的空闲网约车调度策略.实验结果表明，本文提出的供需感知的深度强化学习方法在不同数据集上均取得了比对比方法更好的表现，验证了执行者-评论者网络在协调网约车上的有效性，此外，通过对不同的动作采样策略进行对比试验，证明基于排序优先级的采样策略比采用比例优先级的采样策略效果更优.

在下一步工作中，可以采用多智能体强化学习的方法，以及考虑更复杂的实时路况信息，让模型学到更优的调度策略，以更好地平衡城市中的供需分布.

作者贡献声明

：郑渤龙提出了算法思路和实验方案；明岭峰和胡琦负责完成实验并撰写论文；方一向、郑凯和李国徽提出指导意见并修改论文.