基于改進(jìn)正余雙弦算法的電商物流配送路徑規(guī)劃

王蕓博

(太原城市職業(yè)技術(shù)學(xué)院 信息工程系，山西 太原 030027)

0 引言

隨著計(jì)算機(jī)和網(wǎng)絡(luò)的迅速發(fā)展,我國(guó)實(shí)體銷售逐漸向網(wǎng)絡(luò)銷售進(jìn)行轉(zhuǎn)型,越來(lái)越多的人更習(xí)慣于網(wǎng)絡(luò)購(gòu)物。對(duì)于電商企業(yè)而言,由于網(wǎng)絡(luò)銷售具有購(gòu)買群體分散、交易延時(shí)且一次性發(fā)貨量較大的特點(diǎn),因此對(duì)于企業(yè)下的物流配送要求較為嚴(yán)格,如何降低物流配送成本,成為電商企業(yè)提高效益的重要指標(biāo)之一[1]。物流配送過(guò)程中,運(yùn)輸費(fèi)用約占配送成本的70%.合理規(guī)劃配送路徑,減少配送車輛,降低運(yùn)輸費(fèi)用是節(jié)約配送成本的有效途徑[2]。針對(duì)上述配送路徑規(guī)劃問(wèn)題,主要的方法是通過(guò)智能算法對(duì)配送路徑進(jìn)行求解。

Mohammed等提出一種基于改進(jìn)遺傳算法的物流配送路徑規(guī)劃策略,有效縮短了配送距離,節(jié)約了配送成本,但算法優(yōu)化時(shí)間較長(zhǎng),且在優(yōu)化過(guò)程中易早熟收斂,降低了搜索精度[3]。尚猛等提出一種改進(jìn)鯊魚(yú)算法的配送優(yōu)化策略,通過(guò)正弦機(jī)制和高斯變異對(duì)算法進(jìn)行改進(jìn),提高了算法的收斂精度,降低了配送成本,縮短了配送時(shí)間[4]。劉曉珍等通過(guò)定向變異策略對(duì)布谷鳥(niǎo)算法進(jìn)行改進(jìn),通過(guò)城市間的距離尋找相鄰城市,縮短配送路徑,但算法搜索時(shí)間較長(zhǎng),不易找到最優(yōu)解[5]。吳征等建立了模糊配送模型,通過(guò)改進(jìn)的混合算法對(duì)模型進(jìn)行求解,縮短了配送里程,降低了配送成本[6]。馬艷芳等提出一種基于改進(jìn)慣性權(quán)重的粒子群算法對(duì)配送模型進(jìn)行求解,通過(guò)自適應(yīng)調(diào)整慣性權(quán)重平衡算法的全局搜索能力和局部搜索能力,提高了算法的收斂精度,節(jié)約了配送時(shí)間,提高了配送效率[7]。

上述優(yōu)化策略均在一定程度上降低了配送成本,但均存在算法早熟收斂、收斂精度不高的問(wèn)題,這是由于算法沒(méi)有針對(duì)全局搜索能力和局部搜索能力進(jìn)行平衡導(dǎo)致。因此本文提出一種改進(jìn)的正余雙弦優(yōu)化算法[8],對(duì)配送路徑進(jìn)行優(yōu)化。通過(guò)精英搜索策略和自適應(yīng)區(qū)域搜索算子策略,提高算法的收斂精度,平衡算法的全局搜索能力和局部搜索能力。

1 物流配送路徑規(guī)劃模型

設(shè)某電商配送中心個(gè)數(shù)為M,待配送點(diǎn)個(gè)數(shù)(即購(gòu)買貨品用戶個(gè)數(shù))為P。如何合理地將M個(gè)配送中心的貨物發(fā)送到P個(gè)待配送點(diǎn),使得配送距離最小、車輛花費(fèi)最少、配送時(shí)間最短是電商物流配送路徑優(yōu)化的主要問(wèn)題。因此在建立電商物流配送路徑規(guī)劃模型時(shí),應(yīng)建立以下幾方面的約束:

1)設(shè)配送路徑上全部車輛的最大承載量均為Cn,同時(shí)要求在每一個(gè)配送路徑上,待配送客戶的需求量總和不能超過(guò)該配送路徑上配送車輛的最大承載量,此約束條件的數(shù)學(xué)模型如下:

(1)

式中,N為配送車輛個(gè)數(shù),qi為第i個(gè)客戶的購(gòu)貨量,ai,n為判定參數(shù)。若ai,n為1,則認(rèn)為第i個(gè)客戶的貨物由第n輛車進(jìn)行配送,否則為0.

2)設(shè)任意一條配送路徑上的全部待配送客戶中,其中任意一個(gè)客戶所購(gòu)買的全部物品均只能由一輛配送車進(jìn)行配送,不允許多個(gè)配送車對(duì)一個(gè)客戶的物品進(jìn)行分批配送。此約束條件的數(shù)學(xué)模型如下:

(2)

3)設(shè)任意一條配送路徑上,配送車輛只能對(duì)同一個(gè)客戶進(jìn)行一次配送,即不能多次對(duì)同一個(gè)客戶進(jìn)行配送。此約束條件的數(shù)學(xué)模型如下:

(3)

式中,bijn為車輛路徑重復(fù)行駛控制參數(shù)。若bijn為1,則表示第n輛車從第i個(gè)客戶配送完成后向第j個(gè)客戶開(kāi)始配送，否則為0.

根據(jù)約束(1)、約束(2)和約束(3),構(gòu)建電商物流配送路徑規(guī)劃的目標(biāo)函數(shù)為:

(4)

式中,sij為配送車輛從第i個(gè)客戶到第j個(gè)客戶所需的配送成本。

2 改進(jìn)的正余雙弦優(yōu)化算法

2.1 基本正余雙弦優(yōu)化算法

正余雙弦優(yōu)化算法(sine cosine algorithm, SCA)是一類基于數(shù)學(xué)特征的元啟發(fā)智能優(yōu)化算法,算法簡(jiǎn)單易于實(shí)現(xiàn)。設(shè)SCA算法的種群規(guī)模為NP,維數(shù)為D,最大迭代次數(shù)為Tmax。因此算法中個(gè)體位置更新公式如下所示:

(5)

從式(5)中可知,區(qū)域搜索算子R1用于控制正弦全局搜索區(qū)域和余弦局部搜索區(qū)域的范圍,其數(shù)學(xué)表達(dá)式如式(6)所示。R1在迭代前期較大,算法可以大范圍進(jìn)行全局搜索,使得算法在迭代前期盡可能將全局最優(yōu)解包含在搜索范圍內(nèi)。R1在迭代過(guò)程中線性減小,使得算法在迭代后期的搜索范圍較小,有利于算法在當(dāng)前極值點(diǎn)附近進(jìn)行精確搜索。α為常數(shù)，取值為2。

(6)

R2作為移動(dòng)控制因子,控制個(gè)體遠(yuǎn)離或靠近目標(biāo)。R3為最優(yōu)位置權(quán)重系數(shù),當(dāng)R3≥1時(shí),加大最優(yōu)解對(duì)當(dāng)前個(gè)體的吸引力,當(dāng)R3<1時(shí),則減小最優(yōu)解對(duì)當(dāng)前個(gè)體的吸引力。R4控制正弦全局搜索和余弦局部搜索的概率。

2.2 精英搜索

(7)

式中,N(μ,δ2)為正態(tài)分布概率密度函數(shù),其計(jì)算方式如下所示:

(8)

2.3 自適應(yīng)區(qū)域搜索算子

由式(5)中區(qū)域搜索算子R1可知,種群中每個(gè)個(gè)體均依照區(qū)域搜索算子R1線性改變搜索步長(zhǎng)和搜索范圍,雖然在一定程度上,對(duì)算法的全局搜索能力和局部開(kāi)發(fā)能力進(jìn)行了平衡處理,但線性遞減的規(guī)律并不符合優(yōu)化的過(guò)程。在優(yōu)化過(guò)程中,種群中每個(gè)個(gè)體在進(jìn)行全局搜索和局部搜索轉(zhuǎn)換的時(shí)間并不應(yīng)該是完全相同的。適應(yīng)度值較優(yōu)的個(gè)體應(yīng)盡快減小搜索范圍,使得較優(yōu)個(gè)體可以小范圍進(jìn)行精確搜索,提高收斂精度,加快搜索時(shí)間。適應(yīng)度值較差的個(gè)體,應(yīng)繼續(xù)進(jìn)行大范圍的搜索,使得較差個(gè)體可以向全局最優(yōu)解不斷靠攏,提高算法的全局搜索能力,同時(shí)也防止算法早熟收斂陷入局部最優(yōu)。針對(duì)上述問(wèn)題,本文引入一種以適應(yīng)度值為基準(zhǔn)的自適應(yīng)慣性權(quán)重,對(duì)算法的區(qū)域搜索算子R1進(jìn)行改進(jìn)。改進(jìn)后的區(qū)域搜索算子R1-new如下所示:

(9)

式中,fitnessmin(t)和fitnessmax(t)為當(dāng)前迭代中,全部個(gè)體中計(jì)算所得的最小適應(yīng)度值和最大適應(yīng)度值,fitnessi(t)表示第i個(gè)個(gè)體在第t次迭代時(shí)計(jì)算所得適應(yīng)度值。R1-new的取值范圍在[0,1]之間。改進(jìn)后的個(gè)體位置更新公式如下所示:

(10)

改進(jìn)后的正余雙弦算法的優(yōu)化步驟如下所示:

1)種群初始化,其中種群規(guī)模為NP,維數(shù)為D,最大迭代次數(shù)為Tmax;

2)計(jì)算種群中的全部個(gè)體的適應(yīng)度函數(shù)值,并記錄最優(yōu)值Pbest,適應(yīng)度最大值fitnessmax和最小值fitnessmin;

3)根據(jù)式(9)計(jì)算種群中全部個(gè)體對(duì)所對(duì)應(yīng)的區(qū)域搜索算子R1-new,并通過(guò)式(10)對(duì)個(gè)體進(jìn)行位置更新;

4)計(jì)算位置更新后的全部個(gè)體的適應(yīng)度函數(shù)值,并記錄最優(yōu)值Pbest;

5)根據(jù)精英策略對(duì)最優(yōu)解Pbest進(jìn)行正態(tài)變異,并將所得結(jié)果Pnewbest與Pbest進(jìn)行精英選擇;

6)判斷是否達(dá)到最大迭代次數(shù),若是則輸出當(dāng)前最優(yōu)解，否則返回第2步。

2.4 基于測(cè)試函數(shù)的性能測(cè)試

為了驗(yàn)證本文所提改進(jìn)正余雙弦算法(Improved sine cosine algorithm, ISCA)的算法性能,本文選擇8個(gè)基準(zhǔn)測(cè)試函數(shù)F對(duì)ISCA算法進(jìn)行數(shù)值仿真實(shí)驗(yàn),對(duì)算法的收斂精度和穩(wěn)定性進(jìn)行驗(yàn)證。8個(gè)測(cè)試函數(shù)如表1所示。其中F1—F5為單峰測(cè)試函數(shù),用于驗(yàn)證ISCA算法的局部開(kāi)發(fā)能力,F6—F8為多峰測(cè)試函數(shù),用于驗(yàn)證ISCA算法的全局搜索能力。為了說(shuō)明實(shí)驗(yàn)結(jié)果的有效性,本文將實(shí)驗(yàn)結(jié)果與自適應(yīng)動(dòng)態(tài)雞群算法 (ADLCSO)[9]和改進(jìn)粒子群算法(IPSO)[10]的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比驗(yàn)證。為保證對(duì)比結(jié)果的公平性,三種算法的種群規(guī)模均為100,迭代次數(shù)均為200.三種算法獨(dú)立運(yùn)行50次,取得實(shí)驗(yàn)結(jié)果的最小值、平均值和標(biāo)準(zhǔn)差。實(shí)驗(yàn)結(jié)果如表2所示。

表1 測(cè)試函數(shù)Table1 Test function

從表2可知,對(duì)于單峰測(cè)試函數(shù)F1—F5而言,本文所提ISCA算法求解的最小值和平均值最小,說(shuō)明相較自適應(yīng)動(dòng)態(tài)雞群算法和改進(jìn)粒子群算法而言,ISCA的局部搜索能力較強(qiáng),這是由于加入精英搜索后,種群中的劣質(zhì)個(gè)體均被最優(yōu)個(gè)體所替代,使得種群中全部個(gè)體的質(zhì)量較高,有利于局部搜索。同時(shí),ISCA算法求解的標(biāo)準(zhǔn)差同樣最小,說(shuō)明ISCA算法的尋優(yōu)穩(wěn)定性更強(qiáng),不易陷入局部最優(yōu)早熟收斂。

表2 測(cè)試函數(shù)測(cè)試結(jié)果Table 2 Results of test functions

對(duì)于多峰測(cè)試函數(shù)而言,ISCA算法求解的最小值和平均值同樣最小,說(shuō)明ISCA算法的全局搜索能力要優(yōu)于自適應(yīng)動(dòng)態(tài)雞群算法和改進(jìn)粒子群算法。同時(shí)也說(shuō)明改進(jìn)后的區(qū)域搜索算子R1-new可以更加平衡算法的全局搜索能力和局部開(kāi)發(fā)能力,使得適應(yīng)度值較差的個(gè)體可以充分地進(jìn)行全局搜索,向全局極值點(diǎn)靠近。適應(yīng)度值較優(yōu)的個(gè)體,也可以在全局極值點(diǎn)附近進(jìn)行快速的精確搜索,提高開(kāi)發(fā)能力?？傮w而言,通過(guò)精英策略和自適應(yīng)區(qū)域搜索算子改進(jìn)后的正余雙弦算法,全局搜索能力和局部開(kāi)發(fā)能力得到了有效的平衡,同時(shí)也提高了算法的收斂精度和整體尋優(yōu)性能。

3 仿真

某電商以A城市為物流配送中心,對(duì)31個(gè)城市進(jìn)行貨品配送。其中包含配送中心A城市在內(nèi)的32個(gè)城市的坐標(biāo)以及31個(gè)配送城市的貨品需求量如表3所示,配送中心A城市的序號(hào)設(shè)為0。

表3 32個(gè)城市的基本信息Table 3 Basic information of thirty-two cities

本文通過(guò)改進(jìn)的正余雙弦算法對(duì)電商物流配送路徑進(jìn)行優(yōu)化,并將實(shí)驗(yàn)結(jié)果與自適應(yīng)動(dòng)態(tài)雞群算法和改進(jìn)粒子群算法的優(yōu)化結(jié)果進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果如表4—表6以及圖1—圖3所示。在模型中,設(shè)配送車輛個(gè)數(shù)為5,其中車輛1的最大行駛里程和最大承載量分別為200 km和100 kg。車輛2,3,4,5的最大行駛里程和最大承載量均為2 000 km和100 kg。其中每1 km的物品配送10 kg的價(jià)格為1元。

表4 改進(jìn)正余雙弦算法的優(yōu)化結(jié)果Table 4 The optimization results of the improved sine cosine algorithm for sequential quadratic programming

表5 自適應(yīng)動(dòng)態(tài)雞群算法的優(yōu)化結(jié)果Table 5 Optimization results of adaptive dynamic chicken colony algorithm

表6 改進(jìn)粒子群算法的優(yōu)化結(jié)果Table 6 Optimization results of improved particle swarm optimization

圖1 改進(jìn)正余雙弦算法的配送路徑Fig.1 The distribution path of improved sine cosine algorithm in sequential quadratic programming

圖2 自適應(yīng)動(dòng)態(tài)雞群算法的配送路徑Fig.2 Distribution path of adaptive dynamic chicken colony algorithm

圖3 改進(jìn)粒子群算法的配送路徑Fig.3 Distribution path of improved particle swarm optimization

從表4—表6及圖1—圖3可知,本文所提改進(jìn)正余雙弦算法相較自適應(yīng)動(dòng)態(tài)雞群算法和改進(jìn)粒子群算法而言,配送路程節(jié)省了7.18 km和37.16 km，總配送金額節(jié)約了294.30元和1 523.56元。很大程度上縮短了配送路徑，節(jié)約了配送成本，有效提高了電商企業(yè)的效益。

4 結(jié)論

本文針對(duì)電商物流配送路徑優(yōu)化問(wèn)題,提出一種改進(jìn)正余雙弦優(yōu)化算法的優(yōu)化策略。同時(shí)針對(duì)傳統(tǒng)正余雙弦算法收斂精度低的問(wèn)題,通過(guò)精英策略和自適應(yīng)區(qū)域搜索算子策略進(jìn)行改進(jìn),有效平衡了算法的全局搜索能力和局部開(kāi)發(fā)能力,提高了算法的收斂精度和整體尋優(yōu)能力。最后，通過(guò)改進(jìn)后的正余雙弦算法對(duì)電商物流配送模型進(jìn)行優(yōu)化求解。實(shí)驗(yàn)結(jié)果表明,通過(guò)改進(jìn)正余雙弦算法優(yōu)化后的配送路徑,節(jié)約了配送成本,縮短了配送路程，提高了配送效率。