摘 要：為降低物流配送過程中的能耗和碳排放量，對物流配送路徑進行優(yōu)化顯得非常必要。針對傳統(tǒng)PSO算法易陷入局部最優(yōu)、過早收斂等問題，提出了一種基于改進PSO算法的物流配送路徑規(guī)劃方法，通過調(diào)整算法的權(quán)重系數(shù)和學(xué)習(xí)因子，避免算法誤入局部最優(yōu)極值，優(yōu)化算法收斂。經(jīng)仿真結(jié)果表明，改進PSO算法與傳統(tǒng)PSO算法的路徑規(guī)劃方法相比，在配送地點數(shù)相等的條件下，改進PSO算法比傳統(tǒng)PSO算法規(guī)劃路徑更短，相對綜合成本更低，且改進PSO算法比傳統(tǒng)PSO算法規(guī)劃路徑縮短14.18%。

關(guān)鍵詞：改進PSO算法;路徑規(guī)劃;參數(shù)調(diào)整;優(yōu)化控制

中圖分類號：TP39 文獻標識碼：A" 文章編號：1674-0033（2024）06-0039-06

引用格式：張得龍，張敏.改進PSO算法的物流配送路徑規(guī)劃方法[J].商洛學(xué)院學(xué)報，2024，38（6）：39-44.

Logistics Distribution Path Planning Method Based on Improved PSO

ZHANG De-long1，2， ZHANG Min3

（1.School of Intelligent Manufacturing， Weifang University of Science and Technology， Weifang" 262700， Shandong; 2.Department of Computer Science， Dongshin University， Naju" 58245， Jeollanam; 3.School of Information Engineering， Shandong Management University， Jinan 250357， Shandong）

Abstract： In order to reduce energy consumption and carbon emissions in the logistics distribution process， it is necessary to optimize the logistics distribution routes. Based on the traditional PSO， and addressing issues such as being prone to local optima and premature convergence， a logistics distribution planning method based on an improved PSO is proposed， addressing issues such as premature convergence. The proposed method improves the algorithm by adjusting the weight coefficients， preventing the algorithm from falling into local optima and enhancing convergence. Simulation results， compared with the path planning method of the traditional PSO， show that this method results in shorter paths. Under the same node count conditions， the relative comprehensive cost is lower， with the improved PSO shortening the path by 14.18% compared to the traditional PSO.

Key words： improved PSO algorthm; path planning; parameter adjustment; control optimization

據(jù)科學(xué)數(shù)據(jù)表明，全球因配送運輸產(chǎn)生的碳排放量占到全球碳排放總量的25%～30%[1]。低碳大環(huán)境下，政府發(fā)展綠色技術(shù)創(chuàng)新，推動降低碳排放和能耗，減少環(huán)境污染。優(yōu)化倉儲配送中心布局，科學(xué)規(guī)劃物流配送路徑，能夠極大程度地降低物流運輸配送過程中產(chǎn)生的碳排放量。在解決路徑規(guī)劃的問題上，研究者進行了很多經(jīng)典算法的研究，如Dijkstra 算法[2]、遺傳算法（Genetic Algorithm，GA）[3]、快速擴展隨機樹算法（Rapidly-exploring Random Tree，RRT）、速度障礙法[4]、粒子群算法（Particle Swarm Optimization，PSO）[5]、A*算法、蟻群優(yōu)化算法（Ant Colony Optimization，ACO）[6]、黏菌算法[7]（Slime Mould Algorithm，SMA）等，這些較為經(jīng)典的算法在物流配送的路徑規(guī)劃問題解決方面，奠定了重要基礎(chǔ)。宮月紅等[8]提出了一種融合GA的改進PSO混合算法，以傳統(tǒng)PSO算法為基礎(chǔ)框架，插入GA中變異、交叉操作，對慣性權(quán)重系數(shù)進行自我動態(tài)優(yōu)化調(diào)整，基本可以避免算法陷入局部最優(yōu)解。張翠玲[9]在多級物流路徑規(guī)劃問題中，提出了兩種不同的改進PSO算法，一種是對量子粒子群算法（QPSO）中的精英粒子使用了新的學(xué)習(xí)機制，提出了改進的PSO算法;另一種是融合反向?qū)W習(xí)、自我優(yōu)化慣性權(quán)重系數(shù)等多策略的改進PSO算法，并通過試驗結(jié)果驗證，在解決路徑優(yōu)化的復(fù)雜組合問題中，前者具有更好的穩(wěn)定性和更高的精度?？涤裣榈萚10]根據(jù)梯度下降法（GD）中的負梯度方向變量變化原則，提出了一種應(yīng)用于機器人路徑優(yōu)化的改進PSO算法，增加自適應(yīng)粒子位置更新系數(shù)，嵌入貪心策略，對搜索效率和精度進行提升，仿真收斂速度更快，同時，路徑優(yōu)化的精度、效率、穩(wěn)定性也得到了一定的提升。研究者們提出了多種經(jīng)典算法來解決物流配送路徑的優(yōu)化問題，但在尋優(yōu)速度、全局優(yōu)化能力、算法復(fù)雜度等方面仍存在一定的不足。鑒于此，本文通過改進傳統(tǒng)的PSO算法，優(yōu)化調(diào)整算法中的權(quán)重系數(shù)和學(xué)習(xí)因子，進一步提高了算法在路徑優(yōu)化中的精度和穩(wěn)定性，并在物流配送路徑規(guī)劃領(lǐng)域影響明顯。

1" PSO概述

PSO是進化計算的一個分支，由Eberhart[11]和Kennedy等[12]提出。該算法的靈感來源于鳥群或魚群覓食行為的研究，通過群體內(nèi)信息共享和個體間的協(xié)作來尋找最優(yōu)解，屬于基于群體協(xié)作的隨機搜索方法。在給定的空間中，粒子群以隨機方式初始化，并通過模擬鳥群或魚群的行為，根據(jù)群體共享信息和個體自身經(jīng)驗，不斷調(diào)整個體的策略，決定下一次迭代時的飛行方向和速度變化[13-14]。在每次迭代中，粒子更新其當(dāng)前空間和時刻的速度和位置，同時記錄局部最優(yōu)值和搜索過程中的全局最優(yōu)值，最終收斂于全局最優(yōu)解。

每個粒子的適應(yīng)度由優(yōu)化后的目標函數(shù)決定。在任意時刻，每個粒子都具有當(dāng)前位置和速度兩個屬性。在迭代優(yōu)化過程中，隨著迭代次數(shù)（即時間）的推進變化，粒子的速度和位置信息會不斷更新。如果搜索空間是多維向量空間，則粒子的速度和位置也相應(yīng)表現(xiàn)為多維向量。假設(shè)n維空間中有m個個體，某一時刻第i個個體位置為Xi，速度為Vi，其計算公式為：

Xi=（Xi1Xi2Xi3…Xin）" " " " " " " " " " " " " " （1）

Vi=（Vi1Vi2Vi3…Vin）" " " " " " " " " " " " " " （2）每一次迭代，都需要找到粒子的局部最優(yōu)點Ppbest（即自身歷史最優(yōu)位置）及全局最優(yōu)點Pgbest（即群體最優(yōu)位置），更新速度與采樣點的公式[15]為：

V=wV+C1R1（Ppbest-X）+C2R2（Pgbest-X）" "（3）

X=X+V" " " " " " " " " " " " " " " " " " （4）其中，i=1，2，…，n，V為第i個粒子在k+1時刻的速度;V為第i個粒子k時刻的速度;ω為慣性權(quán)重系數(shù)，主要影響算法的收斂速度;參數(shù)C1、C2為學(xué)習(xí)因子，并分別代表自身極值和全局極值的最優(yōu)靠近的速度;R1、R2為隨機系數(shù)，R1，R2∈[0，1]。

適應(yīng)度對應(yīng)物流采樣點配送規(guī)劃路徑總長，適應(yīng)度的計算公式為：

S=[n-1

i=1]" " " " " " " "（5）

其中，xi（yi）、xi+1（yi+1）分別表示第i采樣點的橫（縱）坐標和第i+1個采樣點的橫（縱）坐標。

2" PSO算法改進

PSO的收斂速度對算法的效率、結(jié)果的多樣性、全局最優(yōu)解的搜索及算法的穩(wěn)定性都有非常明顯的影響。收斂速度過快，可能造成過早收斂，即在局部最優(yōu)解的附近停滯，無法找到全局最優(yōu)解，這樣就會限制算法的搜索空間，忽略全局探索，錯過全局最優(yōu)解，搜索精度一般不高;收斂速度過慢，雖然算法精度提高，但會導(dǎo)致較長的迭代時間，算法會在全局搜索中花費過多的時間，導(dǎo)致搜索效率降低，尋找最優(yōu)解延遲[16]。

PSO的收斂速度一般取決于慣性權(quán)重系數(shù)ω，ω較大時，PSO收斂較快，反之較慢。采用PSO算法求解物流配送路徑的優(yōu)化問題時間，粒子在當(dāng)前時刻向下一時刻運動的路徑，即代表按照配送需求，從一個配送點向下一配送點的移動路程，所有可能去往的下一配送點就相當(dāng)于粒子群。

2.1 傳統(tǒng)PSO算法

傳統(tǒng)PSO算法迭代流程較為簡單，首先對全部粒子進行隨機初始化，并根據(jù)算法計算當(dāng)前時刻每個粒子的適應(yīng)度，記錄其個體最優(yōu)位置Ppbest與全局最優(yōu)位置Pgpbest，然后更新每個粒子當(dāng)前時刻的位置和速度屬性。其中，每個粒子的速度依據(jù)慣性權(quán)重系數(shù)ω和兩個加速度項進行更新，將影響下一時刻的位置更新。經(jīng)過不斷迭代，粒子逐漸逼近最優(yōu)值，通過比較最大迭代次數(shù)或達到預(yù)設(shè)目標（最優(yōu)值），決定是否結(jié)束算法的迭代，最終輸出全局最優(yōu)解。理論上，PSO算法的過程結(jié)合了全局搜索和局部搜索，適用于一般問題的多種問題解決優(yōu)化。傳統(tǒng)PSO算法運算流程如圖1所示。

2.2 改進的PSO算法

傳統(tǒng)PSO容易過早地產(chǎn)生收斂，而陷入局部最優(yōu)解，影響全局最優(yōu)的搜索，為了解決此問題，如產(chǎn)生早熟收斂等問題，在算法迭代過程中引入慣性權(quán)重系數(shù)ω的控制函數(shù)。在函數(shù)設(shè)計時，使用三角函數(shù)變換策略調(diào)整慣性權(quán)重ω，隨著迭代次數(shù)的增加對慣性權(quán)重系數(shù)ω進行自適應(yīng)調(diào)整，并逐漸降低調(diào)整慣性權(quán)重ω，提高全局搜索的精度。慣性權(quán)重系數(shù)ω調(diào)整公式為：

ω=ω1+ω2×tan（×）" " " " " " " " " " " "（6）其中，M為最大迭代次數(shù)，i為當(dāng)前時刻的迭代次數(shù)。設(shè)置ω1=0.6，ω2=0.4。調(diào)整后的慣性權(quán)重取值變化曲線如圖2所示。

參數(shù)C1、C2分別表示個體學(xué)習(xí)因子和社會學(xué)習(xí)因子，主要影響粒子更新的速度，PSO的收斂速度可以通過調(diào)整C1、C2實現(xiàn)。通常C1較大時，粒子會更多的傾向于依賴個體經(jīng)驗，具有較強的局部搜索能力，C2較大時，粒子會更多的依賴于群體信息，具有較強的全局搜索能力，合理設(shè)置C1、C2可以確保PSO在全局搜索和局部搜索之間取得平衡。學(xué)習(xí)因子C1、C2的調(diào)整公式為：

C1=Co+Co+1×sin（×）" " " " " " " " " "（7）

C2=Co+Co+1×cos（×）" " " " " " " " " （8）

在調(diào)整時，通常使C1隨迭代次數(shù)減小，C2隨著迭代次數(shù)增加，并設(shè)置Co=0.6，Co+1=1.2，隨迭代增加，算法的全局搜索能力相比于局部搜索能力逐漸增強。圖3為個體學(xué)習(xí)因子與社會學(xué)習(xí)因子的變化曲線。

3" 試驗仿真結(jié)果與分析

3.1 實驗環(huán)境

系統(tǒng)仿真實驗所用計算機硬件配置CPU為12th Gen Intel（R） Core（TM） i7-12700H @2.30GHz，內(nèi)存為16 GB，GPU為NVIDIA GeForce MX450，操作系統(tǒng)配置為64位Windows11版本。因仿真需要試驗所需的工具與庫支持要求，系統(tǒng)采用編程環(huán)境為MATLAB 2020a。

3.2 路徑規(guī)劃對比分析

試驗仿真過程中，通過對比傳統(tǒng)PSO和改進PSO算法的路徑規(guī)劃效果，改進的PSO具有一定的優(yōu)勢，在10 000 m2的等長封閉區(qū)域中，隨機設(shè)置30個采樣點，分別采用傳統(tǒng) PSO、改進的PSO進行路徑規(guī)劃，設(shè)定最大迭代次數(shù)為500次，圖4（a）為采用傳統(tǒng)PSO算法進行的路徑規(guī)劃結(jié)果，路徑交叉次數(shù)較多，且配送路徑總長為522.4 m。圖4（b）為采用改進的PSO算法進行的路徑規(guī)劃結(jié)果，路徑交叉次數(shù)明顯減少，配送路徑總長為448.3 m。

3.3 適應(yīng)度迭代過程對比分析

圖5（a）為采用傳統(tǒng)PSO算法進行的適應(yīng)度仿真結(jié)果，圖5（b）為采用改進的PSO算法進行的適應(yīng)度仿真結(jié)果，運行開始后，隨著迭代次數(shù)的增加，適應(yīng)度逐漸趨向穩(wěn)定。改進的PSO，在迭代次數(shù)330次左右時，已經(jīng)基本穩(wěn)定，理論上實現(xiàn)全局最優(yōu)。經(jīng)過500次迭代，改進的PSO算法比傳統(tǒng)PSO算法的路徑總長減少70 m，改進的PSO算法收斂更快，更迅速。

3.4 全局路徑規(guī)劃總長對比分析

在試驗仿真過程中，采用傳統(tǒng)PSO算法和改進的PSO算法，分別選用30個、40個、50個不同采樣點數(shù)進行全局路徑規(guī)劃仿真，通過試驗得出不同采樣點數(shù)的全局規(guī)劃路徑總長結(jié)果，如表1所示。由表1可得出，不同采樣點數(shù)條件下，采用改進的PSO算法，相比采用傳統(tǒng)PSO算法，其規(guī)劃路徑總長明顯變短，路徑長度最多減少14.18%。

4" 結(jié)論

在物流配送路徑規(guī)劃中，通過試驗對比，改進的PSO算法在優(yōu)化配送路線、降低運輸里程方面實現(xiàn)了更為理想的效果。改進的PSO算法引入了正切函數(shù)優(yōu)化慣性權(quán)重系數(shù)，增強粒子在迭代早期的探索性，確保算法能夠跳出局部最優(yōu)解的陷阱;同時引入了正弦、余弦函數(shù)動態(tài)的調(diào)整學(xué)習(xí)因子，算法在各階段的收斂靈活性。改進的PSO算法在路徑規(guī)劃過程中，表現(xiàn)出更強的全局搜索能力、更快的收斂速度和更高的穩(wěn)定性，更有利于滿足實際物流配送中的復(fù)雜需求。

參考文獻：

[1]" 王佳南.基于混沌貓群算法的低碳冷鏈物流配送路徑優(yōu)化[D].沈陽：沈陽大學(xué)，2021：2-3.

[2]" 鄭好，馮虢靚雯，蒲文杰，等.基于Dijkstra算法的封閉環(huán)境全局路徑規(guī)劃[J].汽車實用技術(shù)，2023，48（16）：7-11.

[3]" 陳龍，鄭祥盤，唐曉騰.基于遺傳算法的移動機器人全覆蓋路徑規(guī)劃研究[J].閩江學(xué)院學(xué)報，2023，44（5）：18-27.

[4]" 徐小強，楊家鼎，冒燕，等.基于速度障礙和改進人工勢場算法的無人艇路徑規(guī)劃研究[J].武漢理工大學(xué)學(xué)報，2022，44（7）：96-102.

[5]" 智瀚宇，賈新春，張學(xué)立.無人機路徑規(guī)劃：一種粒子群和灰狼復(fù)合算法[J/OL].控制工程，1-8 [2024-02-24].https：//doi.org/10.14107/j.cnki.kzgc.20221058.

[6]" 方文凱，廖志高.基于融合A*-蟻群優(yōu)化算法的移動機器人全局優(yōu)化[J].現(xiàn)代制造工程，2024（7）：77-84.

[7]" 王軍，楊云霄，李莉.基于改進深度強化學(xué)習(xí)的移動機器人路徑規(guī)劃[J].電子測量技術(shù)，2021，44（22）：19-24.

[8]" 宮月紅，張少君，王明雨，等.基于遺傳-粒子群優(yōu)化算法的USV路徑規(guī)劃方法[J].山東交通學(xué)院學(xué)報，2022，30（1）：29-34.

[9]" 張翠玲.改進PSO算法及其在EC多級物流中的應(yīng)用研究[D].沈陽：沈陽理工大學(xué)，2021：54-55.

[10] 康玉祥，姜春英，秦運海，等.基于改進PSO算法的機器人路徑規(guī)劃及實驗[J].機器人，2020，42（1）：71-78.

[11] KENNEDY J， EBERHART R. Particle swarm optimization[C]//Proceedings of IEEE international conference on neural networks. Perth，1995：1942-1948.

[12] EBERHART R， KENNEDY J. A new optimizer using particle swarm theory[C]//Proceedings of the 6th international symposium on micro machine and human science. nagoya，1995：39-43.

[12] TAO Q Y， SANG H Y， GUO H， et al. Improved particle swarm optimization algorithm for AGV path planning[J].IEEE Access，2021，9：33522-33531.

[13] SUN R T， LIU M D， ZHAO L. Research on logistics distribution Path Optimization based on PSO and IoT[J]. International Journal of Wavelets， Multiresolution and Information Processing，2019，17（6）：1950051.

[14] LIN S W， LIU A， WANG J G， et al. An improved fault-tolerant cultural-PSO with probability for multi-AGV path planning[J].Expert Systems with Applications，2024，237：121510.

[15] 王佳榮，周超.改進PSO及其在機器人路徑規(guī)劃中的應(yīng)用[J].計算機仿真，2024，41（5）：436-440，44.

[16] 孫一凡，張紀會.基于模擬退火機制的自適應(yīng)粘性粒子群算法[J].控制與決策，2023，38（10）：2764-2772.

（責(zé)任編輯：王學(xué)軍）

收稿日期：2024-08-12

基金項目：濰坊科技學(xué)院科技研究項目（KJBS202205）

作者簡介：張得龍，男，山東臨沂人，博士，講師