AlphaTransit：学习设计城市级公交路线 AlphaTransit: Learning to Design City-scale Transit Routes
MCTS+神经网络设计公交网络，Bloomington服务率54.6%-82.1%
前置知识
Transit Route Network Design Problem (TRNDP)
公交路线网络设计问题是一个组合优化问题，需要在共享街道网络上设计一组可能重叠的路线，服务于多对多的乘客流，同时受到车队规模和运营成本等约束。与旅行商问题或车辆路由问题不同，TRNDP需要联合设计一个路线网络，其组件通过换乘、拥堵和共享基础设施相互影响。改变一条路线会重新分配整个网络的乘客，改变远处路线段的价值。
本文的核心问题就是TRNDP，理解这个问题的定义和挑战对于理解AlphaTransit要解决的延迟反馈和非局部奖励问题至关重要。
Monte Carlo Tree Search (MCTS)
蒙特卡洛树搜索是一种启发式搜索算法，用于决策过程，特别是在信息不完整或搜索空间巨大的情况下。MCTS通过四个步骤迭代构建搜索树：选择、扩展、模拟和反向传播。选择阶段使用如PUCT这样的公式在已探索节点中选择最有希望的节点，扩展阶段添加新节点，模拟阶段从新节点进行随机或引导的模拟，反向传播将模拟结果沿路径回传更新统计信息。
AlphaTransit的核心创新就是将MCTS与神经策略-价值网络结合，MCTS提供了决策时的前瞻搜索能力，这是理解本文方法的关键。
Graph Attention Network (GAT)
图注意力网络是一种基于注意力机制的图神经网络，它通过计算节点之间的注意力权重来聚合邻居信息。GATv2是改进版本，解决了原始GAT中的动态注意力问题。在AlphaTransit中，使用GATv2作为骨干网络处理道路图，节点特征包括空间属性、OD需求聚合、路线成员资格和前沿状态，边特征包括长度和自由流速度。
AlphaTransit的策略-价值网络使用GATv2作为共享骨干，理解GAT如何处理图结构数据对于理解模型架构至关重要。
PUCT (Predictor + UCB for Trees)
PUCT是MCTS中用于选择动作的公式，结合了当前价值估计和探索奖励。公式为 $a^* = \argmax_{a \in C(s)} \left[ Q(s, a) + c \frac{P_\theta(a|s) \sqrt{1 + \sum_{b \in C(s)} N(s, b)}}{1 + N(s, a)} \right]$，其中Q是平均价值，P是策略先验，N是访问次数，c是平衡系数。这个公式在高价值的利用和未访问节点的探索之间取得平衡。
PUCT是AlphaTransit中MCTS选择动作的核心机制，理解这个公式对于理解搜索过程如何利用神经网络的输出至关重要。
研究动机
公交路线网络设计问题(TRNDP)面临一个根本性的延迟反馈挑战：每条路线扩展决策的质量只有在完整网络构建完成并运行模拟后才能观察到。这种延迟和非局部反馈使得优化景观具有欺骗性——局部看起来有用的扩展可能会创建换乘瓶颈、产生冗余重叠或降低整体吞吐量。在Bloomington设置中，问题空间包含约$10^{82}$个候选路线集合，是NP-hard问题。现有的TRNDP方法通过简化评估模型、迭代修改候选路线集合或学习路线构建策略来处理这个困难，但都无法在决策时提供前瞻能力。精确和分解方法使用分析性的乘客路由和旅行时间目标而不是模拟，使得基于拥堵和车辆容量的模拟目标难以直接优化。经典的元启发式方法（如遗传算法、模拟退火、蜂群优化）可以处理更大的设计空间并避免一些抽象，但依赖于定制的移动算子、惩罚项和特定实例的调优。基于学习的方法减少了手动设计，但大多数将学习嵌入在更大的元启发式循环中，而不是产生独立的构建策略。
本文的目标是本文的目标是开发一个搜索引导的框架，通过前瞻搜索改进局部决策，同时避免在每个节点进行昂贵的模拟。具体来说，要解决TRNDP中奖励信号延迟和非局部的问题，即每个路线扩展的影响只有在路线集合完成、分配频率并模拟乘客流后才能观察到。目标是在不增加计算负担的情况下，在决策时提供前瞻能力，以便在设计过程中评估局部选择的下游网络效应。
与已有工作不同的是，本文的独特切入角度是将学习到的先验与前瞻搜索结合起来，专门针对模拟器定义的公交TRNDP。虽然MCTS已经在相邻设置中应用，但据作者所知，没有先前工作将学习到的策略和价值先验引导搜索、MCTS基于前瞻的细化动作选择以及基于模拟的评估提供的终端奖励信号这三个要素结合起来。MetroZero是最接近的神经搜索方法，但它是在预算约束下选择地铁扩展站点，而AlphaTransit在现有共享道路上构建完整的公交路线集，并通过乘客和交通模拟进行评估。这种整合使得AlphaTransit能够针对稀疏终端反馈更有效地协调路线构建。
核心方法
AlphaTransit是一个搜索引导的强化学习框架，结合了蒙特卡洛树搜索(MCTS)和神经策略-价值网络。直觉上，就像AlphaGo在围棋中通过搜索改进决策一样，AlphaTransit在构建公交路线时使用MCTS在决策时前瞻搜索，神经网络提供先验知识和价值估计。技术路线上，策略-价值网络$f_\theta = (P_\theta, V_\theta)$将图状态映射到节点动作概率和状态价值估计。在每个构建状态，MCTS使用网络的输出作为先验进行搜索，访问次数定义MCTS策略，从中采样下一个动作。只有在完整路线集构建完成后才调用模拟器返回终端奖励，然后使用样本$(s_t, \pi_t, \tilde{z})$训练网络，其中$\pi_t$是MCTS策略，$\tilde{z}$是归一化的价值目标。这种方法使得每个决策都有前瞻能力，而不需要在搜索树内运行模拟器前向推演。
核心创新点是将学习到的先验与MCTS搜索结合，专门针对模拟器定义的TRNDP延迟反馈问题。与端到端RL不同，AlphaTransit在决策时使用MCTS提供前瞻搜索，访问次数定义的策略既用于采样下一个动作，也用于训练actor。与纯MCTS不同，AlphaTransit使用神经网络的策略先验和价值估计来引导搜索，使得决策时搜索保持在秒级而不是需要数百到数千秒。本质区别在于：端到端RL在没有决策时搜索的情况下选择每个节点，纯MCTS使用均匀先验和完整模拟器前向推演，而AlphaTransit使用学习到的先验和价值估计引导搜索，避免树内模拟器调用。这种结合使得稀疏终端反馈对路线设计更有用。
方法步骤详情
方法步骤完整描述：1)状态表示：在每个步骤t，状态编码道路图和到目前为止构建的公交网络，包括已完成路线、当前部分路线和前沿节点。策略网络接收$st = (Xt, I, Z)$，其中I是有向边列表，Z存储边特征如长度和自由流速度，$Xt \in \mathbb{R}^{n \times dx}$包含每个节点的特征，捕获空间属性、OD需求聚合、路线成员资格和前沿状态。2)动作选择：在每个步骤，代理选择$at \in A = \{1, \ldots, n\}$，其中$at = i$将节点$vi$追加到当前路线。可接受候选集是$Ct = \{i \in \{1, \ldots, n\} : \{v_{ft}, vi\} \in E \text{ and } vi \notin r_{k,t}\}$，其中$v_{ft}$是前沿节点。使用无效动作屏蔽，二进制掩码$mt \in \{0, 1\}^n$将策略限制为可行扩展。3)网络架构：策略-价值网络使用共享GATv2骨干处理节点特征和边特征，连续的注意力块产生多跳表示，跳跃知识聚合将不同接收场尺度的表示拼接并投影到节点嵌入。节点级actor MLP产生logits，然后屏蔽不可行的logits。图级critic使用全局平均和最大池化预测$V_\theta(s)$。4)MCTS搜索：在每个构建状态$st$，AlphaTransit运行以$st$为根的MCTS，搜索可接受的路线扩展动作。每条边$(s, a)$存储访问次数$N(s, a)$、总价值$W(s, a)$、平均价值$Q(s, a)$和先验$P_\theta(a|s)$。叶节点由$V_\theta$评估，避免树内模拟器调用。每次模拟通过选择(使用PUCT)、扩展和评估(网络前向传播)、反向传播(更新统计信息)进行。5)动作采样和训练：$N_{iter}$次模拟后，根动作分布从访问次数导出：$\pi_t(a|st) = \frac{N(st, a)^{1/\tau}}{\sum_{b \in C(st)} N(st, b)^{1/\tau}}$。训练时，下一个动作从$\pi_t$采样，对$(st, \pi_t)$存储用于回合。一旦完整路线集$\Pi$构建完成，模拟器返回终端奖励$z = R_T(\Pi; \xi)$，在线归一化形成价值目标$\tilde{z}$并与每个存储的状态配对。网络从样本$(s, \pi, \tilde{z})$通过最小化损失$L(\theta) = \mathbb{E}_{(s,\pi,\tilde{z})} [-\sum_{a \in C(s)} \pi(a|s) \log P_\theta(a|s) + (V_\theta(s) - \tilde{z})^2]$训练，第一项将MCTS访问次数蒸馏到actor，第二项训练critic预测归一化的终端结果。
技术新颖性
技术新颖性体现在三个方面：1)首次将学习到的策略和价值先验引导搜索、MCTS基于前瞻的细化动作选择以及基于模拟的评估提供的终端奖励信号这三个要素结合用于公交TRNDP。与MetroZero等相邻工作不同，AlphaTransit构建完整的公交路线集，而不仅仅是选择地铁扩展站点。2)提出了一个新的Bloomington TRNDP基准数据集，包含拓扑正确的道路图(143个节点和243条双向边)、从美国人口普查数据衍生的街区级OD需求矩阵以及16条现有的真实世界公交路线。与合成基准不同，这个数据集提供了真实的道路拓扑和空间异质性的出行需求。3)系统隔离了学习前瞻的作用，通过将AlphaTransit与没有决策时搜索的端到端RL和没有学习先验或价值估计的纯MCTS进行比较，以及与启发式、元启发式、神经进化和真实世界基线比较，证明学习到的先验与前瞻搜索结合比单独使用任一方法对公交网络设计更有效。
实验结果
核心发现包括：在混合需求($\alpha = 0.3$)下，AlphaTransit在Bloomington基准上达到54.64%的服务率，使用80辆公交车，达到最高的公交利用率22.10%和第二高的路线效率21.99%。相比端到端RL，服务率提升9.9%(从49.70%到54.64%)；相比纯MCTS，服务率提升2.5%(从53.30%到54.64%)。在全公交需求($\alpha = 1.0$)下，AlphaTransit达到82.08%的服务率，相比端到端RL提升11.4%(从73.68%到82.08%)，相比纯MCTS提升11.2%(从73.80%到82.08%)。在全公交需求下，AlphaTransit还获得最低等待时间、最高路线效率和最高公交利用率。学习动态和搜索成本分析显示：端到端RL依赖密集塑形奖励来学习，Delta-coverage变体优于终端-only和Raw + Early Stopping反馈，其中Delta + No Early Stopping在后续比较中使用。AlphaTransit在相同环境步骤预算下提高样本效率，因为MCTS提供搜索改进的动作目标，而学习到的策略-价值估计使决策时搜索保持在秒级。扩展行为研究显示：搜索深度在$N_{iter} = 400$时性能达到峰值(top-5奖励1.67)，而在500时降低到1.29且运行时间更高；每次迭代的回合数提高top-5奖励从0.19(8回合)到2.20(32回合)；更大的GAT策略没有提供增益(16×策略降至0以下)。图6显示，增益不仅仅是更广泛的覆盖：AlphaTransit覆盖117个节点(81.8%)和120.8公里，而端到端RL覆盖138个节点(96.5%)和142.3公里，但AlphaTransit用更小的车队服务更多需求。相比真实世界路线，AlphaTransit有相似的节点覆盖率(114个节点，79.7%)但减少共享边缘重叠(24.4% vs 34.8%)并将服务率从42.77%提高到54.64%。跨城市迁移测试显示：在更大的Laval网络上($\sim256$公里²，632个节点和1971条边)，使用只在Bloomington上训练的策略，全公交需求下AlphaTransit达到90.72%服务率，而端到端RL只有55.03%，同时AlphaTransit在可迁移方法中获得最低等待时间和最高路线效率。在混合需求下，AlphaTransit服务率89.25%，接近Shortest Path的90.72%，但给出最低等待时间。
查看结构化数据
| 任务 | 指标 | 本文 | 基线 | 提升 |
|---|---|---|---|---|
| Bloomington基准混合需求($\alpha=0.3$) | 服务率(%) | 54.64±4.77 | End-to-End RL: 49.70±5.40; Pure MCTS: 53.30 | vs RL: +9.9%; vs MCTS: +2.5% |
| Bloomington基准全公交需求($\alpha=1.0$) | 服务率(%) | 82.08±3.14 | End-to-End RL: 73.68±3.71; Pure MCTS: 73.80±5.40 | vs RL: +11.4%; vs MCTS: +11.2% |
| Bloomington基准混合需求($\alpha=0.3$) | 公交利用率(%) | 22.10±4.77 | End-to-End RL: 15.73±3.93 | +40.5% |
| Bloomington基准全公交需求($\alpha=1.0$) | 等待时间(分钟) | 6.03±0.58 | End-to-End RL: 15.80±0.74 | -61.8% |
| Laval跨城市迁移全公交需求($\alpha=1.0$) | 服务率(%) | 90.72±0.71 | End-to-End RL: 55.03±1.79 | +64.9% |
局限与改进
作者承认的局限性包括：1)地理范围有限：大多数实验和模型开发依赖Bloomington基准，结果可能无法完全捕捉不同城市公交网络的多样性。Laval实验提供了初步的跨城市检查，但需要在更多大都市系统上进行更广泛的验证。2)路线起始假设：每条路线都从公交中心枢纽开始，这与Bloomington Transit匹配并减少了构建空间，但可能不适合多枢纽、跨城或网格状网络。3)模拟器和决策模型抽象了几个部署因素：需求由静态高峰小时OD矩阵表示，奖励没有明确编码公平性、可达性、可靠性、预算或鲁棒性约束。我自己观察到的局限性：1)训练计算成本较高：需要约1M环境步骤和$N_{iter} = 500$ MCTS模拟，这对实时应用可能有挑战。2)搜索深度和策略大小的权衡：研究发现更大的GAT策略没有提供增益，甚至性能下降，表明当前架构可能已达到可扩展性极限。3)频率优化简化：频率使用max-load规则分配，而不是联合优化路线和频率，这可能导致次优的频率配置。4)单阶段决策：方法假设路线构建和频率分配是顺序的，但实际运营中可能需要联合优化。
独立分析的弱点
独立分析的弱点包括：1)静态需求假设：需求由静态高峰小时OD矩阵表示，但实际公交需求具有显著的时空变化性。改进方向是整合时间变化的需求模式，可能使用循环神经网络或时间序列建模来捕捉日内和日间变化。2)缺乏鲁棒性考虑：奖励函数没有明确编码对需求波动、交通拥堵、车辆故障等扰动的鲁棒性。改进方向是引入鲁棒优化技术，在训练时考虑需求不确定性，或在奖励中加入对扰动的惩罚。3)公平性和可达性缺失：奖励函数没有明确编码不同社区的服务公平性和可达性。改进方向是在奖励中加入公平性指标，如Gini系数或不同社区的服务覆盖率差异。4)跨城市泛化有限：虽然Laval实验显示了一定的跨城市迁移能力，但地理范围仍然有限。改进方向是在更多不同拓扑和需求模式的城市上训练和评估，可能使用元学习或领域自适应技术提高泛化能力。5)计算效率：虽然MCTS搜索保持在秒级，但整体训练成本仍然较高。改进方向是探索更高效的搜索策略，如渐进式扩大搜索预算，或使用蒸馏技术将搜索策略转移到更小的网络。
未来方向
未来研究方向包括作者提出的和基于成果可延伸的：作者提出的扩展包括：1)内生模式选择和更多城市以及更大的大都市网络的训练和评估；2)放松公交中心起始约束，或联合学习路线起点和路线扩展；3)时间变化需求、随机扰动、第二阶段频率策略以及更清楚地暴露邻里间服务质量权衡的约束目标。基于成果可延伸的方向：1)多目标优化：当前奖励函数使用固定权重平衡乘客和运营商目标，但实际决策可能需要考虑多个相互冲突的目标。可以探索帕累托优化方法或基于偏好的强化学习。2)可解释性：虽然GAT提供了一定的可解释性，但路线决策的透明度仍然有限。可以探索可解释AI技术，如注意力可视化和决策反事实解释。3)实时部署：当前方法主要用于离线规划，但实时运营可能需要在线适应。可以探索在线学习技术，使系统能够根据实时反馈不断改进。4)多模态集成：当前方法专注于公交网络，但实际城市交通系统包括多种模式。可以探索将AlphaTransit扩展到多模态网络设计，包括地铁、自行车道和步行路径。5)政策约束集成：实际公交设计受到政策约束，如最小服务频率、最大换乘次数等。可以将这些约束显式编码到决策过程中，确保生成的路线满足实际政策要求。
复现评估
复现评估：作者声明代码和数据公开可用(https://github.com/poudel-bibek/AlphaTransit)，这对复现性是有利的。Bloomington基准数据集包括拓扑正确的道路图、人口普查衍生的OD需求矩阵和现有的真实世界公交路线，这些数据都是公开或可衍生的。实验使用UXsim mesoscopic交通模拟器，这是一个开源模拟器，便于复现。训练设置包括约1M环境步骤、$K=16$条路线、$L_{max}=14$个站点、$N_{iter}=500$ MCTS模拟，这些参数在论文中有详细说明。基线方法包括Real-World、Random Walk、Demand Cover、Shortest Path、Genetic Algorithm、Bee Colony、Neural Evolutionary、Pure MCTS和End-to-End RL，大多数方法都有标准实现或论文中描述的足够细节。然而，复现难度仍有一些挑战：1)计算需求较高，需要并行episode workers和大量MCTS模拟；2)UXsim的特定配置和扩展可能需要仔细重现；3)神经网络的超参数(如GAT块数量、隐藏维度、注意力头数)虽然在附录中提供，但最佳调优可能需要实验；4)跨城市迁移实验需要额外的Laval数据集处理。总体而言，开源代码和详细的论文描述使复现是可行的，但需要适当的计算资源和仔细实现细节。
论文图表
