李 銳，李曉會(huì)，陳 鑫

遼寧工業(yè)大學(xué) 電子與信息工程學(xué)院,遼寧 錦州 121001

1 引言

配送網(wǎng)絡(luò)是物流配送系統(tǒng)運(yùn)作的基礎(chǔ)。合理的配送中心選址及車輛路徑規(guī)劃對(duì)于配送系統(tǒng)的有效運(yùn)作具有重要作用。選址-路徑問題（Location-Routing Problem，LRP）同時(shí)集成選址問題和車輛路徑優(yōu)化問題。國內(nèi)外學(xué)者對(duì)各種LRP 問題及其擴(kuò)展問題進(jìn)行了研究。Caroline 等[1]和 Michael 等[2-3]分別從不同角度對(duì)近年來LRP的相關(guān)研究進(jìn)行了詳細(xì)的綜述，包括標(biāo)準(zhǔn)LRP，以及多階段LRP、多周期LRP、多目標(biāo)LRP等各種擴(kuò)展問題。

隨著環(huán)境保護(hù)意識(shí)的增強(qiáng)，人們也開始注意到物流配送過程中CO2排放對(duì)環(huán)境的污染。綠色的物流配送系統(tǒng)設(shè)計(jì)對(duì)于發(fā)展可持續(xù)物流具有重要意義。目前，對(duì)于綠色LRP 問題的研究較少。Govindan 等[4]研究易腐食物供應(yīng)鏈中帶時(shí)間窗的兩級(jí)LRP問題，同時(shí)最小化成本和環(huán)境影響。Toro等[5]研究綠色有容LRP問題，最小化運(yùn)作成本和環(huán)境影響。Tricoire 等[6]對(duì)城市樞紐LRP問題進(jìn)行了研究，同時(shí)優(yōu)化成本和CO2排放。戢守峰等[7]研究考慮庫存的LRP聯(lián)合優(yōu)化問題，同時(shí)優(yōu)化總成本和碳排放。Ko? 等[8]研究考慮排放的城市貨物運(yùn)輸LRP 問題。Dukkanci 等[9]研究綠色 LRP 問題，建立單目標(biāo)優(yōu)化模型，最小化運(yùn)作成本及排放成本，并考慮時(shí)間窗約束。然而，以上研究并沒有考慮安全性問題。

當(dāng)前，各種系統(tǒng)的安全性越來越受到人們的關(guān)注。實(shí)際中，物流配送系統(tǒng)內(nèi)部或外部的干擾都會(huì)給系統(tǒng)帶來中斷風(fēng)險(xiǎn)，從而影響系統(tǒng)的正常運(yùn)作。因此，設(shè)計(jì)安全的物流配送系統(tǒng)具有現(xiàn)實(shí)意義。最近，一些學(xué)者對(duì)于考慮中斷的可靠性LRP問題進(jìn)行了一定的研究。Zhang等[10]研究有容LRP 問題，考慮倉庫的隨機(jī)中斷，建立基于情景的混合整數(shù)規(guī)劃模型，并設(shè)計(jì)元啟發(fā)式算法求解。Xie 等[11]考慮設(shè)施以概率中斷，并建立整數(shù)規(guī)劃模型，設(shè)計(jì)一種拉格朗日松弛方法求解。Ahmadijavid等[12]研究中斷風(fēng)險(xiǎn)下的LRP 問題，考慮隨機(jī)的生產(chǎn)-配送中心和車輛的中斷，基于風(fēng)險(xiǎn)測(cè)度建立優(yōu)化模型，并設(shè)計(jì)啟發(fā)式方法求解。Rayat等[13]研究集成庫存的可靠性LRP 問題，同時(shí)考慮配送中心的供應(yīng)中斷和部分缺貨。但目前為止，考慮CO2排放的可靠性LRP問題還沒有得到研究。

因此，本文研究可靠性綠色物流配送選址-路徑優(yōu)化問題。與現(xiàn)有LRP 問題研究不同，本文基于NTM 方法計(jì)算油耗和CO2排放成本，定義車輛路徑可靠性，以總成本最小化為目標(biāo)，建立帶有車輛路徑可靠性約束的物流配送選址-路徑優(yōu)化模型，并設(shè)計(jì)一種混合帝國競(jìng)爭(zhēng)算法求解。最后，通過實(shí)驗(yàn)來驗(yàn)證模型的合理性及算法的有效性。

2 問題描述及模型建立

如圖1所示，物流配送網(wǎng)絡(luò)包括配送中心、客戶、配送車輛和配送線路。車輛從配送中心出發(fā)依次通過不同的客戶進(jìn)行配送后再返回到配送中心。現(xiàn)實(shí)中，由于不確定因素的影響，配送中心和運(yùn)輸線路可能發(fā)生中斷。中斷的發(fā)生會(huì)影響配送系統(tǒng)的正常運(yùn)作。此外，運(yùn)輸過程的油耗和CO2排放會(huì)對(duì)環(huán)境造成污染。可靠性綠色物流配送選址-路徑優(yōu)化問題通過選擇開設(shè)配送中心、優(yōu)化不同車輛的行駛路徑，最小化總物流成本及油耗和CO2排放成本，同時(shí)滿足車輛路徑可靠性約束。

圖1 配送網(wǎng)絡(luò)系統(tǒng)

模型假設(shè)條件如下：

（1）客戶點(diǎn)的位置、數(shù)量和需求量已知；

（2）配送中心的位置、數(shù)量、開設(shè)成本、能力和中斷概率已知；

（3）任意兩點(diǎn)之間的距離和中斷概率已知；

（4）車輛的類型不同且數(shù)量已知，每個(gè)車輛的固定運(yùn)作成本、運(yùn)輸能力、單位距離運(yùn)輸成本、空載和滿載油耗已知；

（5）任意一個(gè)客戶點(diǎn)必須有且只有一輛車通過；

（6）每輛車只能從一個(gè)配送中心出發(fā)，并返回該配送中心；

（7）每個(gè)配送中心允許多個(gè)車輛駛出和駛?cè)搿?/p>

2.1 符號(hào)及變量

模型符號(hào)定義如下：

I：客戶點(diǎn)集合；

J：配送中心集合；

M=I?J；

K：車輛集合；

di：客戶點(diǎn)i∈I的需求量；

Gj：配送中心j∈J的固定開設(shè)成本；

Uj：配送中心j∈J的能力；

Pj：配送中心j∈J的中斷概率；

Hk：車輛k∈K的固定運(yùn)營成本；

Qk：車輛k∈K的運(yùn)輸能力；

Ck：車輛k∈K的單位距離運(yùn)輸成本；

：車輛k∈K的空載油耗；

：車輛k∈K的滿載油耗；

e：油耗和CO2排放成本系數(shù)；

Dil：點(diǎn)i∈M到點(diǎn)l∈M的距離；

pil：點(diǎn)i∈M和點(diǎn)l∈M之間線路的中斷概率；

τ：運(yùn)營周期（τ=365）。

決策變量定義如下：

filk≥ 0 表示車輛k∈K在點(diǎn)i∈M和點(diǎn)l∈M之間的運(yùn)輸量。

2.2 優(yōu)化模型

基于以上符號(hào)和變量定義，建立可靠性綠色物流配送網(wǎng)絡(luò)選址-路徑模型如下：

目標(biāo)函數(shù)（1）最小化總成本，包括配送中心的開設(shè)成本、車輛的固定運(yùn)營成本、運(yùn)輸成本及運(yùn)輸油耗和CO2排放成本，其中Filk表示車輛k在點(diǎn)i∈M和點(diǎn)l∈M之間線路的運(yùn)輸油耗，計(jì)算詳見2.3節(jié)。式（2）為車輛k的路徑可靠性約束，其中車輛路徑的可靠性定義為該路徑保持正常運(yùn)作的概率，β為要求的可靠性水平。約束（3）表示車輛k分配給配送中心j。約束（4）表示開設(shè)的配送中心必須有車輛駛出。約束（5）表示如果配送中心沒有開設(shè)，則沒有車輛駛出。約束（6）表示車輛從一個(gè)點(diǎn)駛?cè)?，也要從該點(diǎn)使出，即保證路徑為一個(gè)環(huán)路。約束（7）避免各個(gè)客戶點(diǎn)之間形成子環(huán)路。約束（8）保證每個(gè)車輛至多只能從一個(gè)配送中心駛出。約束（9）保證每個(gè)客戶點(diǎn)必須有且只有一個(gè)車輛服務(wù)。約束（10）要求任意兩個(gè)配送中心之間沒有車輛線路。約束（11）表示車輛的能力約束。約束（12）表示配送中心的能力約束。式（13）表示客戶點(diǎn)兩端流量的平衡約束。式（14）表示兩點(diǎn)之間線路流量的上限和下限約束。式（15）～（17）為二值變量約束。式（18）為兩點(diǎn)之間流量的非負(fù)約束。

2.3 運(yùn)輸油耗計(jì)算

本文采用NTM（Network for transport and environment）的方法來計(jì)算運(yùn)輸車輛油耗[14]?；贜TM 的方法，運(yùn)輸車輛的油耗可由式（19）計(jì)算：

其中，F(xiàn)empty為空載車輛的油耗，F(xiàn)full為滿載車輛的油耗，lf為負(fù)載系數(shù)。

車輛k在點(diǎn)i∈M和點(diǎn)l∈M之間線路之間的運(yùn)輸油耗Filk為：

3 算法設(shè)計(jì)

可靠性綠色物流配送選址-路徑問題是經(jīng)典LRP問題的擴(kuò)展，所以也是NP-hard 問題。當(dāng)規(guī)模較大時(shí)問題的求解困難，所以設(shè)計(jì)智能優(yōu)化算法對(duì)該問題進(jìn)行求解。

帝國競(jìng)爭(zhēng)算法[15]是由 Atashpaz-Gargari 和 Lucas 提出的一種基于社會(huì)政治進(jìn)化的智能優(yōu)化算法。算法通過模擬人類社會(huì)中帝國主義殖民地競(jìng)爭(zhēng)過程來實(shí)現(xiàn)對(duì)優(yōu)化問題的求解。目前，ICA 算法已經(jīng)應(yīng)用于不同領(lǐng)域問題的求解，如旅行商問題[16]、靜態(tài)同步補(bǔ)償器的設(shè)計(jì)問題[17]、柔性作業(yè)車間調(diào)度問題[18]和混流雙邊裝配線平衡問題[19]等，并且算法的性能已經(jīng)在應(yīng)用中得到了驗(yàn)證。

鑒于問題模型的特點(diǎn)，本文設(shè)計(jì)一種HICA算法對(duì)問題進(jìn)行求解。HICA算法采用實(shí)數(shù)向量對(duì)問題的解進(jìn)行編碼，并在產(chǎn)生新殖民地位置的過程中引入變異和交叉操作，進(jìn)而改善算法的搜索能力。

3.1 HICA算法的主要步驟

步驟1根據(jù)3.2節(jié)中解的編碼方式，生成初始國家，并初始化帝國集團(tuán)（詳見3.3節(jié)）；

步驟2每個(gè)帝國集團(tuán)中，產(chǎn)生新的殖民地位置（詳見3.4節(jié)）；

步驟3對(duì)于每個(gè)帝國集團(tuán)，交換帝國和殖民地的位置（詳見3.5節(jié)）；

步驟4計(jì)算所有帝國集團(tuán)的勢(shì)力（詳見3.6節(jié)）；

步驟5帝國之間的競(jìng)爭(zhēng)（詳見3.7節(jié)）；

步驟6消滅失去所有殖民地的帝國（詳見3.8節(jié)）；

步驟7當(dāng)群體中只剩下一個(gè)帝國集團(tuán)，或者達(dá)到最大迭代次數(shù)時(shí)，算法終止，否則，轉(zhuǎn)到步驟2；

步驟8輸出勢(shì)力最大的帝國。

3.2 解的編碼與解碼

如圖2所示，問題的解可由實(shí)數(shù)向量來表示。向量由三部分組成。假設(shè)NC表示客戶點(diǎn)數(shù)量，ND表示配送中心數(shù)量，NV表示車輛數(shù)。第一部分表示車輛經(jīng)過客戶點(diǎn)的次序，每一位對(duì)應(yīng)一個(gè)客戶點(diǎn)，取值為[0,1]之間的實(shí)數(shù)。將各個(gè)位的取值從小到大排列，即得到客戶點(diǎn)的排序。第二部分表示客戶點(diǎn)的車輛分配，每一位取值為[1,NV]之間實(shí)數(shù)，對(duì)其四舍五入取整得到選擇的車輛號(hào)。第三部分表示車輛所屬的配送中心，每一位對(duì)應(yīng)一個(gè)車輛，取值為[1,ND]之間實(shí)數(shù)，四舍五入取整對(duì)應(yīng)的整數(shù)表示車輛選擇的配送中心。

圖2 解的表示

假設(shè)客戶點(diǎn)的數(shù)量為4，配送中心數(shù)量為3，車輛數(shù)量為2。那么，客戶點(diǎn)編號(hào)為1～4，配送中心編號(hào)為1～3。根據(jù)第一部分值得到客戶點(diǎn)的排序?yàn)?-4-2-1。根據(jù)第二部分值可得客戶點(diǎn)1、3分配給車輛1；客戶點(diǎn)2、4分配給車輛2。再由第三部分值可得車輛1分配給配送中心3，車輛2 分配給配送中心1。最后，可得車輛1 的行駛路徑為配送中心3?客戶3?客戶1?配送中心3，車輛2的行駛路徑為配送中心1?客戶4?客戶2?配送中心1。根據(jù)上述解碼規(guī)則，給定向量的取值可以唯一確定每輛車的行駛路徑，進(jìn)而可以確定變量xilk、yjk的值，再由約束（4）和（5）即可確定解zj。

3.3 初始化帝國集團(tuán)

隨機(jī)生成數(shù)量為Npop的初始國家。選擇勢(shì)力最大的Nimp個(gè)國家作為帝國主義國家，剩下的Ncol個(gè)國家作為殖民地國家，其中Ncol=Npop-Nimp。

根據(jù)帝國主義國家的勢(shì)力大小分配殖民地，按照式（21）～（23）計(jì)算帝國分配的殖民地?cái)?shù)量：

其中，cn為帝國n的代價(jià)函數(shù)（詳見3.9節(jié)）；Cn為標(biāo)準(zhǔn)化后的代價(jià)函數(shù)；pn表示帝國的勢(shì)力大??；NCn為帝國n分配的殖民地?cái)?shù)量。

對(duì)于每個(gè)帝國，從Ncol個(gè)殖民地中隨機(jī)選擇相應(yīng)個(gè)數(shù)的殖民地分配給該帝國，最終形成初始的Nimp個(gè)帝國集團(tuán)。

3.4 產(chǎn)生殖民地的位置

為了改善標(biāo)準(zhǔn)ICA算法的性能，引入變異和交叉操作來產(chǎn)生新的殖民地位置，具體步驟如下：

步驟1對(duì)于當(dāng)前循環(huán)代數(shù)t的殖民地i按照式（24）向最好帝國移動(dòng)得到變異位置向量Vi(t+1) 。

步驟2將變異位置向量Vi(t+1) 與殖民地所屬帝國n按照式（25）進(jìn)行交叉得到新的殖民地位置：

3.5 交換帝國和殖民地的位置

殖民地移動(dòng)到新的位置后，如果殖民地的勢(shì)力比所屬帝國的勢(shì)力大，則交換殖民地與所屬帝國的位置。殖民地將作為新的帝國，帝國則成為殖民地。

3.6 帝國集團(tuán)的勢(shì)力

一個(gè)帝國集團(tuán)的勢(shì)力由兩部分組成：帝國主義國家的勢(shì)力和帝國所擁有的殖民地國家勢(shì)力。帝國主義國家的勢(shì)力對(duì)總勢(shì)力的影響更大。一個(gè)帝國集團(tuán)的總勢(shì)力按照式（26）定義：

其中，TCn為帝國集團(tuán)的總勢(shì)力；ωi為帝國集團(tuán)中殖民地的代價(jià)函數(shù)（詳見2.9 節(jié)）；ξ為常數(shù)，取值為[0,1]之間的實(shí)數(shù)。

3.7 帝國集團(tuán)競(jìng)爭(zhēng)

通過競(jìng)爭(zhēng)的方式，最弱帝國集團(tuán)中的最弱殖民地將被其他帝國集團(tuán)占有。每個(gè)帝國集團(tuán)都可能占有最弱殖民地國家，可能性按照式（27）計(jì)算：

其中，NTCn為帝國集團(tuán)n的相對(duì)代價(jià)函數(shù)，按照式（28）計(jì)算：

令向量D=P-R，其中P=[pr1,pr2,…,prNimp]，R=[r1,r2,…,rNimp]，r1,r2,…,rNimp～U( 0,1) 。D中最大元素對(duì)應(yīng)的帝國集團(tuán)將占有最弱的殖民地國家。

3.8 弱勢(shì)帝國滅亡

在競(jìng)爭(zhēng)中，弱勢(shì)帝國的殖民地將被其他帝國瓜分，當(dāng)一個(gè)帝國集團(tuán)失去所有的殖民地國家時(shí)，該帝國將滅亡，該帝國會(huì)被從種群中刪除。

3.9 代價(jià)函數(shù)

給定帝國主義國家或者殖民地國家，通過解碼得到解(X,Y,Z)，并按式（29）計(jì)算國家的代價(jià)函數(shù)：

其中，f(X,Y,Z)為目標(biāo)函數(shù)表達(dá)式（1），路徑可靠性約束（2）、車輛能力約束（11）和配送中心能力約束（12）作為懲罰項(xiàng)加入評(píng)價(jià)函數(shù)中。α1、α2和α3為懲罰系數(shù)。(·)+表示如果括號(hào)內(nèi)值為正，則取該值。

4 實(shí)驗(yàn)仿真與分析

為了驗(yàn)證模型的合理性和HICA算法的有效性，對(duì)不同的數(shù)值算例進(jìn)行測(cè)試。表1給出不同算例的規(guī)模，包括配送中心數(shù)量、客戶數(shù)量和車輛數(shù)量。算例的參數(shù)按照表2中均勻分布產(chǎn)生。算法通過Matlab編程實(shí)現(xiàn)，并且所有測(cè)試的實(shí)驗(yàn)環(huán)境為Intel Core i5 CPU 2.2 GHz，內(nèi)存4 GB計(jì)算機(jī)，操作系統(tǒng)Windows 7。

表1 算例的規(guī)模

表2 算例的參數(shù)

首先，對(duì)不同規(guī)模算例I1～I(xiàn)12 進(jìn)行求解來測(cè)試HICA 的性能，并將結(jié)果與標(biāo)準(zhǔn)ICA 算法及PSO 算法進(jìn)行對(duì)比。其中，所有算例的可靠性水平β取值為0.5。為公平比較，HICA 算法和標(biāo)準(zhǔn)ICA 算法的初始國家數(shù)量為100，初始帝國的數(shù)量為10，最大迭代次數(shù)為100，ξ取值為0.1。HICA 算法的常數(shù)F取值為1.5，交叉概率CR取值為0.9。PSO 算法的種群規(guī)模為100，最大迭代次數(shù)為100，慣性系數(shù)為0.8，加速常數(shù)為1.6。

對(duì)于每個(gè)算例，每種算法分別運(yùn)行10 次。表3 給出不同規(guī)模下HICA 算法、ICA 算法和PSO 算法的結(jié)果比較，包括最好值、最差值、平均值、平均偏差率和CPU平均運(yùn)行時(shí)間。其中，平均偏差率定義為：（（平均值?最好值）/最好值）×100%。由表3可見，對(duì)于不同規(guī)模的算例，HICA 算法的最好值、最差值、平均值和平均偏差率均低于標(biāo)準(zhǔn)ICA 算法及PSO 算法。其中，HICA 算法的平均偏差率在2.4%～8.3%之間變化，而標(biāo)準(zhǔn)ICA算法的平均偏差率在9.5%～18.9%之間變化，PSO 算法的平均偏差率在8.8%～14.7%之間?？梢?，HICA 算法能夠?qū)Σ煌?guī)模的算例進(jìn)行有效求解，并且隨著問題規(guī)模的增大，HICA 算法仍然能夠保持較好性能。此外，由于引入交叉和變異操作會(huì)增加HICA算法的運(yùn)行時(shí)間，所以HICA 算法的CPU 平均運(yùn)行時(shí)間略高于標(biāo)準(zhǔn)ICA算法。

表4給出算例I1～I(xiàn)12的詳細(xì)結(jié)果，包括配送中心的開設(shè)成本、車輛的固定運(yùn)營成本、運(yùn)輸成本、運(yùn)輸油耗及CO2排放成本。

為了分析可靠性水平β對(duì)算法性能和優(yōu)化決策結(jié)果的影響，以算例I5 為例進(jìn)行實(shí)驗(yàn)。其中，可靠性水平β取值為0.3～0.8。對(duì)于不同的可靠性水平，每種算法分別運(yùn)行10 次。表5 給出不同可靠性下HICA 算法與標(biāo)準(zhǔn)ICA 算法的結(jié)果對(duì)比。由表5 可見，HICA 算法的平均偏差率在2.9%～7.3%之間變化，而標(biāo)準(zhǔn)ICA算法的平均偏差率在13.1%～16.9%之間。HICA 算法的最好值、最差值和平均值也都優(yōu)于標(biāo)準(zhǔn)ICA算法。因此，不同的可靠性水平下HICA算法仍然能夠保持性能穩(wěn)定，并且求解效果優(yōu)于標(biāo)準(zhǔn)ICA算法。

表3 不同規(guī)模算例下HICA與ICA及PSO結(jié)果對(duì)比

表4 不同規(guī)模算例的詳細(xì)結(jié)果

表5 不同可靠性水平下HICA與ICA結(jié)果對(duì)比

表6 不同可靠性水平下算例I5的詳細(xì)結(jié)果

表6 給出算例I5 在不同可靠性水平下的詳細(xì)結(jié)果。由表6 可見，隨著可靠性水平的增大，總成本和車輛的固定運(yùn)營成本都單調(diào)增大，運(yùn)輸成本和運(yùn)輸油耗及CO2排放成本也呈現(xiàn)增大的趨勢(shì)。因?yàn)?，減少每個(gè)車輛經(jīng)過的客戶會(huì)增加車輛路徑的可靠性，所以當(dāng)可靠性水平增大，車輛數(shù)會(huì)增多，導(dǎo)致車輛的固定運(yùn)營成本增加，同時(shí)也將導(dǎo)致總的運(yùn)輸距離增大，進(jìn)而運(yùn)輸成本和運(yùn)輸油耗及CO2排放成本也會(huì)增大，以上成本的增大最終使總成本增大。

5 結(jié)束語

本文研究可靠性綠色物流配送選址-路徑優(yōu)化問題，建立了問題的優(yōu)化模型，在滿足路徑可靠性約束的條件下最小化總成本，包括配送中心的開設(shè)成本、車輛的運(yùn)營成本、運(yùn)輸成本及運(yùn)輸油耗和CO2排放成本。根據(jù)問題特點(diǎn)，設(shè)計(jì)了混合帝國競(jìng)爭(zhēng)算法（HICA）。最后，通過數(shù)值算例對(duì)算法性能進(jìn)行測(cè)試，并對(duì)重要參數(shù)進(jìn)行分析。實(shí)驗(yàn)結(jié)果表明，HICA算法能夠?qū)栴}有效求解，其性能優(yōu)于標(biāo)準(zhǔn)ICA 算法，并且隨著可靠性水平的增大，車輛數(shù)量增加，進(jìn)而使車輛運(yùn)營成本、運(yùn)輸成本、運(yùn)輸油耗及CO2排放成本增加，最終導(dǎo)致總成本增加。在未來研究中，可進(jìn)一步考慮動(dòng)態(tài)環(huán)境下的可靠性綠色物流配送選址-路徑優(yōu)化。