基于統計步長PSO算法的煙草配送線路優化方案研究

錢漫 鐘培泉 張亞萍 張振軍

摘 要：煙草配送線路優化問題是煙草行業物流層面的重點問題之一。微粒群算法（Particle Swarm Optimization，簡稱PSO）是一種利用群體智能的隨機全局優化方法，廣泛應用于路徑尋優、函數優化等領域。為了提高PSO算法的全局搜索能力，本文在標準PSO算法的基礎上，定義了一種基于統計步長的微粒群算法：針對PSO算法易出現局部極值問題，引入慣性權重因子進行改進;針對PSO算法中加速步長為常量值而不符合實際情況的問題，定義了基于統計的加速步長進化方程。實踐證明，本文研究的算法應用于煙草配送線路優化方案中，可以大大節約運輸里程及運輸成本。

關鍵詞：線路優化;微粒群算法（PSO）;煙草配送線路優化方案

中圖分類號：F252 文獻標識碼：A 文章編號：1003-5168（2021）09-0028-03

Abstract： he optimization of tobacco distribution routes is one of the key issues at the logistics level of the tobacco industry. Particle swarm optimization （PSO） is a stochastic global optimization method using swarm intelligence， which is widely used in route optimization， function optimization and other fields. In order to improve the global search ability of PSO algorithm， based on the standard PSO algorithm， the paper defined a particle swarm optimization algorithm based on statistical step size： aiming at improving the global search ability of PSO algorithm， the inertia weight factor was defined; aiming at solving the problem that the acceleration step size in PSO algorithm was constant， the evolution equation of acceleration step size based on statistics was defined. The practice shows that the algorithm studied in this paper can greatly save the transportation mileage and transportation cost when it is applied to the tobacco distribution route optimization model.

Keywords： route optimization;particle swarm optimization （PSO）;tobacco distribution route optimization plan

在煙草行業降本增效的大背景下，伴隨著煙草物流配送業務的快速發展，成本問題成為制約煙草物流業的突出問題。如何經濟、高效地進行卷煙配送成為煙草物流業務重點關注的問題之一。配送線路優化正是以距離最短、成本最低為目標的解決方案。配送線路優化方面的研究較多。謝萍等[1]針對鄉鎮執法部門的外業巡查工作效率問題，通過空間聚類形成巡查片區、車輛路徑優化模型進行線路規劃等兩階段設計了土地利用執法巡查路徑優化模型;周愛蓮等[2]針對卡車-無人機共同配送問題，在滿足卡車可達性前提下以總配送時間最短為目標建立了混合整數規劃模型;陳汐等[3]針對通勤類型定制公交線路規劃問題，以乘客出行成本最小、車輛運營成本最優為目標，構建多區域運營模式的通勤定制公交線路規劃模型，并以兩階段啟發式算法求解多目標優化模型;許智宏等[4]針對線路優化算法動態性能不佳及大規模數據處理性能不足等問題，研究了基于遺傳算法的大數據車輛動態線路調度模型，模型考慮了線路與時間對成本的影響，通過設計懲罰因子來改善遺傳算法的收斂性與尋優性等。

微粒群算法是一種利用群體智能的隨機全局優化方法，它具有易實現、可調參數少、全局搜索能力強等優點，但存在易陷入局部極值、常量值的加速步長無法反映實際粒子飛行狀況等問題。因此，本文以基本的微粒群算法為基礎，定義了一種基于統計步長的微粒群算法：針對局部極值問題，算法引入慣性權重因子進行改進;針對加速步長常量值問題，算法定義了基于統計的加速步長進化方程。實踐證明，本文所提的算法應用于煙草配送線路優化方案中，可以大大節約運輸里程及運輸成本。

1 微粒群算法

微粒群算法（Particle Swarm Optimization，簡稱PSO）[5-6]是群體智能算法的一種，基本思想是通過群體中的個體相互協作和信息共享尋找最優解，目前廣泛應用于路徑尋優、函數優化、組合優化等各類優化問題。

基本微粒群算法的速度進化方程、位置進化方程如下：

式中，[vij（t）]為第[t]次迭代粒子的速度;[xij（t）]為第[t]次迭代粒子的位置;[r1j（t）]、[r2j（t）]為兩個獨立的隨機函數;[pij（t）]為從開始到第[t]次迭代時個體最好位置或最優解;[pgj（t）]為從開始到第[t]次迭時全局最好位置或最優解;[c1]、[c2]為加速度常數。

微粒群算法具有易實現、可調參數少、全局搜索能力強等優點。微粒群算法研究較多。例如，高明瑤等[7]針對軌道交通接運公交的站點設置與線路布局問題，以接運乘客的客運周轉量最大化為目標函數，以公交線路長度和剩余客流量、區段剩余通過量為約束條件，以粒子群算法求解公交線路最優解;張耀軍等[8]針對車輛路徑優化問題，研究了一種改進的量子PSO算法，其以2-opt算法和1-1交換算法為局部優化算法，以種群熵算法為衡量算法;董鍇等[9]針對電力系統評估結果誤差較大的問題，利用PSO算法探求電力系統狀態評估的最優策略。

2 基于統計步長的微粒群算法模型

微粒群算法雖然有很多優點，但還存在一些不足：第一，微粒群算法易陷入局部極值問題;第二，微粒群算法中的加速步長為常數，無法反映實際粒子的飛行狀況。針對上述不足，本文提出了一種改進的微粒群算法——基于統計步長的微粒群算法。算法改進后，速度進化方程被改進為：

3 煙草配送線路優化方案

煙草配送線路優化目標是以最優路線、最低成本和最快時間將卷煙從配送中心送到目的地。為了解決煙草配送過程中過遠運輸、重復運輸、無效運輸等問題，本文定義了煙草配送線路優化方案。其間定義的運輸平衡方程為：

步長為1次，重復執行下文所述步驟，直到車輛平均裝載率達到70%為止。

利用基于統計步長的PSO算法求解，并確定路徑最優方案，求解步驟如下。

一是設置PSO算法的初始參數，包括群體規模、加速度[c1]和[c2]、慣性權重[wi]的最大值及最小值、最大迭代次數及迭代停止準則等;初始化微粒群的隨機位置和初始速度;定義適應度函數，以最小里程的目標函數式（13）為適應度函數。

二是根據適應度函數計算群體中每個粒子的適應值，改變粒子的歷史最優位置及粒子鄰域的局部最優位置：將每個粒子適應值與所經歷過的歷史最優位置的適應值進行比較，若較好，則將其位置作為該粒子的歷史最優位置;同時將每個粒子的適應值與粒子動態鄰域所經歷過的最優位置的適應值進行比較，若較好，則將其位置作為該粒子鄰域的局部最優位置。

三是根據線性遞減權值策略改變每個粒子的慣性權重;根據基于統計的加速步長進化方程式改變每個粒子的加速步長;根據粒子的速度進化方程與位置進化方程對粒子的速度、位置進行進化;其速度進化和位置進化方程分別如式（5）、式（4）所示;判斷適應值是否滿足迭代停止準則或是否達到最大進化代數，如不滿足則返回第二步重新計算，否則結束并得到所要求的結果。

本文以某煙草局物流配送中心A送貨部部分線路的實際配送為例，在未采用優化方案前，從A送貨部某天送往客戶的總里程數為1 809 km，出車次數為18次，如表1所示。

比較發現，本文所提的優化方案可節約里程數11.2%左右，提高車輛裝載率11.73%左右，減少出車次數6次，大大節約了煙草物流配送的成本與時間。

4 結論

本文針對微粒群算法易陷入局部極值且常量值的加速步長無法反映實際粒子的飛行狀況等問題，在PSO算法基礎上，定義了一種基于統計步長的微粒群算法，利用慣性權重因子和基于統計的加速步長進化方程改進了PSO算法，提高了算法的全局搜索能力，并根據線路優化目標建立了煙草配送線路優化方案，為煙草配送線路優化提供了一種新的方法。

參考文獻：

[1]謝萍，劉小平，莊浩銘，等.基于車輛路徑優化的土地利用執法巡查線路規劃研究[J].地理與地理信息科學，2020（4）：70-76.

[2]周愛蓮，蔣利，侯夏杰.應急物流中無人機配送線路優化[J].長沙理工大學學報（自然科學版），2020（2）：54-60.

[3]陳汐，王印海，劉劍鋒，等.多區域通勤定制公交線路規劃模型及求解算法[J].交通運輸系統工程與信息，2020（4）：166-172.

[4]許智宏，王怡崢，王利琴，等.關于大數據的車輛動態線路遺傳優化仿真研究[J].計算機仿真，2020（6）：122-125.

[5]劉曉峰，陳通.PSO算法的收斂性及參數選擇研究[J].計算機工程與應用，2007（9）：14-17.

[6]SHI Y，EBERHART R C.Empirical Study of Particle Swarm Optimizer[C]//Proceedings of the 1999 Congress on Evolutionary Computation.1999.

[7]高明瑤，石紅國.基于改進PSO算法的軌道交通接運公交線路優化問題[J].交通運輸工程與信息學報，2019（4）：49-54.

[8]張耀軍，諶昌強.基于改進量子PSO算法的可約束車輛路徑優化[J].計算機測量與控制，2014（9）：2875-2878.

[9]董鍇，崔艷林，周巍，等.基于PSO算法的電力系統狀態評估分析方法研究[J].電子設計工程，2020（14）：158-162.