The compelling advantage of our approach follows from the fact that the sum of factorials is much smaller than the factorial of the sum. For a TSP with Ncities, the search space is a function of N!. Thus the computing time, which is proportional to the search space, is also a function of N!. When N is a large number, the computing time is extremely long.
When decomposing the problem, if N cities are divided into P clusters, the
average number of cities in each cluster in N/P. Therefore, the search space
for each cluster is a function of (N/P)!. The total search space for all
clusters is: P(N/P)!. When N is large, our approach will save several
orders of magnitude worth of time since
