Learning Variable Neighborhood Search Algorithm for Transportation-assembly Collaborative Optimization Problem

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

Abstract

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

CLC Number:

TP391.9

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.

Figures/Tables 14

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Table 1

Neighborhood actions and related symbols

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

Table 1

Table 2

Table 3

Parameter level setting

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

Table 3

Table 4

Parameter setting and response value

组别	$α$	$β$	响应值
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

Table 4

Table 5

Parameter level and response value

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

Table 5

Fig. 6

Table 6

Comparison results of LVNS_TO、LVNS _GS and 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

Table 6

Fig. 7

Table 7

Comparison results of LVNS_DS、VNS、NSGA-Ⅱ and 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

Table 7

References 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]	Jiaying Yu, Hongli Zhang, Yingchao Dong. Research on No-Wait Flow Shop Scheduling Based on Discrete State Transition Algorithm [J]. Journal of System Simulation, 2023, 35(5): 1034-1045.
[2]	Zhijun Song, Zongyu Chen, Lü jing, Tianshu Wang. Rigid-liquid Coupling Simulation of Liquid-filled Spacecraft Based on OpenFOAM [J]. Journal of System Simulation, 2022, 34(8): 1789-1798.
[3]	Zheng Yang, Zhimin Xiang, Shiwen Ma. A Method of Loose Coupling Entity Modeling Based on Variable Rules [J]. Journal of System Simulation, 2022, 34(7): 1506-1511.
[4]	Pengfei Gu, Lin Zhang, Zhen Chen, Junjie Ye. Collaborative Design and Simulation Integrated Method of Civil Aircraft Take-off Scenarios Based on X Language [J]. Journal of System Simulation, 2022, 34(5): 929-943.
[5]	Kaiqing Zhang, Qichun Ji. Research on Multi-depot Half-open Vehicle Routing Problem with Time-varying Speed [J]. Journal of System Simulation, 2022, 34(4): 836-846.
[6]	Weiquan Wang, Ding Ding, Shuyan Cao. Hybrid Variable Neighborhood Search algorithm for the Multi-trip and Heterogeneous-fleet Electric Vehicle Routing Problem [J]. Journal of System Simulation, 2022, 34(4): 910-919.
[7]	Limei Wang, Hongyan Yao, Kang Zhang. Simulation of Robust Optimal Synchronization Control for Direct Drive H-Type Motion Platform [J]. Journal of System Simulation, 2022, 34(3): 527-535.
[8]	Qu Jue, Wang Dayan, Wang Wei, Dang Sina. Study on Bidirectional Coupling of Human Thermal Comfort Parameters and Cabin Thermal Environment [J]. Journal of System Simulation, 2022, 34(1): 20-35.
[9]	Li Hui, Yun Hao, Yue Hongli. Cloud Model PID Control of PMSM Based on SVM Inverse System [J]. Journal of System Simulation, 2021, 33(8): 1846-1855.
[10]	Gao Yang, Li Yanbin, Wang Ying, Zhang Ze, Lü Rui. Research on Variable Swept Wing Mode of Missile Based on Flutter Characteristics [J]. Journal of System Simulation, 2021, 33(5): 1224-1232.
[11]	Wang Wei, Chen Zhimei, Wang Zhenyan. Compensation Sliding Cross Coupling Control Research of Cartesian Coordinate Robot [J]. Journal of System Simulation, 2021, 33(4): 867-874.
[12]	Zhang Songzhi. Regional Integrated Energy System Model Based on Seasonal Load Difference [J]. Journal of System Simulation, 2021, 33(3): 562-571.
[13]	Ma Lixin, Zhu Yongjie, Ji Leyan. Neural Network Optimized Sensorless Permanent Magnet Synchronous Motor Control System [J]. Journal of System Simulation, 2021, 33(3): 622-630.
[14]	Liu Yunqin, Li Ni, Zhao Luming, Bai Jinpeng, Li Tingjun, Wang Chenguang. Real-time Simulation Technology of Fluid-thermo-solid Coupling of Hypersonic Vehicle [J]. Journal of System Simulation, 2021, 33(12): 2820-2827.
[15]	Xiu Supu, Wen Yuanqiao, Xiao Changshi, Yuan Haiwen, Zhan Wenqiang. Design and Simulation on Autonomous Landing of a Quad Tilt Rotor [J]. Journal of System Simulation, 2020, 32(9): 1676-1685.