论文研究-铁路超限超重货物运输径路综合优化模型与算法.pdf

所需积分/C币:10 2019-07-22 19:57:13 996KB .PDF
收藏 收藏
举报

以铁路超限超重货物运输径路决策为研究对象, 结合超限超重货物运输特征, 构建了边带属性向量和权重向量的超限超重货物运输网络; 综合考虑限界、桥梁承载能力、车流平衡等约束因子, 以最小化对正常运输组织的干扰、最小化运输里程和最小化运输费用为优化目标, 建立超限超重货物运输径路综合优化模型。为便于模型求解, 改进戒上型和戒下型隶属度函数定量表达干扰; 在采用对数Logistic模式规范化目标函数的基础上构建综合评价函数, 将多目标模型转换为单目标模型, 并进行了模型一致性证明。设计了启发式径路搜索算法, 运用不断修正规范化目标函数权重的实例匹配策略求解模型。实例表明, 模型和算法可以快速决策合理的
2878 计算机应用研究 第29卷 值得注意的是,模型M1并不一定总是有解。例如,从发 0 站至到站因限界或桥梁承载能力限制不存在径路,只能通过改 7(x)= 造线路(设眢拆除、桥梁加固等)来确定运输径路。 如果节点路段的第k个区间进行了限界改造,则记改造其中;a>0,b≤0,c≥0。 后的区间在直线和曲线上综合最小建筑限界分别为1和12;否 上述戒上型和戒下型隶属度函数的值域为[0,1],用这个 区同的值来度量干扰区分不明显。引入参数g,对戒上型和戒 则和分别为和2。对V∈E,松抛约束条件式(1)下型隶属度函数进行收进,使得函数的值域为[0,g1],增强函 如下: 数的实用性。 x2⑧(S④S”)≮!k=1,2,…,n;p=1,2 1)改进的戒上型隶属度函数 若节点路段纩的第k个区间的第q座桥梁进行了改造,改 造后的桥梁检定承载系数记为c;否则令c=cb。对∈E r>c 1+[a(x-c)]b 约束式(2)可松弛为 其中:a>0,b>0,c>0,g>0。 k=1.2 2)改进的戒下型隶属度函数 记节点路段的第k个区间的改造费用为f,则第三优化 目标函数式(7)可扩展为 7(x)= x≥c min(x)=∑/M2∑/ (10 共中:a>0.b′<0,c’≥0,g>0 约束条件和目标函数扩展后,模型M1转换为模型M2:式 约定十扰度量区间为[0,g]。超限超重车禁会将导致区 (3)-(6)(8)-(10)。当模型M1可行时,模型M2也可行,反间其他运输任务停止,对正常运输组织的干扰最大,规定 之不然。当模型M2不可行时,说明该超限超重货物无汏经由g。节点路段访第k个区间的允许最大速度记为6。超限 铁路运输,或者还需要进行更大规模的线路改造,如对不可拆超重车在节点路段沪第k个区间的最小限速记为tm,实际运 卸的控制物进行拆除 行速度为vt越小,干扰越严重,以n运行干扰最大,以 M2属于多目标规划模型,不同量纲使得三个目标无法直1或接近υ运行,对正常运输组织的干扰忽略不计。结 接进行比较。典型的情况是赋予数值较大日标稍大权值即可合改进的戒上型隶属度函数,依据∫随吻变化的趋势,参数c 抵消数值较小目标,以致数值较小目标无法在问题中发挥作取m可表示为 用。考虑到(x)的最大值和最小值未知且不易获得,采用对 数 logistic模式对f(x)进行规范化处理,h=1,2,3。 g m≤≤ (17) 1+「a(n-tmm)1b y k-1,2,3 (11) 共中:a>0,b>0,g>0 其中:y:(x)为/(x)的规范化形式,k=1,2,3 超限超重货物经节点路段的第k个区间运输因正常运 构建规范化目标函数的加权综合评价函数,将多目标模型输繁忙产生的扰与和有关。若右=0,则=0,←越 转换为单目标模型。 接近越大。结合改进的戒下型隶属度函数,依据/随 y(x))=∑oky(x) (12)变化的趋势,参数c取0,可表示为 其中:u(y(x))为加权综合评价函数;y(x)=(y1(x),y2(x), <0 y3(x));:为规范化目标函数的权系数,uk>0 ,,、0≤≤、 构建加权综合评价函数后,模型M,由多日标模型转换为 其中:a′>0,b′<0,g>0。 单目标模型M3:式(3)(4)(8)(9)(12)。 3.2模型一致性证明 3模型进一步处理 本节将证明由模型M3得到的解,或者是模型M2的绝对 最优解,或者是模型M,的弱有效解。 3.1目标函数定量表达 证明记x4分别为f(x),k=1,2,3在X上的最优解 在模型的目标函数中,运输里程和运输费用都可以定量表为M3的最优解,即Ⅴx∈x,有 ,对正常运输组织的干扰属于定性指标。为便于问题解决 f(x)≤f(x)k=1,2,3 对干扰目标函数进行定量化处理。在模糊控制论中,研究对象 l(y(x"))≤(y(x) (20) 具冇模牣性和经验性。模糊变量语言的定量描述由隶鳥度函 对y(x)的f(x)求导,有 数确定,隶属度函数实质上反腴了事物的渐变性。 dy(x) e/k() 1)戎上型隶属度函数 d4(x)(1-c2(x) >0k=1.2,3 (21) t≤C 由式(21)可知γk(x)是关于f(x)的单调递增函数,结合 式(19),有 其中:n>0,b>0,c>0。 1+ei-AN 1+-7 2)戎下型隶属度函数4 yh(x),x∈X;k=1,2,3 第8期 汤波,等:铁路超限超重货物运输径路综合优仳模型与算法 2879 由式(11)可得 定义3匹配实例。与新货物的发、到站,以及超限程度 14(x)=h、y4(x) k=1,2,3 (23) 和超重程度相同或相似的实例。通过以下三个条件进行判断 y a)发、到站属于同一区段或同一極纽 a)若x=x1=x2=x3,由式(23)可知,对x∈X,有 b)中心高差小于40mm,超限货物的上部、中部、下部与国 f(x”)=f(x)=ln h=1,2,3 (24)标的距离差小于20mn。 c)重车总重差小于10t。 令γ(x) 1()对y(x)的n(x)求导,有 y 超限超重货物运输径路综合优化模型的实例匹配决策过 程如下 dy(x)(1-%(x)x>0k=1,2,3 )确定匹配实例。给定目标八允许偏差量△4,k=1,2,3 记x为当前最好解,置初始x为任取一个匹配实例对应的解 因此,yA(x)是关于y4(x)的单调递增函数,结合式(22)有 记R为最大循环次数。 y(xn)≤yh(x)= b)按照式(11)将目标函数f(x),k=1,2,3进行规范化处 rk(tk 理,得到规范化目标函数γ4(x),=1,2,3。给定模型M3的初 Yk(x) 1-yk(x),Vx∈xk=1,2,3 (26)始权系数ωk≥0,k=1,2,3;令r=1。 由式(23)(24)和(26)可得 )求解模型M3(求解模型M3的径路搜索算法在4.2节 f(x”)=hy4(x) <Iny,(x) 给出)得到解x。若循环若干次后x保持不变或者r>R,则输 y.(*)1-(x1(x)k=1,2,3(27)出x为所求满意解决策结束;否则进行步骤d) 由式(27)可知,x”=x1=x2=x3是M2的绝对最优解。 d)满意性判断。计算(x),将其与匹配实例的均值进行 b)若xi、x不全相同,假设x“不是模型M,的弱有效比较,若(x) 解,则由弱有效解的定义可知,存在x’∈X使 ≤Δ,k=1,2,3,转步骤g);否则,转步骤e)。 f(x’)</6(x)k=1,2,3 e)修正不满足允许偏差量目标的权系数。记不满足允许 山式(28)及y(x)是关于f(x)的单调递增函数可知 偏差量的目标为∫(x),h=k1,…,,,1≤S,≤3。令vk= yk(x’)<y(x”)k=1,2,3 (29)f(x)-f,.k=h1,…,A,计算 由式(29)可得 t/∑thh=k1 (AYk(x 由式(30)可得 f)更新当前最好解。 ∑okyk(x')<∑ayk(x) (31) 若u(y(x))<u(y(x)成立,置当前解x为当前最好解 转步骤h) 式(31)也可以表示为 若m(y(x))=u(y(x))成立,以概率0.5接受当前解 n(y(x’))<n(y(x)) (32)为当前最好解r,转步骤h 式(32)与式(20)矛盾,假设不成立。因此,x是模型M2 若u(γ(x)>>u(γ(x)成立,当前最好解x保持不变 的弱有效解。 转步骤h) 证毕。 若(y(x))>l(y(x))成立且a(y(x)>>u(y(x))不 4模型求解 成立,以慨率eP(u(y(x))-u(y(x2))接受当前解x为当 前最好解x,即若 random0,1]<exp(u(y(x)-u(y(x), 4.1实例匹配决策 接受当前解x′为当前最好解x,转步骤h)。 在实际工作屮,超限超重货物发、到站相对固定或者在同 g)输出满意解。若u(y(x))<u(y(x)),置当前解x′为 一区段或枢纽。对于新的超限超重货物可以遵守规章并结合酊最好解x;否则,当前最好解x不变。输出x为所求满意 过去的经验来决策其运输径路。首先查找承运货物是否有厉解,决策结束 史运输记录,若没有,再查找类似货物是否有历史运输记录,它 h)更新模型M3。令1=04,k=k1,…,h、,其余ak保持不 们走怎样的运输径路,这此径路可以作为标准来评判求解模型变,更新后的模程仍记为M3。+1,转步骤) 得到的运输径路是否可以接受。笔者有近10年来铁道部和部42径路搜索算法 分路局的批复电报及部分专列运输方案,是多年积累下来的历 4.1节已经给出了超限超重货物运输径路综合优化的实 史资料。以这些成功案例为基础数据,建立超限超重货物运输例匹配决策过程,其中有一个重要问题尚未解决:求解模型 径路实例库,通过相同或相似货物的运输径路来ⅳ估求解模型M。模型M实质上是最短路冋题。文2」指出铁路车流径 获得的径路。 路冋题应采用动态广探算法(DBFS)进行求解。DBFS是启发 定义1实例。实例是指过去已安全运输过的超限超重式方法,典型的是A算法。A算法的核心是对问题中所含的 货物基厶数据与运输径路,是超限超重运输组织者经验知识的启发信息进行正确分析判断和充分挖掘,抓住冋题的关键特 总结。 征,得出估计节点价值的算式或算法。估计节点价值的算式或 定义2实例库。实例库是所有实例的集合,即保存在数算法是A·算法的关健。根据超限超重货物运输安全特征,结 据库中所有超限超重货物基本数据及相应的运输径路。 合模型M3设计节点价值估计函数f(i)。对于Ⅴi∈V,有 2880 计算机应用研究 第29卷 fi=g(i)+h(i) (b)桥梁承载能力约束判断。 其中:gε(讠)表示从起始节点〃到当前节点i的实际径路耗散 ①令集合(i)=②。对于节点i和∈ψ(i),若(如≤ 值;h(i)表示当前节点i到月标节点d的最优径路估计耗散s,k=1,2,…,n,q=1,2,…,n成立,将节点加入到v(1); 值,h(i)称为启发函数 否则,跳过节点j若(i)=ψ(i),转步骤(c);否则,转② 根据两点之间直线段最短的原理,对于ieV,令 ②对于节点讠和V∈ψ(i)-ψ(i),若式(2)成立,保持节 h(i)=f(ldi) (35 点∮在ψ(讠不变;否则,对不满足承载要求的桥梁进行加固改 其中!b=√(x1-x)2+(y-y)表示节点i与目标节点d造后判别式(9)是否成立。若式(9)成立保持节点j在v(i) 的直线距离;(x,y:)为节点i的地理坐标;(x,ya)为目标节点不变并记录桥梁改造费用;否则,(i)←b(i)-j。 d的地理坐标:f(lda)表示里程为ld的运输径路的总耗散值, 石()=Q,转步骤g);香则,转步骤(c)。 包括运输里程、干扰和运输费用。其中干扰的计算与运输组织 (c)对于节点i和j∈ψ(i),若式(4)成立,保持节点j在 方式冇关,改造费用与限界有关。根据直线距离la无法计算v(i)不变;否则,(i)ψ(i)-j 这两项指标,估计下界也是一个十分困难的事情。因此,计算 若ψ(i)=⑧,转步骤g);否则,转步骤h) ∫(lan)的过程中忽略干扰和改造費用。由式(35)可知: g)返回到节点i的父节点,删除节点i及其与之相关联的 h(i)+f(ld )=f(lid )+f(ld)= 边,令父节点为节点i,返回步骤e);否则,转步骤h)。 f(ldli +ldu)ef(ld d)=h(i) (36) h)将ψ(i)中的节点(未进入过open表或 closed表的节 出式(36)和文献[15中定义43可知,出式(35)确定的点)作为i的后继节点添加到搜索树T中。设置(i)中的成 启发函数h(i)满足单调限制;由文献[15]中定理43可知,员指向节点i的指针。把b(中的节点成员加入甲en表并计 g(i)为从起始节点到节点i的最优径路耗散值。 算f值。 基于上述的节点价值估计函数设计超限超重货物运输径)按照f值重排open表,转步骤c)。 路搜索算法。 算法Ⅰ超限超重货物运输径路搜索算法 5实例 输入:G=(VE,P,W)、S1、S2、S' Q o,d,fon.al,k=1,2,3 输出:超限超亘货物运输径路。 根据本文提出的模型和算法,开发了超限超重货物运输径 )建立一个只含有起始节点o的搜索树T,T中边的方向 路决策支持系统。现有国家电网公司实施的重点工程所需电 由子节点(扩展节点的后继节点)指向父节点(扩展节点)。建 抗器1台,采用铁路组专列方式进行运输,发站为南宁南站,到 立一个未扩展节点表en,将起始节点o置于其中。pen表站为长沙东站,件重284t,外形尺寸为10230×3920×4970 mm,重心位置纵向不偏心,横向偏离几何中心线30mm,重心 中的节点按f值由小到大排序。 b)建立扩展节点表 closed,初始置为空。 高度为2160mm。电抗器使用D26B型290t落下孔车装载,装 c)若open为空则输出未找到最优径路;否则,转下一步。后数据如表1所示;装后轮廓如图1所示。 表1货物装后数据 d)选择open表上的第一个节点(f值最小的节点),将其 从qpen表转移至 closed表。若存在若干个f值最小且相同的 次序 距轨闻货物及车辆通过300m线半径时 高度/mm 半宽 计算半宽/mm 节点,为了保证搜索能尽量朝着目标节点的方向进行,选择起中心高 始节点到当前节点的矢量方向和当前节点到日标节点的矢量 一侧高 4960 1540 1807 方向夹角最小的节点。记此节点为节点讠 二侧高 1690 1715 1982 e)若节点讠为目标节点d,则输出最优径路并退出。此径 三侧高 4740 四侧高 4700-4460 路可在搜索树T由目标节点d回溯至起始节点o。 五侧高 4460-4240 2017 f)若节点i不为目标节点d,生成节点的后继节点集合 六侧高 4240 2119 (i),令v(i)=。生成v(i)实质上是确定超限超重货物可 七侧高 3950~2550 1990 通行节点路段集合。为了提高效率,夏好地利用超限超重货物 八侧高 2550~1750 2050 17501280 运输径蕗实例库,记节点路段安全运输过的超限货物装后在 九侧高 十侧高 1280~360 1750 20l7 直线和曲线上的最大综合轮廓分别为S和S2.,安全通过节 十一侧高 250 1607 点路段的超重车的最大运行活载为Q",∈E。 去口尺寸未衔接处均为斜坡形连接 表中高度及宽度尺寸包 (a)限界约束判断。 备注含了30mm裕量。其中八侧高2550~1750mm处为车辆心 ①对于节点i和i∈φ(i),若S≮S,P=1,2成立,重车重心高/m 间限制速度/km/h ψ(i)←ψ(i)Uj;否则,跳过节点j。若ψ(i)=φ(i),转步骤 超限等级 超级超限 超重等级 h);杳则,转②。 g、a、b、a′、b'分别取值1000、0.03、20.0035、-5;初始权 ②对于节点和j∈φ()-(i),若式(1)成立,(i)←重,k=1,2,分别取0.50.30.2;解不变的迭代次数取10 ψ(i)∪j;否则,检杳区间的控制设备是否可拆卸。若存在可拆次;允许偏差量▲取10%,k=1,2,3。 卸的控制设备,改造相应可拆卸控制设备并记录改造费用;否 综合优化径路全长986km,途经湘桂线和京广线,跨南宁 则,跳过节点j。改造完成后运用判别式(1)的方法判别式(8)和广州两个铁路局。若区间蓝家村一滩头湾、黄土井一紫溪 是否成立,直到货物可通行或者所冇的可拆卸设备都已改造。幽兰一黄冕和高溪市一黄阳司不进行改造,因永州一娄底线路 若ψ(i)=⑧,转步骤g);否则,转步骤(b) 限界限制,将从洛满一牙屯堡一怀化一娄底一株洲北绕行。考 第8期 汤波,等:铁路超限超重货物运输径路综合优仳模型与算法 881 虑到实际工作的需要,可将综合优化径路作为主选径路,将绕参考文献: 行径路作为备选径路。 [」雷定猷.货物装运优理论与应用研究[D].长沙:中南大学 2005 建筑狠界 二级超限限界 [2]胡思继.铁路行车组织[M].2版.北京:中国铁道出版社,2009 114-117 货物装后轮廓 4000 「3江南,李夏苗,朱永辉,等.论铁路车流径路的数学冋题「J.中囯 铁道科学, 农静,李令,叶玉玲,等.铁路车流径路优化分布式算法[冂].中国 铁道科学,2008,29(3):115-121 [5杨瑞臣,周永忖,云庆厦.寻找车辆最优路径的混合算法J].交通 1000 单位:mm 运输工程学报,2005,5(1):102-105 轨面 3000-200010000100020003000 [6〗邓亚娟,庥小鸿,杨超.霄永不确定的枢纽輻射式航线网络设计 图1货物装后轮廓 [J].交通运翰二程学报,2009,9(6):69-74,79 径路比铰结果如表2所示。与绕行径路相比,综合优化径[7]祁文祥,陆志强,孙小明.带软时间窗的集货与送货多车辆路径闩 路经由的区间数更少,总运输里程缩短」14.48%,总运输费 題节约算法[J].交通运输工裎学报,2010,10(2):99-103,109 用减少了18.66%,总干扰度量降低了12.59%。 [8』徐肖豪,李成功,赵嶷飞,竽.基于人匚势场算法的改航路泾规划 表2径路比较 [冂].交通运输二程学报,2009,9(6):64-68. 径路经由区间数量总千扰度量总运输里/km总运输费用/元 [9彭松,贾阳.月球仝局路径规划屮的A*算法改进[J].航天器 综合优化径路 112970.02 97205.35 工程,2010,19(4):80-85 绕行径路126129240.441153119510.10[1U]符草,聂靖.哀解带装载能力限制的开放式车辆路径问题的遗传 区间稔竹—黎塘、來宾一风凰、白山一进德、幽兰一黄冕和 算法[J.系统二程,2008,26(2):78-83 田心铺一才湾限速15km/h;区间黎塘一和吉村、和吉村一小[1] WASSANNA, WASSAN A H, NAYG G. A reactive labu search al go 平阳、小平阳一平塘、大溪河一横山、永岁一夏马、黄土井一紫 rithm for the vehicle routing problem with simultaneous pickups and 溪、黄阳司一水口桥和南河岭一万福岭限速25km/h;其他区 deliveries[ J. Journal of Combinatorial Optimization, 2008, 15 问限速50km/h,无禁会区间。 (4):358-368 [12 FALLAHI A E, PRINS C, CALVO R W. A memetic algorithm and a 6结束语 tabu search for the multi-compartment vehicle routing problem[J] Computers and Operations Research, 2008, 35(5): 1725-1741 径路决策是超限超重货物运输调度的核心内容之一。综[131 BRANDAO J, EGLESE R. a deterministic tabu search algorithm for 合考虑对正常运输组织的干扰、运输里程和运输费用休现了优 the capacitated are routing problem[ J]. Computers and Oper 化方案的整体性。目标函数的定量表达有利于问题的求解,模 tions,2008,35(4):1112-1126 型一致性证明保证了解的有效性,实例匹配策略体现∫优化方[14]王季方,户正鼎.瘓糊控制巾隶属度函数的确定方法[J].河南科 案的灵活性,实例表明了模型和算法的有效性。以本文提出的 学,2000,18(4):348-351. 模型和算法为基础开发的铁路超限超重货物运输径路决策支[15]王亠司,陈剑夫.人工智能中的模糊启发式索技术ˉM].北京: 持系统叮实现全路超限超重货物运输组织的全程网上办公。 机械工业出版社,1993:35-54. (上接第2871页) space clustering of high dimensional data C// Proc of SIAM Interna [3 RAJINI N IL, BILAVANI R. Enhancing K-Imeans and kernelized fuzzy l ional Conference on Dala Mining. 2004. 517-521 C-means clustering with cluster center initialization in segmenting MRI 9 GAN Guo-jun, WU Jian-hong. A convergence theorem for the fuzzy brain images_ C]//Proc of the 3rd International Conference on Ele subspace clustering( FSC )algorithm[ J]. Pattern Recognition tronics Computer Technology. 2011: 259-263 2008,41(6):1939-1947 [4 WEI Lai, ZENG Wei-ming, WANG Hong K means clustering with [1U ASUNCION A, NEWMAN D J. UCI machine learning repository[EB/ manifold C]//Proce of the: 71h Inlerralicnal Conferene e on Fuzzy Sy Olj.(2007).htlp://www.icsuciedu/-mlearn/mlrepositor tems and Know ledge Diseovery 2010: 2095.2099 [5 LIN Y Il, TSAI M S, CIIIN C S. Applications of fuzzy classification [11 CHen Xin, CHEUNG ST, SO S, et al. Gene expression patterns in ith fuzzy C-means clustering and optimization strategies for load iden tification in NILM systems[C//Proc of IEEE International Confe- human liver cancers[J]. Molecular Biology of the Cell, 2002, 13 renee on Fuzzy Systems. 2011: 859-866 (6):1929-1939 [6 HALL L O, GOLDGOF DB Convergence of the single-pass and on L 12 CIIANA E Y, CIIINGA W K An optimization algorithm for clustering line fuzzy C-means algorithms[ J].IEEE Trans on Fuzzy Systems using weighted dissimilarity measures J]. Pattern Recognition 2004,37(5):943-952 [7. DOMENICONI C, GUNOPLLOS D, MA Sheng, et al. Laox ally adaptive [13] HICHEM F, OLFA N. Unsupervised learning of prototypes and attr metrics for clustering high dimensional data[J. Data Mining and bute weights[ J_. Pattern Recognition, 2004, 37(3): 567-581 Knowledge Discovery, 2007, 14(1): 63-97 [14 JOLLIFFE I T. Principal component analysis M. New York [8 DOMENICONI C, PAPADOPOLLOS D, GUNOPULOS D, et al. Sub- Springer-Verlag, 198

...展开详情
试读 6P 论文研究-铁路超限超重货物运输径路综合优化模型与算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-铁路超限超重货物运输径路综合优化模型与算法.pdf 10积分/C币 立即下载
    1/6
    论文研究-铁路超限超重货物运输径路综合优化模型与算法.pdf第1页
    论文研究-铁路超限超重货物运输径路综合优化模型与算法.pdf第2页

    试读已结束,剩余4页未读...

    10积分/C币 立即下载 >