Convex Hulls for the Traveling Salesman Problem
<p>this method only works directly in the case of the <strong>Euclidean TSP</strong>.<strong> </strong>This is a special class of TSP problems where the distance between two cities is given by the Euclidean distance, also known as the L2 norm. However, there are also ways to extend it to non-Euclidean instances as shown by the authors of the paper A Convex Hull Cheapest Insertion Heuristic for the Non-Euclidean and Precedence Constrained TSPs. But we will keep it simple here.</p>
<p>To the best of my knowledge, S. Eilon, C. D. T. Watson-Gandy, N. Christofides came up with this method in 1971 in their book <strong>Distribution management-mathematical modelling and practical analysis</strong>. Despite being fairly old, this idea stood the test of time as it is still picked up today as a heuristic for solving large TSPs. The paper I mentioned above is from 2023, for example.</p>
<p><a href="https://allaboutalgorithms.com/convex-hulls-for-the-traveling-salesman-problem-71622e1867bf"><strong>Read More</strong></a></p>