第25卷,第4期中國鐵道科學(xué)Vol.25 No.42004年8月CHINA RAILWAY SCIENCEAugust,. 2004文章編號: 1001 .4632 (2004) 04 011604鐵路OD分配優(yōu)化方法史峰'，黎新華'，莫輝輝'，顏湘禮”，廖時元2(1.中南大學(xué)交通運輸工程學(xué)院，湖南長沙410075; .2.鐵道第四勘察設(shè)計院線路站場設(shè)計研究處,湖北武漢430063)摘要: 基于最短徑路、合并徑路、適度分流徑路三種徑路形式研究鐵路OD分配問題。通過巧妙地構(gòu)造合并徑路鄰域系，設(shè)計優(yōu)化合并徑路分配方案的模擬退火算法，解決鐵路OD分配的核心問題。進(jìn)而在合并徑路分配方案的基礎(chǔ).上，采用貪婪算法增加分流徑路獲得適度分流徑路分配方案，以解決能力相對緊張的鐵路運輸網(wǎng)絡(luò)的oD分配問題。大規(guī)模鐵路0D分配實例計算表明，這些優(yōu)化方法具有良好的優(yōu)化質(zhì)量和運算效率。關(guān)鍵詞:鐵路運輸組織; OD分配，合并徑路，模擬退火算法，貪婪算法中團(tuán)分類號: U292.39文獻(xiàn)標(biāo)識碼: A鐵路OD分配問題是將鐵路貨運OD流在鐵路里耗費最少。運輸網(wǎng)絡(luò)中按照運輸能力合理分配徑路。為了使鐵由于鐵路運輸?shù)奶攸c，每一支OD流通常只選路網(wǎng)絡(luò)的運輸能力與運輸需求相適應(yīng)，制定鐵路網(wǎng)擇- 條徑路， 同終點OD流的徑路集也通常具有合絡(luò)發(fā)展規(guī)劃時必須充分考慮鐵路運量對鐵路網(wǎng)絡(luò)運并結(jié)構(gòu)(即同終點的徑路集由指向終點的有向樹唯輸能力的需求，而鐵路運量對運輸能力的需求關(guān)一確定)。 合并結(jié)構(gòu)反映在同終點OD流在技術(shù)站系，正是通過鐵路OD分配來確定的。同時，鐵路改編中轉(zhuǎn)時并 人同-一個編組去向，因此具有相同的OD分配也是制定鐵路運輸計劃、列車編組計劃等后續(xù)徑路。 在網(wǎng)絡(luò)能力緊張時，允許選擇分流徑路工作的基礎(chǔ)。進(jìn)行分流。結(jié)合目前鐵路的最短徑路、特定徑路這文獻(xiàn)[1]至文獻(xiàn)[8] 對鐵路車流徑路優(yōu)化問兩個概念, 鐵路0D分配采用三種徑路形式:最短題的研究獲得了不少結(jié)論，其中文獻(xiàn)[3]提出的徑路、 合并徑路、適度分流徑路。其中最短徑路具合并徑路與鐵路運輸組織形式最為吻合。本文以合有里程最短、 合并結(jié)構(gòu)的特點，但不考慮路網(wǎng)的能并徑路的概念為核心，創(chuàng)建了合并徑路鄰域系，在力限制;合并徑路具有合并結(jié)構(gòu)的特點，還要求此基礎(chǔ)上設(shè)計了優(yōu)化合并徑路OD分配的模擬退火OD分配與路網(wǎng)能力相適應(yīng);適度分流徑路在合并求解算法，并采用Floyd-Warshall算法和貪婪算法徑路的基礎(chǔ)上，適當(dāng)增加一些遷回分流徑路使超限設(shè)計了最短徑路和適度分流徑路兩種徑路形式的路段能夠得到最大程度的緩解。OD分配優(yōu)化方法。大規(guī)模鐵路OD分配實例計算方便敘述起見，引人符號如下:記鐵路網(wǎng)絡(luò)為表明，這些優(yōu)化方法具有良好的優(yōu)化質(zhì)量和運算效(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;數(shù)組D = (d(k))m表示路段長鐵路OD分配問題-般可敘述如下:在給定鐵度,其中d(k)表示e(k)的長度;數(shù)組H=路網(wǎng)絡(luò)、路段通過能力和OD流量的條件下，確定(h(k))m表示通過能力，其中h(k)表示e(k)的通各支OD流的運送徑路，使之與路網(wǎng)運輸能力相適過能力;數(shù)組F = (f(i,j))x. 表示OD流，其中應(yīng)，與鐵路運輸?shù)奶厥饨M織形式相吻合，并使噸公f(i,j)表示s(i)至s(j)的OD流。中國煤化工收稿日期: 2003-08-18作者簡介:史嶸(1956- -),男. 湖南芷江人，教授，博士生導(dǎo)師。MHCNMHG第4期鐵路0D分配優(yōu)化方法117P= {P.(i,j),rw(i,j):s(i),s(j)∈S,w= - 條徑路(最短路)，并要求同終點徑路具有合并.1,2,., W(i,j)l表示OD流的徑路集，其中W(i,結(jié)構(gòu)，沒有能力限制，建立最短徑路分配模型M1j)表示OD流f(i,j)的徑路數(shù), 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)。由于合并徑路僅僅取決并結(jié)構(gòu)，具有能力限制，建立合并徑路分配模型于各支流從起點出發(fā)第一個到達(dá)的車站，合并徑路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)出發(fā)的第二個站。因此，合并徑路可由矩陣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) .的規(guī)則導(dǎo)出。P(i,j) = (i,q(i,j))//P(q(i,j),j)對于適度分流徑路，盡管OD流f(i,j)的徑路(5)數(shù)為W(i,j)條,但仍可限制f(i,j)從s(i)出發(fā)的對于適度分流徑路方案，由于OD流f(i,j)有.第二個站最多只能是兩個之一，序號為y(i,j)和多條徑路，f(i,j) 的部分流量到達(dá)s(yr(i,j))的yx(i;,)(只有一條徑路時x(i,;)為0而無效),并.后續(xù)徑路與f(y,(i,j),j)徑路相同，到達(dá)s(y2(i,且f(i,j)的部分流量到達(dá)s(y.(i,j))的后續(xù)徑路j))的后續(xù)徑路與f(y2(i,j),j)的徑路相同，并具與f(sy(i,j),j)徑路相同，到達(dá)s(y2(i,j))的后有能力限制，建立適度分流徑路分配模型M3如續(xù)徑路與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)出發(fā)的第二個站。進(jìn)而，適度分流徑路又可s.t.由矩陣Y按P。(i，j)=(i,y。(i,j))//P。f(i,j). r.(i,j)≤h(k)(yn (i, j), j)的規(guī)則導(dǎo)出。e(k)∈E(7)2鐵路 OD分配優(yōu)化模型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分配優(yōu)化算法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(;,)), 最后計算出目標(biāo)函數(shù)值118中國鐵道科學(xué)第25卷2 f(i,j). |P(i,j)|即可， 算法復(fù)雜度僅為 為初值,接收頻率不足0.8時適當(dāng)提高， 超過0.8O(n')。時適當(dāng)降低，直到將初始溫度調(diào)整得使接收頻率接對于現(xiàn)實的鐵路網(wǎng)絡(luò)，鐵路運輸能力和鐵路運近0.8為止。量基本相適應(yīng)，鐵路運輸?shù)闹黧w徑路形式是合并徑溫度下降規(guī)則采用比例下降控制,其比例值以路，在能力緊張地區(qū)有少量分流徑路。下面主要討0.65為初值,逐步單調(diào)上升至0.9。論合并徑路分配的模擬退火算法，進(jìn)而在合并徑路同一溫度的迭代次數(shù)采用迭代次數(shù)下限、上限的基礎(chǔ).上適當(dāng)調(diào)整以獲得適度分流徑路分配方案。和接收頻率來綜合控制。取下限初值為車站數(shù)的3.1合并徑路分配的鄰域 系和模擬退火算法0.2倍，上限初值為車站數(shù)的0.25 倍,接收頻率初模擬退火算法是一種基于鄰域系的隨機(jī)搜索算值為0.6。隨著溫度的下降，迭代次數(shù)的上下限和法，每次迭代從當(dāng)前解出發(fā)在其鄰城中隨機(jī)游動找接收頻率也適當(dāng)提高。到該鄰域中- - 個新的解，新解比前者較好時完全接算法終止規(guī)則采用溫度降至接近0或目標(biāo)函數(shù)受這個解，較差時按- -定概率接受這個解，模擬退式(10)在次迭代無改變綜合控制?；鹚惴ㄒ脺囟萾逐步下降至0來描述接受較差解3.2適度分流徑路分配的貪婪算法的概率從略小于1降至接近0為止，其中在相同溫對于模型M2的滿意解Q = (i;,)),若Q度需要迭代充分多次以便反映出概率特征。模擬退既是最短徑路又滿足能力約束，則Q無需舔加分流火算法在理論以概率為1地收斂F全局最優(yōu)解。徑路， 否則可通過添加分流徑路達(dá)到降低超限率或簡化模型M2的約束條件起見，引入罰因子縮短徑路長度的目的。但添加分流徑路的同時也使η=”2 f(i,j). IP(i,j)|(其值為路段平均運輸組織復(fù)雜化，所以分流徑路的數(shù)量應(yīng)視降低超限率或縮短徑路長度適當(dāng)控制。統(tǒng)- -降低超限率和費用的n倍),將能力約束(4) 以相對超限量的形縮短徑路 長度的目標(biāo)起見，類似模型M2的處理，式并人目標(biāo)函數(shù)(3)得(若模型MI中增加標(biāo)號，將模型 M3轉(zhuǎn)化為以式(8), 式(9)為約束條件、前一行要作相應(yīng)修改):式(11)為目標(biāo)函數(shù)的優(yōu)化問題。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... 習(xí)f(i,j).r.(i,j)- h(k),0} (11)模型M2便轉(zhuǎn)化為以(5) 式為約束條件、(10) 式為目標(biāo)函數(shù)的優(yōu)化問題。其解即使不滿足能力約貪婪算法的初始解為: xy(i,j) = q(i,j)，束，能力超限量也相對均衡。y2(i,j)=0,r(i,j)=1, r.(i,j)=0,(w>1),下面討論合并徑路的鄰城系和模擬退火算法的目標(biāo)值為:Z;(Y,R)。退火計劃表。模擬退火計劃表包括:初始溫度、溫對任意j,由于以s(j)為終點的徑路集由指向度下降控制規(guī)則、同一溫度的迭代次數(shù)控制規(guī)則、s(j)的子圖Y, 確定，任意選擇路段(i,k)∈E-算法終止規(guī)則。y,滿足yx(i,j)=0,且不存在w使i∈P。(k,給定一個合并徑路方案e,對任意點s(j),由j),預(yù)置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在有徑路上按目標(biāo)函數(shù)值(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)],即目標(biāo)函數(shù)值為: z,( Y[yx(i,僅相差- -個元素的解,這些解構(gòu)成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分配優(yōu)化方法19若Z;(Y,R)> Z3(Y[y2(I,J)= K],R[r.(u,J)查詢及 OD分配查詢等模塊。路網(wǎng)數(shù)據(jù)組織充分利= m(u,J),I∈P。(u,J1)]),則Y= Y[x2(I,J) 用了線路信息，以便于按線路進(jìn)行整體數(shù)據(jù)維護(hù)。= K],R = R[r(u,J) = rB(u,J),I∈ P.(u,為了方便數(shù)據(jù)的多樣化統(tǒng)計和文檔整理，數(shù)據(jù)按J)],Z,(Y,R)= z(Y[y2(I,J)= K],R[r.(4,Excel格式文件導(dǎo)人導(dǎo)出。直觀起見，系統(tǒng)還給出.J)= r*(u,J),I∈P.(u,J)]),如此循環(huán)直至了路網(wǎng)結(jié)構(gòu)、徑路及配流結(jié)果的圖形表示。Z3(Y,R)不能下降，或分流徑路的數(shù)量到達(dá)- -定利用該系統(tǒng)對400余個節(jié)點的鐵路OD分配實例計算表明，該系統(tǒng)具有良好的優(yōu)化質(zhì)量和運算效值為止。研究表明，合并徑路是鐵路OD分配的核心概4優(yōu)化分配系統(tǒng)應(yīng)用 與結(jié)論念,適度分流徑路分配方案只要由合并徑路分配方根據(jù)上述優(yōu)化模型和求解算法，用C++開發(fā)案局部調(diào)整便可得到。合并徑路鄰域系是優(yōu)化合并了鐵路OD分配優(yōu)化系統(tǒng)，系統(tǒng)包括:路網(wǎng)數(shù)據(jù)維徑路OD分配的重要基礎(chǔ)，以此為基礎(chǔ)設(shè)計的模擬護(hù)與查詢、OD流維護(hù)與查詢、最短徑路分配優(yōu)化、退火求解算法具有分配規(guī)模大、運算速度快、優(yōu)化合并徑路分配優(yōu)化、適度分流徑路分配優(yōu)化、徑路效率高的特點。獻(xiàn)[1鄭時德，吳漢琳.鐵路行車組織[M]. 北京:中國鐵道出版社，1988.[2]高旭敏,周 潮,顧炎.鐵路網(wǎng)貨車車流經(jīng)路分配的優(yōu)化模型及算法[].鐵道學(xué)報，1992 (4): 43- -47.[3]史峰, 李致中。鐵路車流徑路的優(yōu)選算法[J]. 鐵道學(xué)報，1993, 15 (3): 70- -76.[4]孫晚華, 鄭時德.鐵路車流徑路優(yōu)化算法的研究[].北方交通大學(xué)學(xué)報，19，9(增): 39- -4.4[s]黃平，張仲義.運輸網(wǎng)絡(luò)運量分配問題的模型及算法研究([]. 中國管理科學(xué)，197,7(1):48- -54.[6]查偉雄， 秦作睿.路網(wǎng)上車流徑路最優(yōu)配流法[].北方交通大學(xué)學(xué)報, 1999 21 (3): 259- -263.[7]史 峰, 孔慶鈐,胡安洲.車流徑路與編組計劃綜合優(yōu)化的網(wǎng)絡(luò)方法[J]. 鐵道學(xué)報，1997,19(1); 1-6.[8] 薛華勇. 交通分配模型在鐵路貨運量分配中的應(yīng)用[].交通工程科技, 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(責(zé)任編輯劉衛(wèi)華)