学习型变邻域搜索算法求解运输-装配协同优化问题

doi:10.16182/j.issn1004731x.joss.22-0132

摘要/Abstract

摘要：

针对运输-装配协同优化问题，建立其整数规划模型，提出一种融合分解策略的学习型变邻域搜索算法(learning variable neighborhood search with decomposition strategy，LVNS_DS)对其求解。为降低问题的求解难度，设计一种分解策略将原问题分解为路径规划问题和装配线平衡问题；应用LVNS算法对2个子问题进行求解；通过合并子问题解可得原问题的完整解。相比常规VNS算法，LVNS算法依据邻域动作概率值来转换邻域结构，依据邻域动作产生的贡献来动态地更新其概率值，LVNS算法能以较大的概率值选择适于当前搜索阶段的邻域动作，从而易于找到子问题的优质解。通过不同规模算例的仿真实验，验证了运输-装配协同优化的有效性和LVNS_DS算法的有效性。

关键词: 协同优化, 耦合性, 装配线平衡, 车辆路径优化, 变邻域搜索, 分解策略

Abstract:

Aiming at transportation-assembly collaborative optimization problems, an integer programming model is established, and a learning variable neighborhood search with decomposition strategy (LVNS_DS) is proposed. To reduce the difficulty of solving the problem, a decomposition strategy is designed to decompose the original problem into a path planning problem and an assembly line balance problem. LVNS is used to solve the two subproblems, and the subproblem solutions are merged to obtain the complete solution of the original problem. Compared with the conventional VNS, LVNS transforms the neighborhood structure according to the neighborhood action probability value, and dynamically updates the probability value according to the contribution of neighborhood action. Therefore, LVNS algorithm can select the neighborhood action suitable for the current search stage with high probability value to easily find the high-quality solution of the subproblem. Through the simulation experiments of different scale examples, the importance of transportation assembly collaborative optimization and the effectiveness of LVNS_DS are verified.

Key words: collaborative optimization, coupling, assembly line balance, vehicle routing optimization, variable neighborhood search, decomposition strategy

中图分类号:

TP391.9

张腾飞, 胡蓉, 钱斌, 吕阳. 学习型变邻域搜索算法求解运输-装配协同优化问题[J]. 系统仿真学报, 2023, 35(6): 1260-1277.

Tengfei Zhang, Rong Hu, Bin Qian, Lü Yang. Learning Variable Neighborhood Search Algorithm for Transportation-assembly Collaborative Optimization Problem[J]. Journal of System Simulation, 2023, 35(6): 1260-1277.

图/表 14

图1

图 2

图3

图4

图5

表1

邻域动作及相关符号

参数	相邻逆序	交换	插入	局部逆序
编号	$N A 1$	$N A 2$	$N A 3$	$N A 4$
概率值	$P 1$	$P 2$	$P 3$	$P 4$

表1

表2

表3

参数水平设置

参数	水平
$α$	0.1	0.3	0.5
$β$	0.2	0.4	0.6

表3

表4

参数设置及响应值

组别	$α$	$β$	响应值
1	1	1	0.013
2	1	2	0.015
3	1	3	0.026
4	2	1	0.023
5	2	2	0.014
6	2	3	0.014
7	3	1	0.030
8	3	2	0.020
9	3	3	0.019

表4

表5

参数水平及响应值

水平	$α$	$β$
影响等级	1	2
1	0.018	0.022
2	0.017	0.016
3	0.023	0.020
极差	0.006	0.005

表5

图6

表6

LVNS_TO、LVNS _GS与LVNS_DS的对比结果

算例	LVNS_TO		LVNS_GS		LVNS_DS
算例	$N_N$	$R_N$	$N_N$	$R_N$	$N_N$	$R_N$
NB	0	0	1	1	5	5
JACKSON	2.36	0.13	0.36	0.02	7.64	0.40
JAESCHKE	0.00	0.00	1.36	0.04	2.09	0.15
BUXEY	1.00	0.06	1.00	0.04	9.91	0.48
KILBRID	0.00	0.00	13.91	0.37	10.00	0.25
LUTZ 1	0.50	0.02	2.20	0.09	17.70	0.59
LUTZ2	0.45	0.02	11.09	0.21	28.27	0.54

表6

图7

表7

LVNS_DS与VNS、NSGA-Ⅱ、MOEA/D的对比结果

算例	VNS		NSGA-Ⅱ		MOEA/D		LVNS_DS
算例	$N_N$	$R_N$	$N_N$	$R_N$	$N_N$	$R_N$	$N_N$	$R_N$
NB	1	1	0	0	0	0	5	5
BUXEY	1.70	0.06	1.00	0.04	1.75	0.07	2.25	0.08
JACKSON	5.20	0.11	1.65	0.03	2.25	0.05	4.75	0.09
JAESCHKE	6.30	0.14	5.40	0.10	2.80	0.05	6.75	0.13
KILBRID	6.65	0.12	2.10	0.03	3.05	0.04	7.10	0.11
LUTZ1	14.75	0.13	6.00	0.05	10.10	0.08	15.60	0.13
LUTZ2	1.70	0.06	1.00	0.04	1.75	0.07	2.25	0.08

表7

参考文献 26

1	徐颖, 刘勤明, 周林森. 基于博弈论的闭环双渠道回收供应链决策研究[J]. 系统仿真学报, 2022, 34(2): 396-408.
	Xu Ying, Liu Qinming, Zhou Linsen. Research on Decision-making of Closed-loop Supply Chain for Dual-channel Recovery Based on Game Theory[J]. Journal of System Simulation, 2022, 34(2): 396-408.
2	王玉. "物流+制造"共探新时代融合发展路径[J]. 物流技术与应用, 2021, 26(5): 100-103.
	Wang Yu. The Integrated Development Path of Logistics Plus Manufacturing in the New Era[J]. Logistics & Material Handling, 2021, 26(5): 100-103.
3	张明超, 孙新波, 王永霞. 数据赋能驱动精益生产创新内在机理的案例研究[J]. 南开管理评论, 2021, 24(3): 102-114.
	Zhang Mingchao, Sun Xinbo, Wang Yongxia. A Case Study on the Internal Mechanism of Data Enablement Driving Lean Production Innovation[J]. Nankai Business Review, 2021, 24(3): 102-114.
4	Zhou Binghai, He Zhaoxu. A Static Semi-kitting Strategy System of JIT Material Distribution Scheduling for Mixed-flow Assembly Lines[J]. Expert Systems with Applications, 2021, 184: 115523.
5	Emde S, Boysen N. Optimally Routing and Scheduling Tow Trains for JIT-supply of Mixed-model Assembly Lines[J]. European Journal of Operational Research, 2012, 217(2): 287-299.
6	胡蓉, 陈文博, 钱斌, 等. 学习型蚁群算法求解绿色多车场车辆路径问题[J]. 系统仿真学报, 2021, 33(9): 2095-2108.
	Hu Rong, Chen Wenbo, Qian Bin, et al. Learning Ant Colony Algorithm for Green Multi-depot Vehicle Routing Problem[J]. Journal of System Simulation, 2021, 33(9): 2095-2108.
7	Miranda D M, Conceição S V. The Vehicle Routing Problem with Hard Time Windows and Stochastic Travel and Service Time[J]. Expert Systems with Applications, 2016, 64: 104-116.
8	Zhang Defu, Cai Sifan, Ye Furong, et al. A Hybrid Algorithm for a Vehicle Routing Problem with Realistic Constraints[J]. Information Sciences, 2017, 394-395: 167-182.
9	Koulamas C, Kyparisis G J. The No-wait Flow Shop with Rejection[J]. International Journal of Production Research, 2021, 59(6): 1852-1859.
10	Driscoll J, Thilakawardana D. The Definition of Assembly Line Balancing Difficulty and Evaluation of Balance Solution Quality[J]. Robotics and Computer-Integrated Manufacturing, 2001, 17(1/2): 81-86.
11	Becker C, Scholl A. A Survey on Problems and Methods in Generalized Assembly Line Balancing[J]. European Journal of Operational Research, 2006, 168(3): 694-715.
12	邓超, 钱斌, 胡蓉, 等. 融合规则的HEDA求解带工件批量运输的三阶段装配集成调度问题[J]. 控制与决策, 2020, 35(10): 2507-2513.
	Deng Chao, Qian Bin, Hu Rong, et al. Rule-based Hybrid EDA for Three-stage Assembly Integrated Scheduling Problem with Job Batches Transportation[J]. Control and Decision, 2020, 35(10): 2507-2513.
13	周炳海, 彭涛. 混流装配生产线准时化物料补给调度方法[J]. 控制与决策, 2017, 32(6): 976-982.
	Zhou Binghai, Peng Tao. Scheduling Methods of Just-in-time Material Replenishment in Mixed-model Assembly Lines[J]. Control and Decision, 2017, 32(6): 976-982.
14	Fathi M, Rodríguez V, Fontes D B M M, et al. A Modified Particle Swarm Optimisation Algorithm to Solve the Part Feeding Problem at Assembly Lines[J]. International Journal of Production Research, 2016, 54(3): 878-893.
15	Golz J, Gujjula R, Günther H O, et al. Part Feeding at High-variant Mixed-model Assembly Lines[J]. Flexible Services and Manufacturing Journal, 2012, 24(2): 119-141.
16	Rahman H F, Janardhanan M N, Nielsen P. An Integrated Approach for Line Balancing and AGV Scheduling Towards Smart Assembly Systems[J]. Assembly Automation, 2020, 40(2): 219-234.
17	Mladenović N, Hansen P. Variable Neighborhood Search[J]. Computers & Operations Research, 1997, 24(11): 1097-1100.
18	严洪森, 万晓琴, 熊福力. 基于VNS-EM混合算法的两阶段装配流水车间调度[J]. 东南大学学报(自然科学版), 2014, 44(6): 1285-1289.
	Yan Hongsen, Wan Xiaoqin, Xiong Fuli. Two-stage Assembly Flow Shop Scheduling Based on Hybrid VNS-EM Algorithm[J]. Journal of Southeast University(Natural Science Edition), 2014, 44(6): 1285-1289.
19	南丽君, 陈彦如, 张宗成. 改进的自适应大规模邻域搜索算法求解动态需求的混合车辆路径问题[J]. 计算机应用研究, 2021, 38(10): 2926-2934.
	Lijun Nan, Chen Yanru, Zhang Zongcheng. Improved Adaptive Large Neighborhood Search Algorithm for Mixed Fleet Routing Problem of Dynamic Demands[J]. Application Research of Computers, 2021, 38(10): 2926-2934.
20	Hansen P, Mladenović N. Variable Neighborhood Search: Principles and Applications[J]. European Journal of Operational Research, 2001, 130(3): 449-467.
21	Prajapati A, Chhabra J K. Information-theoretic Remodularization of Object-oriented Software Systems[J]. Information Systems Frontiers, 2020, 22(4): 863-880.
22	Tang Qiuhua, Li Zixiang, Zhang Liping. An Effective Discrete Artificial Bee Colony Algorithm with Idle Time Reduction Techniques for Two-sided Assembly Line Balancing Problem of Type-II[J]. Computers & Industrial Engineering, 2016, 97: 146-156.
23	Ishibuchi H, Yoshida T, Murata T. Balance between Genetic Search and Local Search in Memetic Algorithms for Multiobjective Permutation Flowshop Scheduling[J]. IEEE Transactions on Evolutionary Computation, 2003, 7(2): 204-223.
24	郑逸凡, 钱斌, 胡蓉, 等. CE-GA协同进化算法求解人机共同作业的U形装配线平衡问题[J]. 机械工程学报, 2020, 56(9): 199-214.
	Zheng Yifan, Qian Bin, Hu Rong, et al. CE-GA Co-evolutionary Algorithm for Solving U-shaped Assembly Line Balancing Problem with Man-robot Cooperation[J]. Journal of Mechanical Engineering, 2020, 56(9): 199-214.
25	Deb K, Pratap A, Agarwal S, et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
26	Zhang Qingfu, Li Hui. MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731.

[1]	余佳英, 张宏立, 董颖超. 基于离散状态转移算法的无等待流水车间调度研究[J]. 系统仿真学报, 2023, 35(5): 1034-1045.
[2]	胡蓉, 丁帅, 钱斌, 张长胜. 超启发式三维EDA求解绿色双边装配线平衡问题[J]. 系统仿真学报, 2023, 35(3): 454-469.
[3]	范厚明, 咸富山, 王怀奇. 动态需求下考虑订单聚类的外卖配送路径优化[J]. 系统仿真学报, 2023, 35(2): 396-407.
[4]	古鹏飞, 张霖, 陈真, 叶俊杰. 基于X语言的起飞场景民机协同设计与仿真一体化方法[J]. 系统仿真学报, 2022, 34(5): 929-943.
[5]	张凯庆, 嵇启春. 速度时变的多中心半开放式车辆路径问题研究[J]. 系统仿真学报, 2022, 34(4): 836-846.
[6]	王伟权, 丁鼎, 曹淑艳. 混合变邻域搜索算法求解大规模电动车辆路径优化问题[J]. 系统仿真学报, 2022, 34(4): 910-919.
[7]	范双南, 陈纪铭, 高为民, 王增凤. 基于改进智能水滴算法的动态车辆配送路径优化[J]. 系统仿真学报, 2020, 32(9): 1808-1817.
[8]	王恒, 徐亚星, 王振锋, 周天鹏, 田德春. 基于道路状况的生鲜农产品配送路径优化[J]. 系统仿真学报, 2019, 31(1): 126-135.
[9]	张小平, 饶盛华, 张铸, 赵轩. 基于混沌果蝇算法的SRM多目标协同优化研究[J]. 系统仿真学报, 2018, 30(7): 2640-2647.
[10]	张静华, 韩璞. 多算法多种群协同优化差分进化算法[J]. 系统仿真学报, 2018, 30(5): 1690-1699.
[11]	陈文杰, 王艳. 离散制造过程生产协同能耗优化调度方法[J]. 系统仿真学报, 2018, 30(11): 4367-4375.
[12]	陈静, 吕玉超, 王利敏. 一种快速收敛的动态松弛协同优化方法[J]. 系统仿真学报, 2018, 30(1): 96-104.