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

a. First allow user to identify starting city (iStart)

b. Loop through all possible starting cities (1 to nCities) and pick the shortest total distance 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("How many cities in this problem?", "Traving 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) = .Offset(i, 0)

.Offset(i, i) = 0

For j = i + 1 To intNCities

.Offset(i, j) = WorksheetFunction.RandBetween(50, 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()

'Finding the longest distance and assign to variable intMaxDist

'Mark all cities unvisited

intMaxDist = 0

For i = 1 To nCities

For j = 1 To nCities

Dist(i, j) = .Offset(i, j)

If Dist(i, j) > intMaxDist Then intMaxDist = Dist(i, j)

Next j

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

'Define iStart = Starting City Number

'Use city 1 as the starting city (iStart),

intTD = 0

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)

nowAt = iStart

blnVisited(nowAt) = True

For iSeg = 1 To nCities - 1

intMinDist = intMaxDist

For i = 1 To nCities

If Not blnVisited(i) And Dist(nowAt, i) < intMinDist Then

intMinDist = Dist(nowAt, i)

nextC = i

End If

Next i

blnVisited(nextC) = True

intTD = intTD + intMinDist

.Offset(nCities + 2, iSeg) = nowAt

.Offset(nCities + 3, iSeg) = nextC

.Offset(nCities + 4, iSeg) = intMinDist

.Offset(nCities + 5, iSeg) = intTD

nowAt = nextC

Next iSeg

.Offset(nCities + 2, iSeg) = nextC

.Offset(nCities + 3, iSeg) = iStart

.Offset(nCities + 4, iSeg) = Dist(nextC, iStart)

.Offset(nCities + 5, iSeg) = intTD + Dist(nextC, iStart)

End With

End Sub