没有合适的资源?快使用搜索试试~ 我知道了~
53《理论计算机科学电子札记》66卷第6期(2002)网址:http://www.elsevier.nl/locate/entcs/volume66.html13页基于最短路径的铁路阻抗管理JeDay1;2美国威斯康星州格林湾施耐德物流George L. Nemhauser 3Joel S.索科尔4号佐治亚理工关闭IN,USA摘要运输路线是运输服务的一个主要后勤问题。对于铁路,路由历来是由大型的硬编码表处理的。北方铁路公司利用网络流理论开发了一个更复杂的路线选择系统.他们的物流封锁和分类(ABC)系统根据最短路径路由运输商品(运单)。多个运单的路径选择问题是多商品流问题的一种形式。由于商品的路线通常是预先确定的,ABC的成功依赖于使所需路线成为最短路径的成本。确定成本以使解最优的问题称为逆优化。的程序为 ABC 系 统 确 定 一 组 适 当 的 成 本 被 称 为 校 准 , 是 逆 多 商 品 流 问 题(IMCFP)的一种形式。校准寻求一种解决方案,使所有预定路径相对于成本唯一最优。校准问题(IMCFP)可以使用单纯形法进行优化求解。然而,单纯形算法的直接应用并不总是有利的,特别是对于大的问题。我们提出的配方,原始-对偶解决方案的算法,和热启动的基础- nding算法获得最佳解决方案。此外,我们可以使用拉格朗日松弛找到好的启发式解决方案。c2002年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。戴、内姆豪泽和索科尔541引言铁路运营的一个重要组成部分是将运单从起点发送到目的地。传统上,铁路公司使用巨大的表格来存储路线偏好。因此,每种商品在指定的起点和目的地之间的路线必须是硬编码的。要包含所有类型的交通工具以及所有可能的起点和目的地,需要大量的存储空间。大多数主要的铁路网络都有超过1000码,这意味着超过100万个可能的起点-目的地对。即使实际上只使用了其中的一小部分,对traffic类型的额外考虑也很容易需要数万条显式编码的路由。此外,使用既定的路线允许非常小的灵活性。对一条标准路线的调整可能会影响许多其他本地路线。诺福克南方铁路公司开发了一种替代的路线系统。铁路阻塞和分类(ABC)系统[6]是一个决策支持系统,它根据人工成本(阻抗)推荐路线,这些人工成本捕获了铁路的先前路线选择趋势。基于阻抗的集合(每个区块/弧一个),ABC系统定义每个潜在起点-目的地路线的总成本;具体地,该总成本等于路线上所有区块的阻抗的总和。使用标准的最短路径算法,ABC可以快速确定任何运单的最低成本路线。如果阻抗设置正确,则最低成本路线将与每个运单的铁路期望路线完全相同。这构成了进度,因为ABC不需要显式存储路由,从而节省了存储空间,并通过允许控制器操纵成本提供了灵活性。然而,如何正确设置阻抗,使最短路径与所需路线一致的实际问题是困难的。此外,铁路的路由偏好不会随着时间的推移而保持不变,因此需要周期性的阻抗更新程序(“校准”)。初始阻抗设置和校准问题都可以被视为需要数天时间才能解决的庞大线性程序。在本文中,我们提出了计算策略,更快地解决问题,使阻抗为基础的路由将变得更加有效。1 作者要感谢诺福克南方铁路公司的支持,以及罗杰·鲍尔、埃里克·威库姆和克拉克·程帮助我们理解了这个问题。2 电子邮件地址:dayj@schneider.com3 电子邮件:george. isye.gatech.edu4 电子邮件:joel. isye.gatech.edu戴、内姆豪泽和索科尔552当前路由实践铁路网由车场和区段组成。在数学术语中,码是网络的节点,块是弧。在标准铁路网络中,一对节点之间通常有几个平行的块,所有块都表示相同的轨道段,但每个块都具有不同的允许属性集。铁路车辆在该系统中表示为运单。运单是一组具有相同属性的一辆或多辆汽车。运单的特征包括货物本身的属性以及用于运输货物的汽车的属性。铁路通常总共使用40多个属性,包括始发地、目的地、高度、重量和货物类型。可能不允许运单使用每个区块。 每个区块都有一组权限逻辑,用于确定哪些运单有资格使用街区。块的许可逻辑结合了交通的属性以及块穿过的路线中固有的限制(高度、重量、板尺寸)。例如,在穿过隧道的一段轨道上定义的块将对在其上行驶的轨道车的高度有限制。每个运单的可行网络是简单的;换句话说,在任何一对节点之间最多有一个弧。当一个运单符合同一对堆场之间的多个区块时,优先级方案选择最合适的区块。为专门的交通而建造的街区(即,汽车零部件、多式联运)具有最高优先级。一般交通阻塞的优先级最低。运单的最终可行网络将只包括每对码之间的最高优先级的资格块。许可逻辑的限制导致每个运单都有一个个性化的可行区块网络ABC的效用在1996年夏季奥运会期间得到了证明由于当时亚特兰大的活动高度集中,这是广告-尽可能多地将交通工具从该地区转移出去。诺福克南方铁路公司的一名员工就能在另一条铁路上的一整组工人所需的时间的一小部分内制定出可接受的替代路线。ABC的主要缺点是确定和管理块阻抗(电弧成本)以实现期望的布线的困难。铁路-公路控制器有能力改变块阻抗,以满足可能出现在任何时刻的路由需求。在大多数情况下,控制者都在争取某种特定的影响。在这种情况下,测试不同的样本成本是有帮助的,以便对哪些成本应该改变以及改变多少做出有根据的猜测。以这种方式运行多个场景构成了一种假设方法来改变成本。然而,随着越来越多的阻抗改变以实现一些商品的期望路线因此,有必要定期重新计算戴、内姆豪泽和索科尔56成本,以确保正确的路线。正确的路径选择要求每个运单的“correct”路径是运单可行网络中唯一的最短路径。我们把这个路径称为期望最短路径。 运单所需的最短路径通常是由历史路线和经验丰富的铁路人员的洞察力建立的。阻抗的重新计算称为校准。我们可以把运单问题看作是多商品现在,铁路试图优化其路线受到能力的限制块。一旦铁路确定了其路由计划,就有必要确定每个块的阻抗;我们在本文中解决的正是这个逆优化给定阻抗的正确集合,铁路然后可以沿着具有最低总阻抗的路线路由每个运单现实生活中的铁路逆优化问题通常是不可行的,因为不同运单指定的路线不能同时实现; Day [4]描述了两种预处理方法,用于尽可能少地修改从这一点上,我们假设不失一般性,我们的问题是可行的。对于铁路应用,在文献中提出的问题公式太大,太复杂,不能直接用线性规划软件解决。因此,在本文中,我们提出了优化算法,解决了问题的nding良好的校准解决方案,在合理的时间量的大型铁路问题。接下来的两节简要介绍了方法;更多细节将在配套文件中提供。3逆多商品流逆优化是确定优化问题的成本函数的问题,使得给定的可行解是问题的最优解[2]。在这个意义上,校准问题是多商品流问题的逆问题。这两个问题的网络结构是相同的,但是我们不需要根据一组成本来寻找最优路由,而是需要得出一组成本,对于所述成本,一组所要路线是最佳的。文献中包含两个多连通性ow逆问题的公式,一个来自Ahuja和Orlin[1] ,它不强制最短路径的唯一性,另一个来自Farago 、Szentesi 和Szviatovszki[5]它们通过添加j K jj N j + j K jj A j约束来扩展以加强唯一性,其中N是节点的集合,A是弧的集合,并且K是商品的集合。 Day [4]证明了在给定简单修改的情况下,额外的约束是不必要的,并且Ahuja和Orlin的公式也可以修改为需要唯一的最短路径,而无需添加任何新的变量或约束。由于根在同一节点的商品将共享相同的最短路径树,因此它们可以被视为具有多个目的地的单个商品。戴、内姆豪泽和索科尔57CNNCJKXxKJJK对于每个节点r,我们将弧集A划分为两个集合。集合Ar包含作为以节点r为根的期望最短路径树的一部分的弧。 设置A r包含所有其他弧。设从节点r到节点s的最短距离为drs,且定义drr= 0foralln odesr. 因此,设N^更多商品表示作为一个或多个节点的原点的节点集合因为铁路打算周期性地重新校准区段阻抗,所以他们的目标是找到一种可行的解决方案,该解决方案使成本尽可能少地改变其已知的先前值c。因此,我们可以用cij+ijij代替每个新阻抗,其中ij和ij是增加量,减小a r c(i; j)的impedance,并最小化Pij(ij+ij)。第[4]天表明,[1]和[5]的公式都与他的公式(LPC)等价,因为它们都将给出相同的最优解。(LPC)(一)最小化X(j;k)2Ajk+X(j;k)2AJK(二)受dikdij+jkjkcjk8nodesi2Ni;8弧(j; k)2Ai(3)dikdij+jkjk=cjk8nodesi2Ni;8弧(j; k)2Ai(4)JK08弧(j; k)2A(5)JK08弧(j; k)2A(6)JKcjk8arcs(j; k)2A:不等式约束(2)是用于弧不在相关商品的期望最短路径中。等式约束(3)是最短路径中弧的紧对偶约束(来自原始互补松弛),其余约束是决策变量的界。该公式的对偶如下:(LPF)(7)最大化XXcjkxi+Xcjkyjk受i2N^(j;k)2A(j;k)2A(8)Xkj( j;k)2 A伊JKkj(k;j)2Ai=08nodesi2N^;8个节点j2 A(9)我18弧(j; k)2 Ai2N^XXX戴、内姆豪泽和索科尔58XxXNnnnnnnJKJK(10)i+ y jk18弧(j; k)2 A(11)i2N^青年党08弧(j; k)2A(12)i08nodesi2N^;8个弧(j;k)2Ai:这些公式,以及由Zhang和Yang [8]提出的更一般的公式,都是弧流公式(或弧流公式)。虽然这些公式是紧凑的,计算经验告诉我们,他们需要更长的时间,更困难的是在实践中解决比循环公式,特别是对于铁路应用程序所需的大型实例。3.1循环配制和色谱柱生成为了加快求解过程,我们将使用问题的循环公式而在相同的两个端点之间的任何两条路径P1和P2形成一个循环,其中P1的弧是正向弧,P2的弧是反向弧。具体来说,对于任何商品,我们将P1设为当前最短路径(或当前最短路径的子路径),P2为相同两个节点之间的任何其他路径。 这两条路径形成一个环n,弧为A n。设Z是所有这些圈的集合。对于每个循环n,我们将弧An划分为两个集合:A+是正向弧(最短路径中的弧)的集合,A是反向弧的集合。我们可以用周期来代替(LPF)中的各个电弧流变量.这样做的主要优点是,所有周期固有地满足所有节点的流量平衡约束。因此,唯一剩下的约束是每个弧的束约束和每个变量的边界。 交易是变量的数量变成指数。我们使用标准的列生成技术,允许实际处理的周期数是可管理的;类似的方法已经成功地解决了逆最短路径问题[7],这相当于用单一商品逆多商品流。我们称之为循环公式(LPFc)。(LPFc)(13) 最大化Xdn zn+ Xcjkyjk受n2Z(j;k)2A(14)Xnj(j;k)2AZnXnj(j;k)2A+zn+ejk= 18arcs(j; k)2A(15)Xnj(j;k)2A+ZnXnj(j;k)2Azn+yjk+sjk= 18arces(j; k)2A(16)ejk08弧(j; k)2A(17)sjk08弧(j; k)2A戴、内姆豪泽和索科尔59一一n(18)青年党08弧(j; k)2A(19)zn08次循环n2Z:目标系数的矢量d是通过对给定循环zn的前向弧减去后向弧的成本求和来计算的。更明确地说,dn= XcjkXcjk:(j;k)2+(j;k)2n出现在约束(14)中的松弛变量e jk被称为alpha松弛,并且对应于c jk的增加。 以相同的方式,我们将约束(15)中的松弛变量s jk称为β松弛,对应于c jk的减小。互补松弛告诉我们,当ejk是基本的时,弧(j;k)上的阻抗增加()必须为零。类似地,当sjk为基本时,阻抗减小()必须为零。 我们最终会对那些非基本的松弛变量感兴趣,因为对应的s和的将是非零成本修改器的候选者注意,公式(LPFc)可以通过将Dantzig-Wolfe分解应用于(LPF)来获得3.2热启动原-对偶方法已被证明是解决多重共通性问题的有效方法 问题[3],所以我们第一种方法是求解(LPFc),使用原始对偶算法不幸的是,我们发现原始-对偶求解方法(LFPc)在计算上是不精确的,它在初始时很快接近最优,但需要很长时间才能最终收敛。 收敛缓慢的一个主要原因是,在以后的迭代中,步长很小,因此有益的循环逐渐进入基础,而不是一次全部进入。然而,我们能够利用它的初始快速改进在一个原始-对偶为基础的“热启动”算法,可以迅速给我们一个很好的先进的基础,从它解决线性规划的其他手段。最后,我们关心的解决方案的主要方面是识别那些在一个方向或另一个方向上达到最大容量的弧,并且是非零成本变量的候选者。虽然纯原始-对偶方法确实会逐渐增加弧容量,允许相应的或变量变为非零,但实际上它运行得非常慢。许多迭代都是在从未达到容量的弧上构建ow。此外,有许多替代的可行的解决方案是等价的,因为它们在每个弧上具有相同的目标值和总ow。唯一的区别是不同商品的价差。我们可以创建一个基础的问题,逐步增加个人周期与一个完整的单位,而不是一件一件。这说明了小的移动和收敛速度慢的问题,其特点是我们的计算实验与纯原始对偶算法。此外还有戴、内姆豪泽和索科尔60由于商品在每个弧上都接收一个完整的单位ow或没有,因此简并的模糊性较小。热启动方法的优势在于它使用网络流而不是线性规划来产生改进方向。网络流部分是更新网络上的最短路径问题。由于每个商品的子问题是可分离的,这减少了所需的总内存存储,使我们能够解决比使用其他方法更大的问题此外,单个商品的解决方案非常快,使我们能够在很短的时间内解决许多问题热启动算法的基本轮廓是这样的:(i) 基于最短路径创建改进周期。例如,对于任何商品,当前最短路径和期望最短路径将形成循环。将这个循环变量输入到基中,可以确保期望的最短路径将变得比当前的最短路径更短(注意,这并不意味着期望的最短路径成为该商品的总体最短路径;可能存在第三条路径现在是最短的)。(ii) 将这些循环的可行子集放入ow为1的解中(iii) 创建剩余网络:通过修改成本来更新弧容量,以反映不能在一个方向或另一个方向上使用的弧。从某种意义上说,这些弧被从网络中移除。(iv) 基于剩余网络创建新的最短路径循环(v) 如果找不到新的改善周期,停止。否则,请转到步骤2然后重复(vi) 用松弛变量完成基础。4启发式的解决方案任何一组适当路由traffic的阻抗都是校准问题的可行解决方案。对于铁路-公路阻抗校准问题的所有实例,最优性并不重要。虽然使新的块阻抗与旧的阻抗稍微接近是有用的,但实现可行的解决方案更重要。在最终答案的客观值和所涉及的计算时间之间存在一个折衷。我们注重可行性,但也考虑到客观价值。这些启发式方法是植根于拉格朗日松弛理论拉格朗日松弛允许我们利用嵌入子问题的网络我们从一个不可行的解决方案开始,并努力实现可行性。这种启发式算法被称为近似最优启发式(NOH),得出一个流,然后以这种方式修改原始问题(LPFc),使流是可行的。然后,它使用基于单纯形的方法,包括专门设计的旋转策略(见[4]),以ND的对偶变量是最佳的戴、内姆豪泽和索科尔61JKJK对于修改的问题。在我们的拉格朗日算法中,我们修改公式(LPFc)中约束(14)和(15)的右侧,然后放松这些约束。回想一下,这两个约束的对偶变量是和,它们表示铁路网络弧段上成本的增加或减少。因此,改变(LPFc)中这些约束的右侧相当于对成本变化变量进行加权,因此所得成本对于逆问题是可行的。该算法正确性的关键之一是最短路径循环构成拉格朗日问题的最优解当且仅当期望路径是给定商品的第一或第二最短路径[4]。给定一个改进的有限制流问题的最优解,我们可以利用单纯形主元导出无限制流问题的最优解。单纯形算法将终止于最优基和最优对偶变量。这些对偶变量将是具有加权目标系数的成本问题的最优解,并且将是具有单位目标系数的原始问题新的问题将是(LPFc)的变化与修改的右手边,其中b和b是arc(j; k)的alpha和beta约束的新右侧当所有期望路径对于其对应的商品至少是次优设zi是从商品i的弧成本为c+的最短路径创建的循环设i为商品i在相同成本下所需路径的长度。然后,如果对于每个商品i,至多有一条路径的长度严格小于i,则对于所有商品i,zi= 1,对于所有其他n2Z,zn= 0的解是带乘子的拉格朗日问题的最优解。4.1改进的最优启发式算法该算法的一个变体是使所有约束等式约束的右侧等于owf。这是唯一的方法来保证我们的修改线性规划的最优性,因为每个解决方案具有相同的它将具有相同的客观价值。这个结果只适用于最短路径不需要唯一的情况。由于拉格朗日技术将产生一个最优的ow到(LPFc)的修改版本,我们称之为修改的最优启发式(MOH)。要使alpha和beta约束组合形成等式,它们必须在不等式的两侧具有相同的变量和系数到目前为止,beta约束已经有了额外的项+yjk来捕获形式为jkcjk的最终成本的非负性约束。为包括戴、内姆豪泽和索科尔62n振英nnnn而且,只有当o_n_j(j;k)~ 2A+z_n_P_n_j(j;k)~ 2A时,y_j_k>0 zn超过等式的左边是:Pnj(j;k)2A+znPnj(j;k)2A zn+yjk.nn对于alpha约束中的这一项,我们只需将约束改为jkjkc jk. 这是有效的,因为它简单地说明了c jk+jkjk0,或者调整后的成本必须是非负的。进行此更改将使两组上容量,这总是导致这些项的总和为等于最大容量。然后,只要上容量超过下容量,这是我们的问题总是如此,下容量约束将得到满足。由此产生的公式(LPMOH)是:(利比里亚公共卫生部)(20) 最大化Xd znn2Z+ X(j;k)2Ajkjk(21)受Xnj(j;k)2A+ZnXnj(j;k)2Azn+ yjk=fjk8 arcs(j; k)2A(22)青年党0 8弧(j; k)2 A(23)zn0 8次循环n2 Z:由于fjk在这个问题中是一个常数,所有可行的解决方案都有相同的目标值,我们的ow是可行的,是最优的。这意味着将不会有改善方向或单纯形枢轴,增加目标函数。然而,它可能仍然需要许多单纯形枢轴来寻找对偶变量,这些对偶变量对于成本问题是可行的,因此是最优的。5计算结果我们在几个测试实例上测试了我们的算法,这些测试实例被设计成类似于现实生活中的铁路网络问题。每个测试实例的大小在表1中给出。问题一 BCDEFGH我J50J100公司简介J200节点弧商品1020520401040802080160401603208032064016064012803201280256064010010005030080050300800100300800150300800200表1戴、内姆豪泽和索科尔63问题的大小请注意,实例I的密度比其他实例大得多。事实上,由于铁路网络通常是平面或几乎是平面的(因此jM j 3jN j),它的密度也比实际的铁路网络要高得多。<我们包含了一个实例来测试我们的算法在密集网络上的性能戴、内姆豪泽和索科尔64这些问题实例比南诺福克所面临的问题要小,但相关的线性规划仍然可以变得很大;例如,实例G和H包含400,000个变量和200,000个约束。因为我们测试代码的实例没有Norfolk Southern的实例那么大,所以我们的求解时间(见表3)不能直接与NS的校准算法进行比较,NS的校准算法通常需要整个周末才能运行。我们发现,我们的原始-对偶为基础的热启动算法一般减少了高达30-40%的线性规划的解决方案的时间。表3显示了有和没有热启动程序的解决方案时间。所有计算都是在具有200MHz处理器的SGI Octane机器上完成的问题没有热开始热开始SP电子数据采集器一0.080.05百分之三十八B0.170.09百分之四十七C0.180.15百分之十七D0.660.60百分之九E3.393.67-8%F38.6843.97-1戴、内姆豪泽和索科尔654%G329.47277.37百分之十六H25451712百分之三十三我2小时20分钟2小时38分钟-13%J5035.0129.17百分之十七J100116.4175.04百分之三十六公司简介233.76176.41百分之二十五J200438.47280.44百分之三十六平均百分之十八戴、内姆豪泽和索科尔66表2溶液时间(秒)热启动算法缩短了75%以上的情况下的求解时间,平均缩短了18%的求解时间。我们还测试了我们的拉格朗日为基础的算法的情况下,快速找到一个可行的解决方案比找到一个最优的解决方案更重要。一般来说,MOH启发式往往比NOH启发式更好。在与CPLEX 7.0的进一步比较中,MOH启发式算法找到给定目标值的可行解的速度比CPLEX找到相同值的可行解的速度更戴、内姆豪泽和索科尔67可行的解决方案。表4显示了一个代表性测试问题(H)的比较。客观价值MOHCPLEX117928235390103396387790815233051126735815431240表3找到可行解决方案的时间(秒)对于每个客观值,MOH似乎比CPLEX具有显著的速度优势。但是,CPLEX的优势在于能够结束所有这些目标值与一个单一的运行,逐步减少目标值与每个非退化枢轴。MOH只返回一个目标值;为了得到多个解,它必须运行多次,每次都有不同的拉格朗日步长。因此,如果铁路需要某个最大目标值,则CPLEX可能更有效,因为MOH可能需要多次运行才能找到具有所需目标的可行解决方案。然而,大多数铁路网络需要定期重新校准在这种情况下,在最初几次重新校准之后,将知道特定网络的适当拉格朗日步长,并且MOH启发式通常应该能够在比使用线性规划求解器所花费的时间更短的时间内找到可接受的可行解。引用戴、内姆豪泽和索科尔68[1] 阿胡贾河K.,和J. B.林明,多商品流动问题,研究论文(1998)。[2] 阿胡贾河K.,和J. B. Orlin,逆优化,运筹学49(2001),771{783.[3] 巴恩哈特角,和Y.谢明,基于网络的原始-对偶启发式算法求解多商品网络流问题,交通科学27(1993),102{117.[4] 戴,J,基于最短路径路由的铁路阻抗管理,博士。论文,工业与系统工程学院,佐治亚理工学院,2002年。[5] Farag o,A.,A.Szentesi和B. Szviatovszki,高速网络中的逆最短路径算法工作论文(1999)。戴、内姆豪泽和索科尔69[6] Wikum,E. D、基于数学规划的校准最短路径阻塞网络,NorfolkSouthern Corporation(1996)。[7] 张杰,Z. Ma和C.杨,一种求逆最短路径问题的列生成方法,Zeits chriftf《操作研究》41(1995),347{358.[8] 张杰,和C. Yang,A node-controlled inverse shortest paths problem,University of Hong Kong(1998)。
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功