編組站車流接續(xù)優(yōu)化模型及算法

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

（北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京 100044）

編組站車流接續(xù)優(yōu)化模型及算法

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

（北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京 100044）

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

編組站；調(diào)度計劃；車流接續(xù)優(yōu)化；自適應(yīng)免疫克隆算法；Lingo

1 引言

編組站作為運(yùn)輸網(wǎng)絡(luò)中的重要結(jié)點(diǎn)，擔(dān)負(fù)著列車的到、解、集、編、發(fā)等任務(wù)。貨運(yùn)過程中的大部分時間是消耗在編組站內(nèi)，這當(dāng)中很大一部分時間是由于設(shè)備不足或是技術(shù)作業(yè)組織不夠合理而導(dǎo)致的等待時間。而有效的、合理的編組站調(diào)度優(yōu)化方式能夠使列車在技術(shù)作業(yè)過程中以最少的時間，完成最多的貨車周轉(zhuǎn)，使得編組站在有限的作業(yè)設(shè)備基礎(chǔ)上達(dá)到運(yùn)輸效率最大化。

車流接續(xù)優(yōu)化作為編組站調(diào)度優(yōu)化中的一個主要構(gòu)成部分，是編組站調(diào)度計劃優(yōu)劣的重要評估標(biāo)準(zhǔn)。車流接續(xù)優(yōu)化效果的好壞，直接影響著到達(dá)車組給出發(fā)列車提供車流來源合理性，從而影響到車組在站停留時間、出發(fā)列車編組內(nèi)容以及出發(fā)列車是否能準(zhǔn)時出發(fā)，對車站和整個路網(wǎng)的車流周轉(zhuǎn)時間有著決定性的作用。提升車流接續(xù)優(yōu)化效果，對提高編組站和整個路網(wǎng)的效率都有很大的幫助。

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

當(dāng)前對于車流接續(xù)優(yōu)化的研究，出發(fā)列車屬性一般只考慮出發(fā)列車車輛數(shù)滿軸。本文結(jié)合實(shí)際生產(chǎn)需要，同時考慮了列車的換重、換長和滿軸數(shù)三個約束并建立數(shù)學(xué)模型，分別利用一般數(shù)學(xué)軟件Lingo11.0和自適應(yīng)免疫克隆算法對模型進(jìn)行了求解。

2 數(shù)學(xué)模型

2.1 符號定義

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

2.2 模型構(gòu)建

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

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

3 模型求解

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

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

3.1 ACSA設(shè)計說明

（1）抗體（解）的表示：以整數(shù)編碼組成抗體，抗體長度為到達(dá)列車車組個數(shù)K?？贵w的編碼為每個到達(dá)車組滿足時間接續(xù)和空間接續(xù)條件下的出發(fā)列車編號。

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

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

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

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

（6）算法運(yùn)行的終止條件為當(dāng)最優(yōu)值連續(xù)迭代5次不再變化或者迭代次數(shù)達(dá)到迭代最大步驟M時，即代表了算法已經(jīng)收斂到最優(yōu)解，可以終止運(yùn)行，輸出最優(yōu)值。

3.2 利用自適應(yīng)免疫克隆算法求解優(yōu)化模型實(shí)現(xiàn)步驟

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

Step.2：確定解編順序。

Step.3：基于到達(dá)列車的解體順序，考慮單調(diào)機(jī)資源約束，求解每個到達(dá)列車的解體時刻。

Step.4：基于出發(fā)列車的編組順序，考慮單調(diào)機(jī)資源約束，求解每個出發(fā)列車的編組時刻。需要說明的是，當(dāng)某個出發(fā)列車編組時刻要晚于出發(fā)列車的最晚編組時刻，則說明該列車無法在該階段作業(yè)時間內(nèi)準(zhǔn)時編組出發(fā)，本文對于此類列車的車流接續(xù)策略為優(yōu)先為其它出發(fā)列車車流接續(xù)。

Step.5：各個到達(dá)車組的解體時刻以及各個出發(fā)列車的編組時刻確定后，結(jié)合編組去向，確定每個到達(dá)車組可接續(xù)的出發(fā)列車序號集合D。

Step.6：根據(jù)Step.4的結(jié)果，初始化群體P。以整數(shù)編碼組成抗體，抗體的長度為到達(dá)列車車組個數(shù)K?？贵w的編碼為集合D中隨機(jī)獲取的一位。

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

Step.8:克隆。對抗體群P中的抗體進(jìn)行克隆擴(kuò)增操作，得到擴(kuò)增后的抗體群C，每個抗體克隆數(shù)按照算法設(shè)計說明的第（3）點(diǎn)自適應(yīng)確定。

Step.9：高頻變異。對抗體群C中的抗體進(jìn)行高頻變異，得到C*。變異概率按照算法設(shè)計說明的第（4）點(diǎn)自適應(yīng)確定。

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

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

Step.12：如果終止條件滿足，則程序結(jié)束，輸出最優(yōu)解。

4 算例分析

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

4.1 Lingo11.0求解車流接續(xù)優(yōu)化模型

本文在出發(fā)列車同時考慮換長、換重和滿軸數(shù)約束的基礎(chǔ)上，以車組在站停留最短為目標(biāo)函數(shù)，通過Lingo11.0進(jìn)行求解。求解結(jié)果見表3。

4.2 自適應(yīng)免疫克隆算法求解車流接續(xù)優(yōu)化模型

通過實(shí)現(xiàn)文中提出的自適應(yīng)克隆選擇算法求解，在抗體規(guī)模和變異概率φ、選擇常數(shù)θ、最大克隆數(shù)和最小克隆數(shù)取不同數(shù)值的條件下，對算法進(jìn)行了多次測試，結(jié)果表明，當(dāng)抗體規(guī)模在20-30范圍內(nèi)變化、變異概率φ在0.5-0.8范圍內(nèi)變化、最大克隆數(shù)在15-10范圍內(nèi)變化、最小克隆數(shù)在5-3范圍內(nèi)變化時，算法均可收斂至相同的最優(yōu)解，說明對參數(shù)的依賴性不強(qiáng)，有較好的穩(wěn)定性。算例實(shí)現(xiàn)的參數(shù)設(shè)置如下：抗體規(guī)模為20，變異概率常數(shù)φ取值0.6，選擇常數(shù)θ取值為5。最大克隆數(shù)為10，最小克隆數(shù)為3，迭代代數(shù)為20。算法迭代過程如圖1所示，迭代總次數(shù)為20次，當(dāng)?shù)?4次后，群體平均適應(yīng)度就收斂到1。求解結(jié)果見表4。

4.3 算例結(jié)果分析

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

在本算例中可以發(fā)現(xiàn)，Lingo11.0求解的結(jié)果是全局最優(yōu)解，要好于自適應(yīng)免疫克隆算法求解的結(jié)果：在正點(diǎn)出發(fā)列車數(shù)相等的情況下，自適應(yīng)免疫克隆算法求解的車流接續(xù)優(yōu)化結(jié)果車組停留時間較多。但是當(dāng)車組數(shù)增加后，Lingo 11.0求解所需的時間呈指數(shù)增長，而免疫克隆算法迭代的時間增加是可控的。

5 結(jié)論

本文建立了在解編順序給定下的車流接續(xù)優(yōu)化模型，并用一般的數(shù)學(xué)軟件和自適應(yīng)免疫克隆算法進(jìn)行了求解，結(jié)合算例，證明了模型和算法的合理性。

列車屬性方面同時考慮了換重、換長和滿軸數(shù)三個約束，通過算例證明，相比于列車屬性只考慮滿軸正點(diǎn)出發(fā)，該設(shè)定不但更加結(jié)合實(shí)際生產(chǎn)，而且使得車流接續(xù)優(yōu)化具有了一定的靈活性。

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

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

[2]王明慧，趙強(qiáng).編組站智能調(diào)度系統(tǒng)階段計劃優(yōu)化模型及算法研究[J].鐵道學(xué)報,2005，27（6）：1-9.

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

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

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

[6]王世東，鄭力，張智海，劉書成.編組站階段計劃自動編制的數(shù)學(xué)模型及算法 [J].中國鐵道科學(xué)，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

國家自然科學(xué)基金項(xiàng)目（60776825）；北京交通大學(xué)優(yōu)秀博士生創(chuàng)新基金（141076522）；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金資助（2009YJS042）

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