There’s a trivial algorithm running in n! . That would be good enough for n=12. N=16 would talk about 43,000 times longer - probably just outside what you’d call a solution. Here’s a method that should save you just enough time to solve for n=16:
Take a sub tour abcd. If the distance abcd is longer than the distance acbd then abcd cannot be part of an optimal tour (since swapping b and c creates a shorter tour). If both sub tours have the same length we can arbitrarily exchange b and c if b is later in the alphabet than c. So we accept exactly half of the subsequences in an attempt to find an optimal tour.
Now we pick any fixed city b as the second city. We don’t need to try different cities as the second city because we can rotate the tour. We then pick any a and c as the first and third city, picking their order so that a comes before c in the alphabet. There are 15 x 14 / 2 = 105 choices for these three cities.
Then we choose the fourth city d. But instead of 13 choices, the requirement that abcd is not longer than acbd removes on average half the choices, so 6.5 on average. For cities 15 and 16 there is only one choice.
Total choices for the order of all cities is 15! / 2^13 ≈ 160,000,000. You’ll need to implement this in an efficient way. For general n, it is (n-1)! / 2^(n-3).
You could improve this by choosing which sequences abcde are possible. B, c and d can be visited in six different orders, and only one can be optimal.