一种基于均匀设计穷举法的TSP问题求解方法

摘要

本发明涉及一种基于均匀设计穷举法的TSP问题求解方法。通过计算机程序，利用均匀设计来对穷举法中的部分路径排列方式进行设计，并通过逐步确定城市编号顺序的方式进行路径优化。该方法包括：首先，确定已选择城市列表以及未选择城市列表，从未选择城市列表中选取3个城市编号后与已选择城市列表组合得到部分路径。其次，利用均匀设计对剩余的路线进行设计，计算所有得到的路径的距离后记录最短的路径。之后，对3个城市的所有情况进行穷举并重复上述步骤，在记录的路径中选出最短的一条，据此确定下一个城市的编号并加入已选择城市列表中。最后，通过以上过程逐一确定城市直到城市列表中包含了所有的城市，该列表就是得到的最佳路径。