无神经元智能交通——基于表格强化学习的公平地铁网络扩展

# 无神经元的智能交通——基于表格型强化学习的地铁网络公平扩展
来源：https://arxiv.org/html/2606.04167
Dimitris Michailidis, Sennay Ghebreab, Fernando P\. Santos 社会智能人工系统实验室 阿姆斯特丹大学 \{d\.michailidis, s\.ghebreab, f\.p\.santos\}@uva\.nl

###### 摘要

本文研究地铁网络扩展问题（MNEP），这是交通网络设计问题（TNDP）的一个子集，专注于扩展地铁系统以满足出行需求。传统方法依赖于精确算法和启发式方法，需要专家定义的约束来缩小搜索空间。近年来，深度强化学习（Deep RL）因其在复杂序列决策过程中的有效性而兴起——然而，它计算成本高昂、环境代价较大，并且需要额外的工程工作才能实现可解释性。我们证明，MNEP问题的规模足够小，无需采用深度强化学习方法。通过将MNEP重新表述为非马尔可夫奖励决策过程（NMRDP），我们使用表格型强化学习在显著减少训练回合数的同时实现了相似性能，并提供了更高的可解释性。此外，我们将社会公平标准纳入奖励函数，重点关注效率和公平性，凸显了我们方法的灵活性。在西安和阿姆斯特丹的真实世界环境中评估，我们的方法平均将总训练回合数减少了18倍，总碳排放量减少了12倍，同时与深度强化学习保持竞争力。该方法提供了一种可复制、模块化、可解释且资源高效的解决方案，可推广到其他组合优化问题。

*关键*词优化与控制·强化学习·公共交通·地铁网络

## 1 引言

公共交通是现代快节奏生活的基础，它使市民能够参与就业、教育、医疗和社交活动[30 (https://arxiv.org/html/2606.04167#bib.bib19)]。然而，规划公共交通网络极具挑战性，因为物理、社会、经济和法律约束使得创建新的交通线路或扩展现有线路变得复杂。可持续性和公平性已成为网络设计中的关键考量，要求系统既能服务不同地区、社会经济地位或年龄的多样化人群，实现可及性，又能保持高效。低效的系统，例如利用率低的公交车，可能导致每位乘客的排放量高于私家车[29 (https://arxiv.org/html/2606.04167#bib.bib50)]，而低客流量可能会随时间推移降低服务质量[33 (https://arxiv.org/html/2606.04167#bib.bib56)]。这些权衡给交通规划带来了复杂性，使得数据驱动和自适应的解决方案变得不可或缺。

交通网络设计问题（TNDP）是一个NP难的组合优化问题，专注于设计公共交通系统以最大化出行需求满意度[16 (https://arxiv.org/html/2606.04167#bib.bib1)]。对于地铁系统，这一挑战通过地铁网络扩展问题（MNEP）来解决，该问题专门针对城市环境中现有地铁线路的扩展[53 (https://arxiv.org/html/2606.04167#bib.bib2)，51 (https://arxiv.org/html/2606.04167#bib.bib67)，46 (https://arxiv.org/html/2606.04167#bib.bib60)]。地铁网络因其速度快、可靠性高和运能大，在现代城市中发挥着关键作用，优于传统的公共交通模式[51 (https://arxiv.org/html/2606.04167#bib.bib67)]。地铁线路通常覆盖长距离，穿越多个城市区域，通常设计为相对笔直的路线，避免过度蜿蜒[53 (https://arxiv.org/html/2606.04167#bib.bib2)]。作为TNDP中的一个独特子问题，MNEP引入了地铁网络设计特有的额外约束。

传统上，TNDP问题采用整数优化和启发式算法[28 (https://arxiv.org/html/2606.04167#bib.bib22)，37 (https://arxiv.org/html/2606.04167#bib.bib6)]，需要大量专家定义的约束来缩小搜索空间以实现可解性。最近，地铁网络扩展问题（MNEP）被构建为序列决策问题，利用强化学习（RL）推导最优解决方案[53 (https://arxiv.org/html/2606.04167#bib.bib2)]。RL非常适合具有多个目标（如效率和公平性）的序列决策，并已成功应用于组合优化问题[11 (https://arxiv.org/html/2606.04167#bib.bib29)，42 (https://arxiv.org/html/2606.04167#bib.bib10)，23 (https://arxiv.org/html/2606.04167#bib.bib65)]。与传统方法不同，RL可以通过优化奖励函数灵活地探索搜索空间，无需指数级增加的约束。

鉴于许多问题中状态动作空间很大，强化学习（RL）的复杂性似乎合情合理。近年来，深度强化学习（Deep RL）在扩展组合优化能力方面显示出前景，它学习策略表示，自主识别关键特征，并在现实世界问题中取得了最先进的结果[31 (https://arxiv.org/html/2606.04167#bib.bib26)，36 (https://arxiv.org/html/2606.04167#bib.bib46)，54 (https://arxiv.org/html/2606.04167#bib.bib47)]。

尽管计算能力的进步和算法研究表明RL可以改变像MNEP这样的问题，但我们认为深度强化学习并非总是理想解决方案。其大量的训练时间和环境成本随着AI系统的广泛部署而变得越来越显著[3 (https://arxiv.org/html/2606.04167#bib.bib71)，45 (https://arxiv.org/html/2606.04167#bib.bib69)，38 (https://arxiv.org/html/2606.04167#bib.bib70)，25 (https://arxiv.org/html/2606.04167#bib.bib72)]。虽然MNEP涉及复杂的解空间，但它们本质上是静态优化问题，输入特征有限。其可扩展性受到固有约束——地铁线路通常间隔1-3公里[19 (https://arxiv.org/html/2606.04167#bib.bib76)]，并且在位置、形状和其他设计因素上受到限制。因此，擅长捕获高维特征空间中复杂模式的复杂神经网络结构，可能并非有效策略训练所必需。这得到了其他机器学习领域研究成果的支持[8 (https://arxiv.org/html/2606.04167#bib.bib68)]。

在本文中，我们认为，当恰当构建时，传统RL方法可以有效解决像MNEP这样的复杂问题。我们证明，一种表格型方法在两个现实世界环境（西安和阿姆斯特丹）中，与深度学习方法相比，在显著缩短训练时间的同时实现了有竞争力的性能。此外，我们的新表述结合表格型RL，比黑盒深度学习模型提供了更高的可解释性。

为了进一步展示表格型RL的潜力，我们通过纳入基于不同社会福利概念的多样化奖励函数，探索了MNEP中的社会公平性。我们将最先进的MNEP的RL公式扩展以整合公平标准。我们的主要贡献如下：我们将交通网络设计和地铁网络扩展问题重新表述为非马尔可夫奖励决策过程，显著减少了状态动作空间。我们通过将RL框架扩展以整合社会善的考量（包括基于效率和公平性的目标），弥合了机器学习和交通规划研究之间的差距。我们提出了一种用于MNEP的蒙特卡洛表格型强化学习算法，旨在比深度学习模型需要更少的训练回合。我们在两个现实世界环境——中国西安和荷兰阿姆斯特丹——中验证了我们的方法，证明了与最先进的深度强化学习方法相当的性能，训练回合数减少了18倍，二氧化碳排放量减少了12倍。我们提供所有代码、数据集和超参数设置，以复现我们的结果并使该方法能够应用于其他组合优化问题¹¹¹Github: https://github\.com/dimichai/tabular\-tndp。本文的其余部分结构如下：首先，我们将我们的工作置于先前研究的背景下（第2节），并重新构建MNEP（第3节）。我们继续描述表格型模型和提出的社会福利奖励函数（第4节），以及实验中使用的现实世界环境（第5节）。最后，我们展示并讨论结果（第6节）。

## 2 相关工作

我们概述了先前关于TNDP、用于组合优化的强化学习以及交通公平性分析的工作。

### 2.1 交通网络设计问题

传统上，交通网络设计问题（TNDP）通过整数优化技术和启发式方法的结合来解决，包括使用预定义或动态发现的走廊[28 (https://arxiv.org/html/2606.04167#bib.bib22)，57 (https://arxiv.org/html/2606.04167#bib.bib63)，21 (https://arxiv.org/html/2606.04167#bib.bib3)]、模拟退火[15 (https://arxiv.org/html/2606.04167#bib.bib4)，1 (https://arxiv.org/html/2606.04167#bib.bib23)]、蜂群优化[56 (https://arxiv.org/html/2606.04167#bib.bib61)，47 (https://arxiv.org/html/2606.04167#bib.bib5)]和遗传算法[37 (https://arxiv.org/html/2606.04167#bib.bib6)，34 (https://arxiv.org/html/2606.04167#bib.bib64)]。

尽管这些方法在早期研究中取得了有希望的结果，但它们具有明显的局限性。为了使问题可解，它们通过强制执行一长串环境特定的约束或设置预定义的一组走廊来限制搜索空间。这种限制在应用到大而多样的现实世界城市环境中造成了障碍。更关键的是，以这种方式缩小搜索空间可能会排除这些约束之外的高质量解决方案。

### 2.2 用于交通网络设计的强化学习

强化学习（RL）已被证明对长期最优序列决策有效。通过简单的奖励机制，智能体通过试错学习理解其对环境的影响，这使得RL非常适合通过利用示范和经验来应对现实世界中NP难的组合优化任务，而无需专家先验知识[31 (https://arxiv.org/html/2606.04167#bib.bib26)，52 (https://arxiv.org/html/2606.04167#bib.bib48)，6 (https://arxiv.org/html/2606.04167#bib.bib51)，23 (https://arxiv.org/html/2606.04167#bib.bib65)，10 (https://arxiv.org/html/2606.04167#bib.bib73)]。尽管组合优化问题也可以采用监督学习（SL）方法，但最近的研究表明，RL在常见问题（如旅行商问题[5 (https://arxiv.org/html/2606.04167#bib.bib7)，13 (https://arxiv.org/html/2606.04167#bib.bib27)]和车辆路径问题[35 (https://arxiv.org/html/2606.04167#bib.bib12)，24 (https://arxiv.org/html/2606.04167#bib.bib18)]）上比SL具有更强的泛化能力。

尽管RL在组合优化中的应用日益广泛，但其在交通网络设计中的应用直到最近才受到关注。[11 (https://arxiv.org/html/2606.04167#bib.bib29)]采用策略梯度方法设计公交线路，探索了客户满意度与运营成本之间的帕累托前沿。类似地，[53 (https://arxiv.org/html/2606.04167#bib.bib2)]使用基于指针的模型来解决交通网络设计问题（TNDP），在需求满意度方面表现出优越性能。最近，[2 (https://arxiv.org/html/2606.04167#bib.bib74)]将图神经网络与蒙特卡洛树搜索（MCTS）算法相结合，利用网络连接性增强特征学习。[9 (https://arxiv.org/html/2606.04167#bib.bib75)]也将MCTS应用于现有地铁网络的图扩展，尽管没有直接解决MNEP。此外，多目标强化学习已被用于TNDP中平衡效率与可达性[58 (https://arxiv.org/html/2606.04167#bib.bib62)，32 (https://arxiv.org/html/2606.04167#bib.bib66)]。

大多数关于交通网络设计问题（TNDP）和密切相关的城市轨道交通网络扩展问题（MNEP）的工作都集中在复杂的深度强化学习（Deep RL）模型上。然而，本文质疑了在可解释性对决策者至关重要的问题上采用这种黑盒模型的必要性。我们重新构建了问题，在不限制解空间的情况下显著减少了动作空间，从而实现了基于蒙特卡洛的简单表格型强化学习方法。然后，我们的方法与MNEP最先进的深度强化学习方法[53 (https://arxiv.org/html/2606.04167#bib.bib2)]进行了基准比较。

### 2.3 交通网络设计中的社会公平性

在交通网络设计中采纳社会公平的概念，由于其多维度性质[4 (https://arxiv.org/html/2606.04167#bib.bib9)]及涉及的内在道德判断[50 (https://arxiv.org/html/2606.04167#bib.bib40)]，优化起来颇具挑战。借鉴先前城市交通研究，我们确定了纳入公平性所需的三个关键决策：效用度量、维度和公平性理论。

效用度量：这通常通过建立可达性指标来实现，例如可到达机会的数量[39 (https://arxiv.org/html/2606.04167#bib.bib31)，49 (https://arxiv.org/html/2606.04167#bib.bib32)，22 (https://arxiv.org/html/2606.04167#bib.bib36)]、访问这些机会的可负担性[17 (https://arxiv.org/html/2606.04167#bib.bib38)]，或两者的结合[14 (https://arxiv.org/html/2606.04167#bib.bib39)]。

维度：公平性可以沿空间维度评估，即评估不同地理或行政单位之间的差异[39 (https://arxiv.org/html/2606.04167#bib.bib31)，12 (https://arxiv.org/html/2606.04167#bib.bib35)]，或通过群体度量，其中群体按社会经济特征（如收入、种族）定义[49 (https://arxiv.org/html/2606.04167#bib.bib32)，40 (https://arxiv.org/html/2606.04167#bib.bib33)，7 (https://arxiv.org/html/2606.04167#bib.bib34)]。

公平性理论：多种公平和公正理论为交通网络设计提供了依据[4 (https://arxiv.org/html/2606.04167#bib.bib9)]。大多数方法属于横向公平——旨在所有单位或群体之间实现相等的效用——或纵向公平，即优先考虑需求更大的群体或区域[50 (https://arxiv.org/html/2606.04167#bib.bib40)]。

尽管有这些理论分析，在TNDP的机器学习中全面应用公平框架仍然有限。尽管如此，先前的工作已初步尝试整合公平考量。例如，[41 (https://arxiv.org/html/2606.04167#bib.bib41)]使用RL探索图增广中的效率-公平权衡，并将其应用于芝加哥的交通网络[41 (https://arxiv.org/html/2606.04167#bib.bib41)]。[48 (https://arxiv.org/html/2606.04167#bib.bib30)]比较了针对优势群体和弱势群体的公交线路设计，虽然不