基于布谷鳥算法的物流選址及路徑優化研究

廖 建 國

(柳州鐵道職業技術學院 廣西 柳州 545616)

0 引 言

無論是傳統的貿易方式還是現代電子商務模式，最終都是通過物流實現貨物的送達、驗收和售后服務。隨著我國電子商務的蓬勃發展，物流的“第一公里”和“最后一公里”成為電商發展平臺的瓶頸，物流選址成為“第一公里”的決定性因素，而車輛配送路徑優化是“最后一公里”的重要因素。傳統的研究是將物流選址和車輛路徑優化作為兩個獨立的子問題進行研究，難以實現物流系統的整體最優，將物流選址和車輛路徑優化集成研究對物流企業降低物流成本、提高經濟效益及社會效益具有重要意義。該問題本質上屬于定位-運輸路線安排問題(Location-Routing Problem，LRP)，求解其方法有精確算法和智能算法，精確算法只適合小規模問題，而智能算法適合求解大規模LRP。文獻[1]對不同運營模式下電商企業物流配送中心選址和路徑優化進行研究；文獻[2]對城市生鮮食品冷鏈物流配送中心選址及路徑優化問題進行研究；文獻[3]對電動物流車充站選址和運輸路徑優化問題進行研究；文獻[4]對電子商務企業共享循環包裝選址-路徑問題進行研究；文獻[5]對考慮碳排放的物流配送選址-路徑問題模型及其優化方法進行研究；文獻[6]對某新零售企業物流配送中心選址及配送路徑規劃進行研究；文獻[7]對生鮮農產品多配送中心連續選址-路徑規劃問題進行研究；文獻[8]提出電網企業的配送節點選址_路徑優化問題研究，文獻[9]提出基于雙層規劃的生鮮農產品冷鏈配送中心選址及路徑優化研究，文獻[10]提出了配送選址-多車型運輸路徑優化問題及求解算法，文獻[11]提出兩階段啟發式算法求解定位-運輸路線問題，上述文獻對LRP有作為整體研究和分階段研究。由于LRP的復雜性，各種方法都有一定的局限性，因此探索新算法十分必要。

本文采用改進的布谷鳥算法分階段求解LRP，首先利用算法1確定配送中心及服務客戶群，然后利用算法2對配送中心所服務客戶群的車輛路徑進行優化。通過不同算例的仿真實驗表明本文算法行之有效，為管理決策層提供科學的預算方案，對物流企業降低物流成本、提高經濟效益提供了參考依據。

1 物流配送中心選址的數學模型

物流配送中心選址是在n個客戶中建立m個配送中心，使得m個配送中心到其服務客戶群運輸總距離(成本)最短(最低)，同時還需要滿足一些約束條件：假設每一個客戶只由一個配送中心配送，每一個配送中心的貨物供應量足以滿足其服務客戶群的需求。因此物流選址的數學模型為：

(1)

(2)

uij≤hj,i∈M,j∈N

(3)

(4)

hj∈{0,1},uij∈{0,1},i∈M,j∈N

(5)

M={j|j=1,2,…,m},N={j|j=1,2,…,n}

(6)

式(1)為目標函數，其中：m表示配送中心數目；n表示客戶群數目；qj表示第j個客戶需求量；distij表示配送中心i與客戶j之間的距離；uij為1時表示第j個客戶的貨物由第i個配送中心配送。式(2)-式(6)為約束條件。

2 基本布谷鳥算法

基本布谷鳥算法(Cuckoo Search algorithm，CS)是通過模擬布谷鳥尋窩產卵的行為來求解最優解[12]，其求解過程為：

1) 設置種群數目、棄巢率、問題邊界及最大迭代次數。

2) 在問題領域內隨機產生一定數目的種群并計算每一個個體的目標函數值，求出當前最優值和最優解。

3) 判斷迭代次數是否達到最大迭代次數，如果是則退出循環，輸出最優值和最優解；否則進入步驟4)。

4) 根據式(7)更新鳥巢。

(7)

(8)

式中：β取值為1.5；ν,μ∈N(0,1)；φ按式(9)計算。

(9)

式中：Γ為Gamma函數。

5) 計算新鳥巢的目標函數值，若較之前的優越則替換函數值和相應的鳥巢，并記錄最優解。

6) 隨機生成[0,1]之間的數并與棄巢率比較，若小于則保留該鳥巢，否則按式(10)產生新鳥巢。

(10)

式中：a、c為第t次迭代中不重復的隨機整數；r∈[0,1]的隨機數。

7) 重新計算新鳥巢的目標函數值，若較之前的優越則替換函數值和相應的鳥巢，并記錄最優解。

8) 判斷函數值與最優值，如果小于則替換最優值與最優解；算法轉入步驟3)進行下一次迭代。

3 改進布谷鳥算法求解物流配送中心選址

3.1 構造解向量

本文改進布谷鳥算法求解物流選址問題不同于文獻[13]。其一：編碼的方式不同，文獻[13]對10個需求點選取3個配送中心，通過排序后僅僅選擇前面3個序號作為一組配送中心，這樣配送中心種群數目減少最終導致物流選址求解精度不高，本文的編碼方式如表1所示。

表1 解向量

同樣對10個需求點選取3個配送中心，則選取前面9個序號作為配送中心，如矩陣center所示，即一個鳥巢可以對應3組配送中心，大大拓展了配送中心的多樣性。其二：改進策略不同。

3.2 全局搜索

在基本布谷鳥算法中全局搜索是依靠Levy飛行獲取新的鳥巢，Levy飛行是短距離的移動和偶爾大步長的跳躍，該方式既有利于跳出局部最優解亦可能求解的精度較差，因此借鑒Jaya算法的搜索策略[14]，其表達式為：

(11)

3.3 局部搜索

在基本布谷鳥算法中局部搜索是按式(10)計算，未引用當前最優解，可能導致收斂速度較慢，于是增加下式：

(12)

式中：r1,r2∈[0,1]之間的隨機數；a、b、c表示不重復的隨機整數。

3.4 領域搜索

為了進一步提高布谷鳥算法的效果，采用輪盤賭選擇、鳥巢交叉和鳥巢逆序操作，同時在這三個操作中引入精英保留策略。輪盤賭選擇參見遺傳算法，鳥巢交叉即隨機選擇兩個鳥巢，對這兩個鳥巢隨機選擇兩個位置進行一定概率的交叉操作；鳥巢逆序操作即對隨機選擇的鳥巢進行任意兩個位置的倒序操作。

3.5 改進布谷鳥算法求解物流選址的步驟(算法1)

綜上分析，改進布谷鳥算法(Improved Cuckoo Search algorithm，ICS)求解物流配送中心選址的步驟如下：

1) 設置種群數目、棄巢率、問題邊界及最大迭代次數。

2) 在問題領域內按表1編碼方式隨機產生一定數目的種群并按式(1)計算每個鳥巢的目標函數值，求出當前最優值和最優解。

3) 判斷迭代次數是否達到最大迭代次數，如果是則退出循環，輸出最優值和最優解；否則進入步驟4)。

4) 根據式(11)更新鳥巢，按式(1)計算新鳥巢的目標函數值，若較之前的優越則替換之前目標函數值和相應的鳥巢，并記錄最優解。

5) 將r∈[0,1]與棄巢率比較，若小于則保留該鳥巢，否則再判斷如果r小于棄巢率，則按式(12)計算，否則按式(10)計算。

6) 按式(1)重新計算新鳥巢的目標函數值，若較之前的優越則替換之前目標函數值和相應的鳥巢，并記錄最優解。

7) 進行N次領域搜索，并重新計算新鳥巢的目標函數值，若較之前的優越則替換之前目標函數值和相應的鳥巢，并記錄最優解。

8) 判斷目標函數值與最優值大小，如果小于則替換最優值與最優解；算法轉入步驟3)進行下一次迭代。

4 車輛路徑優化

4.1 車輛路徑問題的數學模型

車輛路徑問題(Vehicle Routing Problem，VRP)可描述為：現有L(i=1,2,…,L)個客戶，第i個客戶的需求為gi(i=1,2,…,L)，每車輛的載重量為qk(k=1,2,…,K)，假設配送中心擁有K(k=1,2,…,K)輛車，車輛從配送中心出發依次配送其服務客戶群，要求滿足各客戶需求的配送路線最短。在實際配送過程中需要對所需車輛數進行估算，通常采用下式來計算：

m=[∑gi/aqk]+1

(13)

式中：m表示車輛數；[ ]表示floor函數；a一般取值為0.98。

用0表示配送中心，dij表示客戶i與客戶j之間的距離，VRP的數學模型為：

(14)

(15)

(16)

(17)

(18)

xijk=0或1,?i,j,k

(19)

yik=0或1,?i,k

(20)

其中：式(14) 表示總距離最短，式(15)表示車輛載重約束，式(16)-式(18)表示每一客戶只由一輛車服務，式(19)-式(20)表示0-1變量約束。

4.2 車輛路徑問題的編碼與解碼

假設有8個客戶3輛車，本文在表1編碼的基礎上采用文獻[15]的編碼方式，用client=[1，2，3，4，5，6，7，8，0，0]表示客戶向量，其中“0”表示配送中心，其數量為車輛數減1。問題維數等于客戶數加上車輛數再減1，隨機產生鳥巢nest=[-3.14，-5.23，9.69，6.93，5.89，8.00，5.60，6.73，-3.57，4.85]，對其進行升序排列后得到index=[2，9，1，10，7，5，8，4，6，3]，將index視為client的配送順序，則得到的配送方案為：3- 1- 0- 8- 6- 0- 5- 7- 2- 4，則車輛1：0- 3- 1- 0，車輛2：0- 8- 6- 0，車輛3：0- 5- 7- 2- 4- 0。利用罰函數法將上述VRP的數學模型轉換為下式：

(21)

4.3 車輛路徑優化(算法2)

1) 根據算法1求解的配送中心及其服務客戶群作為算法2的輸入，求解每個服務客戶群的距離矩陣。

2) 設置參數：種群數目、棄巢率、問題邊界、問題維數、最大迭代次數、車輛數目估算及罰函數系數。

3) 按4.2節編碼方式產生初始種群和按式(21)計算目標函數值，并求出當前最優值和最優解。

4) 判斷迭代次數是否達到最大迭代次數，如果是則退出循環，輸出最優值和最優解；否則進入步驟5)。

5) 計算當前最差解，然后根據式(11)更新鳥巢，按式(21)重新計算新鳥巢的目標函數值，若較之前的優越則替換之前目標函數值和相應的鳥巢，并記錄最優解。

6) 將r∈[0,1]與棄巢率比較，若小于則保留該鳥巢，否則再判斷如果r小于棄巢率，則按式(12)計算，否則按式(10)計算。

7) 按式(21)重新計算鳥巢的目標函數值，若較之前的優越則替換之前目標函數值和相應的鳥巢，并記錄最優解。

8) 對鳥巢進行N次領域搜索，并按式(21)重新計算新鳥巢的目標函數值，若較之前的優越則替換之前目標函數值和相應的鳥巢，并記錄最優解。

9) 判斷目標函數值與最優值大小，如果小于則替換最優值與最優解；算法轉入步驟4)進行下一次迭代。

5 仿真實驗

本文設計了算法1和算法2，算法2是在算法1確定配送中心基礎之上進行路徑優化，任何一個算法的求解效果將直接影響最終結果。因此將算法1和算法2結合之前，分別采用算例進行實驗分析以驗證算法1和算法2的有效性和優越性，然后再將算法1和算法2結合作用于同一算例C101和隨機算例來驗證物流選址和路徑優化研究。所有的實驗均運行在Intel i5- 8350U、8 GB內存、Windows 7和MATLAB 2010b環境下。首先驗證算法1，選取文獻[16-17]中10個配送中心和50個需求點作為測試數據，為比較公平，參數設置與其相同：種群數目為20，最大迭代次數為50，棄巢率為0.25，交叉概率為0.8，領域搜索為5。算法1獨立運行30次并與其他算法比較結果如表2所示，配送方案如圖1所示。從表2中8種算法比較可知，就最優值而言，ICS優于FPA、PSO、GA、DEA、BWPA，與MFPA一致，僅次于IWPA；但就最差值、平均值和方差而言，ICS均優于其他算法。這足以說明算法1的有效性和魯棒性。再驗證算法2，選取VRP標準測試算例E-n33-k4，參數設置：種群規模為60，最大迭代次數為200，棄巢率為0.25，交叉概率為0.8，領域搜索為10。算法2獨立運行30次計算的最優值為835，與當前最優值一致，其車輛配送路線如圖2所示。

表2 各種算法的比較結果

再結合算法1+算法2作用于同一算例C101和隨機算例。由于50個需求點要建設10個配送中心，每個配送中心所服務客戶群的數量較少，故采用Solomon提供的C101作為測試集，假設需要建設10個配送中心。參數設置：種群數目為50，最大迭代次數為100，棄巢率為0.25，交叉概率為0.8，領域搜索為5，每車輛的載重量為100，懲罰系數為5 000。由算法1獨立運行30次求解的最優值為7 752.2，其對應的配送中心及配送范圍如表3所示，由算法2獨立運行30次求解的最優配送中心、車輛數、配送路線、距離(費用)如表4所示，配送中心及配送路線如圖3-圖4所示。由表4可知，對于C101中100個客戶(包含位置和客戶需求數據)如果要建設10個配送中心，算法科學地給出了配送中心建設的最佳位置、所需車輛數，每輛車行駛路線、總距離(費用)。對于該算例，所有配送中心的運輸費用為400.440 28。

表4 C101配送中心、車輛、路線及距離信息

為了進一步驗證算法1+算法2的有效性，增加客戶數目減少配送中心，現在[1 000,4 500]之間隨機生成200個客戶位置，在[10,100]隨機生成200個客戶需求量，假設只需建設5個配送中心。參數設置為每車輛的載重量為400，其余參數與C101實驗相同。由算法1獨立運行20次求解的最優值為：6.025 356 2e+006，其對應的配送中心及配送范圍如表5所示，由算法2獨立運行30次求解的最優配送中心、車輛數、配送路線、總距離(費用)如表6所示，配送中心及配送路線如圖5-圖6所示。由表6可知，對于200客戶5個配送中心，算法科學地給出了配送中心建設的最佳位置、所需車輛數、每輛車行駛路線、總距離(費用)。對于該算例，所有配送中心的運輸費用為5.934 2e+004。

表5 200個客戶的配送中心及配送范圍

表6 200個客戶配送中心車輛、路線及距離信息

續表6

6 結 語

本文針對NP-hard的物流選址及路徑優化問題，采用兩段式智能算法進行求解，由于基本布谷鳥算法在求解性能上較差，因此在布谷鳥算法基礎之上融合輪盤賭選擇、鳥巢交叉和鳥巢逆序操作，分別設計了算法1和算法2，通過算法1確定配送中心最佳位置及服務客戶群，通過算法2對每個配送中心所服務客戶群的運輸路線進行優化。不同規模的仿真實驗驗證了本文算法的有效性，其為管理決策層提供科學的預算方案，但本文沒有考慮不同車型和時間窗等約束條件，相關研究還有待于進一步深入。