VBA CODE: How can you improve the nearest neighbor Heuristic algorithm? Loop through all possible starting cities (1 to nCities) and pick the shortest total distance route.

Here is the code I have that I need to change to find the shortest route:

Option Explicit

Option Base 1

Sub EX8_2_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("Input the number of cities ", "Traveling Salesman Problem", 5) 'Clear all the contents ActiveSheet.UsedRange.Clear ' Write Values to cells A1 and A3 Range("a1") = "Traveling Salesman Problem" Range("a3") = "Distance" '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) 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 .Offset(i, j) = WorksheetFunction.RandBetween(10, 100) .Offset(j, i) = .Offset(i, j) Next j Next i End With End Sub

Sub EX8_2_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 = .CurrentRegion.Rows.Count - 1 'redim Dist() and blnVisited() ReDim Dist(1 To nCities, 1 To nCities) ReDim blnVisited(1 To 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 'Mark all cities unvisited intMaxDist = 0 For i = 1 To nCities blnVisited(i) = False For j = 1 To nCities If Dist(i, j) > intMaxDist Then intMaxDist = Dist(i, j) Next j 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 'Define iStart = Starting City Number 'Use city 1 as the starting city (iStart), intTD = 0 iStart = InputBox("Enter the starting City") 'input starting city nowAt = iStart For iSeg = 1 To nCities - 1 blnVisited(nowAt) = True intMinDist = intMaxDist For i = 1 To nCities If blnVisited(i) = False And Dist(nowAt, i) < intMinDist Then intMinDist = Dist(nowAt, i) nextC = i End If Next i intTD = intTD + Dist(nowAt, nextC) .Offset(nCities + 2, iSeg) = nowAt .Offset(nCities + 3, iSeg) = nextC .Offset(nCities + 4, iSeg) = Dist(nowAt, nextC) .Offset(nCities + 5, iSeg) = intTD nowAt = nextC 'Cycle through all cities to find nearest neighbor excluding already visited cities 'Report back to excel the optimal route ' Current segment starting city (nowAT) Next iSeg .Offset(nCities + 2, iSeg) = nowAt .Offset(nCities + 3, iSeg) = iStart .Offset(nCities + 4, iSeg) = Dist(nowAt, iStart) .Offset(nCities + 5, iSeg) = intTD + Dist(nowAt, iStart) End With End Sub