Code in VBA please, will upvote if done correctly

• Based on EX_2, how can you improve the nearest neighbor Heuristic algorithm?

1. First allow user to identify starting city (iStart)
2. Loop through all possible starting cities (1 to nCities) and pick the shortest total distance route

your file should include two subs:

one to allow user specify starting city;

the other to find the shortest route among different starting cities.

Hint: For the second sub, make sure you initialize all cities as unvisited before finding shortest total distance for each iStart city.

Note: Use the distance matrix produced in EX1 as the input for this HW, you don't need to generate the distance matrix again.

Here's EX 1

Here is the solution file for EX1

Option Explicit

Option Base 1

Sub EX_1GenerateDistanceMatrix() Dim strAns As String Dim intNCities As Integer, i As Integer, j As Integer wsDistance.Activate 'Get the number of cities to be in the Traveling Salesman Problem 'Clear all the contents ActiveSheet.UsedRange.Clear ' Write Values to cells A1 and A3 'Generate Distance Matrix, also write headers to distance matrix With Range("a3") 'Write headers to worksheet 'Generate distances (matrix is symmetric with 0's in the diagonal) End With End Sub

Sub EX_2NearestNeighbor() Dim iSeg As Integer, i As Integer, j As Integer, iStart As Integer Dim nCities As Integer, nowAt As Integer, nextC As Integer Dim intTD As Integer, intMaxDist As Integer, intMinDist As Integer Dim rngA As Range Dim Dist() As Integer Dim blnVisited() As Boolean Set rngA = Range("A3") With rngA 'Find nCities 'redim Dist() and blnVisited() 'read Distance matrix from Excel, assign to Dist() 'Finding the longest distance and assign to variable intMaxDist 'Mark all cities unvisited 'Write Output Headings .Offset(nCities + 2, 0) = "From" .Offset(nCities + 3, 0) = "To" .Offset(nCities + 4, 0) = "Distance" .Offset(nCities + 5, 0) = "Tot Distance" 'initialize total distance intTD 'Define iStart = Starting City Number 'Use city 1 as the starting city (iStart), 'Cycle through all cities to find nearest neighbor excluding already visited cities 'Report back to excel the optimal route ' Current segment starting city (nowAT) End With End Sub

HERE IS THE CODE FOR THE SOLUTION

Option Explicit

Option Base 1

Sub EX_1GenerateDistanceMatrix() Dim strAns As String Dim intNCities As Integer, i As Integer, j As Integer wsDistance.Activate 'Get the number of cities to be in the Traveling Salesman Problem intNCities = InputBox("Enter number of cities in the TSP network.", "Generate TSP inputs.", 5) 'Clear all the contents ActiveSheet.UsedRange.Clear ' Write Values to cells A1 and A3 Range("A1") = "TSP" Range("a3") = "Distance" 'Generate Distance Matrix, also write headers to distance matrix With Range("a3") 'Write headers to worksheet For i = 1 To intNCities .Offset(i, 0) = "City " & i .Offset(0, i) = "City " & i .Offset(i, i) = 0 For j = i + 1 To intNCities 'Generate distances (matrix is symmetric with 0's in the diagonal) .Offset(i, j) = WorksheetFunction.RandBetween(50, 100) .Offset(j, i) = .Offset(i, j) Next j Next i End With End Sub

Sub EX_2NearestNeighbor() Dim iSeg As Integer, i As Integer, j As Integer, iStart As Integer Dim nCities As Integer, nowAt As Integer, nextC As Integer Dim intTD As Integer, intMaxDist As Integer, intMinDist As Integer Dim rngA As Range Dim Dist() As Integer Dim blnVisited() As Boolean Set rngA = Range("A3") With rngA 'Find nCities nCities = Range(.Offset(1, 0), .Offset(1, 0).End(xlDown)).Rows.Count 'redim Dist() and blnVisited() ReDim Dist(nCities, nCities) ReDim blnVisited(nCities) 'read Distance matrix from Excel, assign to Dist() For i = 1 To nCities For j = 1 To nCities Dist(i, j) = .Offset(i, j) Next j Next i 'Finding the longest distance and assign to variable intMaxDist intMaxDist = 0 For i = 1 To nCities For j = i + 1 To nCities If Dist(i, j) > intMaxDist Then intMaxDist = Dist(i, j) Next j Next i 'Mark all cities unvisited For i = 1 To nCities blnVisited(i) = False Next i 'Write Output Headings .Offset(nCities + 2, 0) = "From" .Offset(nCities + 3, 0) = "To" .Offset(nCities + 4, 0) = "Distance" .Offset(nCities + 5, 0) = "Tot Distance" 'initialize total distance intTD intTD = 0 'Define iStart = Starting City Number 'Use city 1 as the starting city (iStart), iStart = 1 'Cycle through all cities to find nearest neighbor excluding already visited cities 'Report back to excel the optimal route ' Current segment starting city (nowAT) blnVisited(iStart) = True nowAt = iStart For iSeg = 1 To nCities - 1 'Find the closest city for nowAt intMinDist = intMaxDist + 1 For i = 1 To nCities If blnVisited(i) = False And Dist(nowAt, i)

Thank you!!

D E F G I City 4 86 82 A B 1 Traveling Salesman Problem 2 3 Distance City 1 City 2 4 City 1 0 5 City 2 62 6 City 3 86 7 City 4 80 8 City 5 76 9 10 From 1 11 To 2 12 Distance 62 13 Tot Distance 298 City 3 62 0 82 88 84 City 5 80 88 85 0 84 0 85 70 76 84 70 84 0 1 N 3 5 3 3 5 70 3 82 4 4 84 4 1 80 14 15 16 D E F G I City 4 86 82 A B 1 Traveling Salesman Problem 2 3 Distance City 1 City 2 4 City 1 0 5 City 2 62 6 City 3 86 7 City 4 80 8 City 5 76 9 10 From 1 11 To 2 12 Distance 62 13 Tot Distance 298 City 3 62 0 82 88 84 City 5 80 88 85 0 84 0 85 70 76 84 70 84 0 1 N 3 5 3 3 5 70 3 82 4 4 84 4 1 80 14 15 16