The traveling salesman problem (TSP) is one of the most intensely studied problems in computational mathematics. Its name reflects the real-life problem traveling salesmen face when taking their business from city to city – finding the shortest roundtrip possible while visiting each location only once. The bigger challenge lies in keeping travel costs at a minimum while maximizing the amount of stops possible in a single trip. To find the optimal solution to this problem, mathematicians need to map out and compare every possibility.
William Cook, professor of combinatorics and optimization at the University of Waterloo, is the researcher behind Concorde– incredibly efficient computer code for optimally solving the symmetric TSP and related network optimization problems. It has been used to calculate the optimal solutions to the full set of 110 TSPLIB problems, the largest having over 85,000 cities. This positions Concorde’s TSP solver as one of the most reliable tools for the problem.
Data points (above) were computed using the traveling salesman problem to create the optimal tour (below) at the University of Waterloo in 2017.
Naturally, the TSP lends itself to being useful in modeling transportation and logistics applications, such as the routing of trucks for parcel post pickup or delivery. Its applications go beyond physical movements between places – the simplicity of the model and the importance of efficiency in operations makes it useful across many industries and domains.
Concorde’s TSP solver finds the optimal solution to a problem and identifies which inefficiencies can be controlled by modeling optimal and different situations. The National Institute of Health found the tool integral to ongoing work in genome sequencing to compute DNA sequence variations. The Worldwide Airport Path Finder web site uses Concorde to find the shortest routes through selections of airports all over the world.
With limited resources, companies can use optimization and operations research to create tools to use these resources as efficiently as possible. The study of mathematical problems like TSP can be used to build powerful tools like Cook’s Concorde to increase efficiencies in complex industrial applications.