基于改進(jìn)免疫優(yōu)化算法的冷鏈多式聯(lián)運(yùn)路徑優(yōu)化研究

段力偉，李震

（重慶交通大學(xué)交通運(yùn)輸學(xué)院，重慶 400064）

目前，隨著冷鏈運(yùn)輸?shù)难杆侔l(fā)展，冷鏈運(yùn)輸結(jié)構(gòu)單一的問題也愈發(fā)明顯。我國冷鏈運(yùn)輸90%以上由公路完成，而鐵路占比不足1%[1]，同時冷鏈運(yùn)輸路徑不合理加劇了途中損耗。因此，優(yōu)化冷鏈?zhǔn)袌龅倪\(yùn)輸結(jié)構(gòu)，發(fā)展多式聯(lián)運(yùn)，發(fā)揮不同運(yùn)輸方式的優(yōu)勢，確保冷鏈貨物的運(yùn)輸質(zhì)量，能夠更好地滿足我國不斷增長的冷鏈運(yùn)輸需求。

多式聯(lián)運(yùn)路徑優(yōu)化問題是一個NP-hard 問題，已有很多學(xué)者對該問題的求解做出了相關(guān)研究，如李飄等提出了一種綜合k-最短路徑算法和逼近理想解排序法的混合算法，以求解時變條件下的多目標(biāo)路徑優(yōu)化模型[2]；劉雪萍采用了模擬退火算法對多應(yīng)急救援點(diǎn)、多受災(zāi)點(diǎn)的救援物資的運(yùn)送路徑選擇問題進(jìn)行了研究[3]；劉松在蟻群算法中設(shè)計Ant-Cycle 模型來更新信息素，以最短時間為目標(biāo)解決應(yīng)急救援物資的路徑優(yōu)化問題[4]；朱欣媛設(shè)計了基于遺傳算法和粒子群算法的混合算法，探討了碳排放約束下的時間模糊路徑選擇問題[5]；Diabat 提出了一種基于禁忌搜索的周期性分配-庫存問題（PDIP）的啟發(fā)式算法，該算法性能優(yōu)于95%以上基于列生成并考慮數(shù)據(jù)集的啟發(fā)式算法[6]。

通過相關(guān)文獻(xiàn)可以看出，目前啟發(fā)式算法被廣泛應(yīng)用于求解多式聯(lián)運(yùn)路徑優(yōu)化問題，然而傳統(tǒng)的啟發(fā)式算法存在陷入局部最優(yōu)解和優(yōu)化效率低的問題。該文綜合考慮冷鏈多式聯(lián)運(yùn)的特點(diǎn)和影響因素，采用Weibull 三參數(shù)分布函數(shù)來描述冷鏈貨物運(yùn)輸途中的變質(zhì)損耗變化情況，并提出了混合粒子群算法雙尋優(yōu)的免疫優(yōu)化算法，對模型進(jìn)行求解，通過對算例的分析計算表明，優(yōu)化后的算法能夠有效解決此類問題，并具有更快的收斂速度。

1 冷鏈多式聯(lián)運(yùn)路徑優(yōu)化模型構(gòu)建

1.1 問題描述

以集裝箱運(yùn)送冷鏈貨物，在中途節(jié)點(diǎn)可進(jìn)行運(yùn)輸方式的中轉(zhuǎn)，相鄰節(jié)點(diǎn)之間有多種運(yùn)輸方式，中轉(zhuǎn)會產(chǎn)生相應(yīng)的時間、費(fèi)用。同時，由于貨物在途中運(yùn)輸時間不同，貨物產(chǎn)生的損耗和制冷成本也不同。模型以總成本最小為目標(biāo)，確定OD 間最佳的運(yùn)輸路徑，并滿足時限要求。

1.2 條件假設(shè)

1）貨物在運(yùn)輸中始終處在冷藏集裝箱中，作為一個整體不被分開運(yùn)輸。

2）運(yùn)輸工具與中轉(zhuǎn)能力充足，能夠滿足這次運(yùn)輸。3）貨物在節(jié)點(diǎn)能夠及時開始轉(zhuǎn)運(yùn)工作。

1.3 符號說明

1.4 模型構(gòu)建

目前在對多式聯(lián)運(yùn)路徑優(yōu)化問題的模型構(gòu)建上，大多采用的是將路段選擇和中轉(zhuǎn)節(jié)點(diǎn)選擇作為規(guī)劃路徑的（0，1）變量，以此構(gòu)建目標(biāo)函數(shù)為總成本最小的整數(shù)線性規(guī)劃模型[7-8]。該文在現(xiàn)有研究的基礎(chǔ)上，考慮損耗成本和制冷成本，以總物流成本最低，建立多式聯(lián)運(yùn)路徑優(yōu)化模型，相關(guān)成本分析如下：

1）基礎(chǔ)運(yùn)輸成本CY

在使用運(yùn)輸工具在路徑上運(yùn)輸時，基礎(chǔ)運(yùn)輸費(fèi)用與所選路徑的運(yùn)輸距離呈正相關(guān)線性關(guān)系。

2）中轉(zhuǎn)成本CZ

當(dāng)時城市節(jié)點(diǎn)中轉(zhuǎn)變量為1 時，產(chǎn)生中轉(zhuǎn)成本。

3）損耗成本CS

該文參考Weibull 三參數(shù)分布函數(shù)來描述冷鏈貨物途中的損耗變化情況，該函數(shù)被證明能夠適用于各種情況，如物品的變質(zhì)損耗情況、電子元件的失效、物品的銷售壽命等[9]，具有極強(qiáng)的普適性，其分布函數(shù)如下：

式中，α是函數(shù)的尺度因子，α＞0；β是函數(shù)的形狀因子，β＞0；γ為函數(shù)的位置因子，t為時間。由該分布函數(shù)得到貨物的損耗率，以計算損耗成本。

4）時間窗懲罰成本C(t)

約束時間內(nèi)不收取懲罰費(fèi)用，貨物提前送達(dá)而沒有超出允許最早時間時，收取相應(yīng)的倉儲費(fèi)用，其他時間段懲罰成本無限大：

5）制冷成本CL

該文制冷成本參考相關(guān)文獻(xiàn)[10-11]中的計算方法，通過計算冷藏車產(chǎn)生的熱負(fù)荷換算成制冷所產(chǎn)生的燃油消耗，熱負(fù)荷來源于車廂內(nèi)外溫度差，計算公式為：

其中，S為箱體表面積，通常通過車廂內(nèi)表面積和外表面積求出，即。

根據(jù)以上各成本分析，加入相關(guān)約束條件，即可建立如下的冷鏈路徑優(yōu)化模型：

其中，式（4）為目標(biāo)函數(shù)；式（5）表示總運(yùn)輸時間；式（6）為運(yùn)輸方式限制；式（7）為轉(zhuǎn)運(yùn)次數(shù)約束；式（8）-（9）為前后選擇平衡約束。

2 算法設(shè)計

2.1 算法簡介

免疫優(yōu)化算法是利用免疫系統(tǒng)的多樣性和維持機(jī)制來保持群體的多樣性，并強(qiáng)調(diào)群體中個體間的信息交換，從而實(shí)現(xiàn)對解空間搜索的一種智能計算方法[12]，在實(shí)際求解時，雖然將優(yōu)秀抗體保存到記憶細(xì)胞中，使迭代全程收斂，但未能避免單個抗體的退化現(xiàn)象，使得算法的收斂速度受到影響?；诖耍撐膮⒖剂Ｗ尤核惴ㄖ须p尋優(yōu)的特性，創(chuàng)建個體最優(yōu)抗體庫，在每一次迭代中更新每一個抗體所經(jīng)歷的最優(yōu)位置，并將其與每代形成的新抗體進(jìn)行適應(yīng)度值比較，從而更新抗體群，加快算法的收斂速度。

2.2 求解步驟

1）抗體編碼。城市節(jié)點(diǎn)選用0 和1 編碼，即經(jīng)過該城市為1，否則為0；運(yùn)輸方式用1、2、3 進(jìn)行編碼，分別代表公路、鐵路、水路。進(jìn)行F 次編碼初始化F 個抗體形成初始抗體群?？贵w的編碼示意圖如圖1 所示。

圖1 粒子編碼示意圖

2）抗體的多樣性評價?？贵w適應(yīng)度Av：將適應(yīng)度函數(shù)設(shè)置為目標(biāo)函數(shù)的倒數(shù)，并初始化抗體個體最優(yōu)庫。

抗體相似度Simv,s：當(dāng)兩個抗體編碼中相同編碼的位數(shù)大于設(shè)定的閾值ps，則表示這兩種抗體相似。

抗體濃度Conv：由抗體與抗體之間的相似度來計算，每個抗體的濃度為群體中與該抗體相似個體占群體總數(shù)的比例。

期望繁殖概率：由抗體的適應(yīng)度值和濃度計算每個抗體的期望繁殖概率，即：

其中，Av為抗體v的適應(yīng)度值，θ為多樣性評價參數(shù)。

形成父代群體：將抗體中期望繁殖概率最高的r個抗體存入記憶庫中作為記憶細(xì)胞，期望繁殖概率最高的（F-r）個抗體構(gòu)成父代群體。

3）遺傳操作。遺傳操作包括選擇、交叉和變異。

4）更新抗體群。計算經(jīng)過遺傳操作形成的子代群體和記憶細(xì)胞的適應(yīng)度值，更新抗體的個體最優(yōu)庫，并從個體最優(yōu)中找出適應(yīng)度最大的群體最優(yōu)抗體并記錄。將子代細(xì)胞的個體最優(yōu)與記憶細(xì)胞結(jié)合生成新的抗體群，返回步驟2）進(jìn)行下一次迭代。滿足終止條件時，輸出記錄的群體最優(yōu)抗體適應(yīng)度值。

3 案例分析

3.1 案例設(shè)計

現(xiàn)假設(shè)有櫻桃、海蝦、柑橘三種農(nóng)產(chǎn)品在運(yùn)輸網(wǎng)絡(luò)中流通，運(yùn)輸具體信息如表1 所示，運(yùn)輸途中的損耗參數(shù)參考相關(guān)文獻(xiàn)[11,13-14]。提前到達(dá)的貨物將收取100 元/t·h 的倉儲費(fèi)用。制冷費(fèi)用參數(shù)[13]中熱傳率R為2.49 kCal/（h·m2·℃），車廂內(nèi)表面積為22.70 m2，外表面積24.67 m2，單位制冷成本e為1 元/kCal。

表1 冷鏈貨物運(yùn)輸信息表

運(yùn)輸網(wǎng)絡(luò)共有14 個節(jié)點(diǎn)城市，如圖2 所示。各節(jié)點(diǎn)運(yùn)輸距離和各運(yùn)輸方式轉(zhuǎn)運(yùn)信息如表2 所示，各運(yùn)輸方式的具體參數(shù)如下：公路運(yùn)輸平均速度為90 km/h，費(fèi)率為9.39 元/（TEU·km），鐵路運(yùn)輸平均速度為60 km/h，費(fèi)率基價一為572 元/（TEU·km），基價二為4.14 元/（TEU·km），水路運(yùn)輸平均速度為40 km/h，費(fèi)率為2.34 元/（TEU·km）；公路與鐵路、水路互相轉(zhuǎn)運(yùn)的費(fèi)用分別為150元/TEU、225元/TEU，時間都為0.5 h，鐵路和水路轉(zhuǎn)運(yùn)的費(fèi)用為826 元/TEU，時間為1 h。

表2 節(jié)點(diǎn)間路段各運(yùn)輸方式運(yùn)輸距離

圖2 運(yùn)輸路徑網(wǎng)絡(luò)

3.2 案例求解

利用數(shù)學(xué)軟件Matlab 對算例進(jìn)行求解，設(shè)抗體種群規(guī)模為80 個，記憶庫容量為20 個，交叉概率0.7，變異概率0.5，相似度閾值ps 為0.8，多樣性評價參數(shù)θ為0.95，迭代次數(shù)100 次。同時，選用第一批貨物為例使用免疫優(yōu)化算法與改進(jìn)后的算法進(jìn)行對比，如圖3 所示，路徑優(yōu)化結(jié)果見表3。

表3 路徑優(yōu)化結(jié)果

圖3 算法迭代對比圖

從圖3 可以看出，改進(jìn)的免疫優(yōu)化算法可以通過對抗體染色體的變化，來描述運(yùn)輸方式和路段的選擇優(yōu)化，能夠有效契合多式聯(lián)運(yùn)路徑優(yōu)化問題；與原算法相比，改進(jìn)后的算法具有更快的收斂速度和更好的收斂效果。

4 結(jié)論

該文采用Weibull 分布函數(shù)來描述不同類型產(chǎn)品的損耗率，并構(gòu)建冷鏈多式聯(lián)運(yùn)路徑優(yōu)化模型，進(jìn)而利用粒子群算法雙尋優(yōu)的特點(diǎn)，對免疫優(yōu)化算法進(jìn)行改進(jìn)，從而加快了算法的收斂速度。最后通過多OD 的算例進(jìn)行模擬，結(jié)果證明改進(jìn)后的算法能夠有效地解決多式聯(lián)運(yùn)路徑優(yōu)化問題，并具有較快的收斂速度，同時在考慮損耗因素時，選用的Weibull三參數(shù)分布函數(shù)也能夠?qū)Σ煌浳锏膿p耗狀況進(jìn)行描述，具有很好的適用性。