RENO-002 | 网约车派单算法与多智能体强化学习
本周写一篇科研笔记，阐述滴滴派单算法背后的核心思想，展示一种以运筹优化（Operations Research & Mathematical Programming）为核心的 AI 视角，从而拓宽对AI的理解，避免局限在传统Machine Learning/Deep Learning的“桎梏”中。 (a) 网约车扎堆 (b) 打车困难 网约车平台的核心问题之一是，如何把订单分配给合适的司机？这一过程被称为Order Dispatching（派单）。派单效果会直接影响用户等待时间，司机收入，平台成交率，用户体验等。 解决派单问题，一种非常直接的思路是：最近司机接最近订单。但这种贪心策略过于短视（myopic），有时会造成供给侧接不到单（如图a）或需求侧打不到车（如图b）。其本质原因在于，当前的决策会影响未来的供需结构。因此，在进行派单时，不仅要考虑当前收益，还需要考虑未来影响。 1 打车流程回顾 用户侧： 用户输入起点和终点 平台进行价格预估 用户提交订单 系统指派合适的司机 司机接驾 完成订单 平台侧： 为订单用户搜索附近可用司机 预测接驾时间 评估不同匹配方案 完成订单分配 现实中的派单并不是“订单一来立刻派单”，而通常采用Batch Dispatch（批量派单），即：每隔几秒钟收集一批订单和司机，统一进行优化匹配。 2 派单问题的数学模型 对于每一个batch，记用户数量为J，可用司机数量为I，派单问题可以用如下二部图（Bipartite graph）表示 其中，左侧节点是用户，右侧节点是司机，边表示对应派单决策。同时，每条边带有一个“价值”。 记$x_{i,j}=1$表示用户j指派给司机i。因此，为最大化总体收益，上述派单问题可以建模为 其中，约束（2）表示每位司机至多接一个用户。约束（3）表示每位用户至多被指派给一个司机。 Remark 1: 这个问题很有意思，表面上看其决策变量是binary的（离散），并不容易求解。而实际上，这个问题约束的系数矩阵具有全单模性（Total Unimodularity），直接求解其线性规划松弛就等价于求解原来的离散优化问题。 Remark 2: 在早期的系统中，$w_{i,j}=-\text{pickup distance}$，即基于最小化接送距离进行派单。后来慢慢加入了订单价格、等待时间，变成$w_{i,j}=\lambda_1 \cdot \text{fare} -\lambda_2 \cdot \text{pickup distance} - \lambda_3 \cdot \text{waiting time}$。但随着系统运行，越来越发现无论怎么调整这些系数，总是会出现某些区域订单很多而司机不足，或者某些区域订单很少而司机非常多。其本质原因在于模型过于短视，只考虑当前最优，而忽略了当前派单决策会直接影响未来的司机分布。 3 多智能体强化学习 Motivation：平台的目标是最大化长期收益。在实时运行中，由于当前派单决策会影响未来司机分布，如果能直接用一个模型来预测每条边对应的长期价值，那么似乎问题就解决了。 3.1 前处理 基于六边形网格，对城市空间位置进行离散化 将调度时间轴离散化...