DiscoverSim™ Case Studies

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):

The 3D plots were created using Mathematica with code adapted from Dr. Ben Nolting: (http://datavoreconsulting.com/programming-tips/a-traveling-salesman-on-a-sphere-pitbulls-arctic-adventure/).

In DiscoverSim Version 2.1, the Genetic Algorithm has improved handling of the DSIM_IsAllDifferent function, so we will use the Genetic Algorithm to solve this TSP problem. The DSIM_IsAllDifferent function will be used in a constraint in order to ensure that the only solutions considered are unique city sequences.

Since this is a deterministic optimization problem, we technically only need a single replication, but DiscoverSim requires a minimum of 2 replications for internal consistency on stochastic problems. If the model included Input Distributions to represent uncertainty (for example if we were using travel times rather than distance), then we would typically use 1000 replications in the optimization settings.

Summary of DiscoverSim Features Demonstrated in Case Study 7:

Create Discrete Input Controls DiscoverSim Copy/Paste Cell Insert DSIM_IsAllDifferent function Create a Constraint that references the DSIM_IsAllDifferent function Run Optimization with Genetic Algorithm

Optimizing Travel to 30 International Cities with DiscoverSim

1. Open the workbook 30 International Cities TSP.xlsx (to access, click DiscoverSim > Help > Case Studies). This is a matrix showing the distance between cities in hundreds of airline miles. The city names are shown in column B and row 3. DiscoverSim Discrete Input Controls will be created in cells C36 to AE36. The output, Total Distance Travelled, will be specified in cell B40. A constraint will be added at cell B42 that references a DSIM_IsAllDifferent function at cell B41. Excel’s OFFSET function is used to extract the city names and distances for the selected Input Control values. Row 37 shows the names of the tour cities in the order visited. Row 38 shows the distances between the tour cities.
   
   


2. Click on cell C36. Select Control:
   
   


3. Click input Name cell reference and specify cell C35 containing the input control name “1st”.


4. Select Discrete. Set Step =1, the Min value =1 and the Max value =29 as shown. There are 30 cities but the first city is defined as Azores, so only 29 need to be solved.
   
   


5. Click OK. Hover the cursor on cell C36 to view the comment displaying the input control settings:
   
   


6. With Cell C36 selected, click the DiscoverSim Copy Cell menu button (Do not use Excel's copy - it will not work!).


7. Select cells D36:AE36 (do not include empty cell AF36). Click the DiscoverSim Paste Cell menu button (Do not use Excel's paste - it will not work!).


8. Review the Input Control comments in cells D36 to AE36.


9. Now we will specify the output. Click on cell B40. Note that the cell contains the Excel formula for Total Distance Travelled: =SUM(C38:AF38).


10. Select DiscoverSim > Output Response:
    
    


11. Enter the output Name as “Distance”. We will not enter any specifications.
    
    
    
    Click OK.


12. Hover the cursor on cell B40 to view the DiscoverSim Output information.
    
    


13. Click on cell B41 and select DiscoverSim > DSIM Function:
    
    
    
    
    
    Scroll down to select DSIM_ISAllDIfferent. Click OK


14. Select the Range C36:AE36
    
    


15. The DSIM function is now in cell B41:
    
    =DSIM_ISAllDifferent('HA30!C36:AE36)
    
    which returns a 1 since the default input control values are different.
    
    Note: All Discrete Input Controls should be included in the DSIM_IsAllDifferent range. DiscoverSim does not support a mixture of having some Discrete Input Controls constrained by DSIM_IsAllDifferent and some not constrained. (However, it is possible to have a mixture with Continuous Input Controls).


16. Now we will add a constraint that references the DSIM function. Click on cell B42. Select Constraint:
    
    


17. Enter B41 in the "Left Hand Side" (LHS) or click the LHS cell reference and select B41. Select =. Enter 1 in the "Right Hand Side" (RHS).
    
    


18. Click OK. Review cell B41:
    
    
    
    


19. The completed model is show below:
    
    


20. Now we are ready to perform the optimization. Select DiscoverSim > Run Optimization:
    
    


21. Select "Minimize" for Optimization Goal, "Weighted Sum" for Multiple Output Metric and "Mean" for Statistic. Select Genetic Algorithm. Set Replications to 2. Select Seed Value and enter “1234” in order to replicate the optimization results given below. All other settings will be the defaults as shown:
    
    
    
    Note: As mentioned above, since this is a deterministic problem, we technically only need a single replication, but DiscoverSim requires a minimum of 2 replications for internal consistency on stochastic problems.


22. Click Run. This optimization will take approximately 4 minutes. To save time, when the solution reaches the best known value of 503, click the Interrupt button.


23. The final optimal parameter values are given as:
    
    
    
    As discussed in the introduction, the final solution of 503 (50,300 miles) is the best known solution for this 30 International City problem.


24. We can see that all of the values are all different satisfying the constraint using DSIM_IsAllDifferent and the “Amount Violated” is 0.
    
    


25. You are prompted to paste the optimal values into the spreadsheet:
    
    


26. Click Yes. This replaces the input control values in cells C36 to AE36 with the optimum values.


27. The final city tour is given in cells C37 to AF37:
    Azores → London → Paris → Rome → Berlin → Moscow → Istanbul → Cairo → Baghdad → Bombay → Manila → Shanghai → Tokyo → Guam → Melbourne → Sydney → Honolulu → San Francisco → Seattle → Juneau → Montreal → New York → Chicago → New Orleans → Mexico City → Panama City → Santiago → Buenos Aires → Rio de Janeiro → Capetown → Azores


28. This matches the known best tour given in Ouyang (2013):
    
    


29. If one wanted to evaluate flight times with uncertainty, rather than distances, then input distributions could be added to create a stochastic model.


30. Another example where DSIM_IsAllDifferent would be used in a constraint is Stochastic Job Scheduling with Due Dates.

Case Study 7: References

• Applegate, D., Bixby, R. E., Chvátal, V., & Cook, W. (2006). The traveling salesman problem: A computational study. Princeton: Princeton University Press.



• Cook, W. (2011). In pursuit of the salesman: Mathematics at the limits of computation. Princeton: Princeton University Press



• X. Ouyang, Y. Zhou, Q. Luo, and H. Chen, “A novel discrete cuckoo search algorithm for spherical traveling salesman problem,” Applied Mathematics & Information Sciences, vol. 7, no. 2, pp. 777– 784, 2013, http://www.naturalspublishing.com/files/published/xk232153a2f4jw.pdf.

<< Return to Table of Contents