A study of complexity transitions on the asymmetric traveling salesman problem

摘要

The traveling salesman problem (TSP) is one of the best-known combinatorial optimization problems. Branch-and-bound (BnB) is the best method for finding an optimal solution of the TSP. Previous research has shown that there exists a transition in the average computational complexity of BnB on random trees. We show experimentally that when the intercity distances of the asymmetric TSP are drawn uniformly from 0,1,2,…, r, the complexity of BnB experiences an easy-hard transition as r increases. We also observe easy-hard-easy complexity transitions when asymmetric intercity distances are chosen from a log-normal distribution. This transition pattern is similar to one previously observed on the symmetric TSP. We then explain these different transition patterns by showing that the control parameter that determines the complexity is the number of distinct intercity distances.