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

錢漫 鐘培泉 張亞萍 張振軍

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

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

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

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

1 微粒群算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

參考文獻(xiàn)：

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

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

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

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

[5]劉曉峰，陳通.PSO算法的收斂性及參數(shù)選擇研究[J].計(jì)算機(jī)工程與應(yīng)用，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]高明瑤，石紅國(guó).基于改進(jìn)PSO算法的軌道交通接運(yùn)公交線路優(yōu)化問題[J].交通運(yùn)輸工程與信息學(xué)報(bào)，2019（4）：49-54.

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

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