基于遗传算法的小规模TSP问题研究分析

Research Analysis of Small-scale TSP Problem Based on Genetic Algorithm

旅行商问题是一个经典的路径规划问题,传统TSP假设客户位置和客户之间旅行时间是固定不变的,而在现实生活中交通状况和客户要求可能会随着时间而改变,为了找到最经济的路线,可在业务员完成对每个客户的服务后做出实时决策。遗传算法具有全局搜索的性能,成为处理组合优化问题的常用方法。在此运用遗传算法,并借助MATLAB在实例中进行分析验证,结果证明利用遗传算法对求解小规模TSP问题可以得到较好的优化结果。

The traveling salesman problem( TSP) is a classical path planning problem. Traditional TSP assumes that the customer location and travel time between customers are fixed,while in real life traffic conditions and customer requirements may change over time,and in order to find the most economical route,real-time decisions can be made after the salesman has completed his service to each customer. Genetic algorithm has the performance of excelling in global search and becomes a common method to deal with combinatorial optimization problems. Genetic algorithm herein is applied in an example for analysis and verification with the help of MATLAB,and the results demonstrate that better optimization results can be obtained by using genetic algorithm for solving small-scale TSP problems.