Multi-level Reserve Material Distribution Optimization Method Based on Improved Particle Swarm Optimization

DU Dong; TIAN Yao; WANG Ge

doi:10.3969/j.issn.1673-3819.2021.03.024

Command Control and Simulation >

2021 , Vol. 43 >Issue 3: 124 - 129

DOI: https://doi.org/10.3969/j.issn.1673-3819.2021.03.024

Engineering & Application

Multi-level Reserve Material Distribution Optimization Method Based on Improved Particle Swarm Optimization

DU Dong ¹ ,
TIAN Yao ² ,
WANG Ge ²

Expand

1. 31432 Unit of PLA, Shenyang 110021, China
2. 78092 Unit of PLA, Chengdu 610031, China

Received date: 2021-01-14

Revised date: 2021-03-04

Online published: 2021-06-10

Fold

Abstract

The multi-level material reserve system can guarantee the force requirements accurately, quickly and efficiently. Firstly, according to the material distribution relationship among the basic storage point, the preset pre storage point and the front demand point, the material support methods such as pre storage guarantee, basic supplement and preset supplement are proposed, and the multi-objective multi-level reserve material distribution scheme optimization model based on mixed integer programming is constructed. Then, aiming at the shortcomings of early maturity, easy to fall into local optimization, parameters and constraints of optimization model are too much and so on, an improved particle swarm optimization algorithm is designed. Finally, the simulation experiment and comparative analysis are studied with an example. The experimental results verify the feasibility, effectiveness and robustness of the model and algorithm.

Key words： multi-level reserve system; improved particle swarm optimization; multi-objective decision-making; Pareto optimality

Cite this article

DU Dong , TIAN Yao , WANG Ge . Multi-level Reserve Material Distribution Optimization Method Based on Improved Particle Swarm Optimization[J]. Command Control and Simulation, 2021 , 43(3) : 124 -129 . DOI: 10.3969/j.issn.1673-3819.2021.03.024

信息化条件下,后勤保障范围大、保障距离远、保障时间短、保障对象多变^[1],传统储备模式通常以大规模、全局性的补充需求为保障目标,存储设施主要分布在纵深地区,以成建制、标准化为基本储备方式,灵敏性差、反应性劣、机动性弱,难以满足现代军队快速及时、精准高效、体系配套的保障需求。多级储备模式是在传统储备的基础上,加入预置预储功能,以基本存储点、预置预储点为核心共同构成多级储备体系,该体系具有综合配套程度高、针对有效性强、机动灵活性好的特点,能够高效保障战斗区域、任务部队的物资需求。

国内外对于多级预储模式的定量化分析和模型化表述较少,多以基础理论和对策建议为主,如文献[2 ⇓⇓-5]均从战备物资预置预储体系的主要构成、基本布局、长远构想和建设规划等角度进行定性分析。同时,对于改进粒子群算法计算模型的研究,通常适用于保障结构简单、变量条件少、约束条件少的物资配送模型,如文献[6 ⇓-8],但对于构成要素较多、层级结构复杂、保障类型多样的多级预储物资配送情况不能有效应用。

针对上述研究不足,本文基于预储保障、基本补充和预置补充等多级预储物资保障方式,采用混合整数规划模型定量描述物资配送过程,运用速度更新、位置变异等策略改进粒子群算法,通过设计编码、约束处理与适应度函数等有效求解混合整数规划模型,进而优化多级储备物资配送方案。

1 多级储备物资配送方案优化模型

1.1 多级储备物资配送问题描述

多级储备物资保障体系主要由基本储存点、预置预储点、前方需求点、运载方式、输送线路、物资等要素构成。基本储存点作为后方区域主要的存储设施,日常储备大量战备物资,保证了物资保障的持续性和稳定性,但距离前方需求点较远,物资保障及时性和灵敏性不足;预置预储点距离前方需求点较近,保障距离近、保障时间短,可满足前方需求点的早期物资需求,但储存空间有限、储备费用较高,在没有基本储存点的持续补充下无法单独支撑前方需求点的长期物资需要;前方需求点一般分布于前方区域多个点位,物资需求呈现品种类型多、规模变化大、数量动态性强等特点。

多级储备模式下主要存在3种物资保障类型:1)预储保障,基本储存点向预置预储点转运物资,提升保障体系的及时配送能力;2)基本补充,在时间允许下,基本储存点直接向前方需求点投送物资满足其物资需求;3)预置补充,时限性要求较高时,预置预储点立即向前方需求点配送物资。具体如图1所示。

显示原图|下载原图ZIP|生成PPT

图1 多级储备模式下的物资配送关系

1.2 模型构建

模型假设:1)基本储存点、预置预储点和前方需求点的位置是已知的,前方需求点的物资需求量信息已知;2)3类节点之间的物资配送距离和配送时间是已知的,在同一时间向前方配送物资,不存在时间差;3)由于物资的数量和重量可以相互转换,模型中只考虑物资数量;4)单个前方需求点的单品种物资只能由1个基本储存点或预置预储点保障,即对于前方需求点的单品种物资需求只存在“一对一”保障关系,不存在单品种物资下“一对多”或“多对一”保障关系,同理于预置预储点保障前方需求点的情况。

构建混合整数规划模型:

(1)s.t. $\begin{aligned} & \min \sum_{i \in I, m \in M} \zeta_{i, m} S_{i, m}+\sum_{j \in J, m \in M} \eta_{j, m} U_{j, m}+\\ & \sum_{m \in M} \delta_{m}\left(\sum_{i, j} \alpha_{i, j} X_{i, j, m}+\sum_{i, k} \beta_{i, k} Y_{i, k, m}+\sum_{j, k} \gamma_{j, k} Z_{j, k, m}\right) \end{aligned}$

(2)min max(a_i_,_jBX_i_,_j_,_m,b_i_,_kBY_i_,_k_,_m+g_j_,_kBZ_j_,_k_,_m) ∀i∈I,j∈J,k∈K,m∈M

(3)

∑ i ∈ I

BY_i_,_k_,_m+

∑ j ∈ J

BZ_j_,_k_,_m=1 ∀k∈K,m∈M

(4)

∑ i ∈ I

BX_i_,_j_,_m=1 ∀j∈J,m∈M

(5)

∑ i ∈ I

Y_i_,_k_,_m+

∑ j ∈ J

Z_j_,_k_,_m=ρ_k_,_m ∀k∈K,m∈M

(6)

∑ k ∈ K

Z_j_,_k_,_m=

∑ i ∈ I

X_i_,_j_,_m ∀j∈J,m∈M

(7)

∑ j ∈ J

X_i_,_j_,_m+

∑ k ∈ K

Y_i_,_k_,_m=S_i_,_m ∀i∈I,m∈M

(8)

∑ k ∈ K

Z_j_,_k_,_m=U_j_,_m ∀j∈J,m∈M

(9)X_i_,_j_,_m,Y_i_,_k_,_m,Z_j_,_k_,_m,S_i_,_m,U_j_,_m⊂N BX_i_,_j_,_m,BYi_,_k_,_m_,BZj_,_k_,_m⊂{0,1} ∀i∈I,j∈J,k∈K,m∈M

模型中符号说明如表1所示。

表1 符号说明

符号	说明
I	基本储存点集合,用i遍历
J	预置预储点集合,用j遍历
K	前方需求点集合,用k遍历
M	物资种类集合,用m遍历
H	运载工具类型集合,用h遍历
X_i_,_j_,_m	储存点i对预储点j物资m的保障量
Y_i_,_k_,_m	储存点i对需求点k物资m的补充量
Z_i_,_k_,_m	预储点j对需求点k物资m的补充量
S_i_,_m	基本储存点i物资m的储备量
U_j_,_m	预置预储点j物资m的预置量
BX_i_,_j	是否选择路径储存点i到预储点j
BY_i_,_k	是否选择路径储存点i到需求点k
BZj_,_k	是否选择路径预置点j到需求点k
α_i_,_j	基本储存点i与预置预储点j的距离
β_i_,_k	基本储存点i与前方需求点k的距离
γ_j_,_k	预置预储点j与前方需求点k的距离
ρ_k_,_m	前方需求点k对物资m的需求量
ζ_i_,_m	基本储存点i物资m的储存费用
η_j_,_m	预置预储点j物资m的储备费用
δ_m	单位物资m的单位距离配送费用

目标函数(1)最小化多级储备物资配送所产生的费用,包括基本存储点的存储费用、预置预储点的预储费用、预储保障费用、基本补充费用和预置补充费用5类费用。目标函数(2)最小化最长物资配送时间,最长物资配送时间主要在基本储存点通过中转预置预储点补充前方需求点、直接通过基本补充的方式这两种补充方式中产生。约束函数(3)限定前方需求点的单品种物资需求至多由1个基本储存点或1个预置预储点补充满足,形成“一对一”保障关系。约束函数(4)限定每个预置预储点至多由1个基本储存点转运配送。约束函数(5)要求基本储存点的基本补充物资量和预置预储点的预置补充量要达到前方需求点的物资需求量,保证需求点的需求得到有效满足。约束函数(6)要求预置预储点向外的物资配送量等于基本储存点向预置预储点的物资配送量。约束函数(7)表示基本储存点的物资储备量等于其向预置预储点和前方需求点的物资配送量。约束函数(8)表示预置预储点的物资储备量等于其向前方需求点的物资配送量。约束函数(9)对各变量的取值范围做出限定,要求必须为自然数或0、1整数。

2 改进的粒子群算法

多级储备物资配送方案优化问题属于NP hard问题,精准计算预储保障、基本补充、预置补充3部分物资保障过程才能优化出最佳的物资配送策略,精确求解的计算量会随着问题规模增大而指数增长。

粒子群算法(Particle Swarm Optimization,PSO)是一种群智能优化算法,局限性主要有3点:1)局部搜索能力较差,搜索精度不够高;2)算法不能绝对保证搜索到全局最优解,在处理高维复杂问题时,算法可能会早熟收敛,粒子群在没有找到全局最优信息之前就陷入停顿状态,这些早熟点既可能是局部最优点,也可能是位于局部最优点邻域内的其他点;3)算法搜索性能对参数具有一定的依赖性,参数值的大小直接影响到算法是否收敛以及求解结果的精度。针对上述传统粒子群算法的局限性,可从以下几方面加以改进。

2.1 种群逻辑初始化

传统粒子群算法通常采用随机化产生初始粒子,这种方式使得初始粒子群在解空间的分布均匀度不佳,不利于最终的收敛精度。引入基于Logistic混沌映射的方法,利用其遍历性和非周期性,初始化粒子种群,使得其均匀分布于解空间。相较于随机化产生,Logistic混沌映射方法产生的粒子种群分布的均匀性和多样性更佳,平均适应度更高。Logistic混沌映射是一种产生混沌序列的非线性映射,可表示为

(10)

X i d s + 1

=μ

X i d s

(1-

X i d s

) id=1,2,…,N

式中,

Y i d s

为第s次迭代粒子位置的混沌变量,其取值范围为[0,1];μ为控制参数,若μ为4,则系统处于完全混沌状态,且产生的混沌变量均属于区间[0,1]。采用四舍五入的方式,对式(10)的混沌映射结果进行二值化修正处理,修正公式为

(11)

Y i d s + 1

=round(

X i d s + 1

)

式中,round()为取整函数;

Y i d s + 1

为修正后的粒子位置变量。

2.2 学习因子异步化

粒子群算法在进行速度更新时,通过学习因子使粒子具备自学习和社会学习的能力。固定的自学习因子和社会学习因子容易使迭代过程缓慢,易陷入局部最优。为改善算法在不同迭代阶段的学习能力,重新设计自学习和社会学习因子的变化公式,在算法迭代初期,使例子具有较强的自学习能力,以增强算法开发性能和全局寻优能力;在算法迭代后期,增强例子的社会学习能力,提高算法开采能力。学习因子变化公式如式(12),式中c_i₁和c_i₂分别表示c₁和c₂的初始值,c_f₁和c_f₂表示c₁和c₂的终值。

(12)c₁=c_i₁+(c_f₁-c_i₁)/Tt c₂=c_i₂+(c_f₂-c_i₂)/Tt

2.3 速度位置更新化

下一次迭代粒子id的速度

V i d s + 1

和惯性权重w按式(13)和(14)进行更新,其中w_max和w_min分别为惯性权重初始最大最小值,s_max为最大迭代次数。

(13)

V i d s + 1

=w^s*

V i d s

+c₁r₁(pbes

t i s

X i d s

)+c₂r₂(gbes

t i s

X i d s

)

(14)w^s⁺¹=w_max-(s+1)(w_max-w_min)/s_max

根据下一次迭代粒子id的速度

V i d s + 1

可以计算下一次粒子位置,如式(15)所示,其中dt是仿真间隔,一般情况下可以取1,如果希望仿真速度更慢、搜索效果更平滑,可适当减小dt。

(15)

X i d s + 1

X i d s

V i d s + 1

2.4 粒子位置变异化

为了表示二进制位取1的概率,速度值被映射到区间[0,1]。将Sigmoid映射函数稍作改变,这里Si(V)表示粒子位置X_id取1的概率:

(16)Si(

V i d s

1 - 2 (1 + e x p (- V i d s)) - 1 i f (V i d s ≤ 0) 2 (1 + e x p (- V i d s)) - 1 - 1 e l s e

粒子i的位置X_id更新策略如公式(17)。当粒子的速度为0时,其位置不发生变化;粒子的速度为负时,其位置只能取0;粒子的速度为正时,其位置只能取1。通过这种位置更新策略,可以使粒子更加靠近局部最优解。

(17)if

v i d s

<0 X _id=

0 i f (r a n d () ≤ S i (v i d d)) X i d e l s e

else Xi_d₌

1 i f (r a n d () ≤ S i (v i d s)) X i d e l s e

3 基于改进粒子群算法的模型求解

3.1 编码设计

使用改进的二进制粒子群算法对从经济性、时效性两个方面对多级储备物资配送方案进行优化,关键在于将模型中的变量合理转化为粒子表示。模型中主要是连续型变量,取值范围为非负整数,如预储保障物资量X、基本补充物资量Y、预置补充物资量Z等,可以采用连续型编码形式。设计一种连续编码方案,如图2所示,粒子编码长度L=ijm+ikm+jkm。由于变量BX、BY、BZ由于可以根据变量X、Y、Z的取值情况进行判定,故为达到既节约计算空间又保持计算精度的编码目的,不对X、Y、Z变量单独编码。

显示原图|下载原图ZIP|生成PPT

图2 粒子编码方式

3.2 约束处理与适应度函数设计

处理约束条件通常使用惩罚函数,其基本思想是通过惩罚违反约束的不可行解,使粒子群逐渐收敛于可行解空间。对约束函数式(3)—(5)转化为无约束函数(18)—(21):

(18)M₁=1-

∑ i ∈ I

BY_i_,_k_,_m-

∑ j ∈ J

BZ_j_,_k_,_m

(19)M₂=1-

∑ i ∈ I

BX_i_,_j_,_m

(20)M₃=ε_k_,_m-

∑ i ∈ I

Y_i_,_k_,_m-

∑ j ∈ J

Z_j_,_k_,_m

(21)CN=

∑ i = 1 3

k_iM_i

违反约束条件程度CN由式(21)给出,其中k_i为较大的正数,表示各约束条件的重要程度,一般取较目标函数值大三个数量级的正数。适应度值是判断粒子优劣的重要标准,在设计适应度函数时需要同时考虑违反约束条件的程度和目标函数值,用以描述不同粒子在违反约束条件时的差别。约束违反程度CN与第n维目标函数值f_n共同构成第n维目标适应度函数F_n,如式(22)所示。与模型目标函数对应,适应度值越小则粒子越优。

(22)F_n=f_n+CN n=1,2

3.3 算法流程

改进的粒子群算法流程如图3所示。

显示原图|下载原图ZIP|生成PPT

图3 改进的粒子群算法流程图

4 仿真算例

以某部后勤保障演习为例,研究物资配送方案的优化问题。该部计划依托3个基本储存点和6个预置预储点,对15个前方需求点进行2类物资的配送补充,基本预储点与预置预储点、基本预储点与前方需求点、预置预储点与前方需求点配送距离分别在区间[40,100]、[90,170]、[10,45]中随机生成,前方需求点的物资需求量服从正态分布N(60,5²);基本储存点和预置预储点的储备费用分别在区间[6,10]、[12,18]中随机生成。

算法运行参数设定如下:粒子长度为307,速度最大值v_max为10、最小值v_min为2,学习因子c₁和c₂均为1.49,控制参数μ为3,迭代次数为500,种群粒子规模为100,变异概率为0.3。由于模型为双目标函数,每次迭代产生一组帕累托最优(Pareto Optimality)解组合,根据粒子拥挤程度机制,将帕累托解组中排序第一的解作为分析对象,取其两个目标值的平均值作为适应度函数值,分析迭代次数与适应度函数值的关系。随着迭代次数不断增加,适应度函数值不断减少而后趋于稳定,说明算法在不断优化物资配送方案,最终得到一组优化解,如图4所示。

显示原图|下载原图ZIP|生成PPT

图4 多级储备物资配送方案的优化迭代过程

计算得到了共计10组物资配送方案解,共同构成一组最优帕累托前沿面(Parento Front),最优解分布如图5所示,具体双目标求解值如表2所示。图5中每个“*”点代表1个求解物资配送方案,图中求解的结果分布较为均匀,在经济成本和最大保障距离2个求解目标上互不构成“占优”关系,说明改进的粒子群算法取得了较好的求解效果。

显示原图|下载原图ZIP|生成PPT

图5 Pareto最优解分布图

表2 Pareto最优解对应的目标值

解序号	1	2	3	4	5
目标1值	303086	317412	304378	314130	310546
目标2值	125	63	115	83	100
解序号	6	7	8	9	10
目标1值	313208	306940	309498	319114	301576
目标2值	84	110	104	61	131

对外部种群档案进行排序并选取排序第1的物资配送方案进行分析,具体的配送关系和物资配送量如图6所示,基本储存点和预置预储点的物资储备量如图7所示。在配送方案中,基本储存点和预置预储点合理分工、精确协同,共同为前方需求点保障战备物资,其中基本储存点物资储备量较多,担负着既向预置预储点预储保障物资,又直接向前方需求点基本补充物资的保障任务,在储存物资、配送保障等方面均起到了主要作用,但是机动性、灵活性较低;预置预储点距离前方需求点更近,在需求点的物资保障时限性要求较高时能够实现快速精准保障,有效弥补基本储存点配送机动性差、反应速度慢的缺点。

显示原图|下载原图ZIP|生成PPT

图6 多级储备物资保障关系及配送量

显示原图|下载原图ZIP|生成PPT

图7 基本储存点和预置预储点的物资储备量

为进一步验证改进粒子群算法的有效性,将其与一般粒子群算法仿真计算过程与结果进行比较。一般粒子群的参数设定与改进粒子群已知,设置速度最大值v_max为10、最小值v_min为2,学习因子c为1.49,迭代次数为500,种群粒子规模100,通过Matlab进行50次仿真计算,搜索得到最优帕累托前沿面(Parento Front)的次数为4次,成功率为8%,而改进的粒子群算法搜索得到最优帕累托前沿面的次数为37次,成功率为74%。两种算法的适应度函数值变化情况有所差异,如图8所示。

显示原图|下载原图ZIP|生成PPT

图8 一般粒子群算法与改进粒子群算法适应度函数值变化比较

改进粒子群算法在迭代次数达到100次之后较为稳定,适应度函数值变化较为平稳。一般粒子群算法的稳定性不够强,适应度值会出现阶跃跳变的情况,是因为构建的物资配送方案优化模型较为复杂,粒子编码长度较长,计算得到的局部最优解往往达不到约束函数要求而进行适应度回调造成的。通过比较结果发现,不论是在收敛速度、搜索精度还是计算稳定性方面,改进的粒子群算法均优于一般粒子群算法。

5 结束语

采用多级储备模式,能够形成快速及时、精准高效、体系配套的物资配送体系,满足前方需求点多样化的物资保障需求。分析多级储备物资配送问题,运用定量方法至关重要。构建混合整数规划模型、改进粒子群算法进行研究,可以优化多级储备物资配送方案,相关优化结果可供后保人员参考,能够提高物资配送策略的科学性。后续可以研究物资需求变化、不固定物资保障关系、风险管理等更加复杂的问题。

References

Publishing order | Descend order by publishing year | Descend order by cited within

[1]	王耀, 李斌, 周济晓, 等. 陆军全域作战后勤战备物资预置储备研究[J]. 军事交通学院学报, 2019, 21(11):50-53.

[2]	王海兰, 赵道致. 用系统思维理论构建战备物资预置预储体系[J]. 系统科学学报, 2016, 24(1):80-83.

[3]	李守耕, 陈铁祺, 王丰. 战备物资预置储备模式研究[J]. 军事交通学院学报, 2019, 21(7):57-60,76.

[4]	张长城, 邱治安. 边境地区物资储备与预置[J]. 军事经济研究, 2013, 34(2):37-38.

[5]	余兴涛, 刘中, 郭占武, 等. 战区应急铁路运输投送存在的问题及对策[J]. 军事交通学院学报, 2018, 20(12):1-5.

[6]	宫华, 张彪. 基于离散粒子群算法的应急救灾物资配送问题[J]. 沈阳理工大学学报, 2015, 34(2):65-70,83.

[7]	姜大立, 林勇. 战区抗震救灾单需求点物资调运模型及算法研究[J]. 军事运筹与系统工程, 2014, 28(4):50-53.

[8]	宋英华, 王莉芳, 杜丽敬, 等. 模糊条件下应急物资配送选址-多模式运输问题[J]. 中国安全科学学报, 2017, 27(7):169-174.

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article

1 多级储备物资配送方案优化模型

1.1 多级储备物资配送问题描述

图1 多级储备模式下的物资配送关系

1.2 模型构建

表1 符号说明

2 改进的粒子群算法

2.1 种群逻辑初始化

2.2 学习因子异步化

2.3 速度位置更新化

2.4 粒子位置变异化

3 基于改进粒子群算法的模型求解

3.1 编码设计

图2 粒子编码方式

3.2 约束处理与适应度函数设计

3.3 算法流程

图3 改进的粒子群算法流程图

4 仿真算例

图4 多级储备物资配送方案的优化迭代过程

图5 Pareto最优解分布图

表2 Pareto最优解对应的目标值

图6 多级储备物资保障关系及配送量

图7 基本储存点和预置预储点的物资储备量

图8 一般粒子群算法与改进粒子群算法适应度函数值变化比较

5 结束语

References