基于免疫優(yōu)化算法的戰(zhàn)略裝車點(diǎn)選址研究

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

1 研究背景

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

圖1 重載運(yùn)輸通道拓?fù)浣Y(jié)構(gòu)圖

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

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

2.1 條件假設(shè)

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

2.2 模型建立

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

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

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

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

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

3.1 算法思想

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

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

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

3.3 抗體多樣性評價(jià)

3.3.1 抗體與抗原間親和力

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

3.3.2 抗體與抗體間的親和力

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

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

3.3.3 抗體濃度

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

3.3.4 期望繁殖概率

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

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

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

3.4 免疫操作

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

（2）交叉算子。采用單點(diǎn)交叉法進(jìn)行交叉操作。

（3）變異算子。采用隨機(jī)變異位法進(jìn)行變異操作。

3.5 算法步驟

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

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

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

步驟 3：對上述種群中的各個(gè)抗體進(jìn)行評價(jià)。通過抗體的多樣性評價(jià)，確定個(gè)體的期望繁殖概率 P。

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

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

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

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

4 算例驗(yàn)算

4.1 背景條件

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

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

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

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

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

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

4.2 參數(shù)確定

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

4.3 結(jié)果分析

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

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

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

5 結(jié)束語

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

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

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

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

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

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

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

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