农机作业路径优化的研究——基于旅行商问题新算法

The Optimization of the Path of Agricultural Operations——Based on a New Algorithm for Traveling Salesman Problem

基于旅行商问题的特点与性质,设计了一种新的启发式算法。算法设计上首先从降维角度出发,先对图上各节点进行区域划分,然后在区域内部找到最小生成树,再将大于2的节点打断重新连接成除始点和终点外度均为2的树,最后相邻区域始点终点相连便可得到问题的解。通过两个实例论证说明,此种启发式算法可以有效地避免不同区域之间若干点的往返。基于此优点,将该算法应用到农机作业路径的优化中,为农机户的日常作业经营提供参考。

Based on the characteristics and properties of the traveling salesman problem,design a new heuristic algorithms.First,from algorithm design dimensionality reduction perspective,the first of the map for a regional breakdown of each node,and then inside the region to find the minimum spanning tree,and then interrupted by more than two nodes connected in addition to re-start and end points are the two outer degree of tree,and finally connected to the end adjacent areas can be the starting point solution of the problem.Demonstrated through two examples illustrate,this heuristic algorithm can effectively avoid a number of points between the different areas of the round trip.Based on this advantage,the algorithm is applied to the optimization of the path of agricultural operations,in order to run daily operations of agricultural households to provide a reference.