Original Code: \'Problem (1) Sub GenerateTravelingSalesmanMatrix() wsTSP.Activat

Question

Original Code:

'Problem (1)

Sub GenerateTravelingSalesmanMatrix()

wsTSP.Activate
  
Dim strAns As String
Dim intNcities As Integer, intI As Integer, intJ As Integer
  
  
'Get the number of cities to be in the Traveling Salesman Problem
Do
strAns = InputBox("Enter number of Cities (>=2)", "Traveling Salesman Problem")
If IsNumeric(strAns) Then
intNcities = CInt(strAns)
If intNcities >= 2 Then Exit Do
ElseIf strAns = "" Then
MsgBox "Entered an empty string, program stops", vbInformation + vbOKOnly
Exit Sub
End If
Loop
  
'Clear all the contents
ActiveSheet.UsedRange.Clear
  
  
Range("a1").Value = "Traveling Salesman Problem"
Range("a3").Value = "Distance"
  
'Generate Distance Matrix
With Range("a3")
  
For intI = 1 To intNcities
'Write headers to worksheet
.Offset(0, intI) = "City " & intI
.Offset(intI, 0) = "City " & intI
  
For intJ = intI + 1 To intNcities
'Generate distances (matrix is symmetric with 0's in the diagonal)
.Offset(intI, intJ) = WorksheetFunction.RandBetween(5, 100)
.Offset(intJ, intI) = .Offset(intI, intJ)
  
Next intJ
  
Next intI
  
End With

End Sub

Sub TravelSalesNearNeigh()
Dim iCurrCity As Integer, iStart0 As Integer, intNc As Integer
Dim intMinD As Integer, intMinJ As Integer, intI As Integer, intJ As Integer
Dim intMaxDoverall As Integer
Dim intTD As Integer
Dim intD() As Integer
Dim strAns As String
Dim blnVisited() As Boolean
  
wsTSP.Activate
  
With Range("A3")
'Get the number of cities
intNc = Range(.Offset(0, 1), _
.Offset(0, 1).End(xlToRight)).Count
  
  
.Offset(intNc + 1, 0).EntireRow("1:15000").Clear
.Offset(intNc + 2, 0).Value = "From"
.Offset(intNc + 3, 0).Value = "To"
.Offset(intNc + 4, 0).Value = "Distance"
  
  
'Get the starting city
Do
strAns = InputBox("Enter Starting City (any number between 1 and " & _
intNc & ")", "Traveling Salesman Problem")
If IsNumeric(strAns) Then
iStart0 = CInt(strAns)
If iStart0 >= 1 And iStart0 <= intNc Then Exit Do
ElseIf strAns = "" Then
MsgBox "Entered an empty string, program stops", vbInformation + vbOKOnly
Exit Sub
End If
Loop
  
intMaxDoverall = -1 'Make the maximum distance something small
  
ReDim intD(intNc, intNc) As Integer 'redim to make them the right size
ReDim blnVisited(intNc) As Boolean
For intI = 1 To intNc 'Loop through the cities to get the distance matrix
For intJ = intI + 1 To intNc
intD(intI, intJ) = .Offset(intI, intJ)
intD(intJ, intI) = intD(intI, intJ)
If intD(intI, intJ) > intMaxDoverall Then intMaxDoverall = intD(intI, intJ)
Next intJ
Next intI
intMaxDoverall = intMaxDoverall + 1 'Total distance cannot be greater than this
  
iCurrCity = iStart0 'Starting city in the tour
For intI = 1 To intNc - 1 'Loop though all cities other than the starting city - that is why intNc-1
blnVisited(iCurrCity) = True 'Set the city to start as having been visited
intMinD = intMaxDoverall 'make the minimum distance a very large number
For intJ = 1 To intNc 'Loop though all cities
If Not blnVisited(intJ) Then
  
'Consider only if the city is a different city that has not been visited
If intD(iCurrCity, intJ) < intMinD Then
  
'if the distance to the city is < the minimun distance found so far
'update the minimum distance and the city
intMinD = intD(iCurrCity, intJ)
intMinJ = intJ
End If
End If
Next intJ
  
'The next city to visit has been found and is city intMinJ and the distance from city iCurrCity is intMinD
intTD = intTD + intMinD 'update the total distance traveled
.Offset(intNc + 2, intI) = iCurrCity 'record the city that was visited last
.Offset(intNc + 3, intI) = intMinJ 'record the city visited next
.Offset(intNc + 4, intI) = intMinD 'record the distance between cities
  
iCurrCity = intMinJ 'redefine the starting city
  
Next intI
  
'Record the results for the last city
intTD = intTD + intD(iCurrCity, iStart0)
  
.Offset(intNc + 2, intNc) = iCurrCity
.Offset(intNc + 3, intNc) = iStart0
.Offset(intNc + 4, intNc) = intD(iCurrCity, iStart0)

'Record the total distance for the tour
.Offset(intNc + 5, 0).Value = intTD
.Offset(intNc + 5, 1).Value = "Total Distance Traveled"
  
End With
End Sub

Example Data resulted from original code when user entered 6 cities and start from city 5.

1). Extend the traveling salesman problem so that each of the cities is used as a starting city The optimal tour will be the tour that starts the nearest-neighbor algorithm in one city that results in the shortest total distance traveled. You can safely assume that the anchor cell will be cell A3 (as in the example we worked in class). The expanded code should work for any number of cities and should show at the end of the run the optimal tour (sequence of cities visited) and the length of the total distance Hint: If you write your code to work on the active worksheet, then it is easier to run the program in a different worksheet. You can start we the code developed in class.

Explanation / Answer

Here is the code for above scenario

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.