鐵路OD分配優(yōu)化方法

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