没有合适的资源?快使用搜索试试~ 我知道了~
货车流问题的最优解
42《理论计算机科学电子札记》66卷第6期(2002)网址:http://www.elsevier.nl/locate/entcs/volume66.html11页货车流问题的最优解RicardoFukasawaa;1;2,MarcusViniciusPoggi deArag~aob;3,OscarPortoa;4和EduardoUchoac;5aDepartamento de Engenharia El etrica,Pontif cia Universidade Catolica doRiodeJanei ro o(PUC-Rio),R. 我是S。Vicente,225,里约热内卢,巴西b巴西里约热内卢市里约热内卢市政局信息部cAxioma优化。R. JardimBot^anico,674/614,RiodeJaneiro,Br asil摘要在货运铁路运营中,一个普遍存在的问题是确定一个可行的车辆流量在这项工作中,我们提出了一种方法来确定最佳的载车和空车的流量,以最大限度地提高利润,收入或运输吨位,给定的列车时刻表,以及它们的牵引能力。我们提出了一个整数多商品ow模型的问题,其线性松弛导致非常好的上界|代价是使用非常大量的变量和约束。为了将这个模型变成一个实用的工具,我们应用了一个预处理阶段,可以将其大小减少两到三个数量级。然后,可以用标准整数程序包求解简化模型,即使有分支,也很少。最大的拉丁美洲铁路公路货运公司的实际情况的计算结果的报告。这项研究的成果已经在那家公司使用。关键词:整数规划,网络OWS,铁路物流1引言由于轨道交通网络系统的高度复杂性,为了实现合理高效的运营,需要周期性地进行大量的联合决策。由于这样的决定涉及到这么多不同的1 CNPQ支持的工作2 电子邮件地址:fukasawa@ele.puc-rio.br3 电子邮件地址:poggi@inf.puc-rio.br4 电子邮件地址:oscar@ele.puc-rio.br5 电子邮件地址:euchoa@axiomaopt.com.brc2002年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。Kazasawa等人43方面和数据,唯一合理的方法是将操作问题分解为许多可管理大小的子问题,并尝试分别解决。无论是在客运或货运铁路,这样的子问题的几项研究,可在文献中。我们建议读者参考Cordeau等人的一项全面调查。[4]的文件。在本文中,我们解决了一个可操作的货运铁路网络问题,即货车流量问题,这是向我们提出的最大的货运铁路在拉丁美洲的运营商。问题在于确定铁路网络中每辆车的完整路线,以及在几天的时间内的装载/卸载顺序当然,空载或满载的车厢只有在连接到火车上时才能在位置之间移动。在货车流问题中,我们假设列车时刻表和列车容量是事先确定的。目标是在给定的时间段内,选择要全部或部分满足的需求,以便最大化(通常)总利润。这个问题的重要性在于,如果“短视地”决定车辆流量,不考虑未来几周的需求预测,人们可能很快陷入非常不希望的情况,即没有可用的空车或列车没有能力满足未来的需求。我们提出了一个整数多商品流模型的问题。这种模型有大量的变量和约束条件,但其线性关系给出了很好的界限。 我们设计了一个简单的预处理过程,原来是必不可少的,以减少这个模型到一个易于处理的大小。这种方法已经转化为产品,目前用于支持巴西一家重要物流运营商的运营决策解决的实例通常涉及7天的时间段、150个铁路调车场和大约350个需求、1700个火车腿和12,000节车厢(分为25种不同的类型)。这种情况通常在几个小时内解决到最优。Holmberg等人已经使用了类似的模型。[5]瑞典国家铁路的空车流量,假设已经确定了装载车厢的流量,并使用列车中的剩余容量来移动空车。这种做法的缺点是:(i)这就留下了一个复杂的问题,即确定一个好的装载车的ow,这个问题要在其他地方解决,以及(ii)当对空车的需求不能得到满足时,假定的装载车的ow就不再可行。因此,可能需要几轮才能找到一个可行的空车和满载车的路线。当然,这种解决方案不太可能是最佳的。本文的提纲如下。第二节对问题进行了详细的描述。第3节介绍了我们的数学模型,而第4节介绍了预处理算法。第5节给出了计算结果。最后评论见最后一节。Kazasawa等人442问题描述货车流问题寻求一个可行的车辆流和相应的装卸顺序,以便尽可能地满足客户的需求。一个可行的ow取决于网络的初始状态,并且必须考虑列车和车场的容量。 现在我们通过解释一些关键词来详细说明这个问题:汽车- 汽车根据其主要特征分为类型比如说粮食车,燃油车,集装箱车等等。在许多情况下,一种商品可以装进一种以上的汽车。网络的初始状态包括以下信息:在初始时间有多少每种类型的车厢停放在每个车场,在初始时间有多少每种类型的车厢连接到已经运行的列车上,以及这些车厢是空的还是装载有来自某些需求的商品。也可以定义最终状态,在最终时间应该停放在每个院子的每种类型的汽车数量的下限和上限停车场-停车场是铁路网络中可以停放汽车的位置。有些堆场配备了装卸设施。有些站场是空车或满载的车厢可以停放的地方,等待另一列火车。一个车场的容量是指可以停放的最大车辆数量。每个车场都有一个处理时间,这是一个时间上限,用于分类、操纵和可能将车辆组装成块,以便它们准备好连接到火车上或装载/卸载。火车-铁路有一个固定的火车时刻表,定义为由一组特定的乘务员/工作人员在连续的码(火车腿)之间的一组行程。例如,一列火车可能在某一天的7:00离开A场,并在7:30到达B场,然后在7:45离开到C场,依此类推。或者装载的车厢可以在调车场连接到列车上/从列车上拆下。停车时间(在该示例中为15分钟)被计算为足以拆卸一些轿厢并连接一些其他轿厢,这些轿厢应该已经被处理并组装成块。一列火车的最大容量是它可以连接的车厢的最大数量需求-客户要求与商品类型兼容的汽车数量,这些汽车应在一组装货日期的每个日期从一组原产地码头出发,并运输到一组目的地码头。这种情况可能会导致一个或多个需求。需求的定义特征是:来自同一需求的重车是不可区分的。例如,假设在A堆场有40辆车装载大豆,运往B堆场,在C堆场有另外40辆车装载大豆如果A公司的大豆与B公司的大豆确实无法区分,则可以将两个订单定义为同一需求。在这种情况下,输出解决方案实际上可能需要一些Kazasawa等人45汽车从A到C,从B到D。需求的其他属性是装载/卸载时间和一组可接受的卸载日期。某些需求必须得到满足(由于合同的原因),但其他需求可能只得到部分满足,甚至完全被拒绝,因为铁路网缺乏资源(空车或列车容量)在这些情况下,它被定义为实际从起点运输到目的地的每辆汽车的货币估计利润。这个问题的目标函数通常是使这些利润最大化。请注意,如果从A到B乘汽车的利润与从C到D乘汽车的利润显著不同,那么即使所涉及的商品是不可区分的,也应该将这些订单定义为不同的需求图1.一、铁路网及其8个运营区(用矩形表示)。我们提供了我们所面临的特定问题的更多细节。铁路经营者希望在他们的操作中尽可能地有规律性。因此,每周固定的列车时刻表是根据对未来需求的预测每季度确定的。当然,实际需求可能与预测有很大差异,因此出现了车辆问题,以便在不改变列车时刻表的情况下尽可能满足实际需求。铁路不能完全满足的 需 求 不会延期交货,Kazasawa等人46图二. 汽车为满足远距离区域之间的需求而采取的路线示例(每个箭头代表一列火车)。因为运营商可以选择以较高的成本使用其自己的卡车EET或租用的卡车来运输剩余的 在这些情况下,利润被定义为卡车和铁路成本之间的差额。铁路网总长16,000公里,分布在巴西4个州:S~aoPaulo(symbolSP)、P aran(PR)、SantaCatarina(SC)Rio Grande do Sul(RS)网络运营商决定将其划分为8个重叠的操作区域,它们在图1的地图中显示为矩形。除了极少数特殊的区间列车外,定期列车的行程完全包含在一个区域。这一政策在很大程度上缓解了乘务管理和机车维修问题,但对车辆问题的影响是:只有使用最少的车辆才能满足跨地区的需求两列火车。图2给出了这种情况的一个极端例子,利用7个不同的列车旅行从起点到目的地。 图中的每个箭头表示一列火车,圆圈是起点,中间和终点站。Kazasawa等人473数学模型设D为需求集合; Y为码集合; K为车厢类型集合;L为列车腿集合;R为列车集合;T=f1;2;3; : :;n g为对连续相关时钟时刻进行编号的集合。如果发生以下事件之一,则时钟时刻被称为相关的:列车段的到达或离开;装载/卸载或装卸/连接/拆卸操作的可能开始或结束将时间(t)定义为编号为t的时钟时刻。 还考虑每个列车r具有集合Lr, 火车腿flr;lr;:;lr G,且Ea_c_h_leg_l在时间t(l)具有起点i(l),且目地12mj(l)在时间(l)。输入数据c d:每车货物的需求利润。d和d:每个ch需求的装卸时间。l和l:列车腿l的连接和拆卸时间。这些时间还包括相应场地的处理时间(d):与需求兼容的一套汽车类型。ITD:在车场i和时间t请求的与需求D兼容的类型的轿厢的数量。itd:在车场i和时间t可以卸载的装载有需求d的车厢的最大数量。CAP l:列车腿l的容量。Y CAP i:堆场i的容量。空车k:t1 t2 t3 t4 t5t6符号:列车节点车场节点颜色分类:堆场12号院k车满载着需求d:弧线:列车连接/分离停放装载/卸载图3.第三章。汽车和需求子网络的小例子在我们的多商品流动公式中,每一种空车类型和每一种装有一定需求的汽车类型都定义为一种商品。 所以我们有网络上的jK j+Pd j(d) j个节点的所有节点,RKazasawa等人48KLKDL;wQQ我我(wW(zKL0有车场节点和列车节点。站场节点之间的弧表示停在该站场的汽车,并且不连接到任何列车。列车节点之间的弧形表示连接到列车的车厢,要么停在车场,要么在列车腿上移动。车场和列车节点之间的弧线表示装卸/连接/分离操作。最后,这是装载和卸载弧,允许将某种类型的空车转换为具有特定需求的那种类型的车,反之亦然。我们更正式地定义上面描述的有向图G=(V; A)(也参见图3):图谱实体(i) 顶点数:vitk:空车厢k的子网络的场地顶点。u itkd:装载有需求d的类型k的车厢的子网络的场地顶点。W0 :空车k的子网络的列车证书,列车段L的起点和目的地(分别)。KDL z0 :车厢k的子网络的列车顶点,(分别)对列车段L的始发地和目的地的需求D。(ii) 弧线:(v itk; v i(t+1)k):对于空轿厢类型k,停放的轿厢从时间(t)到时间(t +1)在场地i处起弧。(u itkd; u i(t+1)kd):对于装载有需求d的轿厢类型k,从时间(t)到时间(t + 1),停放的轿厢在场地i转弯。(wkl(z0KL;z0):k号车厢和l号列车段的车厢运动弧线。1):轿厢k的轿厢移动弧,负载有需求d,以及KDLKDL对于火车腿L.(w0; wr):k型车厢停在克勒特雷恩河klq+1q q+1(z0;ZR):装载有需求d的k型车停在kdlrkdlq+1列R的列腿L R和L R 。q q+1(v i(l)tk; w kl):在码i(l)处附加弧,从时间(t i)=时间(t(l))l对于k型车和l段列车,时间(t(l))。(u i(l)tkd; z kdl):在码i(l)处附加弧,从时间(t i)=时间(t(l))l到时间(t(l)),对于装载需求d的k型车厢,对于列车航段l。kl;vj(l)tfk):在码j( l)处从时间((l))到时间(tf)分离弧=时间((l))+l代表k型车,l代表列车腿。0KDL;uj(l)tfkd):在码j( l)处从时间((l))到时间(tf)分离弧=时间((l))+l用于装载需求d的k型车,用于列车腿l。(v itk; u itf kd):在码i处从时间(t)到时间(t f)的加载弧=时间(t)+k型车的数量d。 这些弧线只存在于k 2(d).(uit kd;vi tfk):从时间(t)到时间(tf)在场地i处卸载弧=时zKazasawa等人49间(t)+由需求d使用的类型k的车厢的d。这些Kazasawa等人50当k= 2(d)时,弧存在.设A1l是与 列 车 航 段 l 相 关 联 的 所有车辆移动弧 的集 合 ;A2 是某对(i;t)的所有停放车辆弧的集合;A3是需求d的在场i和时间t的所有装载弧的集合;A4是需求d的在场i和时间t的所有卸载弧的集合。模型中唯一的决策变量是xa,它表示在弧a上行驶的汽车数量。该变量根据弧的类型有不同的含义。数学模型为:最大值XXXXcd:xa X X:xaS.T.i2Yt2Td2Da2A3itdl2La2A1l(一)Xa2+(v)xa= Xa2英寸(五)xa+b;8 v2V(二)Xa2A1lX aCAP 1;8l 2 L(三)Xa2A2itX a YCAP i;8i 2 Y; t 2 T(四)(五)(六)Xa2A3itdXa2A4itdX aitd;8i 2 Y; 8 t 2 T; 8 d 2 DX aitd; 8 i 2 Y; 8 t 2 T; 8 d 2 D所有变量均为整数约束(1)定义了所有子网的所有顶点的流守恒约束。右侧b仅在对应于初始状态的顶点上(或者在一些罕见的情况下,汽车在周期中间进入或离开网络)与零不同。列车和调车场能力由(2)和(3)建模。约束条件(4)规定,装载弧以当时请求的轿厢数量为界。 同样地,(5)在每个可能的时刻限制卸载操作。 注意可以在模型中留下自由度,并且通过以给定D的ITD之和大于相同D的ITD之和的方式设置参数,允许在不同的可能日期执行卸载。在这个模型中,通常的目标是最大限度地提高利润,从跨-运输汽车以满足需求。 由于实际装载并且卸载对于每个需求必须是相同的,这些变量集合中的任何一个都可以用在目标函数中。我们还为移动弧分配了一些剩余成本,以确保不会进行不必要的移动Kazasawa等人51Holmberg等人[5]使用了一个类似的模型,在给定重车流量后,根据剩余的列车容量确定最佳的空车流量。在这种情况下,只有jK j商品,没有装载/卸载弧。其他Kazasawa等人52最近的文章(Brucker et al.[2]和Cordeau et al.[3])还描述了使用整数多商品OWS来模拟旅客列车中的车辆流问题。在这种问题中,没有要求,每种类型的车厢(头等舱,二等舱,餐厅等)必须移动,以便组装成预定的列车。由此产生的网络没有我们的情况那么大,但所有这些作者都报告了良好的结果,这是由于线性松弛提供的高质量边界。我们的结论是,我们的模型的输出是一个可行的。当我们想知道网络中每辆车的路线时,我们应用了一个标准的ow分解过程,如[1]所述。4预处理模型上述模型是在由jKj+Pd j(d) j个子网(约550个)组成的多商品网络上定义的,每个子网由y组成,直到jYjjT j + jL j顶点和大约相同数量的弧。在我们的测试实例中,集合K是小的(j K j = 25),集合Y 是中等(jY j = 150),但jT j可以变化从200人左右增加到1000多人。jT j的大尺寸反映了这样的事实,即在所考虑的时间段期间,像火车段的到达或离开这样的事件在许多不同的时间发生。结果,模型的大小变得非常大,我们甚至无法分配加载到MIP求解器所需的内存。一个可能的补救办法是通过将时间限制为某个更大单位的倍数(比如30分钟)来减小T当然,这会在一定程度上降低我们更倾向于设计一个预处理过程,以减少模型的大小到一个合理的,而不影响其准确性。第一个预处理过程,称为前度,包括在消除中间顶点的程度2。图4说明了这个过程。对于所有测试的实例,这个过程已经将网络中的弧的数量减少到原始数量的10%以下。这种减少是显著的,但这不足以允许通过MIP求解器来求解模型。一个稍微复杂一点的预处理过程,称为PRE-Path,试图消除需求子网中的弧。这个想法是,如果没有路径,则arc(i;j)肯定不会被装载有需求d的车厢使用在该子网络中从对应于需求D起点的顶点到i以及从j到对应于需求D的目的地的顶点的另一路径。这个简单的想法允许删除许多对应于火车腿的弧,从而减少了许多顶点的程度。之后,可以再次应用测试PRE-Degree以实现进一步的减少。对于所有测试的实例,结合使用程序PRE-Degree和PRE-Path将网络中的弧数减少到原始弧数的1%以下。生成的模型可以通过MIP加载和求解Kazasawa等人53t1 t2 t3 t4 t5 t6空车k:k车满载着需求d:见图4。 图3中PRE-Degree程序的应用示例解算器我们只注意到,现代MIP求解器已经具有非常好的预处理机制,可能已经执行了相同的简化|如果原始模型能被输入的话。5结果我们提出了计算结果,从解决模型对应的8表1中的典型实例。 这些运行是在Pentium- III 800 Mhz和768 MB RAM上执行的。使用的MIP解算器是CPLEX7.1.表1的某些列需要一些解释。第#列是实例编号。列nC是商品的总数,问题(j K j +Pdj(d)j)。列rows和rn是rows的numb在我们的预处理后,模型中的列。 列LPT是时间,秒需要解决的线性松弛的模型,BB是节点的数量在分支和边界树,TT是总时间秒,以找到一个最佳的积分解决方案和差距是百分对偶差距之间的最佳分数和积分解决方案的价值观。 对于所有这些8在某些情况下,不存在二元性差距。然而,在4个案例中,在分枝定界树的根节点处获得的整数解是分数的,并且必须执行某些分枝以便找到具有与第一分数解完全相同的成本的整数解。这证实了由多商品流动模型得到的边界6结论我们提出了一个货车流问题的模型,在实践中证明是非常有效的,使我们能够解决最优的所有情况下测试过的最大的拉丁美洲铁路运营商公司。一Kazasawa等人54#jT jjY jjD jjL jNCcols行LPT(s)BBTT(s)间隙13971593971675548164490012136681168217640.00239715835516755301283438949908713213360.003397154382167554412552639364044291435 0.004417159373170153712249488972706111623 0.0052121593971542548154275111634991306113200.00610451593971722548181765312666031345113640.00734934364151152110549317245351149319110.0081075159405235658335920272650146501212175300.00表18例结果。一种简单而有效的预处理方案也起到了重要作用。所得到的模型和算法被合并到一个完整的软件包中,称为OptVag,该软件包还包括一个图形用户界面和从数据库接收在线信息(如网络中每辆车的当前位置)的能力。该软件包目前用于支持该公司的运营决策目前正在对该模型进行一些改进和扩展,例如更好地衡量列车长度和重量方面的能力,而不是车厢数量,以及适应也涉及卡车的多式联运物流问题。引用[1] 阿胡贾河T.马南蒂和J. Orlin,\网络流:理论、算法和应用,Prentice Hall,1993。[2] Brucker, P. , J. Hurink 和T. Rolfes , Routing of railway carriages : A casestudy,Technical Report 1498,University of Twente,Netherlands(1999).[3] Cordeau,J.F.,F. Soumis和J. Desrosiers,机车和车厢对旅客列车的同时分配,运筹学49(2001),pp. 531{548.[4] Cordeau, J.F. , P. Toth 和 D. Vigo , A survey of optimization models fortrain routing and scheduling , Transportation Science32 ( 1998 ) , pp.380{404.[5] Holmberg,K.,M. Joborn和J. Lundgren,改进的空车分配,运输科学Kazasawa等人5532(1998),pp. 163{173.
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- 中文翻译Introduction to Linear Algebra, 5th Edition 2.1节
- 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
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功