Case Study 7 – The Travelling Salesperson Problem (TSP)Introduction: Optimizing Travel to 30 International Cities
The travelling salesperson problem (TSP) asks the following question: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?” The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. The TSP has several applications such as planning, logistics, and the manufacture of microchips. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. The TSP also appears in astronomy, as astronomers observing many sources will want to minimize the time spent moving the telescope between the sources. In many applications, additional constraints such as limited resources or time windows may be imposed. (Ref.: https://en.wikipedia.org/wiki/Travelling_salesman_problem) The books by Applegate and Cook (see Case Study 7 References) and the University of Waterloo TSP web site (http://www.math.uwaterloo.ca/tsp/index.html) are excellent resources for further study. We will now consider a 30 City TSP problem. The data is from city distance dataset HA30 which describes the airline distances, in hundreds of miles, between 30 international cities: https://people.sc.fsu.edu/~jburkardt/datasets/cities/cities.html. A 30 city problem has 29!/2 = 4.42e30 possible solutions, so obviously this is not something that can be solved using the Discrete Exhaustive option! The goal is to achieve the best known solution minimum of 503 (50,300 miles), as given in Ouyang (2013):

Summary of DiscoverSim Features Demonstrated in Case Study
7: |
|
Web Demos
Our CTO and Co-Founder, John Noguera, regularly hosts free Web Demos featuring SigmaXL and DiscoverSim
Click here to view some now!
Contact Us
Phone: 1.888.SigmaXL (744.6295)
Support: Support@SigmaXL.com
Sales: Sales@SigmaXL.com
Information: Information@SigmaXL.com