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

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

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

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

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

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

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

1 引言

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

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

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

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

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

2.1 符號(hào)定義

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

2.2 模型構(gòu)建

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

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

3 模型求解

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

在諸多智能算法中，免疫算法具有克隆、超變異、抗體與抗原特異性結(jié)合、未被激發(fā)的細(xì)胞消亡及記憶細(xì)胞的產(chǎn)生等特色,因此在保證收斂速度的同時(shí)又能維持抗體的多樣性，為目標(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，簡(jiǎn)稱ACSA），借鑒了文獻(xiàn)[4]提出的自適應(yīng)克隆選擇理論。下面給出該算法設(shè)計(jì)和實(shí)現(xiàn)的詳細(xì)說明。

3.1 ACSA設(shè)計(jì)說明

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

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

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

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

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

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

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

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

Step.2：確定解編順序。

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

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

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

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

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

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

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

Step.10：選擇。從C*中選擇d個(gè)適應(yīng)度高的抗體替換P中d個(gè)低親和度抗體。d按照算法設(shè)計(jì)說明中的第（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á)列車在該階段的解體次序，解體開始時(shí)刻代表著該列車解體作業(yè)的起始時(shí)間。編組順序代表著該列車在該階段的編組次序，最晚編組時(shí)刻代表著該列車的由于計(jì)劃出發(fā)時(shí)刻和技術(shù)作業(yè)所需要的時(shí)間，必須在此時(shí)刻開始編組，否則將會(huì)晚點(diǎn)。本文中令出發(fā)列車的滿軸數(shù)為35，換長(zhǎng)區(qū)間為[37,44]，換重區(qū)間為[36,43]。即出發(fā)列車滿軸數(shù)為35，最小換長(zhǎng)要求為37，最大換長(zhǎng)為44，最小換重為36，最大換重為43。為了證明前面提到的一般數(shù)學(xué)軟件和自適應(yīng)免疫算法在求解這類問題上的不同表現(xiàn)，本算例分別使用Lingo11.0和自適應(yīng)免疫克隆算法進(jìn)行求解。

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

本文在出發(fā)列車同時(shí)考慮換長(zhǎng)、換重和滿軸數(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ù)值的條件下，對(duì)算法進(jìn)行了多次測(cè)試，結(jié)果表明，當(dāng)抗體規(guī)模在20-30范圍內(nèi)變化、變異概率φ在0.5-0.8范圍內(nèi)變化、最大克隆數(shù)在15-10范圍內(nèi)變化、最小克隆數(shù)在5-3范圍內(nèi)變化時(shí)，算法均可收斂至相同的最優(yōu)解，說明對(duì)參數(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é)果分析

通過對(duì)車流接續(xù)優(yōu)化模型的實(shí)例分析可知，Lingo11.0和自適應(yīng)免疫克隆算法都能很好的求解車流接續(xù)優(yōu)化，而且效果都不錯(cuò)。在求解小規(guī)模線性規(guī)劃問題中，Lingo11.0相比于自適應(yīng)免疫克隆算法無論在求解的時(shí)間或是求解效果上都要好， Lingo11.0有以下幾個(gè)優(yōu)勢(shì)：（1）其編程建立于建模語(yǔ)言基礎(chǔ)上，語(yǔ)句最簡(jiǎn)單易懂；（2）在小規(guī)模線性問題上求解時(shí)間短，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é)果車組停留時(shí)間較多。但是當(dāng)車組數(shù)增加后，Lingo 11.0求解所需的時(shí)間呈指數(shù)增長(zhǎng)，而免疫克隆算法迭代的時(shí)間增加是可控的。

5 結(jié)論

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

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

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

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

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

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

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

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

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

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

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