The path planning based on improved genetic algorithm for “water spider” under stack scheduling strategy

doi:10.16731/j.cnki.1671-3133.2019.01.007

Abstract

Abstract: Because the operation path of “water spider” is longer under the stack strategy,choosing it as the research object,based on the characteristics of “water spider” work.Regard the path planning of “water spider” under this strategy as Traveling Salesman Problem(TSP).Because the actual channel is horizontal and vertical line in the factory,choosing the sum of the Manhattan distance after the “water spider” move to all stages and changing the way to solve the TSP in Euclidean distance.Based on the improved genetic algorithm to optimize for it,introduced the reverse evolution operator to improve the local search ability,then using the Matlab to do simulation experiments.The results show that the algorithm can get the approximate optimal solution in path planning of the “water spider”.

Key words: “water spider” work, Manhattan distance, stack scheduling policy, improved genetic algorithm, path planning

CLC Number:

F273
F406.2

Wang Guiyong, Zhou Ermin. The path planning based on improved genetic algorithm for “water spider” under stack scheduling strategy[J]. Modern Manufacturing Engineering, 2019, 460(1): 38-42.

References 14

[1]	杨建宏,殷卫民,黄华.精益生产实战应用[M].北京: 经济管理出版社,2010.
[2]	刘世清,杨孔雨.求解TSP问题的遗传算法改进研究[J].北京信息科技大学学报(自然科学版),2014(2):46-50.
[3]	URSANI Z,ESSAM D,CORNFORTH D,et al.Localized genetic algorithm for vehicle routing problem with time windows[J].Applied Soft Computing,2011,11(8):5375-5390.
[4]	GROBA C,SARTAL A,VÁZQUEZ X H.Solving the dynamic traveling salesman problem using a genetic algorithm with trajectory prediction: An application to fish aggregating devices[J].Computers & Operations Research,2015(56):22-32.
[5]	YANIK S,BOZKAYA B,DEKERVENOAEL R.A new VRPPD model and a hybrid heuristic solution approach for e-tailing[J].European Journal of Operational Research,2014,236(3):879-890.
[6]	ALBAYRAK M,ALLAHVERDI N.Development a new mutation operator to solve the Traveling Salesman Problem by aid of Genetic Algorithms[J].Expert Systems with Applications,2011,38(3):1313-1320.
[7]	NAGATA Y,SOLER D.A new genetic algorithm for the asymmetric traveling salesman problem[J].Expert Systems with Applications,2012,39(10):8947-8953.
[8]	OSABA E,ONIEVA E,DIAZ F,et al.Comments on “ALBAYRAK M,ALLAHVERDY N.Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms[J].Expert Systems with Applications,2011,38(3):1313-1320.”: A proposal of good practice[J].Expert Systems with Applications,2014,41(4):1530-1531.
[9]	单春艳,姚鹏修.遗传算法在旅行商问题的研究与应用[J].工业控制计算机,2013(11):107-109.
[10]	储理才.基于MATLAB的遗传算法程序设计及TSP问题求解[J].集美大学学报(自然科学版),2001(1):14-19.
[11]	刘青凤,李敏.基于遗传算法的TSP问题优化求解[J].计算机与现代化,2008(2):43-44.
[12]	于莹莹,陈燕,李桃迎.改进的遗传算法求解旅行商问题[J].控制与决策,2014,29(8):1483-1488.
[13]	高海昌,冯博琴,朱利.智能优化算法求解TSP问题[J].控制与决策,2006(3):241-247.
[14]	周尔民,王贵用,朱进,等.基于排队论的“水蜘蛛”作业系统调度与仿真[J].工业工程与管理,2016(1):79-88.

[1]	MAO Kun, ZHU Xuejun, YANG Xudong, YU Checao. Robot vision polishing system for complex workpieces: path planning and force control research [J]. Modern Manufacturing Engineering, 2025, 538(7): 31-41.
[2]	DENG Zejian, YANG Miaosen, LIU Xiyang, DU Rongzhen, LIU Jianwei. Research on autonomous welding technology for curved workpieces based on structured light [J]. Modern Manufacturing Engineering, 2025, 538(7): 96-104.
[3]	DONG Jianlin, GUAN Yuanlin, CHENG Qi, XU Guangsheng, WANG Tichen. Mobile robot path planning based on sparrow search-ant colony algorithm [J]. Modern Manufacturing Engineering, 2025, 537(6): 58-66.
[4]	ZHAO Qian, SHI Yuqiang. Research on real time path planning and obstacle avoidance of AGV by integrating improved A^* algorithm and DWA [J]. Modern Manufacturing Engineering, 2025, 536(5): 91-98.
[5]	LIU Zhen, ZHANG Hong. Warehouse mobile robot path planning integrating improved bidirectional A^{* and dynamic window approach}[J]. Modern Manufacturing Engineering, 2025, 536(5): 99-105.
[6]	FU Dandan, LI Bo. Research on path planning algorithm of mobile robot based on improved RRT^* and DWA fusion [J]. Modern Manufacturing Engineering, 2025, 535(4): 91-97.
[7]	ZHU Min, CHEN Siyuan, CHEN Jie. Research on the path planning algorithm of RRT-Connect robotic arm based on improved artificial potential field guidance [J]. Modern Manufacturing Engineering, 2025, 533(2): 1-9.
[8]	ZHOU Guocheng, TAO Yifei, HE Yi, LI Lishan, WU Jiaxing. Research on the online scheduling problem of multi-AGVs in automatic packing system [J]. Modern Manufacturing Engineering, 2025, 533(2): 17-25.
[9]	ZHAO Zhengjun, HU Likun, CAI Chengjie, WEI Wenyang. Mobile robot path planning based on improved egret swarmoptimization algorithm [J]. Modern Manufacturing Engineering, 2025, 533(2): 37-43.
[10]	LI Dandan, ZHU Shilei, LI Zhongkang, JIE Baikun, WANG Hong. Path planning of mobile robot based on improved chameleon swarm algorithm [J]. Modern Manufacturing Engineering, 2024, 528(9): 40-45.
[11]	ZHOU Xiaoqing, TONG Yifei, ZHOU Kaijun. Research on path planning of multi-warehouse robots based on ISO-TW algorithm [J]. Modern Manufacturing Engineering, 2024, 528(9): 54-59.
[12]	QIU Wen, ZHANG Fan, TAN Yuegang, ZHANG Jun, TU Yiwen. Path planning method for continuous carbon fiber composites 3D printing based on principal stress trajectory lines [J]. Modern Manufacturing Engineering, 2024, 525(6): 22-27.
[13]	DUAN Fangzheng, XU Wubin, SUN Jinquan, LI Bing, WANG Jilin, TANG Junhao, LIU Shihang, WANG Xiujie. Research on optimal changing path planning for unmanned single-drum rollers [J]. Modern Manufacturing Engineering, 2024, 525(6): 135-144.
[14]	WU Mingyu, LEI Lu, HUANG Huiping, LIU Gongping, QIAO Xiaoli. Path planning of aviation harness based on joint point routing algorithm [J]. Modern Manufacturing Engineering, 2024, 523(4): 43-48.
[15]	LIU Shangjunnan, LIU Shuhai, XIAO Huaping. Path planning of electric vehicle mobile charging robot based on improved gray wolf optimization algorithm [J]. Modern Manufacturing Engineering, 2024, 523(4): 49-56.