基于統(tǒng)計步長PSO算法的煙草配送線路優(yōu)化方案研究

錢漫 鐘培泉 張亞萍 張振軍

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

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

中圖分類號：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

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

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

1 微粒群算法

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

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

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

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

2 基于統(tǒng)計步長的微粒群算法模型

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

3 煙草配送線路優(yōu)化方案

煙草配送線路優(yōu)化目標是以最優(yōu)路線、最低成本和最快時間將卷煙從配送中心送到目的地。為了解決煙草配送過程中過遠運輸、重復運輸、無效運輸?shù)葐栴}，本文定義了煙草配送線路優(yōu)化方案。其間定義的運輸平衡方程為：

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

利用基于統(tǒng)計步長的PSO算法求解，并確定路徑最優(yōu)方案，求解步驟如下。

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

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

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

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

比較發(fā)現(xiàn)，本文所提的優(yōu)化方案可節(jié)約里程數(shù)11.2%左右，提高車輛裝載率11.73%左右，減少出車次數(shù)6次，大大節(jié)約了煙草物流配送的成本與時間。

4 結論

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

參考文獻：

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

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

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

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

[5]劉曉峰，陳通.PSO算法的收斂性及參數(shù)選擇研究[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算法的軌道交通接運公交線路優(yōu)化問題[J].交通運輸工程與信息學報，2019（4）：49-54.

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

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