基于布谷鳥算法的物流選址及路徑優(yōu)化研究

廖 建 國

(柳州鐵道職業(yè)技術(shù)學(xué)院 廣西 柳州 545616)

0 引 言

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

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

1 物流配送中心選址的數(shù)學(xué)模型

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

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

2 基本布谷鳥算法

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

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

2) 在問題領(lǐng)域內(nèi)隨機(jī)產(chǎn)生一定數(shù)目的種群并計算每一個個體的目標(biāo)函數(shù)值，求出當(dāng)前最優(yōu)值和最優(yōu)解。

3) 判斷迭代次數(shù)是否達(dá)到最大迭代次數(shù)，如果是則退出循環(huán)，輸出最優(yōu)值和最優(yōu)解；否則進(jìn)入步驟4)。

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

(7)

(8)

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

(9)

式中：Γ為Gamma函數(shù)。

5) 計算新鳥巢的目標(biāo)函數(shù)值，若較之前的優(yōu)越則替換函數(shù)值和相應(yīng)的鳥巢，并記錄最優(yōu)解。

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

(10)

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

7) 重新計算新鳥巢的目標(biāo)函數(shù)值，若較之前的優(yōu)越則替換函數(shù)值和相應(yīng)的鳥巢，并記錄最優(yōu)解。

8) 判斷函數(shù)值與最優(yōu)值，如果小于則替換最優(yōu)值與最優(yōu)解；算法轉(zhuǎn)入步驟3)進(jìn)行下一次迭代。

3 改進(jìn)布谷鳥算法求解物流配送中心選址

3.1 構(gòu)造解向量

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

表1 解向量

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

3.2 全局搜索

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

(11)

3.3 局部搜索

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

(12)

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

3.4 領(lǐng)域搜索

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

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

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

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

2) 在問題領(lǐng)域內(nèi)按表1編碼方式隨機(jī)產(chǎn)生一定數(shù)目的種群并按式(1)計算每個鳥巢的目標(biāo)函數(shù)值，求出當(dāng)前最優(yōu)值和最優(yōu)解。

3) 判斷迭代次數(shù)是否達(dá)到最大迭代次數(shù)，如果是則退出循環(huán)，輸出最優(yōu)值和最優(yōu)解；否則進(jìn)入步驟4)。

4) 根據(jù)式(11)更新鳥巢，按式(1)計算新鳥巢的目標(biāo)函數(shù)值，若較之前的優(yōu)越則替換之前目標(biāo)函數(shù)值和相應(yīng)的鳥巢，并記錄最優(yōu)解。

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

6) 按式(1)重新計算新鳥巢的目標(biāo)函數(shù)值，若較之前的優(yōu)越則替換之前目標(biāo)函數(shù)值和相應(yīng)的鳥巢，并記錄最優(yōu)解。

7) 進(jìn)行N次領(lǐng)域搜索，并重新計算新鳥巢的目標(biāo)函數(shù)值，若較之前的優(yōu)越則替換之前目標(biāo)函數(shù)值和相應(yīng)的鳥巢，并記錄最優(yōu)解。

8) 判斷目標(biāo)函數(shù)值與最優(yōu)值大小，如果小于則替換最優(yōu)值與最優(yōu)解；算法轉(zhuǎn)入步驟3)進(jìn)行下一次迭代。

4 車輛路徑優(yōu)化

4.1 車輛路徑問題的數(shù)學(xué)模型

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

m=[∑gi/aqk]+1

(13)

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

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

(14)

(15)

(16)

(17)

(18)

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

(19)

yik=0或1,?i,k

(20)

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

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

假設(shè)有8個客戶3輛車，本文在表1編碼的基礎(chǔ)上采用文獻(xiàn)[15]的編碼方式，用client=[1，2，3，4，5，6，7，8，0，0]表示客戶向量，其中“0”表示配送中心，其數(shù)量為車輛數(shù)減1。問題維數(shù)等于客戶數(shù)加上車輛數(shù)再減1，隨機(jī)產(chǎn)生鳥巢nest=[-3.14，-5.23，9.69，6.93，5.89，8.00，5.60，6.73，-3.57，4.85]，對其進(jìn)行升序排列后得到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。利用罰函數(shù)法將上述VRP的數(shù)學(xué)模型轉(zhuǎn)換為下式：

(21)

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

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

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

3) 按4.2節(jié)編碼方式產(chǎn)生初始種群和按式(21)計算目標(biāo)函數(shù)值，并求出當(dāng)前最優(yōu)值和最優(yōu)解。

4) 判斷迭代次數(shù)是否達(dá)到最大迭代次數(shù)，如果是則退出循環(huán)，輸出最優(yōu)值和最優(yōu)解；否則進(jìn)入步驟5)。

5) 計算當(dāng)前最差解，然后根據(jù)式(11)更新鳥巢，按式(21)重新計算新鳥巢的目標(biāo)函數(shù)值，若較之前的優(yōu)越則替換之前目標(biāo)函數(shù)值和相應(yīng)的鳥巢，并記錄最優(yōu)解。

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

7) 按式(21)重新計算鳥巢的目標(biāo)函數(shù)值，若較之前的優(yōu)越則替換之前目標(biāo)函數(shù)值和相應(yīng)的鳥巢，并記錄最優(yōu)解。

8) 對鳥巢進(jìn)行N次領(lǐng)域搜索，并按式(21)重新計算新鳥巢的目標(biāo)函數(shù)值，若較之前的優(yōu)越則替換之前目標(biāo)函數(shù)值和相應(yīng)的鳥巢，并記錄最優(yōu)解。

9) 判斷目標(biāo)函數(shù)值與最優(yōu)值大小，如果小于則替換最優(yōu)值與最優(yōu)解；算法轉(zhuǎn)入步驟4)進(jìn)行下一次迭代。

5 仿真實驗

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

表2 各種算法的比較結(jié)果

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

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

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

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

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

續(xù)表6

6 結(jié) 語

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