陳沿伊，侯華保

(武漢理工大學(xué) 交通學(xué)院，武漢 430070)

0 引 言

由于生鮮產(chǎn)品的易腐性特征，生鮮配送過程中，客戶滿意度不僅受客戶預(yù)約時間的影響，還受生鮮產(chǎn)品保鮮期長短及配送時間等因素的影響。當(dāng)前關(guān)于生鮮配送的研究主要考慮商品保鮮期，綜合考慮多種不確定因素的研究較少。

梁承姬等[1]為提高生鮮配送的時效性，考慮待配送客戶時間窗，以實現(xiàn)配送過程中成本最小且客戶滿意度最大；王恒等[2]研究生鮮配送時間不確定情況下配送時效性的問題，考慮客戶時間窗及道路實際特征，建立了生鮮配送路徑優(yōu)化模型；李暢等[3]研究生鮮配送的時效性問題時，考慮生鮮產(chǎn)品易腐性，建立以商品新鮮度最大和配送成本最低的多目標(biāo)生鮮配送路徑優(yōu)化模型；吳欣[4]、張濟(jì)風(fēng)等[5]在研究配送時間不確定背景下的生鮮配送問題時，考慮配送過程中配送速度的時變性；康凱等[6]以碳排放最低為目標(biāo)，研究了考慮客戶時間窗的冷鏈配送問題，建立了考慮碳排放的生鮮配送模型。但是，上述研究主要研究配送時效性或配送時間的不確定性，綜合考慮二者的研究較少，且生鮮配送的時效性影響因素較多。當(dāng)前關(guān)于生鮮配送時效性的研究，影響因素考慮得不全面，且當(dāng)前研究多配送中心下的生鮮配送問題較少，不符合當(dāng)下生鮮配送多配送中心化的趨勢。

關(guān)于路徑優(yōu)化的求解方法，張建勇等[7]結(jié)合聚類思想與遺傳算法，提出混合遺傳算法，解決帶模糊時間窗的多對多車輛路徑問題；S.HUBER等[8]采用變鄰域搜索的方式解決路徑優(yōu)化問題；胡蓉等[9]設(shè)置多種鄰域操作及局部優(yōu)化模型，嵌入蟻群算法，解決考慮速度空間特征的車輛路徑問題；邵倩[10]將遺傳算法引入非支配算子，求解考慮速度空間特征帶模糊時間窗的物流配送問題；S.IQBAL等[11]利用人工蜂群算法，結(jié)合局部鄰域搜索優(yōu)化，解決帶軟時間窗的車輛路徑問題；B.D.SONG等[12]提出基于優(yōu)先級的啟發(fā)式(PBH)算法進(jìn)行求解單目標(biāo)車輛路徑問題；范厚明等[13]基于擂臺賽法構(gòu)造非支配解，將局部優(yōu)化算子引入遺傳算法，解決多目標(biāo)車輛路徑問題；周鮮成等[14]在蟻群算法中設(shè)計確定性和隨機(jī)性結(jié)合的轉(zhuǎn)移策略；趙志學(xué)等[15]結(jié)合模型特點，在蟻群算法中引入約束算子，緩解了復(fù)雜問題易陷入局部最優(yōu)的問題；張得志等[16]采用遺傳算法解決考慮速度時變特征的路徑優(yōu)化問題；M.ALZAQEBAH等[17]采用改進(jìn)人工蜂群算法解決帶時間窗的車輛路徑問題。

綜上所述，當(dāng)前關(guān)于生鮮配送的研究主要以單配送中心為主，考慮多配送中心的研究較少，不能適應(yīng)當(dāng)前生鮮電商配送多配送中心化的發(fā)展趨勢。另外，當(dāng)前研究綜合考慮時間窗、保鮮期、路網(wǎng)擁堵特征的研究較少，研究結(jié)果不能完全反映配送的實際情況。鑒于此，筆者建立綜合考慮客戶時間窗、商品保鮮期和路網(wǎng)擁堵特征的多配送中心生鮮路徑優(yōu)化模型。因模型的復(fù)雜性較高，筆者在傳統(tǒng)蟻群-遺傳算法的基礎(chǔ)上，采用兩邊逐次修正算法對初始種群進(jìn)行局部優(yōu)化，對種群適應(yīng)度值降序排列后，選擇前30%作為精英個體，利用蟻群-遺傳算法進(jìn)行迭代優(yōu)化，并對算法參數(shù)進(jìn)行正交試驗設(shè)計，優(yōu)化算法參數(shù)?；谏鲜霾僮鳎梢杂行Ц纳扑惴ㄋ阉骺臻g及求解質(zhì)量。最后以多種分布特征的Solomon算例和筆者提出的算法為基礎(chǔ)，將該模型與不考慮商品保鮮期和不考慮客戶時間窗的模型計算結(jié)果進(jìn)行對比，以驗證該模型可以在配送時間不確定情況下有效提升配送的時效性，并將筆者提出的算法與傳統(tǒng)算法進(jìn)行對比，驗證算法有效性。

1 模型描述

1.1 模型描述

某生鮮企業(yè)在該區(qū)域有多個配送中心，每個配送中心存在多種車型?，F(xiàn)需要對該區(qū)域的客戶訂單進(jìn)行配送，需盡量滿足客戶預(yù)約時間要求且維持商品新鮮度，以保證客戶滿意度?？紤]到車輛行駛速度受高峰小時及所處位置的影響和客戶滿意度受客戶時間窗及商品保鮮期的影響，筆者提出速度時空擁堵函數(shù)和綜合模糊時間窗，建立時空擁堵下考慮客戶時間窗和商品保鮮期的多車場多車型生鮮配送路徑優(yōu)化模型。

1.2 模型參數(shù)與假設(shè)

1.2.1 模型參數(shù)

1.2.2 模型假設(shè)

模型假設(shè)如下：①該區(qū)域有多個配送中心，每個配送中心有多種車型，車輛數(shù)足夠；②每個客戶僅被一輛車一次服務(wù)；③車輛行駛速度受時間和空間的影響；④每輛車服務(wù)結(jié)束后返回原車場；⑤車輛晚于商品保鮮期到達(dá)，客戶滿意度為0；⑥配送速度不能超過最大允許速度。

1.3 模型建立

1.3.1 客戶滿意度函數(shù)

1)客戶模糊時間窗

基于客戶模糊時間窗，貨物在時間區(qū)間[Li,Ui]內(nèi)送達(dá)，客戶滿意度為1；在[li,ui]區(qū)間外到達(dá)客戶滿意度為0，其他區(qū)間客戶滿意度處于遞增或遞減狀態(tài)，具體見圖1。

圖1 客戶滿意度函數(shù)

2)商品保鮮期

假設(shè)在商品保鮮期前送達(dá)客戶滿意度為1，超過商品保鮮期，客戶滿意度為0，詳見圖2。

圖2 商品保鮮期

3)綜合模糊時間窗下客戶滿意度函數(shù)

綜合考慮客戶時間窗和商品保鮮期，取客戶時間窗和商品保鮮期交集，以反映客戶時間窗和商品保鮮期共同作用下的客戶滿意度隨時間的變化情況。假設(shè)當(dāng)商品超過保鮮期送達(dá)時，客戶滿意度為0，當(dāng)在客戶時間窗和商品保鮮期之間送達(dá)，滿意度變化服從客戶時間窗下的滿意度對應(yīng)法則。綜上所述，建立綜合模糊時間窗下的客戶滿意度函數(shù)，見圖3。圖3(a)～圖3(d)滿意度關(guān)系式分別對應(yīng)式(1)～式(4)。

圖3 綜合模糊時間窗下客戶滿意度函數(shù)

(1)

(2)

(3)

(4)

1.3.2 速度時空函數(shù)

1)速度時間擁堵系數(shù)

速度時間擁堵系數(shù)反映了不同時刻的路網(wǎng)擁堵特征。高峰小時附近，路網(wǎng)較為擁堵；其他時間，路網(wǎng)交通流較少，擁堵程度降低，見式(5)：

(5)

2)速度空間擁堵系數(shù)

配送速度受空間因素制約。郊區(qū)配送速度高于市區(qū)配送速度；距離區(qū)域中心越遠(yuǎn)配送速度越大。空間擁堵系數(shù)計算方法見式(6)：

(6)

3)速度時空函數(shù)

綜合考慮速度的時間和空間因素及道路最大限度vmax、道路最低時速vmin等因素，建立速度時空演變函數(shù)，見式(7)：

(7)

1.3.3 目標(biāo)函數(shù)去量綱處理

1)車輛使用數(shù)、配送距離、客戶平均滿意度處理分別如式(8)～式(10)：

(8)

(9)

(10)

2)多目標(biāo)加權(quán)處理

筆者采用加權(quán)法將多目標(biāo)轉(zhuǎn)化為單目標(biāo)，權(quán)重由專家打分確定，各個目標(biāo)通過去量綱化，消除單位對加權(quán)后目標(biāo)值的影響。去量綱化方法見式(11)～式(14)：

(11)

式中：maxf1、minf1分別表示當(dāng)次迭代中種群最多和最少車輛使用數(shù)。

(12)

將客戶平均滿意度與1做差，使得各目標(biāo)協(xié)同，max(1-f3)、min(1-f3)分別表示做差后的當(dāng)次迭代種群內(nèi)的極值。

(13)

經(jīng)過專家打分，確定車輛使用數(shù)、配送里程、客戶平均滿意度的權(quán)重分別為0.22、0.47，0.31，對各個子目標(biāo)加權(quán)處理得到總體目標(biāo)值：

(14)

1.3.4 模型與約束

模型與約束見式(15)～式(25)：

(15)

(16)

(17)

(18)

(19)

(20)

?k∈HP,?S∈J)

(21)

?j∈V)

(22)

(23)

(24)

(25)

其中，式(15)表示加權(quán)后的目標(biāo)值；式(16)表示每個客戶由且僅由一輛車務(wù)；式(17)表示車輛服務(wù)完一個客戶后會返回車場或前往下一個客戶；式(18)表示車輛行駛距離不應(yīng)超過其規(guī)定最大行程；式(19)表示任何從車場出發(fā)的車輛最終返原車場；式(20)表示任意一輛車的載重不可超過其額定載重；式(21)表示任意一輛車的服務(wù)客戶集合不出現(xiàn)閉環(huán)；式(22)表示兩個決策變量之間的關(guān)系；式(23)表示車場之間不允許通車；式(24)和式(25)為決策變量取值約束。

2 模型求解

2.1 求解思路

首先，利用擴(kuò)展啟發(fā)式算法產(chǎn)生初始可行解，在傳統(tǒng)蟻群遺傳算法的基礎(chǔ)上，引入兩邊逐次修正算法對精英群體進(jìn)行局部優(yōu)化。然后，利用定點交叉算法對精英種群進(jìn)行交叉變異，使之達(dá)到初始種群規(guī)模。最后，利用正交試驗設(shè)計思想，對算法參數(shù)進(jìn)行優(yōu)化，以最大迭代次數(shù)作為算法終止條件。對模型進(jìn)行求解算法流程見圖4。

圖4 算法流程

2.2 算法初始化

2.2.1 編碼與解碼

1)編碼

筆者采用十進(jìn)制編碼，根據(jù)車輛和車輛服務(wù)的顧客順序進(jìn)行多段編碼。車輛采用三位數(shù)編碼，百位數(shù)用于防止與客戶編號重復(fù)，十位數(shù)表示車場編號。個位數(shù)表示車型編號，如112表示第一個車場第二個車型?？蛻艟幋a采用十進(jìn)制編碼，編號表示客戶編號，見圖5。

圖5 路徑編碼

2)解碼

根據(jù)編碼順序，結(jié)合車輛、客戶數(shù)據(jù)信息，計算該路徑長度、客戶滿意度、使用車輛數(shù)，進(jìn)而計算該路徑的加權(quán)目標(biāo)值。

2.2.2 初始可行解

Step 1隨機(jī)選擇服務(wù)客戶的車輛，轉(zhuǎn)Step 2。

Step 2當(dāng)客戶集不為空集的時候，計算各個未訪問客戶的狀態(tài)轉(zhuǎn)移概率。采用輪盤賭法選擇待服務(wù)客戶，轉(zhuǎn)Step 3；否則，轉(zhuǎn)Step 4。

Step 3判斷該車輛里程是否能夠返回車場及容量是否有剩余，如果可以，轉(zhuǎn)Step 2；否則，轉(zhuǎn)Step 1。

Step 4輸出路徑，計算顧客平均滿意度、車輛數(shù)、路徑長度，計算整體目標(biāo)值。

2.3 改進(jìn)蟻群-遺傳算法

Step 1設(shè)置算法初始參數(shù)，導(dǎo)入客戶、車場數(shù)據(jù)，基于啟發(fā)式算法產(chǎn)生初始可行解，詳見2.2.2節(jié)，轉(zhuǎn)Step 2。

Step 2求解本代可行解目標(biāo)值，若NC>2，則R(1)=R_best(NC-1)，其中，R_best(NC-1)為NC-1代最優(yōu)解；否則，轉(zhuǎn)Step 3。

Step 3記錄本次迭代最優(yōu)解，更新信息素，清空禁忌表，轉(zhuǎn)Step 4。

Step 4對該代個體目標(biāo)值進(jìn)行降序排列，選擇前10%作為精英個體，轉(zhuǎn)Step 5。

Step 5基于輪盤賭法隨機(jī)選擇精英個體，利用兩邊逐次修正算法進(jìn)行改良，見2.4.1節(jié)，轉(zhuǎn)Step 6。

Step 6把改良個體加入精英種群，判斷種群是否達(dá)到初始種群規(guī)模，是則轉(zhuǎn)Step 7；否則轉(zhuǎn)Step 5。

Step 7基于輪盤賭法判斷個體是否需要交叉變異，是則基于定點交叉算法對個體進(jìn)行交叉變異，詳見2.4.2節(jié)，轉(zhuǎn)Step 8。

Step 8基于輪盤賭法，選擇正交試驗參數(shù)，詳見2.4.3節(jié)，對交叉變異后的精英種群目標(biāo)值進(jìn)行計算，求其平均值，轉(zhuǎn)Step 9。

Step 9判斷種群平均水平是否得到改善，是則轉(zhuǎn)Step 10；否則轉(zhuǎn)Step 8。

Step 10記錄當(dāng)代種群最優(yōu)解，判斷是否滿足迭代終止條件，是則轉(zhuǎn)Step 11；否則轉(zhuǎn)Step 2。

Step 11輸出最優(yōu)解。

2.4 局部優(yōu)化算法

2.4.1 兩邊逐次修正算法

Step 1輸入需要改良的路徑R。

Step 2按服務(wù)順序選擇潛在改良點，翻轉(zhuǎn)改良點之間路徑，即R(i+1:j)=R(j:-1:I,i+1)。記新路徑為R1，判斷改良點是否均被遍歷，是則轉(zhuǎn)Step 7；否則轉(zhuǎn)Step 3。

Step 3判斷改良點i與j或改良點i+1和j+1是否皆為車輛，是則令i=i+1，轉(zhuǎn)Step 2；否則轉(zhuǎn)Step 4。

Step 4計算R1各車輛行程和荷載，轉(zhuǎn)Step 5。

Step 5判斷路徑R1中行程或荷載是否存在超出額定值的車輛，若存在，令i=i+1，轉(zhuǎn)Step 2；否則轉(zhuǎn)Step 6。

Step 6計算R、R1路徑長度、客戶平均滿意度，分別記為len、len1、S、S1；若len>len1且S

Step 7輸出改良的個體R1。

2.4.2 定點交叉算法

路徑R1經(jīng)過多點、不定點交叉或不定點變異后，易產(chǎn)生未服務(wù)客戶或里程、容量超過額定值的車輛。筆者提出定點交叉算法，使得路徑交叉、變異后仍為可行解，步驟如下：

Step 1從種群中隨機(jī)選擇兩個個體，記為R1、R2，轉(zhuǎn)Step 2。

Step 2從R1、R2中隨機(jī)選擇兩個基因，分別記為a、b，轉(zhuǎn)Step 3。

Step 3利用find(a=R2(1,:))、find(b=R1(1,:))函數(shù)，分別找到a在R2中的位置、b在R1中的位置，分別用p1、p2記錄基因在路徑中的位置，轉(zhuǎn)Step 4。

Step 4算法隨機(jī)把p1、p2位置的基因?qū)?yīng)調(diào)換在R1、R2其他位置(非首位)，產(chǎn)生的新路徑分別記為R_new1、R_new2，轉(zhuǎn)Step 5。

Step 5計算R_new1、R_new2各個車輛的里程及荷載，轉(zhuǎn)Step 6。

Step 6判斷R_new1或R_new2中是否存在超出額定荷載和最大行程的車輛，若存在，轉(zhuǎn)Step 4；否則，轉(zhuǎn)Step 7。

Step 7輸出R_new1、R_new2。

2.4.3 正交參數(shù)設(shè)計

對改良蟻群-遺傳混合算法的5個關(guān)鍵參數(shù)設(shè)計L25(56)正交表，每組參數(shù)的初始績效值Ni=1，各組參數(shù)的選擇概率由式(21)確定：

(21)

Step 1利用輪盤賭法選擇一組參數(shù)應(yīng)用于當(dāng)次迭代，轉(zhuǎn)Step 2。

Step 2判斷種群平均水平是否得到改善，且該組參數(shù)的績效值增加1，是則轉(zhuǎn)Step 3；否則轉(zhuǎn)Step 1。

Step 3記錄當(dāng)前最優(yōu)參數(shù)組合及種群最優(yōu)解。

3 算例分析

3.1 算例描述

某生鮮企業(yè)在該區(qū)域有5個配送中心，每個中心有多種車型，對該區(qū)域25個客戶進(jìn)行配送。每個客戶存在一個模糊預(yù)約時間，客戶所定商品具有一定的保鮮期。配送速度受時間和空間的影響，但不能超過最大限速。求得合適的客戶服務(wù)順序，使得總目標(biāo)值最低。

3.2 算例說明

3.2.1車場車型數(shù)據(jù)

調(diào)整Solomon標(biāo)準(zhǔn)算例R101、R201、C101、C201、RC101、RC201，刪除算例中車場，額外增加5個車場。每個車場存在多種車型，車場車型數(shù)據(jù)見表1、表2。

表1 車場信息

表2 車型信息

3.2.2 客戶位置、時間窗數(shù)據(jù)

在Solomon算例中客戶時間窗基礎(chǔ)上，向兩側(cè)隨機(jī)擴(kuò)展成模糊時間窗，并隨機(jī)生成商品最后交貨期。取交集形成綜合模糊時間窗，用x、y表示坐標(biāo)，C表示客戶需求，l、L、U、u分別表示客戶模糊時間窗上下限，ts表示客戶服務(wù)時間，G表示商品保鮮期。部分客戶數(shù)據(jù)見表3。

表3 客戶數(shù)據(jù)信息

3.2.3 速度時空參數(shù)

設(shè)ρ=2,α=0.5,β=0.5，tm取各算例車場運(yùn)營時間中點，dr0為距離車場中心距離最遠(yuǎn)的客戶到車場中心的距離。

3.2.4 正交試驗參數(shù)

選擇6個參數(shù)，參數(shù)水平見表4。設(shè)計L25(56)正交表，部分見表5。其中，M、δ、μ、ε、Pc、Pm分別表示螞蟻數(shù)、信息素啟發(fā)式因子、期望啟發(fā)因子、信息素蒸發(fā)因子、交叉率、變異率。

表4 正交試驗參數(shù)水平

表5 正交試驗表

3.2.5 算法運(yùn)行環(huán)境

算法運(yùn)行環(huán)境為CPU2.20 GHz,內(nèi)存為4.00 GB,操作系統(tǒng)為64位Windows10,編程語言采用MATLAB R2016a。

3.3 不同模型相同算法比較結(jié)果

表6 不同模型計算結(jié)果對比

設(shè)其他條件不變，對不同類型的時間窗展開討論，可見對不同分布特征下的客戶，不同類型時間窗車輛配送距離和車輛使用數(shù)量差別不大，IFTW模型相比FTW和GTW模型的客戶平均滿意度較高。

因此，綜合考慮路網(wǎng)擁堵特征、客戶時間窗、商品保鮮期的生鮮配送模型可以有效平衡配送時效性和配送時間窗不確定性的矛盾。

3.4 相同模型不同算法比較結(jié)果

為測試結(jié)合蟻群算法、遺傳算法、兩邊逐次修正算法提出的改進(jìn)蟻群-遺傳算法的有效性。將改進(jìn)算法的各部分分別對不同分布特征的客戶群進(jìn)行求解，并與改進(jìn)算法求解結(jié)果進(jìn)行對比。即用改進(jìn)蟻群-遺傳算法(IACGHA)中的蟻群算法(ACO)模塊、嵌入兩邊逐次修正算法的改進(jìn)遺傳算法(IGA)模塊、去除兩邊逐次修正算法的遺傳算法(GA)模塊分別對不同分布特征的客戶群進(jìn)行求解，將求解結(jié)果分別與改進(jìn)蟻群-遺傳算法(ACO-GA)的求解結(jié)果進(jìn)行對比，以檢驗ACO-GA算法的求解能力，對比結(jié)果見表7。ACO算法的螞蟻數(shù)M=50，信息素啟發(fā)因子β=2.5，期望啟發(fā)因子μ=4.5，信息素會發(fā)因子ε=0.4，信息素強(qiáng)度Q=100。GA和IGA除嵌入兩邊逐次修正算法的差異外，其他參數(shù)相同。其中，種群規(guī)模NP=100,交叉率Pc=0.7，變異率Pm=0.006，算法迭代次數(shù)G=500。

表7 不同算法改進(jìn)百分比對比

由表7可知，雖然針對部分?jǐn)?shù)據(jù)，改進(jìn)蟻群-遺傳算法計算結(jié)果不如傳統(tǒng)算法，但整體上ACO-GA算法計算能力優(yōu)于傳統(tǒng)算法，平均優(yōu)化5%以上。由此可見，改進(jìn)蟻群-遺傳算法相比于傳統(tǒng)算法，計算能力更強(qiáng)，優(yōu)化效果更好。然而因算法中嵌套正交試驗設(shè)計等局部優(yōu)化模塊，使得算法以最大迭代次數(shù)作為迭代終止條件時，計算時間較長。

4 結(jié) 語

為解決生鮮配送時效性和配送時間不確定的矛盾及應(yīng)對生鮮配送多配送中心化的趨勢，筆者綜合考慮客戶時間窗、商品保鮮期、配送速度的時空特點，建立起綜合模糊時間窗和速度的時空函數(shù)，以反映生鮮配送過程中的時間不確定性；建立多車場多車型生鮮配送路徑優(yōu)化模型，以反映生鮮配送多配送中心化的特點。采用不同類型的Solomon算例反映不同分布情況的客戶特點?？紤]到在時變路網(wǎng)下考慮時間窗的多車場多車型車輛路徑優(yōu)化模型較為復(fù)雜，提出在傳統(tǒng)蟻群-遺傳算法的基礎(chǔ)上，嵌入兩邊逐次修正算法、正交實驗設(shè)計等局部優(yōu)化模塊的改進(jìn)蟻群-遺傳算法，對該問題進(jìn)行求解。

結(jié)果表明，考慮多配送中心的綜合模糊時間窗和速度時空演變函數(shù)的生鮮配送模型更符合實際，可有效緩解配送時效性和配送時間不確定性之間的矛盾，且改進(jìn)蟻群-遺傳算法相對傳統(tǒng)算法求解效率更高。文中模型和算法可為生鮮配送企業(yè)制定調(diào)度計劃提供參考。