FEW COMPARISONS WITH STANDARD KNOWN HEURISTICS
This is a good time to compare applicability of our results with few of standard known methods for finding a optimal tour in ETSP. These results are summarized at http://www.research.att.com/~dsj/chtsp [A] and have been published as a report "The Traveling Salesman Problem and its Variations,"Gutinand Punnen (eds), Kluwer Academic Publishers, 2002, 369-443.
The heuristics which come to close calling with that of ours is nearest insertion (p 29,[A]).The main differences are that we start with a standard convex polygon and our process of improvements ends only when no correction can be made, equivalently when optimal tour is reached. The cheapest insertion and convex hull cheapest insertion is also a similar method but all these methods seem to have only one limitation that they stop after few steps and further improvements are not made. Our possible heuristic seems to succeed only because it ends only when an optimal tour is reached. The greedy method is the closest to our lowest sum method but with a marked difference. In greedy method we can’t always get all the branches in the tour and the nearest branch at certain point may end the tour prematurely, else we deviate from our greedy methods basic philosophy. Also the property 1 specifies that the points are joined to the most optimal branch and it may happen that the nearest branch may not be the most optimal branch.
722
723
724
725