基于超启发式算法的备件供应网络结构优化

doi:10.3969/j.issn.1001-506X.2020.03.016

摘要/Abstract

摘要：

为了通过对供应网络结构进行优化从而提高备件供应的效率和效益,分别对传统正向供应网络、应急横向供应网络以及考虑抢修任务的闭环供应网络3种备件供应网络结构进行研究。以供应成本最小和供应时间最短为目标,以备件满足度、库存等为约束,构建了带约束的多目标优化模型。提出了一种基于排序选择函数的超启发式多目标进化算法,同时可以对不同网络结构模型进行求解。在ZDT系列测试函数上将该算法与其他进化算法进行对比测试,验证了所提出的超启发式算法在收敛性和分布性上的优越性。算例表明,一方面,与传统前向供应网络相比,横向和闭环供应网络能够提高备件供应的时效性和经济性;另一方面,超启发式算法在求解模型时取得的解优于其他元启发式算法。

关键词: 备件供应, 网络结构优化, 闭环供应网络, 多目标优化, 超启发式算法

Abstract:

In order to improve the efficiency and effectiveness of spare parts supply by optimizing the structure of supply network, three kinds of network structures of spare parts supply are studied, which are the traditional forward supply network, emergency lateral supply network and closed-loop supply network considering maintenance. A multi-objective optimization model with the objectives of the minimum supply cost and the shortest supply time and the constraints of satisfaction rate and inventory is proposed. A hyper-heuristic multi-objective evolutionary algorithm based on the ordering choice function is proposed to solve models in different network structures. By comparing the proposed algorithm with other evolutionary algorithms on the ZDT benchmarks, the superiority of the proposed hyper heuristic algorithm in convergence and distribution is verified. The numerical example shows that, on the one hand, compared with the traditional forward supply network, the lateral and closed-loop supply network can improve the timeliness and economy of spare parts supply. On the other hand, the hyper heuristic algorithm is superior to other meta heuristic algorithms in solving the models.

Key words: spare parts supply, network structure optimization, closed-loop supply network, multi-objective optimization, hyper heuristic algorithm

中图分类号:

王亚东, 石全, 夏伟, 陈材. 基于超启发式算法的备件供应网络结构优化[J]. 系统工程与电子技术, 2020, 42(3): 620-629.

Yadong WANG, Quan SHI, Wei XIA, Cai CHEN. Structure optimization of spare parts supply network based on hyper heuristic algorithm[J]. Systems Engineering and Electronics, 2020, 42(3): 620-629.

图/表 14

图1

图2

图3

表1

图4

表2

表3

表4

表5

图5

表6

表7

表8

表9

参考文献 27

1	郭霖瀚, 王恺, 王严, 等. 多级多层备件供应链需求建模与仿真[J]. 计算机集成制造系统, 2010, 16 (10): 2038- 2043.
	GUO L H , WANG K , WANG Y , et al. Multi-indenture multi-echelon spare part supply chain requirement modeling and simulation[J]. Computer Integrated Manufacturing Systems, 2010, 16 (10): 2038- 2043.
2	WEN M , HAN Q , YANG Y , et al. Uncertain optimization model for multi-echelon spare parts supply system[J]. Applied Soft Computing, 2017, 56, 646- 654. doi: 10.1016/j.asoc.2016.07.057
3	刘喜春, 王磊, 许永平, 等. 战时可修复备件供应保障优化模型[J]. 系统工程与电子技术, 2010, 32 (12): 2595- 2598. doi: 10.3969/j.issn.1001-506X.2010.12.21
	LIU X C , WANG L , XU Y P , et al. Research on ABMS based wartime spares support adaptation decision[J]. Systems Engineering and Electronics, 2010, 32 (12): 2595- 2598. doi: 10.3969/j.issn.1001-506X.2010.12.21
4	刘勇, 武昌, 孙鹏, 等. 战损条件下装备备件供应保障仿真研究[J]. 系统仿真学报, 2009, 21 (5): 1470- 1473.
	LIU Y , WU C , SUN P , et al. Research on simulation for communication equipment of air force spare parts supply support under combat damage[J]. Journal of System Simulation, 2009, 21 (5): 1470- 1473.
5	阮旻智, 刘任洋. 随机需求下多层级备件的横向转运配置优化模型[J]. 系统工程理论与实践, 2016, 36 (10): 2689- 2698. doi: 10.12011/1000-6788(2016)10-2689-10
	RUAN M Z , LIU R Y . Configuration and optimization model for multi-indenture spares with lateral transshipments under stochastic demand[J]. System Engineering Theory and Practice, 2016, 36 (10): 2689- 2698. doi: 10.12011/1000-6788(2016)10-2689-10
6	董琪, 徐廷学, 丛林虎. 基于Markov三级库存系统备件横向调拨配置模型[J]. 系统工程与电子技术, 2015, 37 (11): 2524- 2530.
	DONG Q , XU T X , CONG L H . Allocation model of spare parts for three-echelon inventory system with lateral transshipment based on Markov[J]. Systems Engineering and Electronics, 2015, 37 (11): 2524- 2530.
7	张颖, 王蕴, 薛佩. 三站点备件供应保障关系建模与分析[J]. 北京航空航天大学学报, 2017, 43 (8): 1625- 1631.
	ZHANG Y , WANG Y , XUE P . Modeling and analysis of spares supply support relations among three stations[J]. Journal of Beijing University of Aeronautics and Astronautics, 2017, 43 (8): 1625- 1631.
8	BOUCHERIE R J , VAN H G J , TIMMER J , et al. A two-echelon spare parts network with lateral and emergency shipments: a product-from approximation[J]. Probability in the Engineering and Informational Sciences, 2018, 32 (4): 1- 20.
9	FATTAHI M , GOVINDAN K . Integrated forward/reverse logistics network design under uncertainty with pricing for collection of used products[J]. Annals of Operations Research, 2017, 253 (1): 193- 225.
10	LIAO T Y . Reverse logistics network design for product recovery and remanufacturing[J]. Applied Mathematical Modelling, 2018, 60, 145- 163. doi: 10.1016/j.apm.2018.03.003
11	GUO J , WANG X , FAN S , et al. Forward and reverse logistics network and route planning under the environment of low-carbon emissions: a case study of Shanghai fresh food ecommerce enterprises[J]. Computers & Industrial Engineering, 2017, 106, 351- 360.
12	陈文若.备件修复供应链的逆向物流网络设计[D].北京:对外经济贸易大学, 2005.
	CHEN W R. Reverse logistics network design of spare-parts recovery chain[D]. Beijing: University of International Business and Economics, 2005.
13	任骥, 郑小蕾, 谭跃进. 考虑战损件回收再造的战场军需备件供应优化研究[J]. 军械工程学院学报, 2014, 2, 16- 20.
	REN J , ZHENG X L , TAN Y J . Supply planning for military spare parts in battlefield with broken parts remanufacturing consideration[J]. Journal of Ordnance Engineering College, 2014, 2, 16- 20.
14	戎海武. 关于拉格朗日乘数法的两点思考[J]. 高等数学研究, 2013, 16 (4): 81- 86. doi: 10.3969/j.issn.1008-1399.2013.04.029
	RONG H W . Two notes on the method of Lagrange multipliers[J]. Studies in College Mathematics, 2013, 16 (4): 81- 86. doi: 10.3969/j.issn.1008-1399.2013.04.029
15	WANG F, ZHOU L, REN H, et al.Multi-objective optimization model of source-load-storage synergetic dispatch for a building energy management system based on TOU price demand response[J].IEEE Trans.on Industry Applications, 2018, 54(2): 1017-1028.
16	LI W , OZCAN E , JOHN R . Multi-objective evolutionary algorithms and hyper-heuristics for wind farm layout optimization[J]. Renewable Energy, 2017, 105, 473- 482. doi: 10.1016/j.renene.2016.12.022
17	WANG Z, ZHANG Q, ZHOU A, et al. Adaptive replacement strategies for MOEA/D[J]. IEEE Trans.on Cybernetics, 2017, 46(2): 474-486.
18	VO D T , DUONG G D , HO H V , et al. Multi-objective optimization of laminated composite beam structures using NSGA-Ⅱ algorithm[J]. Composite Structures, 2017, 168, 498- 509. doi: 10.1016/j.compstruct.2017.02.038
19	CHENG S, ZHAO L L, JIANG X Y. An effective application of bacteria quorum sensing and circular elimination in MOPSO[J]. IEEE/ACM Trans.on Computational Biology & Bioinformatics, 2017, 14(1): 56-63.
20	MAASHI M , KENDALL G , ÖZCAN E . Choice function based hyper-heuristics for multi-objective optimization[J]. Applied Soft Computing, 2015, 28 (C): 312- 326.
21	WANG H, JIN Y, YAO X. Diversity assessment in many-objective optimization[J].IEEE Trans.on Cybernetics, 2016, 47(6): 1-13.
22	TAN K C , LEE T H , KHOR E F . Evolutionary algorithms for multi-objective optimization: performance assessments and comparisons[J]. Artificial Intelligence Review, 2002, 17 (4): 251- 290.
23	SRINIVAS N , DEB K . Muiltiobjective optimization using nondominated sorting in genetic algorithms[J]. Evolutionary Computation, 1994, 2 (3): 221- 248. doi: 10.1162/evco.1994.2.3.221
24	LUO B, ZHENG J, XIE J, et al. Dynamic crowding distance? a new diversity maintenance strategy for MOEAs[C]//Proc.of the 4th International Conference on Natural Computation, 2008: 580-585.
25	ZHOU A , QU B Y , LI H , et al. Multiobjective evolutionary algorithms: a survey of the state of the art[J]. Swarm and Evolutionary Computation, 2011, 1 (1): 32- 49. doi: 10.1016/j.swevo.2011.03.001
26	MAASHI M , ZCAN E , KENDALL G . A multi-objective hyper-heuristic based on choice function[J]. Expert Systems with Applications, 2014, 41 (9): 4475- 4493. doi: 10.1016/j.eswa.2013.12.050
27	HUBAND S, HINGSTON P, BARONE L, et al. A review of multiobjective test problems and a scalable test problem toolkit[J].IEEE Trans.on Evolutionary Computation, 2006, 10(5): 477-506.

测试函数	表达式	变量取值范围
ZDT1	f₁=y₁ g=1+9$\sum\limits_{i = 1}^k {{z_i}} $/k h=1-$\sqrt {{f_1}/g} $ f₂(y, z)=g(z)h(f₁(y)g(z))	[0, 1]
ZDT2	f₁=y₁ g=1+9$\sum\limits_{i = 1}^k {{z_i}} $/k h=1-($ {{f_1}/g} $)² f₂(y, z)=g(z)h(f₁(y)g(z))	[0, 1]
ZDT3	f₁=y₁ g=1+9$\sum\limits_{i = 1}^k {{z_i}} $/k h=1-$\sqrt {{f_1}/g} $-($\sqrt {{f_1}/g} $)sin(10πf₁) f₂(y, z)=g(z)h(f₁(y)g(z))	[0, 1]
ZDT4	f₁=y₁ g=1+10k+$\sum\limits_{i = 1}^k {} $(z_i²-10cos(4πf₁)) h=1-($\sqrt {{f_1}/g} $)^1/2 f₂(y, z)=g(z)h(f₁(y)g(z))	y₁∈[0, 1]z_{1, 2, …, k}∈[-5, 5]
ZDT6	f₁=1-exp(-4y₁)sin⁶(6πy₁) g=1+9($\sum\limits_{i = 1}^k {{z_i}} $/k)^1/4 h=1-($\sqrt {{f_1}/g} $)² f₂(y, z)=g(z)h(f₁(y)g(z))	[0, 1]

开放成本/千元	库存容量/个	库存成本/(元/个)	节点
中转仓库1	5	20	50
中转仓库2	8	32	40
中转仓库3	12	40	45
中转仓库4	6	28	50

节点	备件需求/个	缺件损失/(元/个)
用装单位1	18	1 000
用装单位2	15	1 500
用装单位3	22	1 200
用装单位4	16	1 600
用装单位5	25	1 500
用装单位6	18	1 300

算法	适应度函数1			适应度函数2
算法	最大值	最小值	均值	最大值	最小值	均值
HHMOEA	48 250	40 000	43 010	3 538	2 613	3 050
MODE/D	52 200	42 200	46 260	3 840	2 790	3 252
NSGA-Ⅱ	47 290	42 100	44 250	3 895	3 131	3 465
MOPSO	49 710	45 000	46 550	4 647	3 907	4 278

算法	适应度函数1			适应度函数2
算法	最大值	最小值	均值	最大值	最小值	均值
HHMOEA	48 240	40 000	43 420	3 345	2 361	2 785
MODE/D	50 180	42 100	45 120	3 649	2 664	3 115
NSGA-Ⅱ	45 660	42 100	43 310	3 686	3 066	3 387
MOPSO	50 230	45 100	46 870	4 311	3 593	3 941