基于改進(jìn)離散粒子群算法的生鮮農(nóng)產(chǎn)品配送路徑設(shè)計(jì)

孫宗軍，馬佳玉，徐海鑫 SUN Zongjun,MA Jiayu,XU Haixin

（山東科技大學(xué) 交通學(xué)院，山東 青島 266590）

(Transportation College,Shandong University of Science and Technology,Qingdao 266590,China)

0 引言

運(yùn)輸成本的控制一直是物流行業(yè)的熱點(diǎn)問(wèn)題之一，因生鮮農(nóng)產(chǎn)品的配送對(duì)時(shí)效性、準(zhǔn)確性要求較高，生鮮農(nóng)產(chǎn)品的高運(yùn)輸成本成為制約生鮮農(nóng)產(chǎn)品物流體系發(fā)展的難點(diǎn)，優(yōu)化配送路徑是提高配送效率、降低運(yùn)輸成本的重要方法[1]。目前，生鮮農(nóng)產(chǎn)品的配送路徑優(yōu)化常采用傳統(tǒng)的路徑優(yōu)化方式[2]，即運(yùn)輸車依次經(jīng)過(guò)需要配送的n個(gè)站點(diǎn)再回到始發(fā)點(diǎn)，求解最短路徑。然而，傳統(tǒng)的路徑優(yōu)化往往無(wú)法得到真實(shí)的最短路徑，增加了運(yùn)輸成本。本文通過(guò)改進(jìn)的粒子群算法[3]，以RH農(nóng)場(chǎng)為例，對(duì)其生鮮農(nóng)產(chǎn)的配送進(jìn)行了路徑優(yōu)化，降低配送成本。

1 RH農(nóng)場(chǎng)的基本概況及現(xiàn)狀分析

RH農(nóng)場(chǎng)的主要生鮮農(nóng)產(chǎn)品包括水果類、蔬菜類、肉類、花類等。對(duì)市區(qū)范圍內(nèi)的18個(gè)配送點(diǎn)進(jìn)行了地理數(shù)據(jù)采集，RH為農(nóng)場(chǎng)，A、B為現(xiàn)有的兩家門店，C為虛擬配送中心，如圖1和圖2所示。

2 改進(jìn)粒子群算法

粒子群算法采用實(shí)數(shù)編碼是其顯著優(yōu)點(diǎn)，不需要采用二進(jìn)制編碼來(lái)進(jìn)行最優(yōu)解的運(yùn)算。在設(shè)置好適應(yīng)度函數(shù)后就可進(jìn)行搜索最優(yōu)解，直到滿足中止條件后終止運(yùn)算。

2.1 TSP離散型粒子群算法

程畢蕓[4]提出了搜索混沌離散粒子群優(yōu)化算法，優(yōu)化后的粒子群算法參數(shù)如式（1）和式（2）所示。

粒子的更新后速度：

粒子的更新后位置：

圖1 RH與各配送中心相對(duì)位置示意圖

圖2 RH與各配送點(diǎn)相對(duì)位置示意圖

當(dāng)配送點(diǎn)的個(gè)數(shù)小于等于30時(shí)，迭代次數(shù)達(dá)到60左右即可達(dá)到最優(yōu)。本文中配送點(diǎn)個(gè)數(shù)有18個(gè)，設(shè)置迭代次數(shù)設(shè)為60，粒子數(shù)為200。

2.2 2SGPSO算法改進(jìn)

2SGPSO算法在解決物流運(yùn)輸路徑問(wèn)題時(shí)，首先利用GPSO算法對(duì)配送站點(diǎn)序列進(jìn)行搜索尋優(yōu)操作，得到最優(yōu)配送站點(diǎn)序列和最短距離。然后利用2SA算法對(duì)GPSO算法得到的最優(yōu)配送站點(diǎn)序列進(jìn)行操作，最終得到的最優(yōu)配送站點(diǎn)序列和最短路徑距離。操作流程如下所示[4]。

輸入：粒子群個(gè)數(shù)、配送點(diǎn)個(gè)數(shù)、配送點(diǎn)坐標(biāo)

（1）初始化粒子速度及位置。

（3）根據(jù)公式更新粒子位置速度。

輸出：Gbest

2.3 ACPSO算法改進(jìn)

ACPSO中設(shè)n個(gè)需要經(jīng)過(guò)的點(diǎn)，任選其中第j1次和第j2次經(jīng)過(guò)的點(diǎn)，在路徑C0中將第j1次和第j2次經(jīng)過(guò)的點(diǎn)進(jìn)行交換，其余點(diǎn)順序不變，變化后的路徑定義為C1；n個(gè)點(diǎn)，任意選取一個(gè)交叉區(qū)域，將old2的交叉區(qū)域添加至old1中隨機(jī)選取的位置，且將old1在old2交叉區(qū)中已經(jīng)過(guò)的點(diǎn)刪除。操作流程如下[5]：

輸入：粒子群、配送點(diǎn)個(gè)數(shù)、配送點(diǎn)坐標(biāo)、最大迭代次數(shù)、隨機(jī)產(chǎn)生對(duì)個(gè)數(shù)的初始解C0

（1）初始化粒子速度及位置。

（3）根據(jù)公式進(jìn)行更新位置：

若：第j個(gè)粒子的路徑C0（j）與個(gè)體最優(yōu)交叉得到C1（j），C1（j）同Gbest交叉到C2（j），C2（j）經(jīng)過(guò)變異操作變?yōu)橄乱淮蔚某跏冀馄渲?，d（ I,j ）＜Pbest（j），則進(jìn)行上述交叉操作，否則進(jìn)行自身變異；

（4）得到當(dāng)前迭代次數(shù)下的適應(yīng)值。

輸出：Gbest及路徑

3 最短路徑優(yōu)化

3.1 常規(guī)路徑優(yōu)化

根據(jù)描繪的實(shí)際位置分別做出A、B、C三個(gè)配送點(diǎn)到需求點(diǎn)的賦權(quán)（無(wú)向）圖，如圖3所示。

圖3 以A、B、C為配送點(diǎn)到各需求點(diǎn)的賦權(quán)圖

運(yùn)用Lingo11軟件求解以A、B、C點(diǎn)為配送中心的最短配送距離：以A點(diǎn)為中心1.5km范圍內(nèi)的最短配送距離為8.64km，配送路徑為A→a5→a4→a3→a1→a2；以B點(diǎn)為中心3km范圍內(nèi)的最短配送距離為18.3km，配送路徑為B→b2→b1→b4→b5→b3；以C點(diǎn)為中心2.2km范圍內(nèi)的最短配送距離為11.77km，配送路徑為C→c4→c3→c1→c2。

由農(nóng)場(chǎng)到全部需求配送點(diǎn)的最短距離為91.91km，配送路徑為RH→a1→a2→A→a4→a3→b4→b5→B→b3→b2→b1→C→c2→c1→c3→c4→a5→RH。

3.2 基于改進(jìn)離散粒子群的路徑優(yōu)化

3.2.1 以A、B、C為配送中心的路徑優(yōu)化

將各配送點(diǎn)的相對(duì)坐標(biāo)導(dǎo)入，通過(guò)MATLAB2016得到ACPSO改進(jìn)粒子群算法與2SGPSO改進(jìn)粒子群算法的收斂曲線如圖4、圖5所示。

圖4 ACPSO算法的收斂曲線

圖5 2SGPSO算法的收斂曲線

表1、表2統(tǒng)計(jì)了兩種算法的運(yùn)行結(jié)果，可以發(fā)現(xiàn)：ACPSO改進(jìn)粒子群算法軟件運(yùn)行結(jié)果顯示收斂效果較好，較快。迭代30次以后，即趨于穩(wěn)定；2SGPSO改進(jìn)粒子群算法軟件運(yùn)行結(jié)果顯示收斂速度較慢，容易形成局部最優(yōu)。

表2 2SGPSO算法運(yùn)行結(jié)果

綜合兩種改進(jìn)粒子群算法以及常規(guī)路徑優(yōu)化結(jié)果，ACPSO算法求得的以A、B、C三個(gè)配送點(diǎn)為起點(diǎn)配送路徑長(zhǎng)度最優(yōu)：A→a2→a1→a3→a4→a5，最短路徑為 6.74km；B→b2→b1→b4→b5→b3，最短路徑為 14.6km；C→c1→c2→c3→c4，最短路徑為8.74km，如圖6所示。2SGPSO改進(jìn)算法中獲取最優(yōu)目標(biāo)函數(shù)過(guò)程波動(dòng)較小，收斂運(yùn)算速度快，針對(duì)優(yōu)化對(duì)象數(shù)量較小的模型，效果一般。

圖6 ACPSO算法優(yōu)化的以A、B、C為配送點(diǎn)的最優(yōu)路徑圖

3.2.2 以農(nóng)場(chǎng)為配送中心的路徑優(yōu)化

將全部配送點(diǎn)坐標(biāo)代入兩種改進(jìn)算法中，再次求解取消配送點(diǎn)的情況下，由農(nóng)場(chǎng)直接配送到各個(gè)需求點(diǎn)的全局路徑，結(jié)果如表3所示。

表3 全局路徑的運(yùn)行結(jié)果

圖7 兩種算法求解全局路徑的收斂曲線圖

圖8 2SGPSO算法的全最優(yōu)路徑

如圖7，從全路徑優(yōu)化來(lái)看，2SGPSO求解全部路徑收斂速度快，收斂效果好，在迭代40～50前后趨于穩(wěn)定。2SGPSO算法求解的最優(yōu)路徑的路徑如圖8所示。全局配送最短路徑為：RH→a1→b4→B→b3→b5→b2→b1→c1→c2→C→c3→c4→a5→a4→A→a2→a1→RH，最短路徑為85.01km。

4 結(jié)論

本文介紹了ACPSO算法與2SGPSO算法在RH農(nóng)場(chǎng)生鮮農(nóng)產(chǎn)品物流路徑設(shè)計(jì)優(yōu)化中的應(yīng)用，結(jié)合運(yùn)行MATLAB軟件得出以A、B、C為起始配送點(diǎn)的最短配送路徑以及由農(nóng)場(chǎng)直接配送的最短配送路徑。ACPSO算法更加適合小范圍內(nèi)最優(yōu)路徑設(shè)計(jì)，ACPSO算法得到的最優(yōu)值明顯優(yōu)于2SGPSO算法；2SGPSO算法下的收斂速度較快，多次迭代后趨于穩(wěn)定，更加適合進(jìn)行數(shù)量較多的配送點(diǎn)的路徑設(shè)計(jì)優(yōu)化。