Half Plane Converging Point Groups TSP Geometric Method And Its Application In Logistics Path Optimization

With the vigorous development of electronic commerce,logistics distribution has become a new industry in the national economy.Vehicle optimal scheduling is an important part of logistics distribution.Path planning of logistics is the foundation of the vehicle optimal scheduling.Path planning belongs to the traveling salesman problem.From the perspective of graph theory,it is to find the optimal hamiltonian circuit problem in weighted graph.Commonly used method are the nearest neighbor method,the minimum spanning tree method,the minimum weight matching algorithm and improved circle algorithm and so on. These algorithms are some approximation algorithms.It is not proved by theory that the Hamiltonian circuit is optimal and it is attributed to the non-deterministic polynomial of combinatorial optimization in graph theory.The main focus of these algorithms is on using optimization method to solve at present,such as simulated annealing,genetic algorithm,evolutionary computation, particle swarm optimization, ant colony and so on. Their research objects are arbitrary directed graphs, and can not be combined with the spatial distribution of logistics distribution target stores.Therefore, it is significant to study the method of solving the logistics path planning problem in practical production.In the real practice of logistics distribution, logistics distribution is affected by these characteristics such as vehicle loading capacity constraints, a small number of single distribution stores and stores the relative aggregation. Based on graph generating Hamilton cycle theory, simplified mathematical model of logistics stowage, defining the half plane aggregation point group concept, half plane set accumulation group TSP geometric solving method is proposed. The basic starting point is: the vertex distance is used as the weighted graph, and the spatial distribution of the Hamilton ring of the graph is related to the spatial distribution of the vertex. The spatial distribution of the constraint graph in the actual production environment can simplify the TSP solution.The specific approach of half plane of focus groups TSP geometric method is: do point group bisector, do the point in the distance from the point of the source point to the length of the distribution line and choose from the point to the nearest vertex and starting point to form the initial line. The order of addition of other points is: add points to get the largest increase of the initial line, and we can decide to put it in loop or path by the length of increased distance. Theoretically it is proved that the loop which is generated by that method is Hamiltonian circuit, analyzing the rationality of the method, giving the program implementation of the method, calculating the complexity of the algorithm, discussing the various situations when the half plane clustered point group are not satisfied by using that method in path planning of logistics.A solution is proposed that the decomposition point group is combined by a number of Hamilton ring to form circle.Half plane of focus groups TSP geometric method through the theoretical analysis is compared with greedy algorithm and genetis algorithm experimentally, the following are the conclusions:(1) the algorithm uses the vertex space distribution feature, and the algorithm complexity is low;(2) for the half plane of focus groups, the generated loop is superior to the Hamilton ring.The method has a high accuracy and stability,and can be applied to the actual logistics path planning.According to the characteristics of logistics path planning, the points set of half plane of focus groups TSP geometric method makes use of space distribution characteristics of the vertices of the graph and simplified mathematical model to solve the path planning problem of logistics better.