（西南交通大學(xué) 交通運輸與物流學(xué)院，四川 成都 610031）

1 研究背景

國家“十二五”綜合交通發(fā)展規(guī)劃戰(zhàn)略目標(biāo)明確提出：大宗貨物要實現(xiàn)重載化，加快既有區(qū)域干線擴能改造和新線建設(shè)，完善跨區(qū)域大能力運輸通道[1]。戰(zhàn)略裝車點作為重載運輸通道組成的一部分，是整個重載運輸網(wǎng)絡(luò)的關(guān)鍵節(jié)點，它聯(lián)系著貨物的供給點和需求點，是貨物運輸?shù)闹修D(zhuǎn)站，重載運輸通道拓撲結(jié)構(gòu)圖如圖1所示。對戰(zhàn)略裝車點的合理布局既可以提高線路的利用能力、節(jié)省鐵路支出、降低鐵路運營成本、增加經(jīng)濟效益，還可以充分完善我國的重載通道資源配置，優(yōu)化通道結(jié)構(gòu)。同時，隨著貨運作業(yè)集中化的推進，也有利于組織直達列車，加快貨物和車輛的周轉(zhuǎn)，對發(fā)展重載運輸、完善重載通道理論體系建設(shè)具有重要意義。

圖1 重載運輸通道拓撲結(jié)構(gòu)圖

目前對裝車點選址研究的大多停留在宏觀層面的指導(dǎo)和常規(guī)的選址方法研究上[2-3]，缺少對新型方法的探索和理論研究。由于戰(zhàn)略裝車點的選擇優(yōu)化問題是一個復(fù)雜多約束的NP問題，采用常規(guī)方法求解時收斂速度慢，有時得不到最優(yōu)解，而免疫優(yōu)化算法具有尋優(yōu)能力強、收斂性能好等優(yōu)點，因而擬構(gòu)造一種基于免疫優(yōu)化計算的戰(zhàn)略裝車點選址優(yōu)化方案。

2 重載戰(zhàn)略裝車點選址優(yōu)化問題的數(shù)學(xué)描述

2.1 條件假設(shè)

為方便構(gòu)建模型，假定以下條件：①戰(zhàn)略裝車點的貨運處理能力足夠大，在模型應(yīng)用期內(nèi)不會出現(xiàn)裝車點處理能力不夠的情況；②各貨源點和需求點的供需能力已知；③初始裝車點備選集已知，在備選集中尋優(yōu)。

2.2 模型建立

戰(zhàn)略裝車點選址關(guān)鍵是在供給點和需求點之間選擇最優(yōu)的裝車點，即從給定的戰(zhàn)略裝車點備選集中確定使整個路網(wǎng)運輸費用最低的戰(zhàn)略裝車點。

定義 0-1 決策變量 zk如下。

綜合考慮運輸成本、裝車點建設(shè)費用及裝車點貨物處理費用，建立模型如下。

模型中，式⑵為目標(biāo)函數(shù)，旨在使綜合運輸費用最??；式⑶和式⑷分別為貨物的供給約束和需求約束；式⑸為節(jié)點流平衡約束；式⑹為建設(shè)資金約束。其中，為i 貨源點到第 k 裝車點的單位運輸費用，元/t；為k 裝車點到 j 需求點的單位運輸費用，元/t；為第 k 裝車點的貨運處理費用，元/t；為第 k 裝車點的日均建設(shè)費用，元/d；xik為i 貨源點到第 k 裝車點的運輸量，t；ykj為k 裝車點到 j 需求點的運輸量，t。

3 基于免疫優(yōu)化算法的選址方案

3.1 算法思想

生物免疫系統(tǒng)是1個高度進化的生物系統(tǒng)，它旨在區(qū)分外部有害抗原和自身組織，從而保持有機體的穩(wěn)定。從計算角度分析，生物免疫系統(tǒng)是1個高度并行、分布、自適應(yīng)和自組織的系統(tǒng)，具有很強的學(xué)習(xí)、識別和記憶能力。免疫算法是1種受生物免疫系統(tǒng)啟發(fā)，在免疫學(xué)理論基礎(chǔ)上發(fā)展起來的新興智能計算方法。它利用免疫系統(tǒng)的產(chǎn)生和維持機制來保持群體的多樣性，克服了一般尋優(yōu)過程尤其是多峰函數(shù)尋優(yōu)過程中難處理的“早熟”問題[4]。

3.2 編碼方案和初始抗體的產(chǎn)生

在備選方案集里選擇合適的裝車點采用實數(shù)編碼方式比較直觀，每個選址方案可以形成一個長度為L的抗體 (L為戰(zhàn)略裝車點的建設(shè)數(shù)量)，每個抗體代表被選為戰(zhàn)略裝車點的一個序列。免疫優(yōu)化算法的計算需要一個初始抗體群，因此算法開始階段需隨機產(chǎn)生一個初始種群。由于免疫算法需要經(jīng)過一定代數(shù)的繁殖才能獲得最優(yōu)解，因而在每一代的繁殖過程中都可以根據(jù)問題的先驗知識和歷史數(shù)據(jù)得到一些較好的潛在最優(yōu)解，把這些解存入記憶庫，在下一代計算中取出和子代抗體組成初始抗體種群作為算法輸入?yún)?shù)進行尋優(yōu)計算，可以有效提高收斂速度。

3.3 抗體多樣性評價

3.3.1 抗體與抗原間親和力

把目標(biāo)函數(shù)解看作抗體，戰(zhàn)略裝車點的選址優(yōu)化問題看作抗原，那么抗體與抗原之間的親和力可以表示為抗體對抗原的識別程度，即衡量抗體質(zhì)量的一個重要指標(biāo)。針對裝車點的選址問題，設(shè)計抗體與抗原間親和力函數(shù)為

3.3.2 抗體與抗體間的親和力

抗體與抗體之間的親和力反映了抗體之間的相似程度。該處借鑒由 Forrest 等提出的R 位連續(xù)方法計算抗體與抗體間的親和力。R 位連續(xù)方法時確定一個判定閥值 R，如果2個抗體中有超過 R 位或連續(xù) R 位的編碼相同，則視2個抗體近似相同，否則可視為2個抗體不同，即在2個任意的選址方案中，如果存在 R個相同的裝車點，則認為2個方案一樣，此時2個方案的多樣性降低，不利于算法找到最優(yōu)解。針對戰(zhàn)略裝車點選址問題，考慮采用變形的R 位連續(xù)方法，即不考慮編碼排序，不考慮閥值 R，計算公式為

式中：Sv.s為抗體 v 與抗體 s 間的親和力；kv，s為抗體v與抗體s中相同的位數(shù)；L為抗體長度。

3.3.3 抗體濃度

抗體濃度指群體中相似抗體所占的比例，計算公式為

3.3.4 期望繁殖概率

在群體中，每個個體的期望繁殖概率 P 由抗體與抗原間親和力 Av和抗體濃度 Cv2個部分共同決定，計算公式為

式中：α為常數(shù)，也稱為抗體多樣性評價參數(shù)。

從式(11)可知，抗體的適應(yīng)度越高，被選中的期望繁殖概率越大；抗體的濃度越高，被選中的期望繁殖概率越小。通過在鼓勵適應(yīng)度高抗體的同時抑制濃度高的個體，可以保證種群的多樣性。免疫優(yōu)化算法在抑制高濃度抗體時，與抗原親和度最高的抗體也可能因其濃度高而受到抑制，從而導(dǎo)致已求得的最優(yōu)解丟失。因此，采取精英保留策略[6]在每次更新記憶庫時，先將與抗原親和度最高的幾個抗體存入記憶庫，再按照期望繁殖概率將剩余群體中優(yōu)秀個體存入記憶庫。

3.4 免疫操作

（1）選擇算子。采用輪盤賭方法[7]進行選擇操作，抗體被選擇的概率為公式⑾計算出的期望繁殖概率。

（2）交叉算子。采用單點交叉法進行交叉操作。

（3）變異算子。采用隨機變異位法進行變異操作。

3.5 算法步驟

根據(jù)上述分析，具體算法步驟如下。

步驟 1：分析具體問題及其解的特性，確定合適的有利于算法迭代的算子形式。

步驟 2：確定抗體種群規(guī)模 N 和記憶庫容量 M。在首次初始化抗體群時，由于記憶庫抗體為空，所以先隨機生成 N個抗體；在以后的子代中，皆由記憶庫中的M個抗體和 (N－M)個經(jīng)選擇、交叉、變異產(chǎn)生的抗體共同組成初始抗體群。

步驟 3：對上述種群中的各個抗體進行評價。通過抗體的多樣性評價，確定個體的期望繁殖概率 P。

步驟 4：形成父代群體。將初始抗體群按期望繁殖概率 P 進行降序排列，取前 M個存入記憶庫中，取前 N個抗體作為父代群體。

步驟 5：判斷是否滿足結(jié)束條件，若滿足則結(jié)束，所得的當(dāng)前最優(yōu)解即為問題最優(yōu)解；否則，進行步驟6操作。結(jié)束條件一般為算法迭代到最大代數(shù)、算法迭代時間停止或2次迭代的最優(yōu)解誤差在容許范圍內(nèi)。

步驟 6：新種群的產(chǎn)生。在新形成的父代群基礎(chǔ)上，對抗體進行選擇、交叉、變異操作得到新的抗體群，再從記憶庫中取出全部抗體，共同構(gòu)成新的種群。

步驟 7：轉(zhuǎn)到步驟 3。

4 算例驗算

4.1 背景條件

為驗證算法的有效性，構(gòu)造以下算例：設(shè)某區(qū)域重載路網(wǎng)有16個貨源點和20個需求點，現(xiàn)欲在10個備選戰(zhàn)略裝車點中選取4個擇優(yōu)建設(shè)，建設(shè)費用投資在14700 萬元以內(nèi)。各貨源點提供的貨物量和各需求點的貨物需求量分別如表1 和表2所示。

綜合考慮運距和貨物周轉(zhuǎn)量的影響，得到從貨源地到裝車點、從裝車點到需求地的單位運輸費用分別用矩陣 cos tO 和 cos tD 表示，單位元/t。

表1 貨源地所提供的貨物量 t

表2 需求地對貨物的需求量 t

假設(shè)裝車點建成后的使用壽命為20個考察期，每個備選裝車點的建設(shè)費用和單位貨物處理成本如表3所示。

表3 備選裝車點建設(shè)費用及貨物處理成本

4.2 參數(shù)確定

設(shè)抗體種群規(guī)模 M=4 0，其中記憶庫容量N =10；算子的交叉概率pcross=0.5、變異概率pmutation=0.4。算子的選擇概率由期望繁殖概率確定，抗體多樣性評價參數(shù) α?= 0.95，抗體長度 L = 4，最大迭代次數(shù) MAXGEN = 30。在初始種群生成前，根據(jù)模型約束，先隨機生成40組運量分配矩陣用于算法適應(yīng)性評價。

4.3 結(jié)果分析

把確定的參數(shù)作為已知條件輸入算法，經(jīng) matlab運算得到最優(yōu)解 bestchrom = [9 6 7 2]，最佳適應(yīng)度值 min F = 1 861.8 萬元，從貨源地到裝車點和從裝車點到需求地的最佳貨流分配分別用矩陣 c arg oO和 c arg oD所示，單位 t。

戰(zhàn)略裝車點選址優(yōu)化收斂曲線如圖2所示，經(jīng)過12次迭代后算法收斂到最優(yōu)并且趨于平衡，從而證明了算法收斂的快速性。通過分析圖中最優(yōu)適應(yīng)度曲線和平均適應(yīng)度曲線的走向可知，每一次迭代后曲線都呈下降趨勢，進而證明了該算法的可靠性。

圖2 戰(zhàn)略裝車點選址優(yōu)化收斂曲線

5 結(jié)束語

通過把戰(zhàn)略裝車點的選址問題抽象為1個3層網(wǎng)絡(luò)結(jié)構(gòu)，在建立目標(biāo)函數(shù)時綜合考慮上層決策者和下層客戶間的利益，以實現(xiàn)整個運輸系統(tǒng)成本最小化，最后在此基礎(chǔ)上運用免疫優(yōu)化算法進行求解。算法的創(chuàng)新之處在于使運量分配和裝車點選址在算法尋優(yōu)過程中緊密結(jié)合，使得運量分配和選址問題同時達到最優(yōu)，為戰(zhàn)略裝車點的建設(shè)提供一套科學(xué)可行的方法。

[1] 中華人民共和國國務(wù)院.“十二五”綜合交通運輸體系規(guī)劃[J].綜合運輸，2012(7)：4-17.

[2] 紀麗君，林伯梁，喬國會，等.戰(zhàn)略裝車點多點選址模型及算法[J].北京交通大學(xué)學(xué)報，2009，33（6）：31-35.

[3] 紀麗君，林伯梁.戰(zhàn)略裝車點選址模型研究[J].鐵道學(xué)報，2008，30(5)：8-11.

[4] 史 峰，王 輝，胡 斐，等.MATLAB 智能算法30個案例分析[M].北京：北京航空航天大學(xué)出版社.

[5] 朱思峰，劉 芳，柴爭義，等.基于免疫計算的IEEE 802.16j網(wǎng)絡(luò)基站及中繼站選址優(yōu)化[J].計算機研究與發(fā)展，2012，49(8)：1 649-1 654.

[6] 楊咚咚，焦李成，公茂果.求解偏好多目標(biāo)優(yōu)化的克隆選擇算法[J].軟件學(xué)報，2010，21(1)：14-33.

[7] 玄光男.遺傳算法與工程優(yōu)化[M].北京：清華大學(xué)出版社，2004.