铁路OD分配优化方法

第25卷,第4期中国铁道科学Vol.25 No.42004年8月CHINA RAILWAY SCIENCEAugust,. 2004文章编号: 1001 .4632 (2004) 04 011604铁路OD分配优化方法史峰'，黎新华'，莫辉辉'，颜湘礼”，廖时元2(1.中南大学交通运输工程学院，湖南长沙410075; .2.铁道第四勘察设计院线路站场设计研究处,湖北武汉430063)摘要: 基于最短径路、合并径路、适度分流径路三种径路形式研究铁路OD分配问题。通过巧妙地构造合并径路邻域系，设计优化合并径路分配方案的模拟退火算法，解决铁路OD分配的核心问题。进而在合并径路分配方案的基础.上，采用贪婪算法增加分流径路获得适度分流径路分配方案，以解决能力相对紧张的铁路运输网络的oD分配问题。大规模铁路0D分配实例计算表明，这些优化方法具有良好的优化质量和运算效率。关键词:铁路运输组织; OD分配，合并径路，模拟退火算法，贪婪算法中團分类号: U292.39文献标识码: A铁路OD分配问题是将铁路货运OD流在铁路里耗费最少。运输网络中按照运输能力合理分配径路。为了使铁由于铁路运输的特点，每一支OD流通常只选路网络的运输能力与运输需求相适应，制定铁路网择- 条径路， 同终点OD流的径路集也通常具有合络发展规划时必须充分考虑铁路运量对铁路网络运并结构(即同终点的径路集由指向终点的有向树唯输能力的需求，而铁路运量对运输能力的需求关一确定)。 合并结构反映在同终点OD流在技术站系，正是通过铁路OD分配来确定的。同时，铁路改编中转时并 人同-一个编组去向，因此具有相同的OD分配也是制定铁路运输计划、列车编组计划等后续径路。 在网络能力紧张时，允许选择分流径路工作的基础。进行分流。结合目前铁路的最短径路、特定径路这文献[1]至文献[8] 对铁路车流径路优化问两个概念, 铁路0D分配采用三种径路形式:最短题的研究获得了不少结论，其中文献[3]提出的径路、 合并径路、适度分流径路。其中最短径路具合并径路与铁路运输组织形式最为吻合。本文以合有里程最短、 合并结构的特点，但不考虑路网的能并径路的概念为核心，创建了合并径路邻域系，在力限制;合并径路具有合并结构的特点，还要求此基础上设计了优化合并径路OD分配的模拟退火OD分配与路网能力相适应;适度分流径路在合并求解算法，并采用Floyd-Warshall算法和贪婪算法径路的基础上，适当增加一些迁回分流径路使超限设计了最短径路和适度分流径路两种径路形式的路段能够得到最大程度的缓解。OD分配优化方法。大规模铁路OD分配实例计算方便叙述起见，引人符号如下:记铁路网络为表明，这些优化方法具有良好的优化质量和运算效(S,E,D,H)，其中点集s = {s(1),s(2),-，率。s(n)}表示铁路车站集;边集E = l(1),(2)，1铁路OD分配问题与基本符号e(m)}表示路段集，即对s(i)至s(j)的路段，存在e(k)=(i,j)∈E;数组D = (d(k))m表示路段长铁路OD分配问题-般可叙述如下:在给定铁度,其中d(k)表示e(k)的长度;数组H=路网络、路段通过能力和OD流量的条件下，确定(h(k))m表示通过能力，其中h(k)表示e(k)的通各支OD流的运送径路，使之与路网运输能力相适过能力;数组F = (f(i,j))x. 表示OD流，其中应，与铁路运输的特殊组织形式相吻合，并使吨公f(i,j)表示s(i)至s(j)的OD流。中国煤化工收稿日期: 2003-08-18作者简介:史嵘(1956- -),男. 湖南芷江人，教授，博士生导师。MHCNMHG第4期铁路0D分配优化方法117P= {P.(i,j),rw(i,j):s(i),s(j)∈S,w= - 条径路(最短路)，并要求同终点径路具有合并.1,2,., W(i,j)l表示OD流的径路集，其中W(i,结构，没有能力限制，建立最短径路分配模型M1j)表示OD流f(i,j)的径路数, P。(i,j) 表示f(i,如下j)从s(i)至s(j)的第w条径路(即s(i)至s(j)的minZ=.2 f(i,j). |P(i,j)|(1)f(ij)∈F车站编号序列), ro(i,j)>0表示f(i,;)通过第wst.条径路的比率，2 r.(i,j) = 1。记R = (r。(i,P(i,j) = (;,q(;,))//P(q(i,j),j)s(i),s(j)∈S(2j)),在径路唯- -时,也用P(i,j)表示P,(i,j)。对于合并径路方案，由于每一- 支OD流都只有对于合并径路，若P(i,j) = (i,,",j),则一条径路(不一定为最短路)，同终点径路具有合P(i,j)= (i,k)//P(k,j)。由于合并径路仅仅取决并结构，具有能力限制，建立合并径路分配模型于各支流从起点出发第一个到达的车站，合并径路M2如下:可用矩阵Q= (q (i, j))来简单描述，其中min2= 2 f(i,j). |P(i,j)I(3)s(q(i,j))表示OD流f(i,j)从s(i)出发的第二个站。因此，合并径路可由矩阵Q= (q (i, j))按s.t.P(i,j)=(i,q(i,j))//P(q(i,j)，j)2 f(i,j)≤h(k) e(k)= E(4) .的规则导出。P(i,j) = (i,q(i,j))//P(q(i,j),j)对于适度分流径路，尽管OD流f(i,j)的径路(5)数为W(i,j)条,但仍可限制f(i,j)从s(i)出发的对于适度分流径路方案，由于OD流f(i,j)有.第二个站最多只能是两个之一，序号为y(i,j)和多条径路，f(i,j) 的部分流量到达s(yr(i,j))的yx(i;,)(只有一条径路时x(i,;)为0而无效),并.后续径路与f(y,(i,j),j)径路相同，到达s(y2(i,且f(i,j)的部分流量到达s(y.(i,j))的后续径路j))的后续径路与f(y2(i,j),j)的径路相同，并具与f(sy(i,j),j)径路相同，到达s(y2(i,j))的后有能力限制，建立适度分流径路分配模型M3如续径路与f(s2(i,j),j) 的径路相同。所以将合并下径路矩阵Q= (q (i, i))推广为适度分流径路矩阵Y= (y (i, j), yz (i, j))来描述,其中minZ=_ 2 f(i,j). 艺r(i,).. s (y。 (i, j))表示OD流f (i, j)的部分流从.. |P_(i,j)|(6s (i)出发的第二个站。进而，适度分流径路又可s.t.由矩阵Y按P。(i，j)=(i,y。(i,j))//P。f(i,j). r.(i,j)≤h(k)(yn (i, j), j)的规则导出。e(k)∈E(7)2铁路 OD分配优化模型r(i,;)= 1,rw(i,j)≥0w= 1,2..., W(i,j),s(i),s(j)∈S (8)记径路P.(i,j)的长度为|P.(i,j)|,由于P.(i,j) = (i,ye(i,j))//P.(y2(i,j),j)OD流f(i,j) 在径路P.(i,j) 上分流的比例为u≤W(i,j),v≤W(y。(i,j),j),g = 1,2,r(i,j),所以，f(i,)在径路上的流量为f(i,j).(9)r(i,)， OD流f(i,j)的费用为2 f(i;,j) ，r.(i,) . P.(i,j)|，全部OD流的费用为3铁路 OD分配优化算法2 Zf(i,j) . r(i,j) . P.(i,j)|或代化求解算法非常简中国煤化工法求解任意两点之W)己f(i,j).艺r(i,j). |P(i,j)|。:FYHCNMHG.录每条路上的第二NTEF对于最短径路方案，由于每一-支OD流都只有点得Q = (q(;,)), 最后计算出目标函数值118中国铁道科学第25卷2 f(i,j). |P(i,j)|即可， 算法复杂度仅为 为初值,接收频率不足0.8时适当提高， 超过0.8O(n')。时适当降低，直到将初始温度调整得使接收频率接对于现实的铁路网络，铁路运输能力和铁路运近0.8为止。量基本相适应，铁路运输的主体径路形式是合并径温度下降规则采用比例下降控制,其比例值以路，在能力紧张地区有少量分流径路。下面主要讨0.65为初值,逐步单调上升至0.9。论合并径路分配的模拟退火算法，进而在合并径路同一温度的迭代次数采用迭代次数下限、上限的基础.上适当调整以获得适度分流径路分配方案。和接收频率来综合控制。取下限初值为车站数的3.1合并径路分配的邻域 系和模拟退火算法0.2倍，上限初值为车站数的0.25 倍,接收频率初模拟退火算法是一种基于邻域系的随机搜索算值为0.6。随着温度的下降，迭代次数的上下限和法，每次迭代从当前解出发在其邻城中随机游动找接收频率也适当提高。到该邻域中- - 个新的解，新解比前者较好时完全接算法终止规则采用温度降至接近0或目标函数受这个解，较差时按- -定概率接受这个解，模拟退式(10)在次迭代无改变综合控制。火算法引用温度t逐步下降至0来描述接受较差解3.2适度分流径路分配的贪婪算法的概率从略小于1降至接近0为止，其中在相同温对于模型M2的满意解Q = (i;,)),若Q度需要迭代充分多次以便反映出概率特征。模拟退既是最短径路又满足能力约束，则Q无需舔加分流火算法在理论以概率为1地收敛F全局最优解。径路， 否则可通过添加分流径路达到降低超限率或简化模型M2的约束条件起见，引入罚因子缩短径路长度的目的。但添加分流径路的同时也使η=”2 f(i,j). IP(i,j)|(其值为路段平均运输组织复杂化，所以分流径路的数量应视降低超限率或缩短径路长度适当控制。统- -降低超限率和费用的n倍),将能力约束(4) 以相对超限量的形缩短径路 长度的目标起见，类似模型M2的处理，式并人目标函数(3)得(若模型MI中增加标号，将模型 M3转化为以式(8), 式(9)为约束条件、前一行要作相应修改):式(11)为目标函数的优化问题。minZ:= 2 f(i,j). |P(i,j)l+ η.minZ,=_ 2 f(i,j).艺r(i,j).之htymax|》f(i,i)- h(),.0|P(i,i)|+η. 2丽，(心e民,(10)m... 习f(i,j).r.(i,j)- h(k),0} (11)模型M2便转化为以(5) 式为约束条件、(10) 式为目标函数的优化问题。其解即使不满足能力约贪婪算法的初始解为: xy(i,j) = q(i,j)，束，能力超限量也相对均衡。y2(i,j)=0,r(i,j)=1, r.(i,j)=0,(w>1),下面讨论合并径路的邻城系和模拟退火算法的目标值为:Z;(Y,R)。退火计划表。模拟退火计划表包括:初始温度、温对任意j,由于以s(j)为终点的径路集由指向度下降控制规则、同一温度的迭代次数控制规则、s(j)的子图Y, 确定，任意选择路段(i,k)∈E-算法终止规则。y,满足yx(i,j)=0,且不存在w使i∈P。(k,给定一个合并径路方案e,对任意点s(j),由j),预置yx(i,j)= k得Y[yx(i,j)= k],并将通于以s(j)为终点的径路集由指向s(j)的有向树e,过s(i)且终点为s(j)的OD流在s(i)至s(j)的所唯一确定，任意选择路段(i,k)∈E-Q,且i在有径路上按目标函数值(11)式重新分配r.(u,)=P(k,j), 更换q(i,j)为k,得新的解Q[q(i,j)=2(u,j), i∈P。(u,j),得R[r.(u,j)=心(u，k],由于;和(i,j)的任意性可得到一系列与Q仅j),i∈P_(u,j)],即目标函数值为: z,( Y[yx(i,仅相差- -个元素的解,这些解构成Q的邻域N(Q)。),i∈P.(u,j)]),由此得到合并径路的邻域系。中国煤化工1Rr(.J)=初始温度以YHCNM H Ginz.(Yyx(i,)η. 2 hymax|》f(i,j)- h(k),0|e(b)E(i.)= k],R[r(u,j)=嗜(u,j),i∈P_(u,j)])1第4期铁路0D分配优化方法19若Z;(Y,R)> Z3(Y[y2(I,J)= K],R[r.(u,J)查询及 OD分配查询等模块。路网数据组织充分利= m(u,J),I∈P。(u,J1)]),则Y= Y[x2(I,J) 用了线路信息，以便于按线路进行整体数据维护。= K],R = R[r(u,J) = rB(u,J),I∈ P.(u,为了方便数据的多样化统计和文档整理，数据按J)],Z,(Y,R)= z(Y[y2(I,J)= K],R[r.(4,Excel格式文件导人导出。直观起见，系统还给出.J)= r*(u,J),I∈P.(u,J)]),如此循环直至了路网结构、径路及配流结果的图形表示。Z3(Y,R)不能下降，或分流径路的数量到达- -定利用该系统对400余个节点的铁路OD分配实例计算表明，该系统具有良好的优化质量和运算效值为止。研究表明，合并径路是铁路OD分配的核心概4优化分配系统应用 与结论念,适度分流径路分配方案只要由合并径路分配方根据上述优化模型和求解算法，用C++开发案局部调整便可得到。合并径路邻域系是优化合并了铁路OD分配优化系统，系统包括:路网数据维径路OD分配的重要基础，以此为基础设计的模拟护与查询、OD流维护与查询、最短径路分配优化、退火求解算法具有分配规模大、运算速度快、优化合并径路分配优化、适度分流径路分配优化、径路效率高的特点。献[1郑时德，吴汉琳.铁路行车组织[M]. 北京:中国铁道出版社，1988.[2]高旭敏,周 潮,顾炎.铁路网货车车流经路分配的优化模型及算法[].铁道学报，1992 (4): 43- -47.[3]史峰, 李致中。铁路车流径路的优选算法[J]. 铁道学报，1993, 15 (3): 70- -76.[4]孙晚华, 郑时德.铁路车流径路优化算法的研究[].北方交通大学学报，19，9(增): 39- -4.4[s]黄平，张仲义.运输网络运量分配问题的模型及算法研究([]. 中国管理科学，197,7(1):48- -54.[6]查伟雄， 秦作睿.路网上车流径路最优配流法[].北方交通大学学报, 1999 21 (3): 259- -263.[7]史 峰, 孔庆钤,胡安洲.车流径路与编组计划综合优化的网络方法[J]. 铁道学报，1997,19(1); 1-6.[8] 薛华勇. 交通分配模型在铁路货运量分配中的应用[].交通工程科技, 2002 (4): 1-3.An Optimal Method for Railway Origin Destination AssignmentSHI Feng', LI Xin-hua', MO Hui-hui', YAN Xiang-li2 ，LIAO Shi-yuan'(1. Sthool of Teffice and Transportation Engineeing, Cental South Universit, Changsha Hunan 410075, China;2. Track and Station Yard Department, the Forth Suvey and Design Istite of China Railway, Wuhan Hubei 430063, China)Abstract: The assignment problem is researched based on shortest path, merge path and appropriate diversionpath. A simulated annealing algorithm for smartly structuring a neighbourhood system of the merge path and op-timizing merge path asignment is used to solve the core problemn of OD asgnmnent. Subsequently, based on themerge path asgnmnent, a greedy algorithm is employed to increase diversion flow path and obtain appropriate di-version path asignment options so that a solution may be found for OD asgnment for a railway network with-out ample capacity. The aculaion in a large scale example of railway OD asignnent shows this method of op-timization results in good quality of optimization and high eficiency of calculation.Key words: Railway trffic organization; Railway origin中国煤化工ath; Simulated an.nealing algrithm; Greedy algorithm*YHCNMHG(责任编辑刘卫华)