针对列车单一路线选择问题的精确解决方法

《European Journal of Operational Research》：An exact approach for the Train Single-Routing Selection Problem

　　我们研究了铁路交通管理中的列车单路径选择问题。通过一种专门的BQP线性化方法，引入了一种新的MILP公式。对LP松弛条件的加强显著提高了性能。首次实现了对实际案例的最优求解。新的公式表现优于现有的TSRSP公式。

铁路交通管理（RTM）旨在协调列车运行，确保效率和准时性。它涉及规划列车路线和时刻表，以在发生干扰时最小化延误传播。两个关键任务是：（i）选择允许列车从起点到终点通过控制区域的轨道序列；（ii）确定列车在共享轨道上的通行顺序。文献中提出了不同的方法来解决这些问题；感兴趣的读者可以参考Cacchiani等人（2014年）、Corman和Meng（2015年）、Croella（2022年）、Fang等人（2015年）以及Wen等人（2019年）的研究。总的来说，主要有两种方法：一些方法解决整个列车路由和调度问题（Fischetti和Monaci，2017年；Meng和Zhou，2014年），而另一些方法专注于纯列车调度，考虑每列列车只有一条路线（Corman等人，2014年；Croella等人，2022年；D’Ariano等人，2007年）。通常，前一种方法假设必须同时选择轨道序列和通行顺序，以便有效利用基础设施容量。由于计算资源限制，这种同时选择的方式通常会导致接受次优解。后一种方法则假设可以预先选择具体的行驶轨道序列，计算资源的最高效使用是集中精力寻找调度问题的全局最优解。Pellegrini等人（2015年）采用了这两种假设，他们首先解决纯调度问题，如果计算资源剩余，将找到的解作为路由和调度问题求解的起点。

所有RTM方法的一个关键挑战是为列车分配路线，无论是确定多条路线还是一条路线。在枢纽和车站区域，这个问题变得特别复杂，因为每列列车可能有 dozens 条替代路线可供选择，类似的路线选择决策也出现在更广泛的铁路规划问题中，例如结合乘客流量分配的列车服务设计（Feng等人，2024年）。为了解决这个挑战，列车路由选择问题（TRSP）旨在为一组列车生成一定数量的独特路线分配。在每个分配中，每列列车只选择一条路线，选定的路线必须相互兼容，并且任何两个分配至少在一条列车路线选择上有所不同。目标是以最低成本生成这些分配，成本包括两部分：一部分与路线本身相关，另一部分源于路线对之间的相互作用并反映其干扰。TRSP最初由Samà等人（2016年）在文献中提出，他们提出了一个蚁群优化（ACO）启发式算法来解决它。Pascariu等人（2022年）和Sharma等人（2024年）进一步完善了该算法，提出了设置分配成本和将并行性融入算法的方法。他们的结果表明，通过改进算法，从而改进路由选择解决方案，RTM解决方案在时间表干扰和基础设施中断的情况下都有显著提升。Pascariu等人（2024年）和Samà等人（2017年）证明，将TRSP解决方案整合到RTM中可以显著提高交通性能，无论在解决TRSP时是否知道具体的中断情况、最小化的是延迟函数，还是使用的路由和调度方法是什么。

在本文中，我们解决了列车单路径选择问题（TSRSP），即为每列列车选择一条路线，同时最小化总分配成本并确保选定路线之间的相互兼容性。最小化成本是对调度目标函数的近似，考虑了与选定路线相关的行驶时间以及路线对之间的潜在相互作用（Samà等人，2016年）。Pascariu等人（2022年）提供了统计证据，表明这种成本与RTM调度解决方案有显著的正相关：低成本TSRSP解决方案更有可能导致列车延误较低的调度解决方案。

TSRSP在实践中的重要性体现在三个主要应用中。首先，TSRSP在RTM中至关重要：基于调度的RTM方法要求每列列车选择一条路线，它可以为涉及重新路由的方法提供高质量的初始解决方案。其次，它在战术RTM问题中有潜在用途，其中经常忽视了列车路由优化。例如，无论是在几个月前计划的时间表中，还是在操作前不久为了处理轨道不可用的意外情况进行调整时，都必须为每列列车指定一条路线（Pascariu等人，2022年）。第三，一个高效的TSRSP方法可以集成到迭代框架中，以生成不同的分配，为高级精确和启发式算法提供基础。在所有这些应用中，最优的TSRSP解决方案可以作为RTM方法中列车的指定路线分配。由于是最优的，这是成本最小的分配，根据Pascariu等人（2022年）的结果，这很可能会导致最低的列车重新调度需求或延误。此外，计算和认证最优TSRSP解决方案为评估启发式方法和量化路线分配决策的改进潜力提供了参考点。

除了在RTM中的实际相关性外，TSRSP还呈现出一个有趣的组合优化结构。如第2节所示，TSRSP实例可以表示为一个加权无向层状图，其中路线对应于顶点，兼容的路线对对应于边。在这种设置中，可行解对应于图中的每个层恰好包含一个顶点的k-团。这种表示揭示了与几个知名图优化问题的联系，包括最大团问题、顶点加权最大团问题（Alidaee等人，2007年；San Segundo等人，2019年）和加权k-子图问题（Billionnet，2005年；Lanciano等人，2024年；Martí等人，2010年）。利用这种特定结构是获得强松弛和有效精确解方法的关键。

到目前为止，只有Pascariu等人（2021年）解决了精确的TSRSP问题，他们提出了一个整数线性规划（ILP）模型并进行了测试。这个ILP模型被用来开发一种启发式方法，然后与文献中的ACO启发式算法进行了比较。然而，从这个ILP模型得出的启发式解决方案在短计算时间内不如ACO算法得到的解决方案。此外，即使延长计算时间，Pascariu等人（2021年）的ILP模型也难以计算出最优解或强下界。因此，该模型几乎不能作为评估启发式或元启发式算法性能的基准，而精确模型可以发挥这样的基准作用。

本研究的主要贡献是第一个能够在短计算时间内证明最优解的精确方法，而此类实例之前仅通过启发式方法解决。从二元二次规划（BQP）公式和定制的线性化方法出发，我们开发了一种利用TSRSP组合结构的问题特定强化策略。这产生了一系列改进的公式，并建立了理论上的优势关系，显著提高了计算性能。此外，所提出的公式使得能够计算和认证一系列实际实例的最优解，从而首次为评估TSRSP启发式方法的质量提供了可靠的基准。

本文的其余部分组织如下。第2节正式定义了TSRSP并提供了其图论解释。第3节介绍了BQP公式并讨论了相关的解决方案方法。第4节介绍了提出的强化公式，第5节描述了用于比较的基准公式。第6节提供了公式之间的理论比较。第7节报告了在实际铁路实例上的计算结果。最后，第8节总结了本文并展望了未来研究的方向。

列车单路径选择问题（TSRSP）包括为每列列车选择一条路线，同时最小化总分配成本，并确保所选路线之间的相互兼容性。最小化的成本是对调度目标函数的近似，考虑了与选定路线相关的行驶时间和路线对之间的潜在相互作用（Samà等人，2016年）。Pascariu等人（2022年）提供了统计证据，表明这种成本与RTM调度解决方案有显著的正相关性：低成本TSRSP解决方案更有可能导致列车延误较低的调度解决方案。

TSRSP在实践中的重要性体现在三个主要应用中。首先，在RTM中，TSRSP至关重要：基于调度的RTM方法要求每列列车选择一条路线，它可以为此类方法提供高质量的初始解决方案。其次，它在战术RTM问题中有潜在用途，其中经常忽视列车路由优化。例如，无论是在几个月前计划的时间表中，还是在操作前不久调整时间表以应对轨道不可用的意外情况，都必须为每列列车指定一条路线（Pascariu等人，2022年）。第三，高效的TSRSP方法可以集成到迭代框架中，以生成不同的分配，作为TRSP的先进精确和启发式算法的基础。在所有这些应用中，最优的TSRSP解决方案可以作为RTM方法中列车的指定路线分配。由于是最优的，这是成本最小的分配，根据Pascariu等人（2022年）的结果，这很可能会导致最低的列车重新调度需求或延误。此外，计算和认证最优TSRSP解决方案为评估启发式方法和量化路线分配决策的改进潜力提供了参考点。

除了在RTM中的实际相关性外，TSRSP还呈现出一个有趣的组合优化结构。如第2节所示，TSRSP实例可以表示为一个加权无向层状图，其中路线对应于顶点，兼容的路线对对应于边。在这种设置中，可行解对应于包含图中每一层恰好一个顶点的k-团。这种表示揭示了与几个众所周知的图优化问题的联系，包括最大团问题、顶点加权最大团问题（Alidaee等人，2007年；San Segundo等人，2019年）和加权k-子图问题（Billionnet，2005年；Lanciano等人，2024年；Martí等人，2010年）。利用这种特定结构是获得强松弛和有效精确解方法的关键。

精确的TSRSP解决方案之前仅由Pascariu等人（2021年）解决，他们提出了一个整数线性规划（ILP）模型并进行了测试。这个ILP模型被用来开发一种启发式方法，然后与文献中的ACO启发式算法进行了比较。然而，从这个ILP模型得出的启发式解决方案在短计算时间内的效果不如ACO算法。此外，Pascariu等人（2021年）的ILP模型即使延长计算时间也难以计算出最优解或强下界。因此，该模型几乎不能用作评估启发式或元启发式算法性能的基准，而精确模型可以发挥这样的基准作用。

本研究的主要贡献是第一个能够在短计算时间内解决实际TSRSP实例并证明其最优性的精确方法，而此类实例之前仅通过启发式方法解决。从二元二次规划（BQP）公式和定制的线性化方法出发，我们开发了一种利用TSRSP组合结构的问题特定强化策略。这产生了一组改进的公式，并建立了理论上的优势关系，显著提高了计算性能。此外，所提出的公式使得能够为广泛的实际实例计算和认证最优解，从而首次为评估TSRSP启发式方法的质量提供了可靠的基准。

本文的其余部分组织如下。第2节正式定义了TSRSP并提供了其图论解释。第3节介绍了BQP公式并讨论了相关的解决方案方法。第4节介绍了提出的强化公式，第5节描述了用于比较的基准公式。第6节提供了公式之间的理论比较。第7节报告了在实际情况上的计算结果。最后，第8节总结了本文并概述了未来研究的方向。

列车单路径选择问题（TSRSP）的一个实例包括一组k列列车K={1,2,…,k}和一组n条路线V={1,2,…,n}。路线集V被划分为k个子集Vi，每个列车i∈K对应一个子集，即我们有：V=?i∈KVi且Vi∩Vj=0?，i,j∈K,i< />< />
针对tsrsp的一个新的bqp公式：对于兼容图g=(v,e)中的每个顶点r∈v，让xr∈{0,1}是一个二进制变量，如果顶点r包含在g的k-团中则取值1，否则取值0。使用这些|v|个二进制变量，我们提出了以下tsrsp的bqp公式：minx∈{0,1}|v|∑r∈vprxr+∑{r,s}∈ecrsxrxs：xis ak-clique ing。公式（8）中的二次目标函数最小化了总成本，包括路线成本和配对成本。当xr=1时，表示路线r∈v的成本，而配对成本表示...

针对tsrsp的一个新的milp公式：在本节中，我们在bqp公式（8）的基础上，引入了一种新的、有效的milp公式，专门通过适应glover（1975）提出的线性化技术来针对问题的独特结构进行设计。得到的模型包含了一定数量的额外非负变量和约束。关键的是，它利用了tsrsp兼容图的k部分结构，从而获得了强lp松弛和非常好的计算性能...

针对tsrsp的其他公式：在本节中，我们引入了两种用于基准测试的额外tsrsp公式。第一种是通过glover和woolsey（1974）提出的经典线性化方法获得的milp公式（参见caprara（2008年）和pisinger（2007年））。我们将这种线性化称为glover–woolsey线性化技术...

针对tsrsp的milp公式的理论比较：在本节中，我们提供了对本文研究的tsrsp的milp公式的理论比较。分析集中在公式的变量数量和约束数量以及它们的lp松弛强度上。然后，第7节的计算测试对此进行了补充。

在计算测试中，我们展示了我们广泛的计算测试结果，以评估新公式g在tsrsp（见第4节）与前面几节讨论的基准公式（即q、gw和s公式，见第3节和第5节）相比的性能。我们的主要目标有三个：1. 通过识别最大的实例大小来评估公式的计算效率...

结论：tsrsp是rtm中的一个重要问题，它旨在为每列列车分配一条路线，同时最小化总成本并确保所选路线之间的相互兼容性。在本文中，我们介绍并测试了一种新的milp公式，通过将glover（1975）的线性化技术适应到问题的bqp公式中获得。通过利用tsrsp的特定结构，我们进一步加强了新milp模型的lp松弛。我们进行了...

credit作者贡献声明：anna livia croella：撰写——原始草稿，可视化，验证，软件，方法论，调查。fabio furini：撰写——审阅与编辑，撰写——原始草稿，可视化，验证，监督，方法论，调查，概念化。ivana ljubi?：撰写——审阅与编辑，验证，监督，方法论，概念化。bianca pascariu：数据整理。 针对tsrsp的一个新的bqp公式：对于兼容图g=(V,E)中的每个顶点r∈V，让xr∈{0,1}是一个二进制变量，如果顶点r包含在G的k-团中则取值1，否则取值0。使用这些|V|个二进制变量，我们提出了以下TSRSP的BQP公式：minx∈{0,1}|V|∑r∈Vprxr+∑{r,s}∈Ecrsxrxs：xis ak-clique ing。公式（8）中的二次目标函数最小化了总成本，包括路线成本和配对成本。当xr=1时，表示路线r∈V的成本，而配对成本表示... 针对tsrsp的一个新的milp公式：在本节中，我们在bqp公式（8）的基础上，引入了一种新的、有效的milp公式，专门通过适应glover（1975）提出的线性化技术来针对问题的独特结构进行设计。得到的模型包含了一定数量的额外非负变量和约束。关键的是，它利用了tsrsp兼容图的k部分结构，从而获得了强lp松弛和非常好的计算性能... 针对tsrsp的其他公式：在本节中，我们引入了两种用于基准测试的额外tsrsp公式。第一种是通过glover和woolsey（1974）提出的经典线性化方法获得的milp公式（参见caprara（2008年）和pisinger（2007年））。我们将这种线性化称为glover–woolsey线性化技术... 针对tsrsp的milp公式的理论比较：在本节中，我们提供了对本文研究的tsrsp的milp公式的理论比较。分析集中在公式的变量数量和约束数量以及它们的lp松弛强度上。然后，第7节的计算测试对此进行了补充。 在计算测试中，我们展示了我们广泛的计算测试结果，以评估新公式g在tsrsp（见第4节）与前面几节讨论的基准公式（即q、gw和s公式，见第3节和第5节）相比的性能。我们的主要目标有三个：1. 通过识别最大的实例大小来评估公式的计算效率... 结论：tsrsp是rtm中的一个重要问题，它旨在为每列列车分配一条路线，同时最小化总成本并确保所选路线之间的相互兼容性。在本文中，我们介绍并测试了一种新的milp公式，通过将glover（1975）的线性化技术适应到问题的bqp公式中获得。通过利用tsrsp的特定结构，我们进一步加强了新milp模型的lp松弛。我们进行了... credit作者贡献声明：anna livia croella：撰写——原始草稿，可视化，验证，软件，方法论，调查。fabio furini：撰写——审阅与编辑，撰写——原始草稿，可视化，验证，监督，方法论，调查，概念化。ivana ljubi?：撰写——审阅与编辑，验证，监督，方法论，概念化。bianca>
针对tsrsp的一个新的bqp公式：对于兼容图g=(v,e)中的每个顶点r∈v，让xr∈{0,1}是一个二进制变量，如果顶点r包含在g的k-团中则取值1，否则取值0。使用这些|v|个二进制变量，我们提出了以下tsrsp的bqp公式：minx∈{0,1}|v|∑r∈vprxr+∑{r,s}∈ecrsxrxs：xis ak-clique ing。公式（8）中的二次目标函数最小化了总成本，包括路线成本和配对成本。当xr=1时，表示路线r∈v的成本，而配对成本表示...

针对tsrsp的一个新的milp公式：在本节中，我们在bqp公式（8）的基础上，引入了一种新的、有效的milp公式，专门通过适应glover（1975）提出的线性化技术来针对问题的独特结构进行设计。得到的模型包含了一定数量的额外非负变量和约束。关键的是，它利用了tsrsp兼容图的k部分结构，从而获得了强lp松弛和非常好的计算性能...

针对tsrsp的其他公式：在本节中，我们引入了两种用于基准测试的额外tsrsp公式。第一种是通过glover和woolsey（1974）提出的经典线性化方法获得的milp公式（参见caprara（2008年）和pisinger（2007年））。我们将这种线性化称为glover–woolsey线性化技术...

针对tsrsp的milp公式的理论比较：在本节中，我们提供了对本文研究的tsrsp的milp公式的理论比较。分析集中在公式的变量数量和约束数量以及它们的lp松弛强度上。然后，第7节的计算测试对此进行了补充。

在计算测试中，我们展示了我们广泛的计算测试结果，以评估新公式g在tsrsp（见第4节）与前面几节讨论的基准公式（即q、gw和s公式，见第3节和第5节）相比的性能。我们的主要目标有三个：1. 通过识别最大的实例大小来评估公式的计算效率...

结论：tsrsp是rtm中的一个重要问题，它旨在为每列列车分配一条路线，同时最小化总成本并确保所选路线之间的相互兼容性。在本文中，我们介绍并测试了一种新的milp公式，通过将glover（1975）的线性化技术适应到问题的bqp公式中获得。通过利用tsrsp的特定结构，我们进一步加强了新milp模型的lp松弛。我们进行了...

credit作者贡献声明：anna livia croella：撰写——原始草稿，可视化，验证，软件，方法论，调查。fabio furini：撰写——审阅与编辑，撰写——原始草稿，可视化，验证，监督，方法论，调查，概念化。ivana ljubi?：撰写——审阅与编辑，验证，监督，方法论，概念化。bianca pascariu：数据整理。>Paola Pellegrini：写作——审稿与编辑、验证、监督、方法论、利益冲突声明
作者声明他们没有已知的、可能影响本文所述工作的财务利益或个人关系。

致谢
本项工作是在MOST（可持续交通国家研究中心）的支持下完成的，并获得了欧盟“下一代欧盟计划”（PNRR）（任务4，组成部分2，投资1.4，项目编号1033，日期2022年6月17日，编号CN00000023）的资助；同时该项目还获得了MICIU/AEI/10.13039/501100011033以及ERDF/EU的资助（项目编号PID2024-155948OB-C54）。本手稿仅代表了作者的观点和意见，欧盟委员会对此不承担任何责任。

Anna Livia Croella | Fabio Furini | Ivana Ljubi? | Bianca Pascariu | Paola Pellegrini | Pablo San Segundo