CN-116308017-B - Logistics path planning method based on K-means clustering and improved genetic algorithm

CN116308017BCN 116308017 BCN116308017 BCN 116308017BCN-116308017-B

Abstract

The invention provides a logistics path planning method based on K-means clustering and an improved genetic algorithm, which comprises the following steps of clustering n clients, dynamically adjusting K values, selecting K clusters with the best clustering effect, encoding and decoding the K clusters, constructing an initial solution for each cluster s K to calculate the fitness of a population, constructing each cluster s K for multiple times to finish population initialization, judging whether a current population meets an algorithm termination criterion to output a current population optimal solution, outputting a population optimal solution meeting the algorithm termination criterion, judging whether the improved genetic algorithm traverses all clusters to carry out the next step, otherwise, carrying out population initialization again, and integrating the optimal solutions of the K clusters to obtain a problem overall solution. According to the invention, the algorithm clustering is used to reduce the scale of the optimization problem, and the heuristic algorithm is adopted to perform optimization calculation, so that the optimization speed is effectively increased, and the solution precision is improved.

Inventors

WANG LIN
JIAO HANYANG
PENG JINYE
ZHU XUAN
WANG JUN
JIANG BO
ZHAO WANQING
ZHANG ZHE
MA ZHENPENG

Assignees

西北大学

Dates

Publication Date: 20260512
Application Date: 20230315

Claims (5)

1. A logistics path planning method based on K-means clustering and improved genetic algorithm is characterized by comprising the following steps: S1, acquiring coordinate systems corresponding to n clients, clustering the n clients, and dynamically adjusting K values to select K clusters with the best clustering effect, wherein client groups of the K clusters are respectively in S= { , ,..., -Representation; S2, encoding and decoding the K clusters in S1, and encoding and decoding each cluster Constructing initial solutions to calculate fitness of the population, for each cluster Constructing multiple times to generate an initial solution population for each cluster To complete population initialization; S3, judging whether the current population meets the algorithm termination criterion to output the optimal solution of the current population, otherwise, regenerating the initial solution population of each cluster Optimizing using an improved genetic algorithm; S4, outputting a population optimal solution meeting an algorithm termination criterion, judging whether the improved genetic algorithm traverses all cluster types to carry out the next step, and if not, carrying out population initialization again; s5, integrating the optimal solutions of the K clusters to obtain an overall solution of the problem; the pair generates an initial solution population for each cluster class The improved genetic algorithm is used for optimization, namely, firstly, the genetic algorithm is adopted for optimization operation through selection, crossover, mutation and natural selection to generate a next generation solution, and then, a large-scale neighborhood search algorithm is adopted for operation on a new solution generated by the genetic algorithm, wherein the algorithm comprises a Remove process and a Re-inserting process; the Remove process is as follows: Step 21.1 from A client is randomly removed into D as the first element of set D; step 21.2, randomly selecting a client Z from the set D to be The rest clients are arranged in order of small to large correlation with Z from Selecting client C with maximum correlation with Z from Removing C and adding it to D; Step 21.3, repeating the step 21.2 for a total of E-1 times until all the remaining E-1 elements are selected to form a complete set D; The Re-inserting process comprises the following steps: Step 31.1, calculating the optimal insertion position of each client in the set D, finding out the position which minimizes the increase of the final optimization target from a plurality of insertion positions, namely the optimal insertion position, and recording the corresponding target value of each client to be inserted back in the set D; Step 31.2 selecting the customer plug-in partial solution with the smallest target value increment in D Update set D, go back to step 31.1 until all clients in D are reinserted back into the partial solution Obtaining a new complete solution 。
2. The logistics path planning method based on K-means clustering and improved genetic algorithm of claim 1, wherein the logistics path planning method is characterized by: the judging whether the current population meets the algorithm termination criterion is as follows: The final optimization objective of the VRPTW mathematical model is: (1) Wherein the constraint conditions: (2) (3) (4) (5) (6) (7) The parameters used in the model are defined as follows: N= {1,2,., N }; m= {1,2,., M }; d ij the distance between customer i and customer j; w is the maximum load of the vehicle; r i customer i's cargo demand; p a the travel path of vehicle a; [ T ei ,T li ] customer i's time window constraints; T ai the point in time when the vehicle arrives at customer point i; t wi waiting time of the vehicle at customer point i; t si service time at customer i; T ij time from customer i to customer j.
3. The logistics path planning method based on K-means clustering and improved genetic algorithm of claim 2, wherein the logistics path planning method is characterized by: The encoding and decoding of K clusters in S1 is as follows When the number of customers per cluster is N K and the maximum number of vehicle uses is m, each cluster has a viable solution length of N K +m-1, and each cluster has a viable solution expression form of (1, 2, 3.
4. The logistics path planning method based on K-means clustering and improved genetic algorithm of claim 1, wherein the logistics path planning method is characterized by: The pair of each cluster The construction is performed a plurality of times: step 1.1 initializing input ,W,P a ; Step 1.2 traversal Each of the clients in (a) ; Step 1.3, judging whether P a is empty or not, if P a is empty, then Adding P a , turning to step 1.2, otherwise turning to step 1.4; Step 1.4, judging the total cargo mass of the path P a Plus the cargo weight of the current customer point Whether or not it is equal to or less than the maximum load W of the vehicle, i.e Whether or not it is true, if so, then Adding P a according to the order of the left time window of the client in P a , turning to step 1.2, otherwise, storing the current P a , generating an empty P a+1 of the new vehicle, turning to step 1.3; Step 1.5, integrating and encoding the generated P a of a plurality of vehicles according to a coding and decoding method to generate clusters Is a solution to the initial solution of (2).
5. The logistics path planning method based on K-means clustering and improved genetic algorithm of claim 1, wherein the logistics path planning method is characterized by: integrating the optimal solutions of the K clusters to obtain an overall solution of the problem is: The obtained optimal solution of each cluster Integration is performed because of the optimal solution for each cluster All starting from the same distribution center and finally returning to the distribution center, so that only the optimal solutions of each cluster are integrated The distribution center of each cluster can be connected to get an overall problem solution.

Description

Logistics path planning method based on K-means clustering and improved genetic algorithm Technical Field The invention relates to the technical field of intelligent transportation, in particular to a logistics path planning method based on K-means clustering and an improved genetic algorithm. Background Many solutions have been presented to the vehicle path problem (Vehicle Routing Problem with Time Windows, VRPTW) with a time window, the solution algorithm of VRPTW can be divided into an accurate algorithm and a heuristic algorithm, the accurate algorithm finds the accurate solution of the problem by a strict mathematical method, the heuristic algorithm explores the relationship and rule from the algorithm and the model based on practical experience or reasoning, so as to obtain a heuristic in the searching process, the solution found by the heuristic is an approximate solution, and a certain deviation may exist from the optimal solution of the problem. The existing precise algorithm of the VRPTW mainly comprises a branch-and-bound method, a dynamic programming method and the like, wherein the VRPTW is solved by the branch-and-bound method, label storage information is added in a sub-problem by using the dynamic programming idea, a label method is provided for solving the VRPTW, however, the precise solution can be solved by using the method, but only the VRPTW with a small number of nodes can be solved, and in addition, the conventional precise solution is an optimal solution, and only a local optimal solution can be obtained sometimes due to the characteristics of an initial solution or the limitation of a searching method. The common method for solving the VRPTW based on the heuristic algorithm mainly comprises a simulated annealing algorithm (Simulated Annealing, SA), a Tabu Search algorithm (TS), a genetic algorithm (Genetic Algorithm, GA) and the like, wherein the simulated annealing algorithm is used for solving the VRPTW which considers time-varying travel time and aims at the minimum total energy consumption, the determined annealing algorithm is designed for solving a vehicle path Problem (CAPACITATED VEHICLE Routing Problem, CVRP) with capacity constraint, the calculation time of the method is shorter than that of the traditional simulated annealing algorithm, the Tabu Search algorithm is used for solving CVRP which considers the longest driving distance of a vehicle, and the heuristic algorithm can effectively process a large-scale VRPTW Problem but the solution accuracy is difficult to guarantee. The ideal VRPTW solving algorithm has accuracy and rapidity, wherein the accuracy refers to high algorithm solving quality and can effectively evaluate the solving quality, the rapidity refers to the requirement that the algorithm solving speed is high and the rapid solving of a large-scale problem can be realized, and therefore, the VRPTW solving method with accuracy and rapidity still needs to continue to explore. Disclosure of Invention The technical problem to be solved by the invention is to overcome the defects that the heuristic algorithm in the prior art can effectively treat large-scale problems, but the solution accuracy is generally difficult to evaluate and ensure, the optimization efficiency is reduced and local extremum is easy to fall into along with the increase of the problem scale, so that the logistics path planning method based on K-means clustering and improved genetic algorithm is provided. In order to solve the problems, the invention provides a logistics path planning method based on K-means clustering and improved genetic algorithm, which comprises the following steps: S1, acquiring coordinate systems corresponding to n clients, clustering the n clients, and dynamically adjusting K values to select K clusters with the best clustering effect, wherein client groups of the K clusters are respectively represented by S= { S 1,s2,...,sK }; S2, coding and decoding K clusters in S1, constructing an initial solution for each cluster S K to calculate the fitness of the population, and constructing each cluster S K for a plurality of times to generate an initial solution population for each cluster To complete population initialization; S3, judging whether the current population meets the algorithm termination criterion to output the optimal solution of the current population, otherwise, regenerating the initial solution population of each cluster Optimizing by using a genetic algorithm; S4, outputting a population optimal solution meeting an algorithm termination criterion, judging whether the improved genetic algorithm traverses all cluster types to carry out the next step, and if not, carrying out population initialization again; And S5, integrating the optimal solutions of the K clusters to obtain a problem overall solution. Preferably, the determining whether the current population meets the algorithm termination criterion is: in order to be able to clearly describe the mathematica