文摘

摘要matheuristic迭代方法(MHIA)提出解决线路规划问题,也称为网络设计问题,和频率设定在中国高速铁路网络。我们的成本为重和passenger-oriented目标优化模型集成到以利润为导向的目标。因此,旅客旅行时间是包含在票价使用旅行时间的价值。因此,转移和弯路会导致较低的票价,从而降低运营商的收入。当评估一个给定的性能线计划,乘客将旅行的方式通过网络需要模仿。这个乘客分配通常是一个耗时的计算。提出规划迭代方法提高了线计划使用容易地判断指标。在这个过程中,一个混合整数线性规划模型解决了乘客分配和优化频率设置以实现经营利润最大化。执行广泛的计算实验表明了方法的有效性处理现实世界的铁路网络线路规划问题。通过大量计算小例子网络和real-world-based实例,实验结果表明,该模型可以提高平均利润22.4%比较他们最初的解决方案。 When comparing to an alternative iterative approach, our proposed method has advantage of obtaining high quality of solutions by improving the profit 10.8% on average. For small, medium, and large size networks, the obtained results are close to the optimal solutions, when available.

1。介绍

中国高速铁路(高铁)网络在过去的十年里发展迅速。更多的铁路线将建于2020年完成一个全面的中国80%的城市之间的联系。目前,高铁网络包含的基本骨干4“纵向”和“横向”跟踪(4 v4h)。实际在中国高铁业务不同于欧洲和日本,因为在中国,每天大量的长途高铁列车运行满足尽可能多的旅客旅游需求。然而,乘客平均出行距离通常是相对于高铁线路的长度要短得多。例如,平均乘客出行距离的两个主要高铁线路约558公里(京广高铁)和621公里(京沪高铁),而线的长度是2281公里和1318公里,分别为(1]。这可能导致铁路资源的低效使用等培训能力和能力。例如,高铁列车的乘客平均负载率小于40%在一些极端情况下(2]。

高铁网络的线路规划是一个复杂的任务,因为大规模的大小,高交通需求,网络容量有限。开发一个高效的线计划来提高整个网络的运营表现越来越紧迫。

本文旨在设计一个4 v4h高铁网络计划和确定线路的频率,优化运营成本和旅客旅行时间,同时考虑在必要时转移。为了获得这个,以利润为导向的目标函数。当乘客需求(或潜在)被认为是和固定,运营商的利润是由运营商成本和火车票的销售收入。(变量)运营商运营成本是由线。火车票的价格被认为降低当乘客需要转让或绕道到达他们的目的地。这是详细解释3.3节。因此,权衡之间必须在线路规划,一方面,操作越来越长线条和,另一方面,转移和长途旅行的乘客。

本文提出了一种迭代方法结合一个混合整数线性规划(MILP)模型对运营商的利润最大化在线路规划。迭代方法旨在确定更好的行一些修改当前的一组行基于快速评估当前行计划。的MILP优化频率设置行基于预期的路线的乘客将所谓的“客运任务”(或“中转任务”)。这两个阶段被我们称之为matheuristic迭代优化迭代方法。

本文的详细的贡献如下:(我)提出了一种以利润为导向的目标使用一个参数来考虑时间价值的旅行时间机票价格。(2)matheuristic迭代方法旨在解决线路规划问题。(3)不同的本地搜索的改进是提高当前的一组行,比如扩展线,减少一行,插入一行,和删除一条线。快速和启发式评估方法设计选择最有前途的社区解决方案为了获得一个更好的计划。(iv)MILP优化基于预期的频率设置线客运任务。(v)另一种解决方法也发达为了说明我们的方法的有效性。(vi)许多不同大小的基准实例设计和详细信息一起提供最好的解决方案。

本文的其余部分的结构如下。在第二节综述了现有文献关于垂直距离。之后,我们提出一个数学模型来定义我们以利润为导向的详细规划问题第三节。这个模型还将用于解决乘客赋值和频率设置问题。在第四节提出了,我们matheuristic迭代方法。几个案例研究和数值实验中所示第五节评估性能和该方法的有效性。最后,我们的方法的性能,为中国高铁网络,我们的结果和我们进一步的工作进行了总结第六节。

2。文献综述

公共交通的规划过程通常分为连续规划阶段。Desaulniers和西克曼(3考虑网络设计,即。,building the infrastructure, as the first phase, usually followed by line planning, timetabling, and then vehicle and crew scheduling. During operations, disturbances and disruptions might occur. Therefore, real-time rescheduling is required in order to minimize passenger inconvenience. As a crucial component of public transportation planning, the line planning problem (LPP) has attracted more and more attention recently [4- - - - - -7]。基本上,垂直距离决定停止将服务线和秩序。然后,频率设置是决定如何操作通常是每一行。许多不同变体的线路规划,不同的假设和目标,在艺术的状态。我们将讨论选择最相关的论文在这一节和定义变量在下一节我们将解决数学。

Canca et al。7]可能描述一个问题最接近问题探讨。然而,主要的差异是组件的目标函数和时间计划。在[7),目标函数包括门票收入、运营成本和网络基础设施建设成本都基于运营商的观点。相反,我们的模型结合passenger-oriented和成本为重目标以利润为导向的目标。我们使用的方法在我们的模型考虑机票的价格,取决于旅客旅行时间不包括在7]。规划期内,Canca et al。7)考虑收入(即在很长一段时间。,years), while the LPP in this paper considers a much shorter duration (i.e., per day). Since the passenger demand scenario per day used in our model represents the regular pattern of the demand during a long period of time, our objective represents the profit over a longer period of time, typically three months, six months, or a year. If also the investment of building railway infrastructure is considered, as in [7),考虑时间范围通常至少多年。

当比较(7),目标函数类似的组件是收入的函数,变量的操作成本,采购成本(即。在我们的模型中,固定成本)。我们的收益函数认为票价取决于旅行的时间,这是不考虑7]。除此之外,两个模型都包括操作成本的可变成本线的长度有关,但船员成本增加(7]。所示的船员成本(7线(即有关。,frequency) and the yearly crew cost per train. We consider the crew cost as a fixed cost per train in our model. In addition, the acquisition cost in [7)制定购买每列火车模型,而固定成本在我们的MILP包括折旧费用、材料费用、燃料费用,人员费用,每列车和其他相关费用。

总之,我们的模型不仅考虑门票收入,还包括旅客旅行时间进入以利润为导向的目标,以减少旅客旅行时间,要做一块更好的成本为重和passenger-oriented目标之间的权衡。我们认为这个模型对以利润为导向的线路规划在实践中更有用。

行规划模型可以根据目标函数分为两组:成本为重客观和passenger-oriented目标。成本为重线规划问题,目标函数是最小化运营成本(8- - - - - -11]。passenger-oriented线规划问题关注最大化直接旅行者的数量12,13)或减少旅客旅行时间和/或转移的数量(14,15]。在这些问题中,运营商成本视为约束,如有限数量的行。这是经Nachtigall Jerosch [16),建议成本为重客观和passenger-oriented目标可以被认为是通过将其中一个转换为约束条件。

显然,一些方法试图结合成一个单一的两个方面的问题。Pfetsch和Borndorfer17)提出了一个成本为重,passenger-oriented目标函数的加权和。猩红热[18)提出了一个方法来优化运营成本和旅客旅行时间迭代在城市道路网络。

passenger-oriented线规划的一个关键挑战是,线的性能评价计划,乘客路径选择或者旅客作业需要模仿。这也将确定每一行上的乘客的数量。这导致一个上下两层的优化问题,解决了线路规划问题上水平,优化客运任务在低水平1,5]。弗里德里希et al。19]调查成本为重线规划模型与一名乘客分配评估过程。因为目标是成本为重,解决方案更注重运营成本,服务质量有负面影响。Borndorfer和Karbstein20.)集成线路规划和乘客通过使用直接连接路由优化方法,它鼓励和惩罚转移直接连接。此外,Karbstein [21)应用的一种变体2-terminal Steiner连接性问题处理传输集成线路规划和乘客路由。集成线路规划的复杂性和乘客路由调查施密特和Schobel [22]。结果表明,由此产生的问题是np困难甚至在非常特殊的情况下。

解决垂直距离时,一个早期的方法使用一个骨架模型,描述了Silman et al。23从迭代短篇),组装路线。添加停止之后,短片段相连的最短路径形成线的计划。许多线路规划方法假设有限的可能行是可用的或预先计算,例如,(14,19]。许多模型和算法提出了构造线池和可以在Kepaptsoglou Karlaftis [24]。其他方法解决垂直距离构造和修改线而不是使用的线(25- - - - - -28]。这些方法通常认为()和最小最大行每一行的长度。考虑在垂直距离变得倾向于启发式方法减少计算时间,同时承诺高质量的解决方案。分析不同的启发式方法应用于城市线规划研究Ahmed et al。29日]。施密德[30.)分解快速公交线路规划使用一个大型社区搜索计算线规划设计子问题和使用一个线性规划模型来获得乘客的结果赋值和频率设置。几个实例考虑单个通道测试显示该方法的效率。Goerigk和施密特(31日)用上下两层的优化模型线规划与乘客路径选择,并提出了两种不同的技术,二进制变量和“big-M-constraints”,将上下两层的模型到一个水平模型。但当实例变得大,说250个车站,需要遗传算法在确定并执行好乘客出行时间和运营成本之间的权衡。在[7),一个ALNS metaheuristic方法解决线路规划问题提出了铁路快速运输。branch-and-cut每个迭代的算法称为解决乘客分配给操作的结果信息,如频率,火车类型和舰队的规模。可以找到更多细节上的垂直距离在概述Schobel [32)和施密特(33]。

摘要,而不是选择成本为重、以顾客为中心目标,我们提出一个以利润为导向的规划模型,最大化的票价收入减去运营成本。机票价格(因此运营商收入)减少当乘客需要转让或绕道,没有直达车从原点到目的地。这是补偿乘客面临绕道或转让和鼓励铁路运营商尽可能提供直接服务。此外,运营成本考虑固定和length-dependent成本操作不同的线路。以利润为导向的线路规划也将上下两层的线路规划问题和乘客路径选择到一个程度问题。我们有初步结果以利润为导向的线计划发表在会议论文(34]。然而,在这篇论文,乘客的任务是做一些,而本文MILP适用于优化客运任务。此外,在当前的纸,一个更好的结构实现本地搜索运营商可以进一步提高解决方案方法的性能。

3所示。以利润为导向的线路规划

本节首先讨论线路规划问题的假设认为本文以及所需的输入数据。然后,数学上定义的问题是一个混合整数线性规划模型。最后,网络是一个小例子介绍说明了以利润为导向的规划问题。

3.1。假设和输入数据

本文提出了以利润为导向的规划侧重于优化线计划时考虑乘客分配和行计划设计在一个单一的模型。集成模型旨在使成本为重目标之间的权衡,相关操作,和长度的行数和passenger-oriented宗旨,最小化旅游不便。这次旅行不便在这里定义为额外的旅行时间的旅行时间相比,沿着最短路径直接连接的基础设施网络。为了制定集成模型,以下本文中假设是:(我)停止模式:因为只有主要站被认为是作为网络节点,吸引大多数的高铁客运需求和高铁网络的骨干,停止模式的计划被认为是这些主要电视台的都停止模式。小车站的乘客需求的主要车站可以分配给precalculation阶段。(2)需求:乘客需求假设对称。网络中所有的需求必须最多配两个转移。在这个网络的规模有限(只考虑主要站),两个转移应该绰绰有余。转移是由刑罚处罚时间价值。(3)列车类型:列车被认为是均匀的,也就是说。,一个做uble train set with 1000 seats, and its operation speed is 300 km/h. Including trains with different speeds is considered as future work.(iv)乘客路径选择:乘客总是会选择最短的路径旅行时间不管价格路径是什么。高速铁路的乘客通常更加注重旅行时间而不是票价。此外,许多研究论文铁路规划(12,15,25,31日)假设乘客旅行根据最短路径(有或没有转移)。(v)行属性:没有限制线长度考虑和线条可以在任何车站开始和结束。每一行在两个方向上进行操作。(vi)可行行:所有路径的基础设施网络允许线(周期除外)和可能的乘客出行路径或火车线路不提前固定但线规划过程中确定。我们认为没有限制的行数(或频率),可以使用一定的优势,但我们考虑列车的容量。

实际上,有两种类型的高铁列车操作。然而,只有少数论文文献[1,7,11,34)考虑异构机群在规划阶段。因此,我们将考虑不同类型的火车在未来工作。此外,高铁的趋势是操作一个火车的速度,这样的可能性提高高铁产能利用率可以提高在不久的将来。

当考虑最短路径分配为乘客路径选择,更现实的模型(35- - - - - -37)已经提出,但垂直距离已经非常具有挑战性的,即使这种简化(22]。额外的假设乘客不会选择一个长路径(弯路和/或转移)为了减少票价是根据相应的高速列车大部分顾客的行为。我们假设他们买更昂贵的高铁票为了得到更短的旅行。在未来的工作中,这些假设可以放松。

这被认为是作为输入:(我)旅客OD矩阵:旅行的乘客数量任何起源站和目的站之间在一个对称的OD矩阵。旅客OD矩阵代表《每日客运需求。(2)高铁网络拓扑:可用的站点(节点)和跟踪(边缘)是固定的,和两个站之间的每条边的长度是预先知道。

线规划的解决方案是表示为一组线与特定的频率有关。一行包含一个节点序列。

3.2。数学模型以利润为导向的计划

MILP模型提出了解决以利润为导向的计划。为了使模型可以理解(在合理的时间和可以解决的),它假设有限的可能行。因此,模型将决定哪个线从池中操作和频率。应该注意的是,垂直距离我们解决中国高铁,也提出的方法第四节,不需要这样有限的线路和允许操作任何可行的路线。

3.2.1之上。变量和符号

物理网络拓扑是无向图 。定义为节点集 和代表了电台。被描述为边集 ,代表了网络中连接两个站。解决垂直距离时,一列火车服务网络(听)(Fu et al。1])也需要考虑传输时间和描述乘客的行程。这也被称为改变&网络Schobel和肖勒[14]。在这个网络中,每个站是每行复制它。参见图1 (c)听的一个例子。在模型中, 表示重复的车站在线 。

让 OD对的集合 。在一定OD对乘客的数量表示 。池的可能行作为MILP模型的输入。长度的线被认为是已知的。

这些变量在模型中使用: :总运营收入 :总运营成本 :每列火车的能力代表席位的数量 :的可能行 :操作的固定成本与频率 :频率的可变成本每行每公里1 :理想的收入,如果每个乘客会对他/她的直接连接在物理网络最短路径;也就是说, :乘客在一定OD对的数量 :每个OD对的最短路径旅行时间对物理网络独立的计划 :旅行时间价值(票价每单位时间)将旅客旅行时间转化为票价 :每个OD对的最短路径旅行时间听,包括一个固定时间处罚为每个传输 :总开车时间和停止时间 :总传输时间 :固定在一个车站停车时间 :固定的两条线在同一车站之间的传输时间 :处罚时间价值:时间弯路或转移的价值

火车服务网络(听)符号如下: :驾驶弧, ;每个驾驶弧的成本等于边的旅行时间,也就是说, :弧的开车时间在边缘 :设置转移弧, ;每个转移弧的成本被设置为一个固定的惩罚成本;也就是说, :原产地弧, ;每个弧起源的旅行时间成本为0 :目的地弧, ;每个目的地的旅行时间成本弧是0 :电弧集 ,的弧用OD对 :的驾驶弧所使用的线 :这个参数= 1时了线 ;否则,0 :这个参数= 1时的优势了线随着弧 ;否则,0

决策变量如下: :线的频率(可以是零,如果不是实际操作的行) :当旅客OD对二进制变量等于1 使用弧 ;否则,0

3.2.2。客观的

目标是最大限度地增加经营利润,等于收入和运营成本之间的差异。每行的运营成本包括固定成本(频率)和可变成本线的长度和频率相关。通过引入旅游时间价值参数,旅客旅行时间转化为运营收入。因此,运营收入可以制定为乘客总出行时间乘以旅行时间价值和负转移的惩罚,便道:

方程(2)提供特定的信息收入考虑处罚。左侧-是最理想的收入,获得当每个乘客旅行沿着最短路径在物理网络,直接连接。应该注意的是,理想的收入是一个固定值,目标函数可以省略。然而,由于理想的收入是利润的一部分组件,我们想把它为了使目标函数可读性更强,并且可以理解的。的右边-是转移的点球和弯路乘客需要在听。这假定票价降低补偿的不适更长的旅行时间(比理想的最短路径)。提出了运营成本方程(3),这是相关的行数及其相关的频率。的一个例子将在目标函数计算3.3节。

3.2.3。约束

我们假设所有的行选择给定的行,但是一些线可能有一个零的频率。MILP模型中的约束包括下面列出:

方程(4)- (6)保证周围建设基于一行计划。这三个约束条件表明,只可能被覆盖的节点和边的线被认为是为周围的节点和弧;也就是说,edges belonging to the lines can be selected as the driving arc of passenger routes (4)和节点(站)覆盖了超过一行选为潜在的转移弧(5)。来源和目的地弧连接到每个节点由一条线在听(6)。这些约束假设弧一个在听——对应于边缘e在物理网络(4),转移弧一个对应于之间的转移和(5),站是出发地或目的地弧的端点一个(6)。

方程(7)- (9)是网络流守恒约束,要求每位旅客OD对应该有一个可行的路径在听——基于给定行计划。方程(7)和(9)确保只有一个来源和目的地弧弧可以选择为每个旅客OD对。相反,对于每一个旅客OD对,必须有一个起源弧弧和一个目的地。方程(8)确保保护乘客流在中间节点上。如果没有旅行路径的OD对或转移的数量超过两个,该模型将被证明是不可行的。

方程(10)限制转移的数量为每个OD对2。方程(11)- (13)计算每个OD对的实际旅行时间。方程(11)和(12)计算实际的总行驶时间和总传输时间一定OD对。方程(14)确保驾驶上的线弧的容量足以满足乘客的需求,推动电弧;也就是说,一个ll passengers are served taking into account the capacity of the trains. The frequency of the train is calculated based on the number of passengers taking that train. Constraint (15)和约束(16变量值的约束。

这个模型的主要目的是阐明以利润为导向的线路规划问题的考虑。此外,该模型将用于我们在规划方法第四节。然而,可能的线考虑在上面的MILP模型将被替换下的行线计划评估。因此,优化客运任务的频率线计划评估。

3.3。小例子网络

在这里,介绍了一个小型网络图1(一)这将被用来说明目标函数的计算。在这个小例子,除了每个弧对应于距离(公里)和旅行时间(分钟)。在这个例子中,表的数据1假定。

简要说明目标函数的计算,提出了基于线计划图的例子1 (b)。为了考虑转移和描绘乘客的行程,听(见图1 (c))构建基于给定的计划图1 (b)。正如图所示,两线频率1单位时间(例如,1每天每小时或1)。蓝线的运营成本 元人民币。红线,这是21750元,所以总运营成本是42750元。计算的收入是理想的收入减去转移造成的罚款和弯路。为了简化计算过程,我们假设每个OD对的乘客需求是100。理想的收入计算价格,所有的乘客支付他们直接连接的最短路径。例如,乘客从节点1到3的理想收入(路径(1、2和3)) 元人民币。总理想收入可以计算为105750元人民币。当计算转移的处罚费用和弯路,惩罚时间等于实际旅行时间之间的差异和最短旅行时间。例如,处罚费用的乘客从节点1到节点3,需要转移在节点2(而不是停止),等于 元人民币。另一个例子包括乘客从节点2节点,通过节点3需要绕道。绕道的处罚时间价值增加时间和乘客需求= 元人民币。乘客的总损失费用转移和弯路(OD对0 - 3、0 - 5、1 - 3、1 - 5和2 - 5)是2640。这条线的最终利润计划 元人民币。

4所示。行规划Matheuristic迭代方法

生成一个初始行计划后,我们的方法分解的垂直距离为两个子问题,提高线路的设计和乘客一起作业频率设置。这两个子问题优化迭代的基于启发式评估可能的地区在第一子问题的解决方案和MILP模型第二子问题来解决。我们称这种方法MHIA,见图2在接下来的章节中详细讨论。

4.1。最初计划行代

最初的线计划生成的基本思想是选择那些行直接服务尽可能多的乘客需求。据线规划的经典方法中引入Bussieck et al。12),我们首先搜索每个OD对的最短路径的物理网络Floyd-Warshall算法(38]。这导致一组候选线路。最初的线生成计划包括两个阶段,即启发式建设和修复,确定哪些行包括在最初的解决方案。启发式的建设过程中,集是由从候选人选择一行一次线,直到所有的节点都淹没了。线路的选择遵循的规则所选行服务大多数乘客的最短路径没有转移,不仅从开始到结束站行也从转向站在这条线之间。在选择下一行,包括所有乘客服务直接由已经不再被认为是选定的行。例如,第一行是根据计算选择直接乘客每一行。然后,乘客的这条线被淘汰的OD矩阵。下一行然后从候选人中选择行基于剩余的乘客无人看管。选择过程仍在继续,直到所有的节点网络覆盖。

自施工阶段着重于直接连接,它并不保证所有乘客有一个路径和有不到两个转移。出于这个原因,前一节的MILP模型是用来检查线计划可行性通过Floyd-Warshall算法来计算所有OD对的最短路径。如果存在任何OD对路径有两个或更少的传输可以在听,然后在物理网络的最短路径的OD对被选中作为一个新的线并添加到最初的计划。

为了说明初始行计划的一代,我们回到小例子网络图1(一)。列表与每位旅客OD对的最短路径(在一个方向上)是给定的表2。

我们假设每个OD对对应于100名乘客。基于直接服务尽可能多的需求,将第一行(0、2、1,4,6)或(0、2、5、4、6),这两个服务1000名乘客。然后,这些服务乘客从OD矩阵,和第二行被选中的路径以同样的方式。如果我们选择(0、2、1,4,6)作为第一行,然后(3、5、4、6)成为第二行与500名乘客直接服务。现在,网络上的所有节点被选中的行。可行性后检查(旅游道路,转移的数量,和节点覆盖),所选行满足所有约束和初始行计划生成。

4.2。行计划评估和修改

在这条线计划修改和评估过程中,示算法1,考虑两个子问题:方案设计(修改)和乘客赋值和频率设置(评估)。显然,乘客分配是一个关键的一部分线计划评估。不过,客运任务通常需要大量的计算时间,和最小的变化线计划将大大改变乘客分配,因此旅客旅行时间。因此,我们试图限制旅客的次数计算任务。例如,这将是太耗时的计算每一个可能的乘客分配修改当前行下面的考虑。因此,我们试图改善线计划基于容易计算启发式评估指标。只有最有前途的修改,乘客分配和频率设置应用使用MILP模型中讨论第三节。

计划设计或修改部分,框架有四个修改运营商开发迭代改进当前行计划。详细修改和评估过程见图2。四个修改运营商减少一条线(减少),延伸线(扩展),删除一行(删除),插入一行(插入)。减少和扩展加强或改进修改工作,删除和插入使用多样化的搜索。每种类型的修改可能会导致一系列的计划,当前行计划的附近。

的减少附近的电流线计划包含所有计划的一个终端节点删除一行。的扩展附近所有线计划,包含一个节点,相邻的物理网络中的终端节点,添加到行之一。当涉及到插入,每一行对应于OD对没有直接连接在当前行计划被认为是插入到当前行计划。为删除社区包含所有线计划,删除当前行计划的一条线。在每个街区的四个运营商,唯一可行的计划被认为是。

当考虑减少,每一行的码头边的负载因素计算当前行计划的评价指标。负载因素是实际的客流量在一条线的边缘除以总容量(席)的数量相应的线。低负荷系数可能表示一行不盈利的一部分。计算负荷系数为每个终端优势,然后删除终端负载系数最低的边缘线。然后MILP模型应用于优化频率和最优分配乘客新行计划。只有当总利润实际上是增加了删除这条边,新行计划被接受和算法继续考虑扩展。然而,当删除这条边会降低利润,减少和取消该算法认为删除下最低负荷系数的边缘。这一直持续到一个边缘发现实际上提高了利润的数量或者直到邻居认为是达到一个预定义的最大数量(MaxNeighbours)。在这两种情况下,减少是结束,扩展被认为是。

扩展评估,目前需要多少乘客转移可以直接运输由于扩展与一个额外的优势。可以额外提供最直接的边缘连接。再次,MILP模型应用于优化频率和最优分配的乘客新行计划。只有当总利润实际上是增加了延长这条线,新行计划被接受,回到算法仍在继续减少。然而,当添加这条边会降低利润,扩展是取消,该算法考虑添加下一个最有前途的边缘。与减少,这一直持续到一个边缘发现实际上提高了利润的数量或者直到邻居认为是达到一个预定义的最大数量(MaxNeighbours)。在这两种情况下,扩展是结束,减少被认为是一次。

为了限制的总计算时间减少和扩展,我们明确限制的总数乘以MILP模型。当使用MILP模型MaxNumberOfIterations次或可以发现当没有更多的改进减少或扩展,该算法继续多元化阶段。

为了分散算法,两种方式扰乱搜索实现:删除和插入。首先,然而,当几行有一个频率后的零频率设置,这些nonoperated线将被删除。然后,新行计划是随机从所有可能的选择删除和插入附近的解决方案。干扰的解决方案总是接受。多样化的迭代的数量(MaxDiversifications)是预先固定的停止准则的算法。之后,在搜索过程中获得的最佳解决方案将作为最终的解决方案。

另一种实现将考虑所有的四个同时移动。然而,这将花费的时间太长,没有效率。所以我们选择上述运营商执行顺序优化计划。的减少和扩展用于寻找小的变化近似局部最优解的输入行计划。这两个运营商是至关重要的运营商算法的良好性能,被认为是强化动作。然而,插入或删除随机选择多样化的解决方案搜索空间。这些都可以被视为输入行计划的巨大变化。

自初始线计划是由选择的行可以尽可能多的直接的乘客,这通常会导致排长队。为了避免这种负面影响最初的计划,减少首先应用。在有限数量的迭代减少和扩展,随机插入或删除提供其他搜索方向。

相比使用大型社区搜索(LNS) [35,39),本文中提出的方法在以下方面是不同的。在LNS,一个临时的解决方案,首先应用销毁方法,然后给出一种修复方法。本文建议的方法,分别给出了临时解决方案减少,扩展,删除,或插入。具体来说,LNS的销毁方法随机破坏当前的解决方案的一部分,然后,重建被毁的部分的修复方法。然而,我们建议的方法基于四个运营商,分别修改当前解决方案的启发式评估并选择最有前途的一个临时解决方案。

算法中使用的符号1如下: :当前行计划的利润 :最好的利润计算线计划之一 :附近的利润解决当前行计划 :选择的社区计划 :组OD对乘客有更长的旅行时间比他们理想的旅行时间 :目前的数量MaxDiversifications迭代 :目前的数量减少 :目前的数量扩展 :当前集约化的迭代次数

4.3。另一种迭代方法

是非常耗时的获得一个最优的乘客赋值和频率设置网络变大时使用的数学模型。这主要是由于指数应考虑越来越多的可能行。另一种迭代方法(AIA),避免大量使用数学模型,是现在。它将主要用于评估MHIA的性能。友邦保险框架如图3。

友邦保险使用相同的修改运营商和MHIA启发式评估方法。然而,客运任务的计算时间明显减少了使用作业前的结果行计划。我们称之为“启发式客运任务。“如果乘客有一个直接连接的最短路径,乘客路径假设保持一样的在前一行计划。算法只搜索短路径对于那些没有直接连接或迂回,然后计算所需的每一行的频率。另一个区别是MaxNeighbours在友邦保险是有限的,而MaxNeighbours在MHIA仅限于10。因此,只有最有前途的减少(扩展)评估(和实现成功时)在继续之前扩展(减少)。

5。计算实验

在本节中,几个实验显示执行的性能提出MHIA解决以利润为导向的垂直距离。该方法用c#实现,运行在一个英特尔(R) (TM)核心i7 - 3770 CPU 3.40 GHz和16.0 GB的电脑。12.6.3 MILP是实现最大化策略版本,使用c#应用程序界面的解算器使用默认参数值。输入数据包括网络基础设施、客运需求OD矩阵,和其他操作参数,如跟踪旅行时间(取决于固定火车速度),固定成本和可变成本元素。实验中使用的参数表3。应该注意的是,这些值是不同的(更现实)相比,使用的值在表1。为了使网络更现实的小例子,所有链接长度乘以20。因此,节点0之间的距离和节点2,例如,200公里。由于缺少真实数据(这是在中国高铁网络的机密),乘客需求OD矩阵是随机生成的,和不同的场景需求。所有实例数据变得可用https://www.mech.kuleuven.be/en/cib/lp/mainpage第四节。

初步实验后的不同组合的最大数量MaxNeighbours,MaxNumberOfIterations,MaxDiversifications我们将数量设置为10,20,分别和30。

在线路规划问题,传输时间通常是模仿作为惩罚值(1,7,19- - - - - -21,29日- - - - - -31日,33- - - - - -35]。因为火车期间不知道起飞时间线规划、准确的传输时间是未知的,估计转移点球。在这里,我们设置了传输时间(点球)30分钟考虑乘客的不便和中国高速铁路的实际情况。

旅行时间值是用来计算理想的收入。在这里,我们把高速列车的票价转变成一个与时间相关的运营收入和价格联系旅客旅行时间。然而,惩罚时间价值转移用于补偿转移的不便。

5.1。小例子网络实验

在这个实验中在网络中引入小例子3.3节MHIA的性能比较,提出使用MILP模型获得的最优解3.2节。为了获得最好的以利润为导向的规划这网络,MILP模型从一个包含所有62行可行行池,可以为这个网络生成。通过这个实验,我们可以测量距离MHIA可以为小型网络的最优解决方案。

这个实验考虑三种不同的乘客需求场景(PDS),基于三个随机生成的OD矩阵。实际上,以利润为导向的规划问题,我们在这里提出尚未解决之前在文学。这个比较文学的方法(1,7,27,28,31日)是不可能的。

结果10分友邦保险和MHIA表4。计算最优解的MILP模型考虑所有可能的行以来。在所有的表,“PDS”是指一个乘客需求的场景。表4报告最初的解决方案的利润(是)由AIA或MHIA,最好的利润(BS)获得的友邦和MHIA,平均利润(鸟类)运行,运行的平均计算时间(ACT)的方法,和行数()行包含在最好的结果(BS)。MILP, b是最优的解决方案。在这个实验中,差距之间的区别是最佳的解决方案和最佳的解决方案由MHIA(或AIA),也就是说, 。

从表4的最好的结果,可以看出MHIA非常接近最优解,平均差距只有2.9%。此外,最好的结果的MHIA这个小示例网络比结果由友邦保险。所有的方法的计算时间为这个非常小的网络仍然有限,但是,显然,友邦保险比MHIA更快,都比MILP快许多倍。我们得出结论,一个非常小的网络,MHIA保证高质量的解决方案以利润为导向的垂直距离在有限的计算时间。在这种情况下,友邦保险使用的启发式客运任务具有相同的初始结果准确的乘客分配应用于MHIA。

所有详细信息最好的解决方案获得了每个需求场景(线、频率和利润计算)和62年的可行行是可用的https://www.mech.kuleuven.be/en/cib/lp/mainpage第四节。在下一节中讨论的结果也可用。

5.2。现实世界高铁网络实验

学习后的性能MHIA小例子网络,我们现在把它应用在中国三个真实的高铁网络,一个小型网络(11和110节点OD对),一种媒介网络(26节点和650 OD对),和一个大型网络(34节点和1122 OD对)。

鉴于问题的复杂性,以利润为导向的线路规划的最优解是没有和这些高铁网络耗时太长,使用MILP。这使得很难正确评估MHIA这些网络的性能。因此,为了测试的性能MHIA在本节中,最好的解决方案相比发现MHIA将最初的解决方案通过MHIA和友邦找到了最好的解决方案。在5.3节,最好的解决方案发现MHIA将与最好的结果相比,可以得到解决的MILP模型3.2节对于这些网络。

图4显示了小的高铁网络的拓扑结构。我们所有的实验根据给出的参数表3。10分的结果给出了每种方法的表5。在这里,对应的差距 。

应该注意,友邦保险的初步解决方案和MHIA对应相同的计划,但更高的利润计算MHIA由于不同乘客分配计算。由于友邦保险使用的启发式计算客运任务,其利润低于最优乘客转让MHIA小型高铁网络。友邦保险相比,MHIA平均可以提高运营利润的10.7%计算大约10倍时间由于准确客运任务。最好的结果MHIA平均提高40.0%的初始解。以乘客需求场景1为例,详细信息MHIA如图的最好结果5和表6。旁边的数字彩色线条的频率。

行上的高频部分(第4 - 9,9 - 8,以8:7,和7 - 6)与49%这个解决方案很好地对应的最短路径包括这些线部分表明乘客更有可能选择这些线部分。这说明,最好的结果发现MHIA符合乘客的需求。线的原因(4、9、8和10)最高频率是所有乘客想要前往的目的地10必须使用这条线。根据乘客需求OD矩阵,在车站的乘客数量结束10是2336。这表明3列车需要以服务所有的乘客,列车,考虑火车的能力。

当考虑网络的规模增长,寻找最优的计算时间客运网络的任务将会变得非常耗时。因此,我们将最大化策略的最优间隙参数解算器设置为5%,这意味着当前最佳解决方案解决者会给结果当当前最佳解决方案之间的差距和当前的上界是低于5%。这大大加快了乘客赋值和频率设置。媒体的网络拓扑结构高铁网络图6(只有黑色的边缘),5分的结果如表所示7。现在应该注意到计算时间表达了在几分钟内。这里使用的差距 。

随着网络规模,MHIA显示优势解决以利润为导向的垂直距离。在表7,最初的原因,利润线友邦保险计划是友邦保险不同于MHIA再次使用启发式客运任务,而MHIA应用最优客运任务。平均而言,比友邦MHIA执行8.3%,MHIA改善初始解决方案的最佳解决方案的16.5%。

当应用MHIA大的高铁网络,对应于整个4 v4h网络(黑色和灰色的边缘图6),计算时间太长。因此,为了使评估的计算过程,算法参数的敏感性检测单个场景的需求。自MaxDiversification的一个主要参数,决定了算法的计算时间,不同的值MaxDiversification进行测试。为了加快算法的计算速度,另一个两个值MaxDiversification最初被认为是:10到20 (30)。5运行的每个值的结果MaxDiversification给出了在表8。在这里, 。

结果在表8表明,该解决方案质量减少时仍然几乎相同MaxDiversificationMHIA。同时,计算时间从12.0小时减少到4.1小时,减少63%。所以,我们认为这是适当的减少数量的多元化发展,解决大型高铁网络的垂直距离。

最后,我们运行MHIA新参数设置在另两个场景需求大的高铁网络。在这个实验中参数用于MHIA最大化策略最优缺口和10 5%MaxDiversification。同时,友邦保险,只有10MaxDiversification被认为是。这个设置表中列出的结果9。

对于大型网络的情况,MHIA展示了一个优秀的能力获得高质量的解决方案和控制计算时间。MHIA所有需求的初步解决方案场景由友邦保险比最好的结果。平均MHIA的最好的结果是13.3%比最好的结果友邦保险的大的高铁网络。然而,友邦保险的计算时间明显缩短。

这些计算次主要表明问题的困难,而不是算法的效率。实际上,这些类型的计算时间是正常的垂直距离的大小考虑客运任务。等实际应用,此外,计算时间是可以接受的,因为这条线计划通常是唯一的长期改变。

此外,因为我们考虑的问题是新的,算法的性能不能与其他方式相比,从艺术的状态。因此,我们展示算法的效率进行比较获得的结果与最优解使用最大化策略(只可能在较小的实例),友邦保险在所有实例。

5.3。对比MHIA和MILP高铁网络

如上所述,在本节中,最好的解决方案发现MHIA将与最好的结果相比,可以得到的MILP模型3.2节小型,中型和大型高铁网络。MILP模型来获得这些最佳结果,所有行中获得的结果的不同运行MHIA小型高铁网络(AIA)5.2节包括MILP线池中。显然,这并不能保证能找到一个最优解,但至少相当数量的高质量的线现在认为在这条线池。

第一,小的高铁网络,为每一个需求的场景中,我们使用的所有行线计划每个10分的结果MHIA和友邦的线池MILP模型。结果如表所示10。

结果表明,MHIA表现良好在达到计算出的解决方案MILP小型高铁网络的不同场景的需求。差距非常小。当PDS 1作为一个例子,有35行考虑线池和详细信息的结果MHIA和MILP表11。列“频率(MHIA)”提出了频率MHIA找到了最好的解决方案,和列“频率(MILP)”是指MILP模型可以获得最好的结果。

通过比较频率在第二列和第三列,我们可以看到线的频率在MHIA解决方案通常是略有减少,取而代之的是修改的行。例如,第一行的频率(4、9、8、10)减少从3比1,但相反,MILP解决方案运作两个非常类似(4、9、8、7、6、4、9、8、7)。这可能是一个迹象表明MHIA的性能可以提高通过考虑更多的(略)不同的直线,而不是更高的频率更少的线。也许这些更好的解决方案也可以通过增加MaxNeighbours,MaxNumberOfIterations,或MaxDiversification。然而,质量改进是1.0%左右,而计算时间可能会大大增加。当前的解决方案,MHIA需要113年代和261445年代MILP要求。我们得出这样的结论:MHIA表现良好的解决方案质量和计算时间之间的权衡。此外,有更多的(略)不同的乘客也可能使其更难以理解的网络。可能,网络通过MHIA甚至比结果更现实的MILP获得的。

现在我们应用相同的对比MHIA和MILP中型和大型高铁网络。这里,只有行包含在不同PDS线计划通过MHIA包括在内。否则,线条变得太大的池解决MILP模型。MHIA之间的差异和MILP如表所示12。最大化策略的最优性差距解决用于MILP MHIA是一样的,即,5%的高铁网络。

括号之间的数字线列显示的行数考虑MILP线池中,而普通数字表明参与结果的行数。理论上,解决方案获得的MILP应不少于MHIA的结果。然而,由于5%的最优最大化策略解决者的差距,它可以发生的利润MHIA高于MILP的利润,导致负缺口。这种情况第一需求场景对中型和大型网络。PDS 3大网络的计算MILP不能获得,因为解决耗尽内存由于网络和大线池的大小。

对于网络,我们可以看到在桌子上12MILP给出的最优结果非常接近最好的结果MHIA所有场景的需求。这说明MHIA获得高质量的结果。

6。结论

在本文中,我们提出一个matheuristic迭代方法(MHIA)以利润为导向的线路规划和频率设置,应用于高速铁路(高铁)网络。以利润为导向的线路规划考虑运营商的成本和旅客旅行时间。旅客旅行时间被认为是通过减少票价(因此运营商收入)在弯路或转移。讨论了一个数学模型来定义详细的问题。MHIA集成启发式改进的计划和一个精确的乘客分配方法和频率设置。两个强化和两个多元化举措被认为是在算法。

MHIA的性能评估实验网络的不同大小和不同的乘客需求场景。网络上最小的只有7个节点,与最优解MHIA平均差距为2.9%。几个真实的实例的基础上,中国的高铁网络,MHIA提高利润为10.7%,8.3%和13.3%的平均大小不同的网络相比,另一种迭代方法(AIA),不使用准确的乘客赋值和频率设置。此外,MHIA增加的初始解决方案小,介质,和大型网络40.0%,16.5%,和10.7%,分别。平均计算时间的小型,中型,大型网络实例117.3秒,187分钟,和4.7小时。

实验也提供有用的见解时,参数设置网络变得很大。适合的参数更大的网络,MHIA合理的计算时间内获得高质量的解决方案。这证实了比较性能与MILP精确解的方法。所有三个网络的最佳利润使用MILP非常接近最优解,当所有MHIA行包含在池。的小型、中型和大型高铁网络,最佳MHIA解决方案之间的差距和最佳MILP解决方案是0.8%,0.9%,和−0.2%,分别,当以高品质线为行池。

庞大的高铁网络与34个主要站在轨道分裂或加入被认为是。比较所有的加油站网络(超过800个车站),车站的数量被认为是还小。但是所有的4 v4h高速轨道。之间的中间站主要车站并不明确,但阻止有可能被包括在两个站之间的旅行时间。这为进一步研究提供了可能的最优停止模式等后续问题。

进一步的工作可以考虑不同的火车大小和速度和停止的优化模式。有趣也会找出如何使用以利润为导向的线路规划或修改operator-oriented或passenger-oriented线规划。另一个可能性是集成友邦保险和MHIA为了找到一个方法,可以进一步减少计算时间,同时保持相同的解决方案的质量。

数据可用性

使用的数据来支持本研究的发现在网上是可得到的https://www.mech.kuleuven.be/en/cib/lp/mainpage第四节。

的利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项工作是由中国国家重点研发项目(没有。2017 yfb1200700)和中国国家自然科学基金(没有。U1834209)。作者承认的支持中国奖学金委员会(201707000074)。