廖 建 國(guó)

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

0 引 言

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

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

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

物流配送中心選址是在n個(gè)客戶中建立m個(gè)配送中心，使得m個(gè)配送中心到其服務(wù)客戶群運(yùn)輸總距離(成本)最短(最低)，同時(shí)還需要滿足一些約束條件：假設(shè)每一個(gè)客戶只由一個(gè)配送中心配送，每一個(gè)配送中心的貨物供應(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個(gè)客戶需求量；distij表示配送中心i與客戶j之間的距離；uij為1時(shí)表示第j個(gè)客戶的貨物由第i個(gè)配送中心配送。式(2)-式(6)為約束條件。

2 基本布谷鳥(niǎo)算法

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

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

2) 在問(wèn)題領(lǐng)域內(nèi)隨機(jī)產(chǎn)生一定數(shù)目的種群并計(jì)算每一個(gè)個(gè)體的目標(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)更新鳥(niǎo)巢。

(7)

(8)

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

(9)

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

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

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

(10)

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

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

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

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

3.1 構(gòu)造解向量

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

表1 解向量

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

3.2 全局搜索

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

(11)

3.3 局部搜索

在基本布谷鳥(niǎo)算法中局部搜索是按式(10)計(jì)算，未引用當(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)一步提高布谷鳥(niǎo)算法的效果，采用輪盤(pán)賭選擇、鳥(niǎo)巢交叉和鳥(niǎo)巢逆序操作，同時(shí)在這三個(gè)操作中引入精英保留策略。輪盤(pán)賭選擇參見(jiàn)遺傳算法，鳥(niǎo)巢交叉即隨機(jī)選擇兩個(gè)鳥(niǎo)巢，對(duì)這兩個(gè)鳥(niǎo)巢隨機(jī)選擇兩個(gè)位置進(jìn)行一定概率的交叉操作；鳥(niǎo)巢逆序操作即對(duì)隨機(jī)選擇的鳥(niǎo)巢進(jìn)行任意兩個(gè)位置的倒序操作。

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

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

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

2) 在問(wèn)題領(lǐng)域內(nèi)按表1編碼方式隨機(jī)產(chǎn)生一定數(shù)目的種群并按式(1)計(jì)算每個(gè)鳥(niǎo)巢的目標(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)更新鳥(niǎo)巢，按式(1)計(jì)算新鳥(niǎo)巢的目標(biāo)函數(shù)值，若較之前的優(yōu)越則替換之前目標(biāo)函數(shù)值和相應(yīng)的鳥(niǎo)巢，并記錄最優(yōu)解。

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

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

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

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

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

4.1 車(chē)輛路徑問(wèn)題的數(shù)學(xué)模型

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

m=[∑gi/aqk]+1

(13)

式中：m表示車(chē)輛數(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)表示車(chē)輛載重約束，式(16)-式(18)表示每一客戶只由一輛車(chē)服務(wù)，式(19)-式(20)表示0-1變量約束。

4.2 車(chē)輛路徑問(wèn)題的編碼與解碼

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

(21)

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

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

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

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

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

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

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

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

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

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

5 仿真實(shí)驗(yàn)

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

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

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

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

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

表5 200個(gè)客戶的配送中心及配送范圍

表6 200個(gè)客戶配送中心車(chē)輛、路線及距離信息

續(xù)表6

6 結(jié) 語(yǔ)

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