北航与第四范式KDD冠军方案：解密共享出行场景中的优化问题( 二 )

问题定义
本赛题的优化目标是最大化平台上司机一天内的平均总收益，因此在派单时，不仅要考虑最大化当前时间窗的收益，还必须考虑未来的可能收益。同时，当前的订单分配会影响车辆的位置和收益，对未来产生影响，是一个序列决策问题，因此考虑通过强化学习解决。此情景下，环境 (Environment) 包括订单、司机车辆信息位置等，而参赛者需要定义智能体 (Agent)的学习和预测策略，以最大化司机的收益。本问题中司机和车辆一一对应，下文中如未特殊强调，车辆和司机含义一般可以互换。状态 (State)、动作(Action) 和奖励 (Reward) 设计如下：
2.1.1 状态
联合团队使用车辆的地理坐标经过离散化后对应的 ID ，来表示车辆的状态，而不考虑时间因素。具体的，团队同时使用了多种离散化策略，使得每个地理坐标，对应多个不同粒度的状态，如主办方提供的六边形格子划分策略，还可以是多种不同大小的四边形等。如下图所示，对于图中的坐标点（红色圆点），离散化后，可以同时采用六边形、不同大小的四边形来标识该点对应的状态。

本文插图
2.1.2 动作
智能体执行派单程序后，会生成司机和订单的匹配列表。在不考虑取消订单的情况下，成功匹配的司机将会进入服务 (serving) 状态: 司机会到达指定上车点，接到乘客，并运送到指定下车点，拿到相应的奖励。而未能分配到订单的司机，将会闲置(idle) ，不能拿到任何收益。
2.1.3 奖励
每次派单成功后，司机会拿到相应订单的收益，作为本次动作的奖励。本次比赛的目标，即是最大化所有司机的平均收益。
算法设计
每次智能体被调用时，将接收到当前所有的候选订单信息，并在 2 秒内做出司机和乘客的匹配。候选信息列表是候选订单的集合，每个候选订单主要包含如下信息：
oorder_id 和 driver_id: 订单 ID 和司机 ID ，用来唯一标识候选订单和司机；
odriver_location: 司机在当前时刻所处的地理位置，本次比赛中地理位置信息均采用经纬度对来表示；该信息信息经过离散化后，得到订单的起始状态标识；
oorder_finish_location：订单结束位置，即订单的目的地；该信息经过离散化后，得到订单的终点状态标识；
oduration：订单的预估时长；
oreward：订单带来的收益。
此外，还有当前时刻信息、订单起始位置（order_start_location）、接驾距离（司机和乘客的距离 order_driver_distance）、预估接驾时长（pick_up_eta）等，可以根据此类信息推断订单取消概率。
本方案整体策略为通过时序差分算法（Temporal Difference）学习状态值，并通过二分图匹配算法最大化收益。具体的，智能体接受到候选订单列表后，将依次执行以下三个步骤：
1) 构图：通过候选订单信息，将司机和乘客建模成二分图；并根据起止点对应的状态，计算边权；
2) 匹配：通过二分图匹配算法，将司机和乘客匹配，并派单；
3) 更新：根据匹配结果，通过时序差分算法的学习规则，更新涉及到的状态对应的值。
下面详细介绍每个步骤。
2.2.1 构图
本文将订单 ID 和司机 ID 作为图的顶点，并根据候选订单信息，连接相应的订单和司机，得到对应的图。因为订单之间、司机之间均不存在连接关系，因此该图是二分图。另外，为了保证更快的得到匹配效果，加速后续匹配算法，将二分图按如下策略剪枝：对于每个订单，只保留接驾距离最小 K 个司机对应的边；在比赛中， K 取 11 。
不妨将司机位置（driver_location）和订单终点（order_finish_location）对应的状态分别记为 S 和 S^' ，其对应的状态值分别为 V(S) 和 V(S^')，则二分图中的边权 w 计算方式为：