School of Computer Sciences

CMT423 Decision Support Systems and Business Intelligence

CMT426/CMM426 Business Intelligence and Analytics

Academic Session: Semester 2, 2022/2023

Lab 04 – Solving Traveling Salesman Problem with Microsoft Excel Solver

(Evolutionary Method)

I. Objective
This lab manual introduces solving Traveling Salesman Problem (TSP) with Microsoft Excel Solver (Evolutionary
Method). At the end of today session, you should be able to perform the following:
• Develop a spreadsheet model for a TSP.
• Use Excel Solver (Evolutionary Method) to solve a TSP.

II. Introduction
TSP is a discrete combinatorial optimization problem. Suppose a salesman is given a set of n cities associated
with a traveling distance matrix from any city to any other cities. The salesman is required to allocate a
Hamiltonian path with minimum distance. The Hamiltonian tour is also referred to as a round trip tour
whereby the salesman must visit each city once and only once, and eventually return to the starting city.
TSP can be denoted by graph notations as follows. Let 𝐺 = (𝑉, 𝐸) be a weighted complete graph where V is a
set of n cities (𝑉 = {𝑣1 , ⋯ , 𝑣𝑛 }) and E is a set of arcs or edges(𝐸 = {(𝑟, 𝑠): 𝑟, 𝑠 ∈ 𝑉}). E is associated with a
distance matrix, 𝐷 = {𝑑𝑟,𝑠 } where 𝑑𝑟,𝑠 denotes the distance between city r and city s. For all the
combinations, if 𝑑𝑟,𝑠 = 𝑑𝑠,𝑟 the problem is a symmetric TSP (STSP). Otherwise, it becomes an asymmetric TSP
(ATSP). Let Π represents all possible permutations of set V. A solution of a TSP is to determine a permutation
𝜋 ∈ Π, which has the minimum total round trip distance as shown in the following equation, in which 𝜋(𝑖) ∈ 𝑉
indicates the i-th element in 𝜋.
𝑛−1

𝐶𝑇𝑆𝑃 (𝜋 ∈ Π) = ∑[𝑑𝜋(𝑖),𝜋(𝑖+1) ] + 𝑑𝜋(𝑛),𝜋(1)

𝑖=1

An illustrative example, i.e. a 4-city TSP, is shown as Figure 1:

Figure 1: A 4-city TSP.

Page | 1 CMT423 Decision Support Systems and Business Intelligence

CMT426/CMM426 Business Intelligence and Analytics
Lab 04, S2-2022/2023
If a salesman decided to follow a round trip of A-B-D-C-A, the distance will be 8 + 10 + 4 + 4 = 26 units of
distance. If a salesman decided to follow a round trip of A-B-C-D-A, the distance will be 8 + 4 + 4 + 6 = 22 units
of distance.

III. The gr17 TSP Benchmark Problem

In this lab, we will look at how we can solve a TSP benchmark problem (i.e. gr17) which can be obtained from
the TSPLIB (http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/). The problem is explained as follows.
gr17 is a 17-city TSP. It is a TSP benchmark problem which has been solved to optimal. The following visiting
order is the optimal tour with 2085 units of distance.
9-12-16-1-4-13-7-8-6-17-14-15-3-11-10-2-5-9
The raw file taken from the TSPLIB is as follows, where the distances of the lower diagonal rows in the distance
matrix are shown.

NAME: gr17
TYPE: TSP
COMMENT: 17-city problem (Groetschel)
DIMENSION: 17
EDGE_WEIGHT_TYPE: EXPLICIT
EDGE_WEIGHT_FORMAT: LOWER_DIAG_ROW
EDGE_WEIGHT_SECTION
0 633 0 257 390 0 91 661 228 0 412 227
169 383 0 150 488 112 120 267 0 80 572 196
77 351 63 0 134 530 154 105 309 34 29 0
259 555 372 175 338 264 232 249 0 505 289 262
476 196 360 444 402 495 0 353 282 110 324 61
208 292 250 352 154 0 324 638 437 240 421 329
297 314 95 578 435 0 70 567 191 27 346 83
47 68 189 439 287 254 0 211 466 74 182 243
105 150 108 326 336 184 391 145 0 268 420 53
239 199 123 207 165 383 240 140 448 202 57 0
246 745 472 237 528 364 332 349 202 685 542 157
289 426 483 0 121 518 142 84 297 35 29 36
236 390 238 301 55 96 153 336 0
EOF

Page | 2 CMT423 Decision Support Systems and Business Intelligence

CMT426/CMM426 Business Intelligence and Analytics
Lab 04, S2-2022/2023
The complete distance matrix of gr17 is shown in Table 1.

Table 1: The distance matrix of gr17.

City 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
1 0 633 257 91 412 150 80 134 259 505 353 324 70 211 268 246 121
2 633 0 390 661 227 488 572 530 555 289 282 638 567 466 420 745 518
3 257 390 0 228 169 112 196 154 372 262 110 437 191 74 53 472 142
4 91 661 228 0 383 120 77 105 175 476 324 240 27 182 239 237 84
5 412 227 169 383 0 267 351 309 338 196 61 421 346 243 199 528 297
6 150 488 112 120 267 0 63 34 264 360 208 329 83 105 123 364 35
7 80 572 196 77 351 63 0 29 232 444 292 297 47 150 207 332 29
8 134 530 154 105 309 34 29 0 249 402 250 314 68 108 165 349 36
9 259 555 372 175 338 264 232 249 0 495 352 95 189 326 383 202 236
10 505 289 262 476 196 360 444 402 495 0 154 578 439 336 240 685 390
11 353 282 110 324 61 208 292 250 352 154 0 435 287 184 140 542 238
12 324 638 437 240 421 329 297 314 95 578 435 0 254 391 448 157 301
13 70 567 191 27 346 83 47 68 189 439 287 254 0 145 202 289 55
14 211 466 74 182 243 105 150 108 326 336 184 391 145 0 57 426 96
15 268 420 53 239 199 123 207 165 383 240 140 448 202 57 0 483 153
16 246 745 472 237 528 364 332 349 202 685 542 157 289 426 483 0 336
17 121 518 142 84 297 35 29 36 236 390 238 301 55 96 153 336 0

IV. Load the Solver Add-in in Microsoft Excel

You will be guided to use the Solver Add-in in Microsoft Excel to solve the problem described in Section III.
Please be noted that all the steps described in this manual are based on Microsoft Excel 2016.
Before you can develop a spreadsheet model for a TSP and solve it using the Solver Add-in, you need to load
the Solver Add-in in Microsoft Excel.
The steps to load the Solver Add-in in Microsoft Excel are as follows:
a. Click File…Options. You will be navigated to the Excel Options window as shown in Figure 2.

Figure 2: The Excel Options window.

Page | 3 CMT423 Decision Support Systems and Business Intelligence

CMT426/CMM426 Business Intelligence and Analytics
Lab 04, S2-2022/2023
 b. Click Add-ins. Go to Manage, select Excel Add-ins, and click Go. Please refer to Figure 3.

Figure 3: Manage Excel Add-ins in the Excel Options window.

c. Select Solver Add-in in the Add-ins window, then click OK as shown in Figure 4.

Figure 4: Select Solver Add-in in the Add-ins window.

Page | 4 CMT423 Decision Support Systems and Business Intelligence

CMT426/CMM426 Business Intelligence and Analytics
Lab 04, S2-2022/2023
 d. After you load the Solver Add-in, the Solver command is available in the Analysis group on the Data
tab as down in Figure 5.

Figure 5: Solver Add-in is shown in the Analysis group on the Data tab.

V. Modeling a TSP on a Spreadsheet

Let us revisit the gr17 TSP described in Section III.
Create a spreadsheet which contains a distance matrix, a trial solution, the distance of every edge in the trial
solution, and the total tour length as shown in Figure 6. We assume the initial feasible solution for this model
is 1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-1 which the tour length is 4722 units of
distance.

Figure 6: The spreadsheet model for gr17.

In order to get the corresponding distance of a particular edge in a trial solution, the INDEX formula is used.
Figure 7 shows the formulas used in the spreadsheet model. The tour lengths of all the edges in a trial solution
will be added using a SUM formula at cell W19.

Page | 5 CMT423 Decision Support Systems and Business Intelligence

CMT426/CMM426 Business Intelligence and Analytics
Lab 04, S2-2022/2023
Figure 7: The formulas used in the spreadsheet model.

VI. Using Solver to Solve the Model

The steps to use the Microsoft Solver Add-in (with Evolutionary method) to solve the gr17 TSP are as follows:
a. Click the Solver button on the Data tab. The Solver dialog box is shown in Figure 8.

Figure 8: The Solver dialog box.

b. For the Set Objective, enter $W$19.

c. For the To option, select Min as the goal is to minimize the total tour length.
d. For the By Changing Variable Cells, enter $B$21:$R$21. In another words, this model has 17 decision
variables.

Page | 6 CMT423 Decision Support Systems and Business Intelligence

CMT426/CMM426 Business Intelligence and Analytics
Lab 04, S2-2022/2023
 e. Next, three constraints are added to the model. First, all the 17 decision variables must be set to any
value which is less than or equal to 17 (i.e. $B$21:$R$21 <= 17). Second, the value of these 17 decision
variables must be distinct. Third, all the 17 decision variables are of integer type.
f. Impose the non-negativity constraints so that the changing cells reject negative integers. This is done
by selecting the Make Unconstrained Variables Non-Negative option.
g. Select Evolutionary as the solving method. The complete Solver dialog box is shown in Figure 9.

Figure 9: The Solver dialog box after specifying the entire model in terms of the spreadsheet.

Page | 7 CMT423 Decision Support Systems and Business Intelligence

CMT426/CMM426 Business Intelligence and Analytics
Lab 04, S2-2022/2023
 h. Click the options button, in case you want to configure the setting of the Evolutionary method. Let’s
assume we use the default setting as shown in Figure 10.

Figure 10: Default setting of the Evolutionary method.

i. Click the Solve button. This will start the process of solving the problem in the background. The Solver
Results dialog box will show that the Solver found a solution as shown in Figure 11. Click OK.

Figure 11: The Solver Results dialog box that indicates that a solution has been found.

Page | 8 CMT423 Decision Support Systems and Business Intelligence

CMT426/CMM426 Business Intelligence and Analytics
Lab 04, S2-2022/2023
 j. After solving the model, Solver replaces the originals numbers in the changing cells with a set of
numbers in Figure 12. The tour of 3-11-10-2-5-9-12-16-1-4-13-7-8-6-17-14-15-3 with
a length of 2085 units of distance is generated. The generated tour is an optimal tour. However, please
note that the Evolutionary method doesn’t guarantee an optimal solution.

Figure 12: The spreadsheet that shows a TSP tour after solving gr17 using Microsoft Solver (Evolutionary
method).

VII. Exercise
Download the swiss42 dataset from eLearn@USM. It is a CSV file. Create a spreadsheet model for swiss42 and
solve it using Microsoft Solver (Evolutionary method). The best-known optimal tour length of swiss42 is 1273
units of distance.

Tune the parameter of the Evolutionary method. Based on a particular setting, run the Evolutionary method
for five times. Get the average of the five tour lengths and compute the deviation percentage of the average
tour length from the best-known optimal tour length. In your lab report, you should report at least 3 set of
different parameter settings. Present the results nicely in a tabular format.

VIII. Lab Report Submission

Besides student’s name and matrix number, the lab report must contain the following:
• A spreadsheet model for swiss42.
• Detailed parameter settings with corresponding results.
Your report (in .pdf) and the excel model (in .xlsx) must be submitted as a zip/rar package to eLearn@USM,
before 10 Jun 2023 (Saturday), 23:59. Failure to submit the lab report and the excel model will be a
disadvantage to you.

Page | 9 CMT423 Decision Support Systems and Business Intelligence

CMT426/CMM426 Business Intelligence and Analytics
Lab 04, S2-2022/2023
IX. Grading Rubric

Range Spreadsheet Model Parameter Setting & Results

(10%) (15%)

Good A comprehensive spreadsheet model as • Report the results based on at least 3 set
(3) follows: of different parameter settings.
• The TSP requirement, i.e. visit all the • Interpret and explain the results.
cities once and return to the starting • The explanation and the results are
city, is modelled and fulfilled. presented with good clarity,
• The decision variables are correctly comprehensiveness and organization.
modelled.
• The objective function in terms of tour
length is correctly modelled.
Satisfactory • Less than or exactly 5 errors are • Report the results based on at least 3 set
(2) observed in terms of data, constraints, of different parameter settings.
objective function, and decision • Interpret and explain the results.
variables. • The explanation and the results are
presented with satisfactory clarity,
comprehensiveness and organization.
Poor • More than 5 errors are observed in • Report the results based on at least 3 set
(1) terms of data, constraints, objective of different parameter settings.
function, and decision variables. • Interpret and explain the results.
• The explanation and the results are
presented with minimal clarity,
comprehensiveness and organization.
Fail • No submission or late submission. • No submission or late submission.
(0)

~~END OF LAB 04~~

Page | 10 CMT423 Decision Support Systems and Business Intelligence

CMT426/CMM426 Business Intelligence and Analytics
Lab 04, S2-2022/2023