《TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES》：Joint estimation of a semi-Markov decision process model of vacant taxi matching and routing in a large network
编辑推荐：
出租车路径规划建模与参数估计方法研究。采用无限时间半马尔可夫决策过程（SMDP）模型分析网约车司机决策机制，通过上海GPS数据验证，发现期望车费、运营成本和交叉口数量是关键决策因子。理论证明模型存在唯一最优解，并开发并行计算算法提升大规模路网（13,126节点）的参数估计效率。对比显示基于链接的SMDP模型相比区域MVP模型具有更好的跨层级预测鲁棒性。
姜国成|高松
美国马萨诸塞大学阿默斯特分校土木与环境工程系，博士生
摘要
我们将空闲的网约车或出租车司机的路线决策问题构建为一个在道路网络中的无限视界半马尔可夫决策过程（SMDP）。在这个过程中，司机在每个节点决定选择哪条路线，并根据随机的车辆-乘客匹配过程转移到下一个节点。司机的决策基于可观测和不可观测的状态。建模者的任务是根据观察到的状态和行为序列，共同估计司机的参数化效用函数以及状态转移函数。我们进行了理论分析，以确定SMDP的贝尔曼方程存在唯一解，这是进行模型参数最大似然估计所必需的。我们使用并行计算来加速估计算法，使其能够应用于包含数万个节点和路线的案例研究。研究发现，预期车费、预期运营成本以及城市区域内的交叉路口数量是影响司机路线决策的重要因素。考虑多个决策周期、较低的折现率（即折现因子接近1）以及联合估计路线和匹配参数是有优势的。与基于区域的MDP模型相比，基于路线的SMDP模型在预测不同于其估计空间尺度的区域时更为稳健。
部分摘录
动机与研究目标
像Uber和Lyft这样的网约车平台的出现显著改变了城市出行方式。传统的出租车过去仅依靠在街上巡游来寻找乘客，现在与基于智能手机的叫车应用（如纽约市的黄色出租车）共存并常常结合使用（Hu等人，2022年）。此外，像Waymo在包括旧金山和菲尼克斯在内的多个天气条件良好的大城市中提供的机器人出租车服务也日益普及。
文献综述
针对通勤者的路线选择模型已经得到了广泛研究，这些研究的前提是已经给定了一个明确的起点-终点（OD）并且可以从数据中可靠地识别出来。相比之下，空闲的出租车司机在网络中随机游荡以寻找下一位乘客，而背后的随机司机-乘客匹配过程使得目的地（如果有的话）变得模糊或不可观测。例如，一个向市中心行驶的司机可能会与位于市郊的乘客配对，这给决策带来了挑战。
参数化半马尔可夫决策过程模型
出租车在交通网络中移动：
其中 $\mathbf{N}$ 是节点集，$\mathbf{A}$ 是边集。从源节点 $i$ 到目标节点 $j$ 至多存在一条单向边 $a$。$\mathbf{A}(i)$ 表示从节点 $i$ 出发的所有边。一个代理代表一辆空闲的出租车。司机的路线决策被建模为一个连续时间的半马尔可夫决策过程（SMDP），其状态空间为 $S$，动作空间为 $A$，转移概率为 $p$，持有时间为 $t$，奖励为 $r$，时间单位折现率为 $\beta \geq 0$。SMDP在某些方面类似于MDP。
案例研究
我们使用了2015年4月一个典型工作周（五天）上午高峰时段（5:30至11:30）上海12,017辆出租车每10秒一次的GPS数据集。每条记录包含多个字段，其中使用了车牌ID、日期、时间戳、经度、纬度、速度和状态指示（空闲或已雇佣）等信息。该道路网络包含13,126个节点和29,643条有向边（不包括中心点连接器）。研究区域约为6,300平方公里。
结论与未来方向
通过建模和理论与实证分析，我们得出了一些主要结论。SMDP框架能够很好地解释序列决策过程中的持有时间变化。这对于空闲出租车路线问题尤为重要，因为司机的转移不仅是从一条边的一个端点到另一个端点，还可能到达乘客的目的地，从而导致持有时间的大幅波动。一些重要的理论成果来自……
CRediT作者贡献声明
姜国成：数据整理、形式化分析、方法论、验证、可视化、初稿撰写。
高松：概念构思、形式化分析、资金筹集、方法论指导、监督、审稿与编辑。
