The Traveling Salesman Problem: From 19th Century Puzzles to Genetic Algorithms
A salesman must visit a set of cities exactly once and return home, minimizing total travel distance. This deceptively simple puzzle—the Traveling Salesman Problem (TSP)—has haunted mathematicians, computer scientists, and logistics planners for nearly two centuries. It remains one of the most studied problems in computational optimization. Historical Origins The TSP’s roots trace to the 1830s, when Irish mathematician William Rowan Hamilton and British mathematician Thomas Kirkman studied related mathematical problems involving traversing graph vertices....