基于网络的公式化方法及用于分担交通系统区域划分的求解算法

《TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES》：Network-based formulations and solution algorithm for paratransit districting

　　钦诺索·奥科里（Chinonso Okorie）| 陈世杰（Shijie Chen）| 孙彦硕（Yanshuo Sun）
佛罗里达农工大学-佛罗里达州立大学工程学院工业与制造工程系，美国佛罗里达州塔拉哈西市波茨坦街2525号，邮编32310

**摘要**
小型和中型准公共交通运营商通常在一个集中的区域内提供服务。相比之下，较大的运营商通常将其服务区域划分为多个区域，每个区域由独立的承包商管理。虽然这种分区策略具有诸如提高车辆准时性等优势，但区域边界对于需要跨越不同区域的乘客来说却构成了重大障碍。尽管多区域结构在美国主要大都市区得到广泛采用，但相关研究仍然存在明显不足，特别是缺乏严格的定量方法来支持这些重要的准公共交通区划决策，尤其是在离散优化视角下。为了解决这一不足，我们提出了两个整数规划模型，以协助交通管理部门将准公共交通服务区域划分为两个区域。第一个模型主要用于说明性目的，假设边界是一条直线段；第二个模型放宽了这一假设，模拟了由多段线段组成的边界。对于这两个模型，优化目标都是在确保工作量平衡的前提下，最小化区域间的出行需求。我们还设计了一种改进的启发式算法，以减少大规模区划问题的计算时间。在数值研究中，我们使用合成数据对第二个模型进行了全面测试，并将其与现成的求解器进行了性能比较。最后，我们以一个拥有超过四千次日常准公共交通出行的匿名大都市区为例进行了实际案例研究。研究结果表明，所设计的方法有望显著推进美国主要准公共交通管理部门的区划实践。

**引言**
美国所有公共交通运营商都必须为因残疾而无法使用固定路线服务的乘客提供ADA（美国残疾人法案）规定的准公共交通服务（Cortenbach等，2024年；Vansteenwegen等，2022年）。小型或中型交通机构通常维护一个单一的准公共交通服务区域。例如，蒙大拿州米苏拉市的公共交通运营商Mountain Line在其现有22条固定路线周围的3/4英里缓冲区内提供准公共交通服务（见图1）。佛罗里达州杰克逊维尔市（人口约一百万）的准公共交通服务由杰克逊维尔交通管理局（JTA）运营。尽管ADA规定必须在固定路线三分之四英里范围内提供准公共交通服务，但图2显示，较大的交通机构通常会超出这一范围提供服务。这些额外服务是通过州政府规定的项目实现的，例如JTA的交通弱势群体（TD）项目（FDOT，2025年）。米苏拉和杰克逊维尔的例子表明，由于区域规模可管理，单一服务提供商可以有效覆盖整个服务区域。

相比之下，美国许多大型公共交通运营商需要将其整个准公共交通服务区域划分为多个服务区域（Quadrifoglio等，2008年）。例如，马萨诸塞湾交通管理局（MBTA）利用复杂的分区机制高效管理其拥有超过四百万人口的服务区域。如图3所示，MBTA的RIDE服务区域被划分为北、西、南三个区域，而市中心区域则是共享的。MBTA分别为这三个区域分配了三个服务提供商，所有三个提供商都可以使用共享的市中心区域，以确保全面覆盖。此外，郊区区域设有指定的换乘点，以满足跨区域出行需求。另一个例子是洛杉矶县（Los Angeles County）的ADA准公共交通服务区域，如图4所示被划分为六个不同的区域，每个区域都指派了一个独立的服务提供商。虽然来自下四个区域的出行请求需要换乘才能到达上两个区域（圣克拉丽塔和安特洛普谷），但在下四个区域内部旅行的乘客可以无缝地穿越区域边界而无需换乘车辆。

虽然像波士顿和洛杉矶大都市区采用的分区机制可以简化管理并增强服务覆盖范围，但它给跨区域乘客带来了换乘的不便（Shen和Quadrifoglio，2013年）。当准公共交通服务区域被划分为多个区域时（Quadrifoglio等，2011年），一些乘客往往需要在不同服务提供商之间换乘才能完成单次出行。这一过程可能繁琐且耗时，通常涉及在换乘点的大量等待以及不同服务运营商之间的协调。这些困难阻碍了人们利用准公共交通服务进行长途出行，并为那些需要在不同区域获取关键服务（如医疗保健）的乘客造成了障碍。此外，协调跨越多个区域的出行需要不同运营商之间的明确沟通与合作。因此，是否采用分区策略对于服务区域广泛的交通管理部门来说是一个重要决策。如果分区是合理的，精心设计的分区计划可以减少换乘的需求；交通管理部门还可以改善用户体验，提高准公共交通服务的效率，并更好地满足乘客的需求。

尽管有效区域划分在准公共交通服务中起着关键作用，但目前交通领域关于区域划分问题的学术文献相对较少，大多数研究集中在高速公路和铁路交通管理以及物流方面（详见第2.1节）。尽管有关于固定路线和灵活路线公共交通的分区研究，但这些研究要么追求不同的研究目标（如票价方案优化，见第2.1.3节），要么不关注将区域划分为多个区域，而只是优化区域大小（Kim等，2019年）。特别是关于ADA准公共交通服务的研究，主要通过统计和模拟分析探讨了集中式和分散式分区策略，从而在区划优化模型的发展上存在空白。这些现有研究关注的是局部服务质量和运营效率之间的权衡，但未提供定量方法来进行区域设计优化，尤其是从离散优化角度出发。与其他区域划分方法相比，离散优化有两个主要优势：（1）能够通过目标函数明确计算区域间出行需求的数量；（2）可以通过决策变量直接选择构成边界的道路段。因此，这种离散优化建模的缺失被认为是主要的研究差距。

为了解决这一研究空白，我们提出了两种新颖的整数规划模型，即基础区划模型（Base Districting Model，BDM）和扩展区划模型（Extended Districting Model，EDM）。BDM是一个简化的准公共交通区划问题的入门模型，假设单一直线边界在确保区域间工作量平衡的同时最小化区域间出行需求。EDM在BDM的基础上增加了更真实的边界结构，并将边界建模为一系列连接的线段。EDM使用合成数据和真实世界数据进行了测试。在合成分析中，我们发现计算时间随着请求数量和候选边界段数量的增加而迅速增长；尽管所需的计算时间仍然可控（例如几分钟），但提出的解决方案未能达到最优结果。在美国一个大都市区的实际案例研究中，我们进一步验证了该解决方案的有效性，并分析了工作量平衡对区划结果的影响。最后，我们分析了在区域间平衡工作量和管理区域间出行不便之间的权衡。

**本文的贡献**
首先，我们提出了严格的数学公式，用于交通管理部门将其服务区域划分为两个区域的ADA准公共交通区划问题，从而填补了现有文献中的关键空白。为两区域设计案例建立这些离散优化公式本身就是一个重要贡献，而将区划方法扩展到任意数量区域（见附录A）则是一个更大的贡献。其次，我们通过实际案例研究为交通管理部门提供了高效的解决方案，并提供了重要见解，使他们能够做出明智的区划决策，从而提高大都市区的服务质量和运营效率。

我们的基于网络的离散区划研究利用日益丰富的详细运营数据，为ADA准公共交通规划提供了一种及时有效的途径。交通机构越来越依赖先进技术，包括自动化调度和在线出行请求平台，来管理乘客出行和监控服务性能。与连续逼近方法不同，我们的离散优化模型在设计服务区域时利用了详细的出行数据，从而满足了数据驱动决策的需求。

本文的其余部分安排如下：第2节总结了相关区域划分问题的当前文献。第3节提出了初始优化模型，第4节提出了扩展优化模型，第5节提出了自定义解决方案方法。第6节进行了全面的数值研究，以检验区划方法的影响。最后，我们在第7节总结了研究并指出了未来的研究方向。

**文献回顾**
我们在第2.1节回顾了交通管理、物流和传统公共交通中的区域划分问题的方法和策略。随后，在第2.2节，我们调查了准公共交通服务中的多区域结构，分析了跨边界出行的协调机制，并比较了不同的分区策略。第2.3节指出了研究中的空白。

**二维空间中的激励性区划问题**
准公共交通服务中的区域划分问题可以描述如下：准公共交通乘客在二维空间内出行，该空间是一个有界的矩形区域。每个乘客请求ω=(r,s)都有特定的上车地点r和下车地点s，这两个地点都是二维空间中的节点。所有上车和下车地点统称为V，旅行空间中的所有请求集合称为Ω。

**多段边界的扩展**
接下来，我们放宽了边界必须是直线的假设，即边界是由一系列连接的线段组成的，因此称为多段边界。在扩展问题中，我们得到了一组可以作为边界部分的道路链接。为了成为有效的区域边界，边界的一端位于北部边界，另一端位于南部边界。我们需要选择道路链接来形成一条完整的路径。

**提出的解决方案**
公式（21）至（38）的规模随着E和Ω的基数增加而扩大，这促使我们提出了一种分阶段启发式算法，以使处理大规模实例的计算时间可控。总体而言，该启发式算法从一组随机生成的边界开始，通过部分替换边界段来不断改进边界，直到无法进一步改进为止。

**计算实验**
由于考虑单一线段边界的基线模型（见第3节）是对第4节中考虑多段边界模型的简化，我们仅测试扩展模型。为此，我们设计了两个数值研究集合：合成数据和真实世界数据。在第6.1节中，我们考虑了一个矩形区域并测试了所提区划方法的计算效率。在第6.2节中，我们将分析扩展到不规则形状的大都市区。

**总结**
本文提出了首个基于严格定量分析的准公共交通区划问题的离散优化方法。我们首先分析了一个简化案例，即准公共交通服务区域被一条直线划分，并提出了一个基本的整数规划模型。然后，我们考虑了一个道路网络，在该网络上可以选择一系列连接的道路链接来将服务区域划分为两个区域。孙杨：写作——审稿与编辑、写作——初稿编写、内容验证、指导、研究方法、形式分析、概念构建。