李宵寅，魏玉曉

LI Xiao-yin1，WEI Yu-xiao2

（1.鐵三院內(nèi)蒙古鐵道勘察設(shè)計(jì)院 鐵道設(shè)計(jì)分院，內(nèi)蒙古 呼和浩特 010050; 2.呼和浩特職業(yè)學(xué)院鐵道學(xué)院，內(nèi)蒙古 呼和浩特 010051）

(1.Track Design Branch Institute， TSDI Inner Mongolia Railway Survey and Design Institute Corporation Ltd.，Hohhot 010050， Inner Mongolia， China； 2.School of Railway， Hohhot Vocational College， Hohhot 010051， Inner Mongolia， China)

基于不確定參數(shù)的列車編組計(jì)劃優(yōu)化模型研究

李宵寅1，魏玉曉2

LI Xiao-yin1，WEI Yu-xiao2

（1.鐵三院內(nèi)蒙古鐵道勘察設(shè)計(jì)院 鐵道設(shè)計(jì)分院，內(nèi)蒙古 呼和浩特 010050; 2.呼和浩特職業(yè)學(xué)院鐵道學(xué)院，內(nèi)蒙古 呼和浩特 010051）

(1.Track Design Branch Institute， TSDI Inner Mongolia Railway Survey and Design Institute Corporation Ltd.，Hohhot 010050， Inner Mongolia， China； 2.School of Railway， Hohhot Vocational College， Hohhot 010051， Inner Mongolia， China)

在闡述列車編組計(jì)劃與車流徑路優(yōu)化問題的基礎(chǔ)上，針對列車編組計(jì)劃中參數(shù)波動性的問題，分析直達(dá)去向車流量、技術(shù)站編組去向數(shù)、技術(shù)站改編車數(shù)、線路區(qū)間通過列車數(shù)等相關(guān)參數(shù)波動情況，構(gòu)建基于不確定參數(shù)的列車編組計(jì)劃與車流徑路綜合優(yōu)化模型，從處理機(jī)會約束、確定初始可行解、求解目標(biāo)函數(shù)等方面對模型進(jìn)行算法設(shè)計(jì)，最后通過對算例進(jìn)行編程模擬，得到不確定參數(shù)的最優(yōu)編組方案魯棒性更強(qiáng)，為制訂列車編組計(jì)劃提供參考。

列車編組計(jì)劃；車流徑路；不確定參數(shù)；隨機(jī)模擬

列車編組計(jì)劃的優(yōu)化問題屬于超大規(guī)模的組合優(yōu)化問題[1]，由于計(jì)算機(jī)軟硬件能力限制及智能優(yōu)化算法的匱乏，很多研究局限于編組計(jì)劃模型[2-7]的建立和優(yōu)化算法[8-10]的設(shè)計(jì)，而忽略模型在實(shí)際生產(chǎn)中的可操作性。因此，在傳統(tǒng)列車編組計(jì)劃優(yōu)化問題中，車流量、貨車集結(jié)時(shí)間、車流改編額外消耗時(shí)間參數(shù)假設(shè)固定不變，而實(shí)際參數(shù)隨著時(shí)間的變化波動或改變。綜合考慮編組計(jì)劃中參數(shù)的波動性，求解最佳編組計(jì)劃和車流徑路方案，對實(shí)際運(yùn)輸生產(chǎn)和理論研究具有重要意義。

1　列車編組計(jì)劃優(yōu)化模型的數(shù)學(xué)描述

1.1問題提出

基于不確定參數(shù)的列車編組計(jì)劃與車流徑路的優(yōu)化問題，在考慮車流量、集結(jié)參數(shù)、改編參數(shù)波動等情況的基礎(chǔ)上，滿足技術(shù)站和線路相關(guān)參數(shù)的限制，求解最佳編組計(jì)劃和車流徑路方案，使車流耗費(fèi)的集結(jié)、改編和途中運(yùn)行消耗總數(shù)最少。

模型假設(shè)以下條件：①技術(shù)站之間均為單線鐵路，區(qū)間通過車數(shù)按列車編組輛數(shù)折算為通過列車數(shù)，不足 1 列按 1 列計(jì)；②模型中的到發(fā)車流均為單組列車，僅包含這支車流的起訖點(diǎn)；③模型中僅研究技術(shù)直達(dá)列車編組計(jì)劃的優(yōu)化，其余列車編組方案暫不考慮。

1.2變量定義

設(shè)有 r 個(gè)技術(shù)站，k 為技術(shù)站的編號， k ∈ [1，r]；nij為 i 站到 j 站的車流量，車；Tij為 i 站開行到 j 直達(dá)列車的集結(jié)消耗，車小時(shí)；ti為車流在 i 站改編中轉(zhuǎn)每車額外消耗的時(shí)間，h；Dij為線路區(qū)間 i → j 的通過能力，列/d；Bi為 i 站扣除后備能力后允許的最大改編作業(yè)車數(shù)，輛；Sk,k+1為相鄰兩站 k → k+1 間線路的行駛費(fèi)用(折算成時(shí)間，h)；Qi為 i 站的最大編組去向 (直達(dá)去向) 數(shù)；b 為列車平均編成輛數(shù)，輛/列。

設(shè) X 為改編方案變量，可以分為直達(dá)變量、多站改編變量，定義直達(dá)變量

定義改編變量

式中：P 為車流的某一種改編方案，其中元素為所涉及的各改編站標(biāo)號；P (i) 為車流經(jīng) i 站改編的某改編方案；由于同一 OD 對應(yīng)的改編方案變量可能在不同的路徑上，X(m)為車流選擇第 m 條徑路時(shí)的改編方案變量。

定義徑路總方案變量

1.3相關(guān)參數(shù)

（1）直達(dá)去向車流量。假設(shè) θij為編組 i→j 直達(dá)列車時(shí)的車流量，分為以下 4 種情況：① i→j 的車流量 nij；②自 i 站發(fā)往 j 站改編后目的地為 j 站前方站的車流量；③自 i 站的后方站發(fā)出在 i 站改編后再發(fā)往 j 站的車流量；④自 i 站的后方站發(fā)出在 i 站改編后再發(fā)往 j 站，在 j 站改編后又發(fā)往 j 站前方站的車流量。計(jì)算公式為

式中：A (i，j) 為車流 nij所有可能改編方案的集合； w1，…，wi-1為 i 站后方站的標(biāo)號；wj+1，…，wr為 j 站前方站的標(biāo)號。

（2）技術(shù)站編組去向數(shù)。技術(shù)站 i 的編組去向數(shù) Qi' 為 i 站能編組直達(dá)去向的總數(shù)，分為以下 4 種情況：①i 站編組直達(dá)列車到 j ( j≠wi+1) 站的編組去向數(shù)；②自 i 站編組到 j ( j≠wi+1) 站的前方站，途中在 i－j 段開行直達(dá)列車到 j 站改編后，再發(fā)往 j 站前方站的列車編組去向數(shù)；③由 i 站后方某站發(fā)往 j ( j≠wi+1) 站，途中經(jīng)由 i 站改編后開行直達(dá)到 j 站的編組去向數(shù)；④由 i 站后方站發(fā)往 j ( j≠wi+1) 站的前方站，途中經(jīng)由 i 站改編后開行直達(dá)列車到 j 站改編后，再送往 j 站前方站的列車編組去向數(shù)。計(jì)算公式為

（3）技術(shù)站改編車數(shù)。某一技術(shù)站 i 的改編中轉(zhuǎn)車數(shù) Gi包括所有經(jīng)過 i 站并在 i 站進(jìn)行改編作業(yè)的車流量，計(jì)算公式為式中：P (i) 為包含車流在 i 站改編的某一改編方案。

（4）線路區(qū)間通過列車數(shù)。假設(shè) dk,k+1為線路區(qū)間 k→k +1 方向?yàn)?k→k +1 的通過列車數(shù)，分為以下 4 種情況：①由 k 站編組發(fā)往 k +1 站解體的列數(shù)；②由 k 站的后方站編組發(fā)往 k +1 站解體的列數(shù)；③由 k 站編組發(fā)往 k +1 站的前方站解體的列車數(shù)；④由 k 站的后方站編組發(fā)往 k +1 站的前方站解體的列車數(shù)。計(jì)算公式為

因此，考慮上下行方向的線路區(qū)間 k→k +1 的通過列車數(shù)計(jì)算公式為

2　構(gòu)建列車編組計(jì)劃優(yōu)化模型

2.1模型的建立

在模型中涉及的主要因素如下。改編方案考慮編組直達(dá)列車消耗的車輛集結(jié)費(fèi)用、車流改編中轉(zhuǎn)消耗的額外改編費(fèi)用、技術(shù)站的最大編組去向數(shù)和改編能力；車流徑路方案考慮線路通過能力及途中走行費(fèi)用；此外，根據(jù)車流組織中同一支車流不可拆分原則，車流改編和徑路方案遵循惟一性原則。因此，建立基于確定參數(shù)的列車編組計(jì)劃與車流徑路綜合優(yōu)化的模型計(jì)算公式為

式中：I (θij) 為單位躍階函數(shù)δ 為車輛走行費(fèi)用參數(shù)；σ 為改編費(fèi)用參數(shù)，以統(tǒng)一改編消耗、車輛走行費(fèi)用與集結(jié)消耗的單位。

⑴ 式為鐵路網(wǎng)車流的集結(jié)、改編額外和走行總消耗之和；⑵ 式為改編方案惟一性約束；⑶ 式為徑路方案惟一性約束；⑷ 式為技術(shù)站改編能力約束；⑸ 式為技術(shù)站編組去向數(shù)約束；⑹ 式為線路通過能力約束；⑺ 式為改編方案與徑路方案邏輯關(guān)系約束；⑻ 式為改編方案和徑路方案的變量約束。

假設(shè)車流量 nij的變化服從某一概率分布，設(shè) α、β 為給定的置信水平，根據(jù)機(jī)會約束規(guī)劃理論，將模型中與車流量相關(guān)的約束條件改為

假設(shè)集結(jié)費(fèi)用 Tij、單位車輛改編額外消耗 ti為一定波動范圍的模糊數(shù)；ω 為事先給定的置信水平，模型中目標(biāo)函數(shù)則改寫為

綜上所述，建立基于不確定參數(shù)的列車編組計(jì)劃與車流徑路綜合優(yōu)化模型，計(jì)算公式為

2.2模型的退化

所建立的優(yōu)化模型是非線性 0－1 規(guī)劃模型，為使模型求解快捷迅速，需要對模型中的相關(guān)約束進(jìn)行轉(zhuǎn)化，將非線性約束轉(zhuǎn)化為線性約束。

2.2.1徑路總方案惟一性約束的轉(zhuǎn)化

徑路總方案惟一性約束式 ⑶ 式為非線性約束，計(jì)算公式為

2.2.2變量與約束的轉(zhuǎn)化

改編方案與徑路方案變量邏輯關(guān)系約束式 ⒁式為非線性約束，計(jì)算公式為利用為0-1變量的特殊性，對于將原約束等價(jià)轉(zhuǎn)化為若干個(gè)等式，計(jì)算公式為針對模型中的機(jī)會約束，利用隨機(jī)和模糊模擬方法將其轉(zhuǎn)化為線性約束，該部分內(nèi)容將在模型算法設(shè)計(jì)中給出。模型經(jīng)過退化處理，簡化優(yōu)化模型的目標(biāo)函數(shù)和約束條件均為弱非線性，其中目標(biāo)約束的弱非線性表現(xiàn)在階躍函數(shù)上，約束條件的弱非線性表現(xiàn)在通過能力約束中的取整函數(shù)上。

3　列車編組計(jì)劃優(yōu)化模型的算法設(shè)計(jì)

3.1處理機(jī)會約束

為方便簡化計(jì)算及編程，擬對機(jī)會約束進(jìn)行以下處理：①設(shè) α為置信水平，M (為給定的充分大正數(shù))為模擬次數(shù)；②隨機(jī)生成服從某一分布的車流量nij樣本，共計(jì) M 組；③M 組數(shù)據(jù)中隨機(jī)抽取(表示向上取整) 組數(shù)據(jù)，分別代入約束條件 ⒀ 式和 ⒂ 式中組成新的約束條件即可。這樣處理后改編能力約束成為線性約束，而線路通過能力約束成為弱非線性約束，其非線性僅表現(xiàn)在取整函數(shù)上。

3.2確定初始可行解

待解模型性質(zhì)為 0-1 整數(shù)規(guī)劃模型，設(shè)計(jì)算法中可行解的編碼采用二進(jìn)制，可行解向量表示為(改編方案變量 X、徑路方案變量 Y )。

步驟 1：設(shè)變量個(gè)數(shù)為 N (包含 X 和 Y 變量)，i 為設(shè)定的初值 (十進(jìn)制數(shù))，設(shè)函數(shù) de2bi (a，b) 的功能是將十進(jìn)制數(shù) a 轉(zhuǎn)化為具有 b 位的二進(jìn)制向量。

步驟 2：當(dāng) i≤2N時(shí)，進(jìn)行以下循環(huán)：設(shè) Z0= de2bi (i，N )，Z0即為解向量，判斷該向量是否滿足所有約束，如果不完全滿足約束，則 i = i + 1 ；如果滿足全部約束，則跳出循環(huán)。

步驟 3：當(dāng)前所得 Z0向量即為可行解向量。

3.3求解目標(biāo)函數(shù)

擬對車流量、集結(jié)時(shí)間、車輛改編額外消耗時(shí)間波動下的機(jī)會約束進(jìn)行以下處理：①設(shè) ω 為置信水平，M (為給定的充分大正數(shù)) 為模擬次數(shù)，②根據(jù)隨機(jī)模擬生成的車流量 nij、集結(jié)時(shí)間 Tij及車輛改編額外消耗時(shí)間 ti的數(shù)據(jù)樣本，依次計(jì)算目標(biāo)函數(shù)式 ⑼ 式的值 f1，…，fM，將 f1，…，fM從小到大進(jìn)行排序?yàn)?f1'，…，fM'，返回 fM'' 的值即為所求 f。

該處理方法的思想如下。利用隨機(jī)模擬生成的 M 組數(shù)據(jù)求出 M 組最優(yōu)解，按升序排列后的前組最優(yōu)解對應(yīng)函數(shù)的最優(yōu)值，其余 M －ωM 數(shù)據(jù)中的最小值即為所求，根據(jù)大數(shù)定律，序列 { f1，…，fM}中第 M' 個(gè)最小的元素可以作為 f 的估計(jì)。經(jīng)過處理后的機(jī)會約束為弱非線性約束，其非線性僅表現(xiàn)于階躍函數(shù)。因此，采用基于隨機(jī)模擬的改進(jìn)分枝定界法對模型進(jìn)行求解。

4　算例分析

以包含 10 個(gè)技術(shù)站的鐵路網(wǎng)為例，鐵路網(wǎng)共有 53 組非零車流量，假設(shè)車流量的波動均服從均勻分布，所建立模型中共有 4 個(gè)徑路變量和 196 個(gè)改編變量，設(shè)費(fèi)用參數(shù)值 σ 和 δ 均為 1，α = 0.95，β = 0.95，ω = 0.96，模擬 100 組車流量數(shù)據(jù)。分別對基于確定和不確定車流量的列車編組計(jì)劃與車流徑路優(yōu)化模型進(jìn)行求解，不確定車流量對應(yīng)模型所得的最優(yōu)編組方案與車流徑路方案的列流圖如圖1 所示。

模型計(jì)算利用 Lingo10.0 數(shù)學(xué)軟件進(jìn)行編程模擬，在未考慮和考慮車流量波動下的模型求解對比分析如表1 所示。從表1 中可知，針對同一編組計(jì)劃優(yōu)化問題，考慮車流量波動較未考慮車流量波動的模型在模型規(guī)模上要大，但模型經(jīng)退化處理后，約束條件大部分為線性，其余均為弱非線性，目標(biāo)函數(shù)也為弱非線性，模型的求解速度也比較滿意。

圖1　考慮車流量波動下的最優(yōu)編組方案列流圖

表1　未考慮和考慮車流量波動下 2 種模型求解結(jié)果對比分析表

在基于車流量波動的列車編組計(jì)劃與車流徑路優(yōu)化模型中，滿足機(jī)會約束置信水平的大小，從某種意義上代表著編組方案穩(wěn)定性的高低，模型中的機(jī)會約束由大量隨機(jī)模擬數(shù)據(jù)代入約束條件式得出，包含參數(shù)波動范圍內(nèi)的大部分情況。后面通過新一輪隨機(jī)模擬 100 組車流量，組成新的改編能力和線路通過能力約束，將上述 2 種模型的最優(yōu)解結(jié)果分別代入檢測方案的穩(wěn)定性 (約束條件成立率即代表該方案的穩(wěn)定性)，得到未考慮車流量波動的最優(yōu)方案穩(wěn)定性為 86%，考慮車流量波動的最優(yōu)方案穩(wěn)定性為 99%，由此可知，不確定參數(shù)的最優(yōu)編組方案魯棒性更強(qiáng)，并且根據(jù)計(jì)算流程可以確定：隨機(jī)參數(shù)的模擬規(guī)模越大，最優(yōu)方案的穩(wěn)定性越強(qiáng)。

5　結(jié)束語

以鐵路網(wǎng)列車編組計(jì)劃與車流徑路為研究對象，將編組計(jì)劃參數(shù)的波動性考慮到編組計(jì)劃優(yōu)化問題中，結(jié)合模糊機(jī)會約束規(guī)劃相關(guān)理論，建立列車編組計(jì)劃綜合優(yōu)化模型，針對模型特點(diǎn)設(shè)計(jì)基于隨機(jī)模擬的改進(jìn)分枝定界法，對列車編組計(jì)劃的制訂具有參考意義[11]。制訂列車編組計(jì)劃的主要參數(shù)值均為動態(tài)變化值，但目前組合計(jì)算均采用靜態(tài)參數(shù)，傳統(tǒng)的編組計(jì)劃優(yōu)化計(jì)算在實(shí)際應(yīng)用中存在較大偏差。因此，采用動態(tài)參數(shù)構(gòu)建優(yōu)化模型為研究編組計(jì)劃優(yōu)化問題的重要方向。

[1] 林伯梁，朱松年. 優(yōu)化編組計(jì)劃的非線性 0-1 規(guī)劃模型及模擬退火算法[J]. 鐵道學(xué)報(bào)，1999，21(2)：61-66. LIN Bo-liang，ZHU Song-nian. Nonlinear 0-1 Planning Model and Simulated Annealing Algorithm for Optimizating Train Formation Plan[J]. Journal of the China Railway Society，1999，21 (2)：61-66.

[2] 波羅沃依 H.E. 貨物運(yùn)輸直達(dá)化[M]. 北京：中國鐵道出版社，1981.

[3] 鄭時(shí)德. 制定技術(shù)站列車編組計(jì)劃的 0-1 規(guī)劃法[J]. 鐵道學(xué)報(bào)，1985，7(3)：56-64. ZHENG Shi-de. 0-1 Planning Mothed of Making Train Formation Plan for Technical Station[J]. Journal of the China Railway Society，1985，7(3)：56-64.

[4] 何邦模，劉春煌，張理丹. 選擇單組技術(shù)直達(dá)列車編組計(jì)劃的分析計(jì)算法[J]. 鐵道學(xué)報(bào)，1990，12(3)：28-38. HE Bang-mo，LIU Chun-huang，ZHANG Li-dan. The Analysising and Calculating Method for Choicing Formation Plan of Single Group Technical Directing Train[J]. Journal of the China Railway Society，1990，12(3)：28-38.

[5] 曹家明，朱松年. 優(yōu)化列車編組計(jì)劃的 0-1 規(guī)劃法[J]. 鐵道學(xué)報(bào)，1992，14(4)：49-57. CAO Jia-ming，ZHU Song-nian. 0-1 Planning Method for Optimizating Train Formation Plan[J]. Journal of the China Railway Society，1992，14(4)：49-57.

[6] 曹家明，朱松年. 鐵路網(wǎng)上技術(shù)直達(dá)列車編組計(jì)劃優(yōu)化的二次0-1規(guī)劃法[J]. 鐵道學(xué)報(bào)，1993，15(2)：62-70. CAO Jia-ming，ZHU Song-nian. Secondary 0-1 Planning Method for Optimizating Formation Plan of Technical Directing Train in Railway Network[J]. Journal of the China Railway Society，1993，15(2)：62-70.

[7] 史 峰，李致中，孫 焰，等. 列車編組計(jì)劃網(wǎng)絡(luò)優(yōu)化方法[J]. 鐵道學(xué)報(bào)，1994，16(2)：74-79. SHI Feng，LI Zhi-zhong，SUN Yan，et al. The Network Optimizating Method of Train Formation Plan[J]. Journal of the China Railway Society，1994，16(2)：74-79.

[8] 林柏梁，朱松年. 優(yōu)化編組計(jì)劃的非線性 0-1 規(guī)劃模型及模擬退火算法[J]. 鐵道學(xué)報(bào)，1994，16(2)：61-66. LIN Bo-liang，ZHU Song-nian. Nonlinear 0-1 Planning Model and Simulated Annealing Algorithm for Optimizating Train Formation Plan[J]. Journal of the China Railway Society，1994，16(2)：61-66.

[9] 查偉雄，黃孝章，秦作睿. 直線方向列車編組計(jì)劃有利去向模型及其多項(xiàng)式算法[J]. 北方交通大學(xué)學(xué)報(bào)，1996，20(6)：641-644. ZHA Wei-xiong，HUANG Xiao-zhang，QIN Zuo-rui. The Model and Polynomial Algorithm of Train Formation Plan Benefit Direction[J]. Journal of Beijing Jiaotong University，1996，20(6)：641-644.

[10] 王慈光. 貨車集結(jié)參數(shù)的研究[J]. 鐵道運(yùn)輸與經(jīng)濟(jì)，2006，28(7)：83-85. WANG Ci-guang. Study on the Accumulation Parameter of Freight Cars[J]. Railway Transportation and Economy，2006，28(7)：83-85.

[11] 李宵寅. 基于不確定參數(shù)的列車編組計(jì)劃與車流徑路綜合優(yōu)化研究[D]. 成都：西南交通大學(xué)，2011. LI Xiao-yin. Research on the Comprehensive Optimization of Train Formation Plan and Traffic Flow Path based on Uncertain Parameters[D]. Chengdu：Southwest Jiaotong University，2011.

責(zé)任編輯：吳文娟

Study on Optimization Model of Train Formation Plan based on Uncertain Parameter

Based on expounding problem existing in optimization of train formation plan and train flow route, targeting with problems in parameter vibration of train formation plan, this paper analyzes the vibration status of relative parameters, such as train flow volume with through destination, formation destination number of technical station, number of resorting train in technical station and number of passing trains in section, and establishes the comprehensive optimization model of train formation plan and train flow route based on uncertain parameter, then the model is taken algorithm design from the aspects such as restricting processing opportunities, determining initial feasible solution and resolving object function. In the end, through programming and simulating the calculation example, the optimized formation plan based on uncertain parameter is achieved the result of having stronger robustness, which provides reference for establishing train formation plan.

Train Formation Plan; Train Flow Route; Uncertain Parameter; Stochastic Simulation

1003-1421(2015)11-0026-06+1

A

U292.3

10.16668/j.cnki.issn.1003-1421.2015.11.06

2015-02-06

2015-10-22

鐵道部重點(diǎn)課題 (2010X007-C)