Include Top

Case Study 7 – The Travelling Salesperson Problem (TSP)

Back to Table of Contents


  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.




  12. Click OK.

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




  14. Click on cell B41 and select DiscoverSim > DSIM Function:





    Scroll down to select DSIM_ISAllDIfferent. Click OK

  15. Select the Range C36:AE36




  16. 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).


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




  18. Click Run.

  19. 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).



  20. Click OK. Review cell B41:





  21. The completed model is show below:



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



  23. 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.


  24. 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.


  25. The final optimal parameter values are given as:




  26. As discussed in the introduction, the final solution of 503 (50,300 miles) is the best known solution for this 30 International City problem.

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




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




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

  30. 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


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




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


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

Back to Table of Contents


Define, Measure, Analyze, Improve, Control

Lean Six Sigma Software Excel Add-in

Simulate, Optimize,
Realize

Lean Six Sigma Software Excel Add-in

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

Ph: 1.888.SigmaXL (744.6295)

Support: Support@SigmaXL.com

Sales: Sales@SigmaXL.com

Information: Information@SigmaXL.com