Research On Fluctuating Temperature Controlled Simulated Annealing Algorithm For Solving TSP And FSTS

The Traveling Salesman Problem(TSP)is a classic combinatorial optimization problem,which widely exists in many fields of production and life.For many years,researchers have proposed many algorithms to solve this problem,but it is usually difficult to give consideration to both the solution time and accuracy,especially for large-scale TSP,many algorithms are helpless.On the basis of the TSP,there are some nodes that cannot be served by trucks and need to be accessed by drones carried by trucks.This leads to the“single machine single vehicle”intermodal transportation model of truck and drone collaborative transportation problem(FSTSP),which is also an NP hard problem,and the solution space and complexity are greater than TSP.Simulated annealing algorithm is a classic heuristic algorithm for solving combinatorial optimization problems.Its principle comes from the heat treatment process of metal,in which the temperature control strategy is the key link to balance the efficiency and quality of solution.However,the algorithm has some shortcomings such as difficulty in setting temperature parameters,slow solving speed,etc.,which affects the application of the algorithm to a certain extent.In view of this,this article has conducted a systematic reserch on the temperature control mechanism of simulated annealing algorithms,and designed an adaptive simulated annealing algorithm with fluctuation temperature control mechanism to solve TSP and FSTSP.Improvements have been made from five aspects: initial temperature setting,neighborhood search mechanism,Metropolis criterion optimization,number of internal loops,and temperature control function.The key step of the algorithm is to use the ratio of adjacent temperatures as the basis for the change in the number of internal loop searches,and innovatively introduce the improved fluctuation function as the temperature control function into the annealing process of the algorithm.Based on the number of improvement times of the objective function reflected in the Metropolis criterion and the current iteration number of the algorithm,the coefficient of the fluctuation temperature control function is adaptively adjusted,so that the algorithm maintains the overall trend of decreasing temperature amplitude,it can achieve multiple heating and cooling,thereby increasing the probability of the algorithm jumping out of local optima,enhancing the solving effect,and shortening the solving time.Using the fluctuation temperature controlled simulated annealing algorithm to solve the TSP can quickly converge to the vicinity of the optimal value for most instances,which is a performance that other temperature controlled simulated annealing algorithms do not have.Especially for some larger scale instances,they can quickly obtain the optimal solution or highly satisfactory solution.Expanding the use of temperature control algorithms to the problem of truck unmanned aerial vehicle intermodal transportation,taking into account the situation where a single release of unmanned aerial vehicles can serve multiple customers,which was rarely considered in previous research,and using the fluctuation temperature control simulated annealing algorithm for solving,good solution results were also achieved.Further evidence is provided for the effectiveness of the simulated annealing algorithm for fluctuating temperature control.