基于改进麻雀搜索算法的平行行排序问题

doi:10.13229/j.cnki.jdxbgxb.20221178

摘要/Abstract

摘要：

针对平行行排序问题中的物流交互点位置问题，以车间布局为研究背景，提出了具备物流交互点及两行间距的平行行排序问题。以最小物流成本为目标，构建了混合整数规划模型，并运用Lingo求解器对小规模算例进行求解验证。结合问题特性，提出了一种改进的麻雀搜索算法。该算法采用佳点集初始化种群，使种群更具多样性，同时对警惕者数量动态变化，结合PMX交叉算子、连续2-opt算子、插入算子等操作加快求解速度，加入提前终止规则，减少冗余迭代次数。将本文算法与麻雀搜索算法、模拟退火算法、遗传算法等进行对比验证，用于求解25~49不同规模算例，结果表明本文算法在求解质量和求解速度上均具有一定优势。将本文算法应用在某生产车间布局中，对车间布局进行优化，改进后的布局降低了32.40%的物流成本，表明了本文模型及算法的有效性。

关键词: 机械工程, 平行行排序问题, 物流交互点, 麻雀搜索算法

Abstract:

Aiming at the lack of research on the parallel row ordering problem（PROP） of logistics interaction points， the PROP considering logistics interaction point and corridor width was proposed by taking workshop layout as the research background. A mixed-integer programming model with the goal of minimizing logistics costs was constructed. The solutions of a small-scale example were verified by Lingo solver. An improved sparrow search algorithm（ISSA） was proposed by combining the problem characteristics. The good point set was introduced for population initialization to make the population more diverse. The number of vigilants were changed dynamically by proposed algorithm， and algorithm performance was improved by combining operations such as PMX crossover operator， continuous 2-opt operator， and insertion operator. Early termination rule was applied to reduce redundant iterations. By comparing the ISSA with sparrow search algorithm， simulated annealing algorithm and genetic algorithm to solved 25-49 cases， it showed that ISSA has certain advantages in solution quality and solution speed. Finally， the proposed ISSA was applied to a production workshop layout in PROP mode， and the workshop layout was optimized. The results showed that the improved layout reduces the logistics cost by 32.40%， indicating the effectiveness of the proposed model and algorithm.

Key words: mechanical engineering, parallel row ordering problem, logistics interaction point, sparrow search algorithm

中图分类号:

TH181

张则强,王灿,刘俊琦,计丹,刘思璐. 基于改进麻雀搜索算法的平行行排序问题[J]. 吉林大学学报(工学版), 2024, 54(7): 1851-1861.

Ze-qiang ZHANG,Can WANG,Jun-qi LIU,Dan JI,Si-lu LIU. Parallel row ordering problem based on improved sparrow search algorithm[J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(7): 1851-1861.

图/表 10

图1

图2

图3

表1

表2

表3

图4

表4

图5

表5

参考文献 21

1	Salam Q D A, Gualtiero F, Franco F. Analysis of drivers for solving facility layout problems: a literature review[J]. Journal of Industrial Information Integration, 2021, 21: 100187.
2	Mojtaba K, Vahid M D, Sajjad A. A new intelligent algorithm for dynamic facility layout problem in state of fuzzy constraints[J]. Neural Computing and Applications, 2014, 24(5): 1179-1190.
3	Hosseini-Nasab H, Fereidouni S, Fatemi G S M T, et al. Classification of facility layout problems: a review study[J]. The International Journal of Advanced Manufacturing Technology,2018,94(1-4): 957-977.
4	查珊珊, 郭宇, 黄少华, 等. 不确定需求下的车间设施动态布局[J]. 吉林大学学报:工学版, 2017, 47(6): 1811-1821.
	Shan-shan Cha, Guo Yu, Huang Shao-hua, et al. Dynamic facility layout for workshop under uncertain product demands[J]. Journal of Jilin University (Engineering and Technology Edition), 2017, 47(6): 1811-1821.
5	Guan C, Zhang Z Q, Zhu L X, et al. Mathematical formulation and a hybrid evolution algorithm for solving an extended row facility layout problem of a dynamic manufacturing system[J]. Robotics and Computer-Integrated Manufacturing, 2022,78: 102379.
6	Liu J Q, Zhang Z Q, Chen F, et al. A novel hybrid immune clonal selection algorithm for the constrained corridor allocation problem[J]. Journal of Intelligent Manufacturing, 2022, 33(4): 953-972.
7	Zhang Z, Gong J, Liu J, et al. A fast two-stage hybrid meta-heuristic algorithm for robust corridor allocation problem[J]. Advanced Engineering Informatics, 2022, 53: 101700.
8	André R S A. A parallel ordering problem in facilities layout[J]. Computers & Operations Research,2013, 40(12): 2930-2939.
9	Hungerländer P. A semidefinite optimization approach to the parallel row ordering problem[R]. Technical Report, Alpen-Adria-Universität Klagenfurt,2015.
10	Maadi M, Javidnia M, Jamshidi R. Two strategies based on meta-heuristic algorithms for parallel row ordering problem[J]. Iranian Journal of Management Studies, 2017, 10(2): 467-498.
11	Yang X H, Cheng W M, Alice E S, et al. An improved model for the parallel row ordering problem[J]. The Journal of the Operational Research Society, 2020, 71(3): 475-490.
12	Gong J H, Zhang Z Q, Liu J Q, et al. Hybrid algorithm of harmony search for dynamic parallel row ordering problem[J]. Journal of Manufacturing Systems, 2021, 58: 159-175.
13	Cravo G L, Amaral A R S. Adaptive iterated local search for the parallel row ordering problem[J]. Expert Systems with Applications, 2022, 208: 118033.
14	计丹, 张则强, 刘俊琦,等. 具有安全间隙及物料装卸点的多行布局问题建模与优化[J]. 计算机集成制造系统, 2023, 29(9): 3074-3085.
	Ji Dan, Zhang Ze-qiang, Liu Jun-qi, et al. Modeling and optimization of multi-row layout problem with safety clearance and material handling points[J]. Computer Integrated Manufacturing Systems, 2023,29(9): 3074-3085.
15	Karateke H, Şahin R, Niroomand S. A hybrid Dantzig-Wolfe decomposition algorithm for the multi-floor facility layout problem[J]. Expert Systems with Applications, 2022, 206: 117845.
16	刘俊琦, 张则强, 王沙沙, 等. 考虑不规则物流交互点的过道布置问题建模与优化[J]. 计算机集成制造系统, 2021, 27(4): 1155-1166.
	Liu Jun-qi, Zhang Ze-qiang, Wang Sha-sha, et al. Modeling and optimization of corridor problem considering irregular logistics interaction points[J]. Computer Integrated Manufacturing Systems, 2021, 27(4): 1155-1166.
17	董舒豪, 徐志刚, 常艳茹, 等. 考虑物料装卸点与搬运通道的多行设施布局[J]. 计算机集成制造系统, 2021, 27(5): 1269-1280.
	Dong Shu-hao, Xu Zhi-gang, Chang Yan-ru, et al. Multi-row facility layout considering material loading/unloading points and handling passages[J]. Computer Integrated Manufacturing Systems, 2021, 27(5): 1269-1280.
18	Xue J K, Shen B. A novel swarm intelligence optimization approach: sparrow search algorithm[J]. Systems Science & Control Engineering, 2020, 8(1): 22-34.
19	吕鑫, 慕晓冬, 张钧,等. 混沌麻雀搜索优化算法[J]. 北京航空航天大学学报, 2021, 47(8): 1712-1720.
	Xin Lyu, Mu Xiao-dong, Zhang Jun, et al. Chaos sparrow search optimization algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2021, 47(8): 1712-1720.
20	国强,朱国会,李万臣. 基于混沌麻雀搜索算法的TDOA/FDOA定位[J]. 吉林大学学报:工学版, 2023,53(2):593-600.
	Guo Qiang, Zhu Guo-hui, Li Wan-chen. TDOA/FDOA localization based on chaotic sparrow search algorithm[J]. Journal of Jilin University (Engineering and Technology Edition), 2023,53(2):593-600.
21	段锦, 姚安妮, 王震, 等. 改进的麻雀搜索算法优化无线传感器网络覆盖[J]. 吉林大学学报: 工学版,2024, 54(3): 761-770.
	Duan Jin, Yao An-ni, Wang Zhen, et al. An improved sparrow search algorithm optimizes coverage in wireless sensor networks[J]. Journal of Jilin University (Engineering and Technology Edition), 2024, 54(3): 761-770.

相关文章 15

[1]	回丽,金磊,宋万万,周松,安金岚. 转向架用SMA490BW钢不同焊接区域裂纹扩展速率[J]. 吉林大学学报(工学版), 2024, 54(3): 650-656.
[2]	段锦,姚安妮,王震,于林韬. 改进的麻雀搜索算法优化无线传感器网络覆盖[J]. 吉林大学学报(工学版), 2024, 54(3): 761-770.
[3]	段中兴,刘瑞兴,刘冲. 多策略改进麻雀搜索算法优化三维DV-Hop节点定位[J]. 吉林大学学报(工学版), 2024, 54(3): 771-784.
[4]	杨志军,张驰,黄观新. 基于浮动坐标法的刚柔耦合定位平台力学模型[J]. 吉林大学学报(工学版), 2024, 54(2): 385-393.
[5]	石林榕,赵武云. 西北寒旱农区胡麻滚勺式精量穴播器的设计及试验[J]. 吉林大学学报(工学版), 2023, 53(9): 2706-2717.
[6]	柴博森,王广义,闫东,朱国仁,张进,吕恒升. 液力变矩器空化数值模拟及对性能的影响[J]. 吉林大学学报(工学版), 2023, 53(8): 2236-2244.
[7]	陈国辉,徐业银,焦映厚. 考虑偏转的斜齿轮啮合刚度及其振动分析[J]. 吉林大学学报(工学版), 2023, 53(7): 1902-1910.
[8]	陈贵升,罗国焱,李靓雪,黄震,李一. 柴油机颗粒捕集器孔道流场及其高原环境下噪声特性分析[J]. 吉林大学学报(工学版), 2023, 53(7): 1892-1901.
[9]	于立娟,安阳,何佳龙,李国发,王升旭. 机电装备载荷谱外推技术研究进展及发展趋势[J]. 吉林大学学报(工学版), 2023, 53(4): 941-953.
[10]	李胜,朱佳,黄德惠,陈存福,费洪庆,丰伟,胡兴军. 空冷中冷器百叶窗翅片结构参数优化[J]. 吉林大学学报(工学版), 2023, 53(4): 998-1006.
[11]	王建,于威,王斌. 高原状态下甲醇替代率对柴油机燃烧与排放的影响[J]. 吉林大学学报(工学版), 2023, 53(4): 954-963.
[12]	国强,朱国会,李万臣. 基于混沌麻雀搜索算法的TDOA/FDOA定位[J]. 吉林大学学报(工学版), 2023, 53(2): 593-600.
[13]	柴博森,闫东,王广义,左文杰. 制动工况桃腔偶合器三维涡特征分析及仿真评价[J]. 吉林大学学报(工学版), 2023, 53(11): 3045-3055.
[14]	朱凌,王秋成. 空间几何约束下新能源汽车驱动系统协调控制方法[J]. 吉林大学学报(工学版), 2022, 52(7): 1509-1514.
[15]	金兆辉,谷乐祺,洪伟,解方喜,尤田. 液压可变气门系统压力波动的影响分析[J]. 吉林大学学报(工学版), 2022, 52(4): 773-780.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

SSA/GA	n		N_pop		iter_max
	25~30		1 000		2 000
	33~40		2 000		3 000
	42~49		4 000		5 000
SA	n		InitialTemp		iter_max	FinalTemp	Tempfactor
	25~30		1 000		100	0.01	0.99
	33~40		2 000		200	0.01	0.99
	42~49		3 000		300	0.01	0.99
ISSA	n	N_pop	iter_max	by	Pc	p	Pi
	11，15	80	150	0.2	0.8	0.4	0.1
	25~30	200	300	0.2	0.8	0.4	0.1
	33~40	300	500	0.3	0.8	0.4	0.1
	42~49	500	800	0.4	0.8	0.4	0.1

算例		Lingo		ISSA
算例		obj	T/s	obj	avg	T/s
S11	t=n/2	4 854.25	3.77	4 854.25	4 854.25	1.706 9
	t=n/3	6 212.75	1.62	6 212.75	6 212.75	1.535 7
	t=n/4	6 212.75	1.62	6 212.75	6 212.75	1.535 7
	t=n/5	6 444.25	2.32	6 444.25	6 444.25	1.429 9
Am15	t=n/2	4 812	15.45	4 812	4 812	2.225 2
	t=n/3	5 006	20.01	5 006	5 006	2.397 8
	t=n/4	5 006	20.01	5 006	5 006	2.397 8
	t=n/5	6 444.25	23.2	6 444.25	6 444.25	1.429 9

算例	n	Lingo	SA	GA	SSA	ISSA
N25_01	25	2 662.5	2 927.5	2 631.5	2 777.0	2 588.0
N25_02	25	21 507.8	25 028.8	21 216.3	22 121.3	20 912.3
N25_03	25	13 534.5	15 317.0	13 422.5	14 144.5	13 230.0
N25_04	25	28 184.8	33 374.3	27 907.3	28 867.3	27 310.3
N25_05	25	9 190.0	10 252.0	8 979.0	9 733.0	8 954.0
N30_01	30	5 173.5	5 258.5	4 560.5	4 928.0	4 514.0
N30_02	30	13 590.3	14 072.8	12 523.8	13 709.3	12 330.8
N30_03	30	28 036.0	31 093.0	25 389.5	28 174.0	25 172.5
N30_04	30	38 570.3	43 379.3	36 729.8	39 372.8	35 832.3
N30_05	30	73 588.5	83 470.5	67 836.0	76 264.5	66 527.5
P3	33	47 879.8	54 167.3	45 081.8	49 515.3	44 438.8
P6	35	43 532.3	44 514.3	38 808.8	42 771.3	38 292.3
ste36_01	36	7 837.5	10 698.5	7 353.5	9 184.0	7 298.0
ste36_02	36	157 055.0	208 048.0	139 062.5	172 012.5	137 466.0
ste36_03	36	7 7693.8	124 219.3	73 969.8	97 302.3	72 372.8
ste36_04	36	79 692.3	122 244.3	71 509.3	84 604.3	70 150.8
ste36_05	36	77 025.8	111 197.3	77 131.3	80 350.8	66 459.8
N40_01	40	72 902.8	74 304.3	62 403.3	69 908.3	61 193.3
N40_02	40	65 786.0	70 374.5	5 623.0	64 219.5	56 009.5
N40_03	40	57 071.25	60 020.8	47 951.8	54 798.8	46 940.8
N40_04	40	54 572.0	60 989.0	48 479.0	54 807.5	47 173.5
N40_05	40	76 452.0	70 595.0	58 600.5	64 066.5	56 901.5
sko_42_01	42	16 796.0	15 646.0	14 012.5	14 920.5	13 710.5
sko_42_02	42	155 067.8	161 721.8	137 287.3	147 623.8	135 459.3
sko_42_03	42	120 418.2	118 653.3	102 656.8	110 020.3	97 690.8
sko_42_04	42	93 065.0	88 583.0	76 545.0	81 462.5	74 249.5
sko_42_05	42	169 839.8	167 471.8	140 673.3	151 378.8	135 489.3
sko_49_01	49	25 874.5	24 449.0	22 077.5	23 508.5	21 674.0
sko_49_02	49	287 104.5	280 251.0	234 276.5	257 728.0	225 958.5
sko_49_03	49	220 384.0	214 478.5	181 345.5	201 103.0	176 884.5
sko_49_04	49	158 653.8	151 314.8	130 268.3	144 403.8	125 273.3
sko_49_05	49	433 603.0	418 011.5	361 206.5	390 612.5	349 249.0

	U1	U2	U3	U4	U5	U6	U7	U8	U9	U10
U1	0	11.3	4.5	1.7	1.5	0	1	0	0	0
U2	11.3	0	1.5	1	0.8	0	6.5	1.5	0	0
U3	4.5	1.5	0	1.3	1	0	2.5	2	0	0
U4	1.7	1	1.3	0	2	0	1	1.5	0	0
U5	1.5	0.8	1	2	0	0	0.5	0	0	0
U6	0	0	0	0	0	0	1	2	0	0
U7	1	6.5	2.5	1	0.5	1	0	0	0	0
U8	0	1.5	2	1.5	0	2	0	0	4	0
U9	0	0	0	0	0	0	0	4	0	4
U10	0	0	0	0	0	0	0	0	4	0