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

李 銳，李曉會，陳 鑫

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

1 引言

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

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

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

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

2 問題描述及模型建立

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

圖1 配送網絡系統

模型假設條件如下：

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

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

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

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

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

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

（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 優化模型

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

目標函數（1）最小化總成本，包括配送中心的開設成本、車輛的固定運營成本、運輸成本及運輸油耗和CO2排放成本，其中Filk表示車輛k在點i∈M和點l∈M之間線路的運輸油耗，計算詳見2.3節。式（2）為車輛k的路徑可靠性約束，其中車輛路徑的可靠性定義為該路徑保持正常運作的概率，β為要求的可靠性水平。約束（3）表示車輛k分配給配送中心j。約束（4）表示開設的配送中心必須有車輛駛出。約束（5）表示如果配送中心沒有開設，則沒有車輛駛出。約束（6）表示車輛從一個點駛入，也要從該點使出，即保證路徑為一個環路。約束（7）避免各個客戶點之間形成子環路。約束（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 問題。當規模較大時問題的求解困難，所以設計智能優化算法對該問題進行求解。

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

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

3.1 HICA算法的主要步驟

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

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

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

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

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

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

步驟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。根據上述解碼規則，給定向量的取值可以唯一確定每輛車的行駛路徑，進而可以確定變量xilk、yjk的值，再由約束（4）和（5）即可確定解zj。

3.3 初始化帝國集團

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

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

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

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

3.4 產生殖民地的位置

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

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

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

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

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

3.6 帝國集團的勢力

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

其中，TCn為帝國集團的總勢力；ωi為帝國集團中殖民地的代價函數（詳見2.9 節）；ξ為常數，取值為[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給出不同算例的規模，包括配送中心數量、客戶數量和車輛數量。算例的參數按照表2中均勻分布產生。算法通過Matlab編程實現，并且所有測試的實驗環境為Intel Core i5 CPU 2.2 GHz，內存4 GB計算機，操作系統Windows 7。

表1 算例的規模

表2 算例的參數

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

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

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

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

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

表4 不同規模算例的詳細結果

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

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

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

5 結束語

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