Mentally I tend to further categorise heuristics into "construction" and "improvement" heuristics. Your "shortest path" is a construction heuristic that I normally call "nearest neighbour". Other common heuristics are "greedy" (iteratively add the shortest feasible edge) and "farthest insertion" (iteratively add the farthest point from the subtour to the best position). There's an interesting synergy between construction and improvement strategies, e.g. 2-opt might be more worthwhile after nearest neighbour than greedy. It would be extra awesome to be able to choose both construction as well as improvement and see how it pans out.
Thanks so much! I haven't formally studied these so the terminology still gets me sometimes.
When you say "choose construction as well as improvement", I'm curious what you mean. It may not be clear, but if you run shortest path, the resulting best path is fed into whatever algorithm you run next. Is that what you mean?
Ah I see, I didn't realise you could combine heuristics. I still think it would be cool if you could pick from multiple construction heuristics (shortest path, farthest insertion...), followed by which improvement heuristic/s you want to use (2-opt, 3-opt...).
The choice of which heuristics you use and what order you do them in is sometimes called your meta heuristic strategy.
I've been thinking about this problem for a while with a little twist. What if you wanted to run/walk all the streets in your city? What is the shortest path to do it? How do you calculate the number of kilometers of streets in a city?
Nice. If I can suggest a cosmetic improvement, you list number of possible paths, it would be cool to see how many paths algorithm tried so far until it finishes (and how many paths it tried in total).
Mentally I tend to further categorise heuristics into "construction" and "improvement" heuristics. Your "shortest path" is a construction heuristic that I normally call "nearest neighbour". Other common heuristics are "greedy" (iteratively add the shortest feasible edge) and "farthest insertion" (iteratively add the farthest point from the subtour to the best position). There's an interesting synergy between construction and improvement strategies, e.g. 2-opt might be more worthwhile after nearest neighbour than greedy. It would be extra awesome to be able to choose both construction as well as improvement and see how it pans out.