Open AccessResearch on agricultural machinery operation path optimization based on traveling salesman problem (TSP)
Author(s) -
Huichuan Liao
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1976/1/012051
Subject(s) - travelling salesman problem , mathematical optimization , heuristic , minimum spanning tree , path (computing) , computer science , spanning tree , tree (set theory) , graph , mathematics , algorithm , combinatorics , theoretical computer science , programming language
Based on the characteristics and properties of TSP, a new heuristic algorithm is designed. Firstly, the nodes on the graph are divided into regions, and then the minimum spanning tree is found in the region. Then, the nodes larger than 2 are broken and reconnected into trees with 2 degrees except the start and end points. Finally, the start and end points of adjacent regions are connected to get the solution of the problem. Two examples show that this heuristic algorithm can effectively avoid the round trip of several points between different regions. The algorithm is applied to the optimization of agricultural machinery operation path, which provides a reference for the daily operation of agricultural machinery households.