铁路轨道维修调度问题的启发式方法外文翻译资料

 2021-11-29 10:11

英语原文共 30 页

铁路轨道维修调度问题的启发式方法

Fan Peng, Seungmo Kang, Xiaopeng Li amp; Yanfeng Ouyanglowast;

伊利诺伊大学厄巴纳 - 香槟分校土木与环境工程系，美国伊利诺伊州厄

Kamalesh Somani和Dharma Acharya

运营研究，CSX Transportation，杰克逊维尔，佛罗里达州，美国

摘要：每年，数十亿美元用于铁路轨道维护，以保持铁路网络的可维护性。这些维护项目（不同类型）必须由规划范围内的合适维护团队执行。本文提出了一种解决轨道维护调度问题（TMSP）的时空网络模型。目标是最小化维护团队的总旅行成本以及维护项目对铁路运营的影响，这些成本由三种类型的侧面约束条件制定：互斥，时间窗口和优先约束。提出了一种迭代启发式求解方法来解决具有大量边约束的大规模TMSP模型。所提出的模型和解决方案方法适用于大规模的现实问题。与当前的行业惯例相比，模型结果消除了所有硬边约束违规，并将总目标值（旅行成本和软边约束违规处罚）降低了66.8％。

1介绍

每年，北美的铁路公司在轨道维护上花费数十亿美元来恢复轨道的缺陷和损坏的可用性，并防止进一步的磨损和潜在的安全隐患。这些项目通常在每年年初之前通过铁路网络通过人工检查或先进技术（Morales等，2008; Schlake等，2009; Ouyang等，2009）和铁路公司进行识别。通常有一定数量的维护团队在一年内完成这些项目。

这些项目的分配和安排往往构成重大挑战。每个维护项目都需要一定的人力资源，并且通常根据维护任务的性质将其分类为不同的类型。每个维护团队都有特定的专业知识和人员规模。因此，合适的团队完成项目的时间取决于项目类型和团队的生产力。此外，由于各种因素，例如铁路交通运营，气候以及不同维护项目之间的相互关系，可用的维护时间非常有限。这些要求中的一些是软性的（即，如果不存在更好的选择，则可以容忍对它们的违反），并且一些要求是硬性的（即，它们永远不应被违反）。设计不良的维护计划可能会导致高昂的维护和运营成本，或者甚至可能由于违规而无法实施。最后，在完成一个项目后，维护团队必须立即前往下一个项目。在连续的项目位置之间运输船员和重型机械的成本非常高。这要求最小化行驶距离，同时所有项目都由合适的团队在适当的时间进行。

许多研究已经研究了长期或短期视野中的公路基础设施维护规划问题（参见Ng et al., 2009的综合评述）。维护活动对交通运营的影响通常表现为交通延误和拥堵。长期规划问题主要集中在制定维护项目的策略，无论是否有交通改道选项，以便在有限的投资预算下将长期运营成本降至最低（例如， Golabi and Pereira, 2003; Ouyang and Madanat, 2004, 2006; Ouyang, 2007; Durango-Cohen and Madanat, 2008; Unnikrishnan et al., 2009; Li et al., 2010）。短期规划主要侧重于减轻即时交通延误（(Cheu et al., 2004; Jiang and Adeli, 2004; Ma et al., 2004）。还对维持其他类型的运输网络进行了研究，例如水管网（Dridi等，2008），其中还应考虑到“交通”的中断。

铁路轨道维护调度问题（TMSP）通常与其高速公路对应物有很大不同。例如，铁路维护项目通常涉及在大的空间区域（例如，整个铁路网络）上运输非常重的机械和大量机组人员，因此维护团队的旅行成本不再可忽略不计。另一个区别是列车通常被视为离散对象，只有很少的重新路由选项，因此维护活动对交通运营的影响通常由特定的业务规则解决，例如互斥（有时也称为非并发）约束（例如，不再应该同时进行相邻轨道段的一次维护活动）。铁路公司通常有许多这样的规则（如第2节所述），结果显着增加了问题的复杂性和计算难度。这些独特的特性假定需要不同的模型配方和解决方案技术。

TMSP仅在近几年进行了研究，大多数现有的研究都集中在单一铁路轨道部分的TMSP上。Higgins（1998）和Higgins等。（1999）开发了一个数学模型来确定维护团队的分配和时间表，以尽量减少列车运行的中断。该模型考虑了预算约束，列车时刻表，机组人员出行时间以及维护活动之间的各种相互关系。该模型应用于短期项目级调度问题（在轨道段上持续数天的项目）并通过禁忌搜索解决。Lake et al。（2002）修改了模型以最小化总维护成本，同时还包括团队设置和拆卸时间。Cheung等。（1999）解决了资源分配问题。

铁路部门根据优先事项优化工作要求分配的问题。Budai等。（2006）讨论了预防性维护计划问题，其中短期日常活动和长期独特项目的制定方式不同。Zante-de Fokkert等人。（2007）开发了一个模型，通过减少夜间维护活动的数量来提高工人的安全。

在大规模铁路网络（即通常包括数百个段）中对TMSP进行的研究非常有限。网络级问题通常涉及数百个项目以及它们之间更复杂的关系，因此会产生更多的侧面约束。例如，为了减少对交通运营的影响，不同的铁路分区（即铁路段）发生在交叉路口（即多条铁路线路汇合或分叉的地方）或走廊（即交通繁忙的路线）多个细分）不允许同时进行持续维护项目。Nemani等人。（2009）提出了TMSP的几个精确模型和启发式算法，其中在目标函数中没有考虑旅行成本，但是对项目之间允许的最大行进距离存在限制。李等人。（2009）提出了一些解决TMSP的算法方法，其中网络和侧面约束都得到了显着的整合，以减少变量的数量。遗憾的是，当严格执行行程距离和侧面约束的精确测量时，现有方法不适用于大规模TMSP。禁止与具有许多侧面约束的大规模TMSP相关联的复杂性使得现有的计算机求解器（例如CPLEX（ILOG，2006））无法获得最佳或甚至可行的解决方案。由于缺乏系统的解决方案技术，目前铁路行业的实践主要依赖于临时试验，直觉和专家经验。解决方案过程可能需要数周，但很少提供令人满意的甚至可行的解决方案。

常用的解决方案技术如拉格朗日松弛（Fisher，1981）和色谱柱生成（Desaulniers等，2005）很难为TMSP实施。拉格朗日松弛要求模型具有特殊的子结构，以便在放松一些约束时，剩下的问题很容易解决。TMSP问题有许多混合边约束，放松它们会使拉格朗日松弛算法难以收敛。列生成要求原始问题可分解为仅具有少量相互关联约束的子问题。但是，在我们的例子中，子问题是由许多边约束相互关联的。即使拉格朗日松弛和列生成嵌入在分支定界框架中（Fisher，1981;Desaulniers等人，2005），由于大量的分支变量，获得可行的解决方案通常需要很长时间。

本文旨在为大型铁路网络制定TMSP，并开发一种有效地找到良好维护计划的混合启发式方法。该方法显着提高了解决方案质量（即可行性和最优性）并缩短了计算时间。经验数据的数值研究表明，解决方案质量几乎在所有方面都明显优于当前的行业实践。

本文的其余部分安排如下。第2节介绍了问题并详细解释了侧面约束。第3节介绍了解决方案的技巧。第4节将提出的算法应用于经验实例，并显示了算法的性能。第5节总结了本文，并讨论了未来可能的扩展。

2 模型配方

通常，TMSP可以被制定为时空网络（TSN）模型或具有侧面约束的车辆路径问题（VRP）模型。感兴趣的读者可以参考Desrochers等人的文章。（1992），Yan等。（2008年），和施密德等人。（2010）了解这些模型的更多细节。已经提出了一些最近的算法来解决具有通用时间窗的VRP（VRPGTW）（Ibaraki等，2005），并且可以解决TMSP中的侧约束的子集。然而，TMSP通常具有VRP算法无法有效解决的其他类型的侧面约束，因此大多数关于TMSP的研究（例如，Nemani等人，2009; Li等人，2009）采用TSN类型的模型公式。在本研究中，使用商业解算器CPLEX对VRP和TSN配方进行了小问题实例（即两个团队和数十个项目）的测试。事实证明，CPLEX无法在合理的时间限制内（即15分钟）改进VRP配方的初始解决方案，但它能够为TSN配方做到这一点。因此，提出TSN方法来制定TMSP问题。

本节介绍铁路TMSP问题的数学公式。为简单起见，首先引入通用TSN模型而没有侧面约束。然后制定侧面约束。还讨论了拆分项目，提高可行性和最优性的可能做法。

2.1 通用时空网络模型

铁路网络通常规模非常大且非常稀疏。在许多情况下，一个项目跨越了网络中的整整一个轨道（而不是一个点），团队需要从一个顶点到另一个顶点。对于TMSP问题，铁路网络可以用有向终端和项目里程碑作为顶点和铁路段作为边缘的有向图来表示。为了减少计算难度，可以将该有向图进一步简化为具较少数量的顶点和边GV，E的等效网络表示，其中V 1,2，...，V是顶点集（即节点） ），E是一组边（即弧）。这里，V代表集合V的基数。附录解释了网络缩减算法的细节。让T成为一组维护团队。将cv1v2t定义为团队t T从v1 移动到v2，v1，v2 V的旅行成本。我们假设旅行成本仅发生当团队在不同项目之间移动时，而不是在他们执行项目时移动。原因是后一种运动是不可避免的，并导致固定成本。成本cv1v2t也被假定为v1 和v2之间的移动距离的简单线性函数。与项目花费的时间相比，团队旅行时间通常可以忽略不计。

团队和项目通常分为两类：铁路和T＆S（木材和表面处理），每个类别进一步分为多种类型。例如，铁路团队类型可能包括大型铁路，小型铁路和混凝土，铁路项目类型可能包括曲线补丁和混凝土修复。团队可以根据他们的专业来处理一种或多种类型的项目。设P是项目集，Tp属于T是可以执行项目p属于P的团队的子集，Pt属于P是团队t可以执行的项目的子集。

在此模型中，计划范围被离散化为数周（或必要时的任何其他时间单位）。设W 1,2 ...，W表示计划范围内所有周的集合（例如，我们研究中的一年）。由于团队具有不同的生产率，我们将l 铂 定义为项目p属于P由团队t属于Tp执行的持续时间（以周数表示）。我们定义集合

Wt属于W和Wt, W使得在规划范围内，

team t属于T允许在W属于Wt的任何一周开始工作，并在任何一周w, Wt,结束他们的工作。调度灵活性随着Wt 和Wt,的大小而增加。如果Wt 和Wt, 都是单例（即，只有一个元素的集合），团队t必须在指定的周数开始和结束其工作;如果Wt 和Wt, 都等于W，那么该团队可以自由选择其时间表（如果没有其他限制）。

为了模拟TMSP问题，我们构建了一个如图1所示的时空网络。空间铁路网络每周复制一次。将另外两个顶点vs 和vs添加到V以用作时空网络的源和宿。

图1.时空网络的图示

我们假设它们对任何其他顶点的旅行成本为零。时空中有两种类型的流网络：（i）空间网络层内的流动，对应于不同项目之间的旅行;（ii）流过各层，相应的进行项目的活动。定义X：={xv1v2tw，forall;v1，v2 isin;V，forall;tisin;T，forall;wisin;W}作为类型的集合 (i) 如果团队t旅行，二元流量xv v tw = 1从顶点v1到顶点v2 在周w;否则为0。

定义Y：yptw，t Tp，p P，w W作为类型 - （ii）流的集合，其中如果团队t在周w开始在项目p上工作，则二进制流yptw 1 ;或0其他。因为一个项目有两个端点，一个团队可能开始在其中任何一个工作，我们进一步定义

变量yptw 和yptw，st yptw y-ptw yptw，对于按照团队遵循的方向。假设v1 和v2是项目p和v的两个端点v1 lt;v2。然后y ptw = 1，y-ptw = 0如果团队t从v1 开始并结束在v2;yptw 0，yptw 1否则。设Pt ,v Pt 是

可由团队t执行且其端点v，v, 满足v lt;v,的项目子集。类似地，对应物Ptminus;,v Pt 包含vgt; v,的那些项目。

基本数学模型可以表述为

如下：

目标函数（1a）最小化总旅行成本。约束（1b）（1d）确保流量守恒：团队t在规划期开始时开始工作，并且在完成项目之后，它必须立即移动到下一个项目，直到规划期限结束。约束（1e）表示团队在项目执行期间遵循的方向。约束（1f）确保每个项目只执行一次。约束（1g）和（1h）定义二进制变量。

目标函数（1a）最小化总旅行成本。约束（1b）（1d）确保流量守恒：团队t在规划期开始时开始工作，并且在完成项目之后，它必须立即移动到下一个项目，直到规划期限结束。约束（1e）表示团队在项目执行期间遵循的方向。约束（1f）确保每个项目只执行一次。约束（1g）和（1h）定义二进制变量。

2.2 侧面约束

铁路公司施加了限制，以确保项目进度是切实可行的可实施且具有成本效益。我们将众多的边约束分为三类：时间窗（TW），互斥（ME）和前dence（PREC）。对于现实世界的问题，严格执行所有方面的约束通常是不可能的允许违反某些方面的限制，并带来一些惩罚成本。每次违规罚款cTW，我，c我，我 和cPREC，我的值由铁路公司根据约束对公司业务运营的影响来确定，其中下标i表示不同的约束。总惩罚成本可表示为

其中非负整数变量delta;TW，我，delta;我，我和delta;PREC，我 分别是对每个相应约束的违规次数。某些类型的约束（例如下面介绍的互斥约束）可能会导致对一个约束的多次违反。因此整个问题的目标函数变为：

2.2.1时间窗口约束

天气是需要在特定时间窗口内执行项目的最重要因素之一。例如，我们不像北方地区的项目由于低温而在冬季进行由于季节性低/高铁路交通量（例如，假日季节），在某些特定周内/之外进行。对于任何p P，让WTW,p 成为周的子集

不应

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章