Journal of Jilin University(Engineering and Technology Edition) ›› 2024, Vol. 54 ›› Issue (7): 1851-1861.doi: 10.13229/j.cnki.jdxbgxb.20221178

Previous Articles    

Parallel row ordering problem based on improved sparrow search algorithm

Ze-qiang ZHANG(),Can WANG,Jun-qi LIU,Dan JI,Si-lu LIU   

  1. 1.School of Mechanical Engineering，Southwest Jiaotong University，Chengdu 610031，China
    2.Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province，Southwest Jiaotong University，Chengdu 610031，China
  • Received:2022-09-12 Online:2024-07-01 Published:2024-08-05

RICH HTML

 3   

PDF (PC)

73

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

CLC Number: 

  • TH181

Fig.1

Example diagram of EPROP"

Fig.2

Coding and decoding process"

Fig.3

Operator of algorithm"

Table 1

Algorithm parameter settings"

SSA/GAnNpopitermax
25~301 0002 000
33~402 0003 000
42~494 0005 000
SAnInitialTempitermaxFinalTempTempfactor
25~301 0001000.010.99
33~402 0002000.010.99
42~493 0003000.010.99
ISSAnNpopitermaxbyPcpPi
11，15801500.20.80.40.1
25~302003000.20.80.40.1
33~403005000.30.80.40.1
42~495008000.40.80.40.1

Table 2

Small scale calculation verification"

算例LingoISSA
objT/sobjavgT/s
S11t=n/24 854.253.774 854.254 854.251.706 9
t=n/36 212.751.626 212.756 212.751.535 7
t=n/46 212.751.626 212.756 212.751.535 7
t=n/56 444.252.326 444.256 444.251.429 9
Am15t=n/24 81215.454 8124 8122.225 2
t=n/35 00620.015 0065 0062.397 8
t=n/45 00620.015 0065 0062.397 8
t=n/56 444.2523.26 444.256 444.251.429 9

Table 3

Solution results comparison"

算例nLingoSAGASSAISSA
N25_01252 662.52 927.52 631.52 777.02 588.0
N25_022521 507.825 028.821 216.322 121.320 912.3
N25_032513 534.515 317.013 422.514 144.513 230.0
N25_042528 184.833 374.327 907.328 867.327 310.3
N25_05259 190.010 252.08 979.09 733.08 954.0
N30_01305 173.55 258.54 560.54 928.04 514.0
N30_023013 590.314 072.812 523.813 709.312 330.8
N30_033028 036.031 093.025 389.528 174.025 172.5
N30_043038 570.343 379.336 729.839 372.835 832.3
N30_053073 588.583 470.567 836.076 264.566 527.5
P33347 879.854 167.345 081.849 515.344 438.8
P63543 532.344 514.338 808.842 771.338 292.3
ste36_01367 837.510 698.57 353.59 184.07 298.0
ste36_0236157 055.0208 048.0139 062.5172 012.5137 466.0
ste36_03367 7693.8124 219.373 969.897 302.372 372.8
ste36_043679 692.3122 244.371 509.384 604.370 150.8
ste36_053677 025.8111 197.377 131.380 350.866 459.8
N40_014072 902.874 304.362 403.369 908.361 193.3
N40_024065 786.070 374.55 623.064 219.556 009.5
N40_034057 071.2560 020.847 951.854 798.846 940.8
N40_044054 572.060 989.048 479.054 807.547 173.5
N40_054076 452.070 595.058 600.564 066.556 901.5
sko_42_014216 796.015 646.014 012.514 920.513 710.5
sko_42_0242155 067.8161 721.8137 287.3147 623.8135 459.3
sko_42_0342120 418.2118 653.3102 656.8110 020.397 690.8
sko_42_044293 065.088 583.076 545.081 462.574 249.5
sko_42_0542169 839.8167 471.8140 673.3151 378.8135 489.3
sko_49_014925 874.524 449.022 077.523 508.521 674.0
sko_49_0249287 104.5280 251.0234 276.5257 728.0225 958.5
sko_49_0349220 384.0214 478.5181 345.5201 103.0176 884.5
sko_49_0449158 653.8151 314.8130 268.3144 403.8125 273.3
sko_49_0549433 603.0418 011.5361 206.5390 612.5349 249.0

Fig.4

Homework unit boxplot of SSA and ISSA"

Table 4

Homework unit length and width"

U1U2U3U4U5U6U7U8U9U10

33×

15

30×

15

32×

15

26×

15

14×

15

15×

15

33.5×

15

38×

15

32×

15

20×

15

Fig.5

Actual case layout"

Table 5

Logistics matrix"

U1U2U3U4U5U6U7U8U9U10
U1011.34.51.71.501000
U211.301.510.806.51.500
U34.51.501.3102.5200
U41.711.302011.500
U51.50.812000.5000
U60000001200
U716.52.510.510000
U801.521.5020040
U90000000404
U100000000040
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.
[1] Cai-xia SHU,Jia YANG,Qing-xi LIAO,Xing-yu WAN,Jia-cheng YUAN. Design and experiment of diversion type double-cylinder cyclone separation system for rapeseed combine harvester [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(6): 1807-1820.
[2] Li HUI,Lei JIN,Wan-wan SONG,Song ZHOU,Jin-lan AN. Crack growth rate of SMA490BW steel in different welding areas for bogie [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(3): 650-656.
[3] Jin DUAN,An-ni YAO,Zhen WANG,Lin-tao YU. Improved sparrow search algorithm optimizes coverage in wireless sensor networks [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(3): 761-770.
[4] Zhong-xing DUAN,Rui-xing LIU,Chong LIU. 3DDV⁃Hop node localization optimized based on multi⁃strategy improved sparrow search algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(3): 771-784.
[5] Zhi-jun YANG,Chi ZHANG,Guan-xin HUANG. Mechanical model of rigid⁃flexible coupling positioning stage based on floating coordinate method [J]. Journal of Jilin University(Engineering and Technology Edition), 2024, 54(2): 385-393.
[6] Lin-rong SHI,Wu-yun ZHAO. Design and test of rolling spoon type flaxes precision hole sower for caraway in northwest cold and arid agricultural region [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(9): 2706-2717.
[7] Bo-sen CHAI,Guang-yi WANG,Dong YAN,Guo-ren ZHU,Jin ZHANG,Heng-sheng LYU. Numerical simulation of cavitation in torque converter and analysis of its influence on performance [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(8): 2236-2244.
[8] Guo-hui CHEN,Ye-yin XU,Ying-hou JIAO. Meshing stiffness calculation and vibration analysis of helical gear considering deflection [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(7): 1902-1910.
[9] Sheng LI,Jia ZHU,De-hui HUANG,Cun-fu CHEN,Hong-qing FEI,Wei FENG,Xing-jun HU. Structural parameters optimization of louver fins of air⁃cooled charge air cooler [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(4): 998-1006.
[10] Jian WANG,Wei YU,Bin WANG. Effects of methanol substitution percent on combustion and emission of diesel engines under plateau condition [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(4): 954-963.
[11] Li-juan YU,Yang AN,Jia-long HE,Guo-fa LI,Sheng-xu WANG. Research progress and development trend of extrapolation method in electromechanical equipment load spectrum [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(4): 941-953.
[12] Qiang GUO,Guo-hui ZHU,Wan-chen LI. TDOA/FDOA localization based on chaotic sparrow search algorithm [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(2): 593-600.
[13] Bo-sen CHAI,Dong YAN,Guang-yi WANG,Wen-jie ZUO. Three-dimensional vortex characteristic analysis and simulation evaluation of peach cavity hydrodynamic coupling under braking condition [J]. Journal of Jilin University(Engineering and Technology Edition), 2023, 53(11): 3045-3055.
[14] Zhen SONG,Jie LIU. Time series prediction algorithm of vibration frequency of rotating machinery [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(8): 1764-1769.
[15] Ling ZHU,Qiu-cheng WANG. New energy vehicle drive system coordinated control method under spatial geometric constraints [J]. Journal of Jilin University(Engineering and Technology Edition), 2022, 52(7): 1509-1514.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd