編組站車流接續優化模型及算法

甘志雄，何世偉，申永生，黎浩東，程金星

（北京交通大學 交通運輸學院，北京 100044）

編組站車流接續優化模型及算法

甘志雄，何世偉，申永生，黎浩東，程金星

（北京交通大學 交通運輸學院，北京 100044）

在解編順序給定的條件下，建立車流接續優化模型。在模型構建中，列車屬性方面同時考慮了換重、換長和滿軸三個約束，通過算例證明，該設定不但更加符合實際，而且使得車流接續優化具有了一定的靈活性。在算例分析部分，分別利用一般數學軟件Lingo11.0以及VC++編寫的自適應免疫克隆算法對模型進行求解，證明了模型和算法的有效性，為編組站階段計劃車流接續優化智能化提供了較好的解決途徑。

編組站；調度計劃；車流接續優化；自適應免疫克隆算法；Lingo

1 引言

編組站作為運輸網絡中的重要結點，擔負著列車的到、解、集、編、發等任務。貨運過程中的大部分時間是消耗在編組站內，這當中很大一部分時間是由于設備不足或是技術作業組織不夠合理而導致的等待時間。而有效的、合理的編組站調度優化方式能夠使列車在技術作業過程中以最少的時間，完成最多的貨車周轉，使得編組站在有限的作業設備基礎上達到運輸效率最大化。

車流接續優化作為編組站調度優化中的一個主要構成部分，是編組站調度計劃優劣的重要評估標準。車流接續優化效果的好壞，直接影響著到達車組給出發列車提供車流來源合理性，從而影響到車組在站停留時間、出發列車編組內容以及出發列車是否能準時出發，對車站和整個路網的車流周轉時間有著決定性的作用。提升車流接續優化效果，對提高編組站和整個路網的效率都有很大的幫助。

許多學者對問題進行了研究。文獻[1]利用表上作業法對車流接續優化進行求解，效果比較理想，但是在求解大規模問題時，求解的時間會大幅度增長。文獻[2]提出以列車配流為主線，通過構造局部區域優化問題實現解體、編組方案優化的啟發式算法，但其算例結果有待商榷。文獻[3]對編組站車流接續進行了動態配流研究，并給出了模型和相應的算法，但是列車屬性方面只考慮了滿軸數。文獻[4]對基于解編順序的車流接續優化模型及算法進行研究，但是列車屬性方面只考慮了車輛滿軸數。文獻[5]以調機活動為核心，結合文獻[1]提出的靜態車流推算方法，建立以出發列車盡可能滿軸為目標的數學模型，設計了求解該模型的混合遺傳算法，但文中給出的算例結果不太理想，同時算法的時間效率不高。文獻[6]根據編組站實際作業流程，將階段計劃自動編制問題分解為配流計劃、解體／編組計劃、到發線運用計劃3個自動編制子問題，分別建立數學模型并求解。

當前對于車流接續優化的研究，出發列車屬性一般只考慮出發列車車輛數滿軸。本文結合實際生產需要，同時考慮了列車的換重、換長和滿軸數三個約束并建立數學模型，分別利用一般數學軟件Lingo11.0和自適應免疫克隆算法對模型進行了求解。

2 數學模型

2.1 符號定義

設編組站本階段到達列車m列，其中計劃開始階段的站存車和貨場而來的車均視為到達車數，出發列車n列，F為編組站車組方向編號的數量，f為編組站車組方向編號，f=1，…, F，Tk為車組k所在到達列車到達時刻，Ak為車組k所含車輛數，DTj為出發列車j的出發時刻，Lk為車組k的換長，Wk為車組k的換重為出發列車Dj允許的最小換長，為出發列車Dj允許的最大換長，為出發列車Dj允許的最小換重，為列車Dj允許的最大換重為出發列車Dj允許的最小車組數，為出發列車允許的最大車組數，N（j）表示在滿足車流接續時間約束下，能夠為出發列車Dj提供車流的到達車組集合。M為大的正整數，為了保證約束的可行性，Xjk表示車組k為Dj提供車流的車輛數，為0-1變量1表示出發列車滿足換重要求，為0-1變量=1表示出發列車滿足換長要求為0-1變量，=1表示出發列車滿足車組數要求。

2.2 模型構建

在列車屬性方面同時考慮出發列車換重、換長和滿軸數的基礎上，以車組在站停留時間最短為目標，建立目標函數：

約束（2）表示到達車組k或是作為出發列車的車流來源，或是最終成為下一階段計劃開始時的站存車。約束（3）表示出發列車換重小于最大規定換重量，約束（4）表示若出發列車換重大于最小的換重要求，則=1。約束（5）表示出發列車換長必須要小于最大規定換長，約束（6）表示若出發列車換長大于最小的換長要求，則=1。約束（7）表示出發列車車組數量必須要小于最大規定車組數，約束（8）表示若車組數之和大于最小的規定車組數要求，則=1。約束（9）表示出發列車在換重、換長和滿軸這三個約束中只需滿足其中一個。

3 模型求解

在求解車流接續優化問題上，表上作業法和一般的數學軟件都能夠求解。一般的數學軟件在求解小規模線性問題時往往能比較快的獲取到全局最優解，但是在處理非線性大規模問題時，求解效率上往往無法使人滿意，隨著規模的增大，求解時間呈指數增長。而智能算法在求解非線性大規模問題相比于一般的數學軟件往往有比較大的優勢。

在諸多智能算法中，免疫算法具有克隆、超變異、抗體與抗原特異性結合、未被激發的細胞消亡及記憶細胞的產生等特色,因此在保證收斂速度的同時又能維持抗體的多樣性，為目標優化提供了一種有效的新途徑，近幾年引起了研究者更多的關注。考慮到免疫算法的諸多優點，現采用其作為VC6.0中優化解編順序的智能算法。文獻[7]提出的算法是近年來提出的比較典型的一種克隆選擇算法。在免疫諸多算法的基礎上，文獻[4]進一步提出了自適應克隆選擇算法。本文所實現的免疫算法為自適應克隆選擇算法（Adaptive Colonel Select Algorism，簡稱ACSA），借鑒了文獻[4]提出的自適應克隆選擇理論。下面給出該算法設計和實現的詳細說明。

3.1 ACSA設計說明

（1）抗體（解）的表示：以整數編碼組成抗體，抗體長度為到達列車車組個數K。抗體的編碼為每個到達車組滿足時間接續和空間接續條件下的出發列車編號。

（2）適應度計算：通過解析每個抗體個體中能滿足出發要求的出發列車數來確定適應度。需特別說明的是，由于智能算法存在著初始解的隨機生成以及變異的隨機性，可能導致無效抗體的產生，比如抗體解析結果無法滿足時間約束，算法對無效抗體的適應度賦予值-1，從而使該抗體適應度值很低，在克隆過程中由于其親和度很低導致該抗體克隆個數很少，在克隆群體中的比例很小，選擇其進入新群體的可能性很低，最終這些抗體或消亡，或通過變異以新的較優解的形式存在于新群體中。

（3）克隆個數的確定：設定克隆個數最大值cnMax和克隆個數最小值cnMin。每個抗體具體的克隆數cn與其親和度成正比，本文設計的關系為cn=cnMax（1-i/N）,cn＞=cnMin，其中N為抗體群體規模，將要克隆的抗體按親和度大小排序，i是其序號。從上述關系式中可以看出，親和度越大的，其克隆數量越多，這是自適應的一個特點所在。

（4）變異概率的確定：進化初期，為了保證抗體群的全局搜索，需要一個較大的變異概率，隨著進化代數的增加，抗體群適應度相應也會提高，此時變異概率需要變小以便算法收斂。設置變異概率φ為迭代步驟m的函數，其關系式為φ=ρ·（M-m）/M，其中ρ為變異概率常數，M為迭代步驟的最大值。

（5）選擇個數的確定：克隆選擇算法里要求選擇個數d反比于群體適應度，設定d為迭代步驟m的函數，其關系式為d=θ·（M-m）/M，其中θ為選擇常數，M為迭代步驟的最大值。從該關系式中可以看出，隨著迭代步驟的增加，抗體群適應度越高，選擇的個數會越來越少，從而抗體群會越來越穩定收斂于一點，這是自適應的第二個特點所在。

（6）算法運行的終止條件為當最優值連續迭代5次不再變化或者迭代次數達到迭代最大步驟M時，即代表了算法已經收斂到最優解，可以終止運行，輸出最優值。

3.2 利用自適應免疫克隆算法求解優化模型實現步驟

Step.1：讀取到達列車和出發列車的信息：包括到達列車的到達時刻，編組方向及車組數量；出發列車出發時刻，編組去向，以及各個車組的換長、換重和車組數要求。

Step.2：確定解編順序。

Step.3：基于到達列車的解體順序，考慮單調機資源約束，求解每個到達列車的解體時刻。

Step.4：基于出發列車的編組順序，考慮單調機資源約束，求解每個出發列車的編組時刻。需要說明的是，當某個出發列車編組時刻要晚于出發列車的最晚編組時刻，則說明該列車無法在該階段作業時間內準時編組出發，本文對于此類列車的車流接續策略為優先為其它出發列車車流接續。

Step.5：各個到達車組的解體時刻以及各個出發列車的編組時刻確定后，結合編組去向，確定每個到達車組可接續的出發列車序號集合D。

Step.6：根據Step.4的結果，初始化群體P。以整數編碼組成抗體，抗體的長度為到達列車車組個數K。抗體的編碼為集合D中隨機獲取的一位。

Step.7：調整群體P中每個抗體。調整策略為：對于初始群體中的某個抗體，首先計算出各個出發列車的車組情況，如果該出發列車滿足上文所提到的換重、換長或滿軸數要求，則不進行調整；如果某個出發列車車流接續情況超過了換長的上限或是換重的上限或是車組數量的上限，則把為該出發列車提供車組的到達車組數量進行減除調整，直到該出發列車滿足換重換長和滿足車組數上限要求，把減除的整個車組或車組中的某些車放入站存車集合中。在減除調整完成后，進行某些出發列車增軸調整：把不滿足換重、換長或滿軸數下限的出發列車進行增加調整，從站存車集合中獲取滿足該出發列車接續的車組進行補充，直到滿足要求。如果沒有滿足列車接續的車組，則不進行增加。通過上面的調整可以獲取到每個抗體車流接續的初始化編碼，每個編碼出發列車正點出發的列車數量作為適應度函數大小的評定標準。

Step.8:克隆。對抗體群P中的抗體進行克隆擴增操作，得到擴增后的抗體群C，每個抗體克隆數按照算法設計說明的第（3）點自適應確定。

Step.9：高頻變異。對抗體群C中的抗體進行高頻變異，得到C*。變異概率按照算法設計說明的第（4）點自適應確定。

Step.10：選擇。從C*中選擇d個適應度高的抗體替換P中d個低親和度抗體。d按照算法設計說明中的第（5）點自適應確定。

Step.11：判斷終止條件是否滿足，如果未滿足則轉至Step.7。

Step.12：如果終止條件滿足，則程序結束，輸出最優解。

4 算例分析

算例中到達列車和出發列車信息見表1和表2，該原始數據來自文獻[2]。解體次序代表著該到達列車在該階段的解體次序，解體開始時刻代表著該列車解體作業的起始時間。編組順序代表著該列車在該階段的編組次序，最晚編組時刻代表著該列車的由于計劃出發時刻和技術作業所需要的時間，必須在此時刻開始編組，否則將會晚點。本文中令出發列車的滿軸數為35，換長區間為[37,44]，換重區間為[36,43]。即出發列車滿軸數為35，最小換長要求為37，最大換長為44，最小換重為36，最大換重為43。為了證明前面提到的一般數學軟件和自適應免疫算法在求解這類問題上的不同表現，本算例分別使用Lingo11.0和自適應免疫克隆算法進行求解。

4.1 Lingo11.0求解車流接續優化模型

本文在出發列車同時考慮換長、換重和滿軸數約束的基礎上，以車組在站停留最短為目標函數，通過Lingo11.0進行求解。求解結果見表3。

4.2 自適應免疫克隆算法求解車流接續優化模型

通過實現文中提出的自適應克隆選擇算法求解，在抗體規模和變異概率φ、選擇常數θ、最大克隆數和最小克隆數取不同數值的條件下，對算法進行了多次測試，結果表明，當抗體規模在20-30范圍內變化、變異概率φ在0.5-0.8范圍內變化、最大克隆數在15-10范圍內變化、最小克隆數在5-3范圍內變化時，算法均可收斂至相同的最優解，說明對參數的依賴性不強，有較好的穩定性。算例實現的參數設置如下：抗體規模為20，變異概率常數φ取值0.6，選擇常數θ取值為5。最大克隆數為10，最小克隆數為3，迭代代數為20。算法迭代過程如圖1所示，迭代總次數為20次，當迭代到14次后，群體平均適應度就收斂到1。求解結果見表4。

4.3 算例結果分析

通過對車流接續優化模型的實例分析可知，Lingo11.0和自適應免疫克隆算法都能很好的求解車流接續優化，而且效果都不錯。在求解小規模線性規劃問題中，Lingo11.0相比于自適應免疫克隆算法無論在求解的時間或是求解效果上都要好， Lingo11.0有以下幾個優勢：（1）其編程建立于建模語言基礎上，語句最簡單易懂；（2）在小規模線性問題上求解時間短，Lingo11.0通過13秒就可以獲得全局最優解，自適應免疫克隆算法迭代過程用了16秒左右；（3）求解效果好，易收斂于全局最優解。

在本算例中可以發現，Lingo11.0求解的結果是全局最優解，要好于自適應免疫克隆算法求解的結果：在正點出發列車數相等的情況下，自適應免疫克隆算法求解的車流接續優化結果車組停留時間較多。但是當車組數增加后，Lingo 11.0求解所需的時間呈指數增長，而免疫克隆算法迭代的時間增加是可控的。

5 結論

本文建立了在解編順序給定下的車流接續優化模型，并用一般的數學軟件和自適應免疫克隆算法進行了求解，結合算例，證明了模型和算法的合理性。

列車屬性方面同時考慮了換重、換長和滿軸數三個約束，通過算例證明，相比于列車屬性只考慮滿軸正點出發，該設定不但更加結合實際生產，而且使得車流接續優化具有了一定的靈活性。

自適應免疫克隆算法在求解車流接續優化大規模問題時比Lingo求解的效率要高，但是往往獲得的不是全局最優解。而Lingo獲得的是全局最優解，在處理小規模線性問題時，效果比智能算法要好。

[1]王慈光.用表上作業法求解編組站配流問題的研究[J].鐵道學報，2002，24（4）：1-5.

[2]王明慧，趙強.編組站智能調度系統階段計劃優化模型及算法研究[J].鐵道學報,2005，27（6）：1-9.

[3]王慈光.編組站動態配流模型與算法研究[J].鐵道學報，2004，26（1）：1-6.

[4]申永生，何世偉，王保華，穆美如.免疫算法求解編組站階段計劃配流問題研究[J].鐵道學報，2009，44（4）：1-6.

[5]王正彬，杜文，吳柏青，羊艷.基于解編順序的階段計劃車流推算模型及算法 [J].西南交通大學學報，2008，43（1）：91-95.

[6]王世東，鄭力，張智海，劉書成.編組站階段計劃自動編制的數學模型及算法 [J].中國鐵道科學，2008,29（2）: 120-125.

[7]De Castro LN,Von Zuben F J.Learning and mization Using the Clonal Selection Principle[J].IEEE Transactions on Evolutionary Computation，2002，6（3）：239-251．

Model and Algorithm for Marshalling Station Wagon-flow Optimization

GAN Zhi-xiong,HE Shi-wei,SHEN Yong-sheng,LI Hao-dong,CHENG Jin-xing
（School of Traffic&Transportation,Beijing Jiaotong University,Beijing100044,China）

The paper formulates a mathematical model for the wagon-flow optimization at marshalling stations with given sequences of train making and breaking.It develops an adaptive immune clone algorithm via VC++and uses Lingo11.0 to solve the model.In numerical examples,train properties such as weight,length and axis of cars to be shunted are taken as constraints,which renders the result obtained closer to the fact and more flexible.

marshalling station;scheduling plan;wagon-flow optimization;adaptive immueclone algorithm;Lingo

U292

A

1005-152X（2011）02-0048-04

10.3969/j.issn.1005-152X.2011.02.016

2010-12-13

國家自然科學基金項目（60776825）；北京交通大學優秀博士生創新基金（141076522）；中央高校基本科研業務費專項資金資助（2009YJS042）

甘志雄（1987-），男，江西鄱陽縣人，在讀碩士研究生，主要研究方向:運輸組織現代化。