可靠性綠色物流配送選址-路徑問題研究

李 銳，李曉會，陳 鑫

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

1 引言

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

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

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

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

2 問題描述及模型建立

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

圖1 配送網絡系統

模型假設條件如下：

（1）客戶點的位置、數量和需求量已知；

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

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

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

（5）任意一個客戶點必須有且只有一輛車通過；

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

（7）每個配送中心允許多個車輛駛出和駛入。

2.1 符號及變量

模型符號定義如下：

I：客戶點集合；

J：配送中心集合；

M=I?J；

K：車輛集合；

di：客戶點i∈I的需求量；

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

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

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

Hk：車輛k∈K的固定運營成本；

Qk：車輛k∈K的運輸能力；

Ck：車輛k∈K的單位距離運輸成本；

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

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

e：油耗和CO2排放成本系數；

Dil：點i∈M到點l∈M的距離；

pil：點i∈M和點l∈M之間線路的中斷概率；

τ：運營周期（τ=365）。

決策變量定義如下：

filk≥ 0 表示車輛k∈K在點i∈M和點l∈M之間的運輸量。

2.2 優(yōu)化模型

基于以上符號和變量定義，建立可靠性綠色物流配送網絡選址-路徑模型如下：

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

2.3 運輸油耗計算

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

其中，Fempty為空載車輛的油耗，Ffull為滿載車輛的油耗，lf為負載系數。

車輛k在點i∈M和點l∈M之間線路之間的運輸油耗Filk為：

3 算法設計

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

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

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

3.1 HICA算法的主要步驟

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

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

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

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

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

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

步驟7當群體中只剩下一個帝國集團，或者達到最大迭代次數時，算法終止，否則，轉到步驟2；

步驟8輸出勢力最大的帝國。

3.2 解的編碼與解碼

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

圖2 解的表示

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

3.3 初始化帝國集團

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

根據帝國主義國家的勢力大小分配殖民地，按照式（21）～（23）計算帝國分配的殖民地數量：

其中，cn為帝國n的代價函數（詳見3.9節(jié)）；Cn為標準化后的代價函數；pn表示帝國的勢力大??；NCn為帝國n分配的殖民地數量。

對于每個帝國，從Ncol個殖民地中隨機選擇相應個數的殖民地分配給該帝國，最終形成初始的Nimp個帝國集團。

3.4 產生殖民地的位置

為了改善標準ICA算法的性能，引入變異和交叉操作來產生新的殖民地位置，具體步驟如下：

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

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

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

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

3.6 帝國集團的勢力

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

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

3.7 帝國集團競爭

通過競爭的方式，最弱帝國集團中的最弱殖民地將被其他帝國集團占有。每個帝國集團都可能占有最弱殖民地國家，可能性按照式（27）計算：

其中，NTCn為帝國集團n的相對代價函數，按照式（28）計算：

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

3.8 弱勢帝國滅亡

在競爭中，弱勢帝國的殖民地將被其他帝國瓜分，當一個帝國集團失去所有的殖民地國家時，該帝國將滅亡，該帝國會被從種群中刪除。

3.9 代價函數

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

其中，f(X,Y,Z)為目標函數表達式（1），路徑可靠性約束（2）、車輛能力約束（11）和配送中心能力約束（12）作為懲罰項加入評價函數中。α1、α2和α3為懲罰系數。(·)+表示如果括號內值為正，則取該值。

4 實驗仿真與分析

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

表1 算例的規(guī)模

表2 算例的參數

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

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

表4給出算例I1～I12的詳細結果，包括配送中心的開設成本、車輛的固定運營成本、運輸成本、運輸油耗及CO2排放成本。

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

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

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

表5 不同可靠性水平下HICA與ICA結果對比

表6 不同可靠性水平下算例I5的詳細結果

表6 給出算例I5 在不同可靠性水平下的詳細結果。由表6 可見，隨著可靠性水平的增大，總成本和車輛的固定運營成本都單調增大，運輸成本和運輸油耗及CO2排放成本也呈現增大的趨勢。因為，減少每個車輛經過的客戶會增加車輛路徑的可靠性，所以當可靠性水平增大，車輛數會增多，導致車輛的固定運營成本增加，同時也將導致總的運輸距離增大，進而運輸成本和運輸油耗及CO2排放成本也會增大，以上成本的增大最終使總成本增大。

5 結束語

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