1 Attachment(s)
How do I add constraints to my Nearest Neighbour algorithm in VBA
I'm working on a routing heuristics problem where the goal is to organise the cluster of locations that are extremely urgent, the cluster of locations that are urgent, the cluster of locations that are mildly urgent, etc. reducing in urgency as it goes along. I need to decide which critical locations to visit and in which order (not all locations will be visited in every instance).
As a bit of background so you understand each dimension etc - the locations are organised in *C* clusters, where the first cluster is the most urgent, and the last cluster is the least urgent, the team is only allowed to visit locations in the *d* most urgent clusters which have not been completely visited. Each cluster-location has a score for completion. More urgent clusters have higher scores. There is also a maximum time *T* to complete the mission.
The problem can be formalised as this:
• The locations *i= 0,1, …, n*. The location *0* is the starting and ending point of your tour (i.e., the team base)
• The distance between the locations are given, *dij , i,j=0,.., n* (as well as the coordinates of each location for ease of representation).
• The time available to complete the tour is at most *T* units. The time spent at each location is considered to be negligible.
• The clusters *c=1,…,C*. and their associated scores *si*, with *si > sj, if i < j*. Note that this data structure index starts from 1, because the location 0 is not associated to a cluster.
All instances are in text files (there are 10 of these, but once it works for one it will work for all). Below is the contents of an example text file (I've tried unsuccessfully to add this as a text file but was unable to, so this could be pasted into a text file - cell B4 will need to be updated with the file location of the text file):
NumbLocationsN
4
NumbClusters
3
TimeAvailableT
50
ValueD
1
Scores
5
3
1
WhichCluster
1
1
1
3
XCoordinates
0
5
3
5
2
YCoordinates
0
3
4
2
3
I have code to read all the text files, and that works perfectly, this is the main sub below just for context:
Code:
Public Sub RescueTeam()
'Define a msg string to store the messagebox outputs in debugging
Dim msg As String
'initialise storage for location data
Dim locationsInfo As LocationData
'indices, they will come handy later on
Dim ii, i, j, k As Long
' number of instances you will be solving
Dim NumbInstances As Long
' select worksheet
Sheets("ProblemInstances").Select
' select active cell
Range("B2").Select
' cell contains the number of instances that are to be tested
NumbInstances = Range("B2")
For ii = 1 To NumbInstances
'read the data from text file (one text file at a time)
MsgBox ("I start solving " & ActiveCell.Offset(ii, 0) & " ")
'read the data and initialise the data structure with all the info about the instance
Call ReadData(ActiveCell.Offset(ii, 0).Text, locationsInfo) ' I pickup the name of the next instance and read the data
'debugging: generate a random solution for the "test.txt" instance
'allocate memory first
Dim sol As SolutionTeam
ReDim sol.Sequence(0 To locationsInfo.NumbLocations + 1) As Long
'IMPORTANT! set the empty cells of the sol.sequence to -1 (departure and arrival point will be 0)
'initialise a solution and data structures
'Greedy heuristic
Dim solGreedy As SolutionTeam
ReDim solGreedy.Sequence(0 To locationsInfo.NumbLocations + 1) As Long
'Select which initial heuristic to use & comment out others
Call NearestNeighbour(locationsInfo, solGreedy, 1)
Call EvaluateSolution(locationsInfo, solGreedy)
msg = ""
msg = msg & "Greedy heuristic solution is:" & vbCrLf
For i = 0 To locationsInfo.NumbLocations + 1
msg = msg & solGreedy.Sequence(i) & " "
Next i
msg = msg & vbCrLf & solGreedy.SumScores & vbCrLf & "Feasibility is " & solGreedy.Feasible & " and the duration is " & solGreedy.Duration & " and time available is " & locationsInfo.TimeAvailable
MsgBox msg
Next ii
End Sub
This part actually reads in the data (again, working perfectly and not needing to be amended). This code does work perfectly well but the part I've labelled as important and in bold above - setting empty cells to -1. Wasn't sure whether to do this in my public sub or in my Nearest Neighbour algorithm itself? This may be helpful just in case you wanted to copy and paste into vba and run it yourself:
Code:
Function ReadData(NameFile As String, data As LocationData)
Dim msg As String
Dim myFile As String
Dim textline As String
Dim i, j As Integer
myFile = NameFile
Open myFile For Input As #1 'open the file
Line Input #1, textline
Line Input #1, textline
data.NumbLocations = CLng(textline) ' read numb locations n
Line Input #1, textline
Line Input #1, textline
data.NumbClusters = CLng(textline) ' read Numb clusters C
With data ' memory allocation
ReDim .Scores(1 To data.NumbClusters)
ReDim .WhichCluster(1 To data.NumbLocations)
ReDim .x(0 To data.NumbLocations) As Long ' coordinate x memory allocation
ReDim .y(0 To data.NumbLocations) As Long ' coordinate y memory allocation
ReDim .Distances(0 To data.NumbLocations, 0 To data.NumbLocations) As Double ' note that we need the extra slot for the depot here
ReDim .HowManyPerCluster(1 To data.NumbClusters) As Long ' how many locations are in each cluster
End With
Line Input #1, textline
Line Input #1, textline
data.TimeAvailable = CLng(textline) ' read time available T
Line Input #1, textline
Line Input #1, textline
data.d = CLng(textline) ' read value of d
Line Input #1, textline
For i = 1 To data.NumbClusters
Line Input #1, textline
data.Scores(i) = CLng(textline) ' read scores one at a time
Next i
Line Input #1, textline
For i = 1 To data.NumbLocations
Line Input #1, textline
data.WhichCluster(i) = CLng(textline) ' read for each location which is the corresponding cluster
Next i
Line Input #1, textline
For i = 0 To data.NumbLocations
Line Input #1, textline
data.x(i) = CLng(textline) ' read x coordinate for location i
Next i
Line Input #1, textline
For i = 0 To data.NumbLocations
Line Input #1, textline
data.y(i) = CLng(textline) ' read y coordinate for location i
Next i
For i = 0 To data.NumbLocations
For j = 0 To data.NumbLocations
' compute distances one at a time for each pair of locations and departure/return point
data.Distances(i, j) = Sqr((data.x(i) - data.x(j)) * (data.x(i) - data.x(j)) + (data.y(i) - data.y(j)) * (data.y(i) - data.y(j)))
Next j
Next i
' msg = ""
' msg = msg & "Distances:" & vbCrLf
' For i = 0 To data.NumbLocations
' For j = 0 To data.NumbLocations
' msg = msg & data.Distances(i, j) & " "
' Next j
' msg = msg & vbCrLf
' Next i
' msg = msg & vbCrLf
' MsgBox msg
'fill data structure that counts how many locations are in each cluster
For i = 1 To data.NumbClusters
data.HowManyPerCluster(i) = 0
Next i
For i = 1 To data.NumbLocations
data.HowManyPerCluster(data.WhichCluster(i)) = data.HowManyPerCluster(data.WhichCluster(i)) + 1
Next i
Close #1 'close the file
End Function
Here is my nearest neighbour algorithm which does run:
Code:
Option Explicit
Function NearestNeighbour(data As LocationData, sol As SolutionTeam, start As Long)
Dim i, j, k, As Long
Dim current, bestCurrent, dist As Long
Dim Duration As Double
Dim SumScores As Long
Dim visited() As Long
ReDim visited(0 To data.NumbLocations)
sol.Duration = 0
start = 0
current = start
bestCurrent = 0
sol.Sequence(0) = start
sol.Sequence(data.NumbLocations + 1) = 0
visited(start) = 1
sol.SumScores = 0
For i = 1 To data.NumbLocations
dist = 2147483647
For j = 1 To data.NumbLocations
If data.Distances(current, j) < dist And visited(j) = 0 Then
bestCurrent = j
sol.Duration = sol.Duration + data.Distances(sol.Sequence(i), sol.Sequence(i + 1))
dist = data.Distances(current, j)
End If
Next j
current = bestCurrent
sol.Sequence(i) = bestCurrent
visited(bestCurrent) = 1
Next i
End Function
This returns the sequence 0 4 2 1 3 0 but I am expecting a return of 0 2 1 3 4 0. I think it's to do with my constraints not working.
My EvaluateSolution contains all my constraints that need to be adhered to (pre-determined and not able to amend) and the feasibility of the solution i.e., all clustered locations being visited within the time available - it's okay if all locations cannot be visited within the time:
Code:
Public Sub EvaluateSolution(data As LocationData, sol As SolutionTeam)
Dim i, j As Long
Dim msg As String
' first we evaluate the objective function value
' compute the sum of the scores
sol.SumScores = 0
For i = 1 To data.NumbLocations + 1
If (sol.Sequence(i) > 0) Then
sol.SumScores = sol.SumScores + data.Scores(data.WhichCluster(sol.Sequence(i)))
End If
Next i
'now we start checking the feasibility of the solution
'first the distance constraint: first we compute the duration of the route
sol.Feasible = True
sol.Duration = 0
For i = 0 To data.NumbLocations + 1
If (sol.Sequence(i) > 0 Or i = 0) Then
sol.Duration = sol.Duration + data.Distances(sol.Sequence(i), sol.Sequence(i + 1))
End If
Next i
If (sol.Duration > data.TimeAvailable) Then
sol.Feasible = False
End If
'check precedences
Dim cc As Integer ' cc contains the current most urgent cluster not yet completely visited
Dim foundFull As Boolean ' variable used later to check if a cluster has been fully visited
Dim countClusters() As Integer 'this counts how many locations in each cluster we have visited so far
ReDim countClusters(1 To data.NumbClusters) As Integer
foundFull = False
For i = 1 To data.NumbClusters
countClusters(i) = 0 'initialise data structure
Next i
cc = 1
For i = 1 To data.NumbLocations + 1
If (sol.Sequence(i) > 0) Then
'check if current location does not respect the urgency constraint
If data.WhichCluster(sol.Sequence(i)) > cc + data.d Then
sol.Feasible = False
Else
'update number of locations in the just visited cluster
countClusters(data.WhichCluster(sol.Sequence(i))) = countClusters(data.WhichCluster(sol.Sequence(i))) + 1
' if the location is in the current most urgent cluster and the cluster is all visited, we need to update cc
If (data.WhichCluster(sol.Sequence(i)) = cc And countClusters(data.WhichCluster(sol.Sequence(i))) = data.HowManyPerCluster(cc)) Then
foundFull = True
cc = cc + 1
Do While foundFull = True
If cc <= data.NumbClusters Then
If countClusters(cc) = data.HowManyPerCluster(cc) Then
cc = cc + 1
Else
foundFull = False
End If
Else
foundFull = False
End If
Loop
End If
End If
End If
Next i
'MsgBox ("the solution is feasible=" & sol.Feasible & " and the score is " & sol.SumScores & " and the duration is " & sol.Duration)
End Sub
In the example above the total available time *T* is 50 so the aim would be to try and get to all 4 locations *n* within each cluster *C*. The distance between each location is calculated within in the code and is as follows:
Code:
data.Distances(i, j) = Sqr((data.x(i) - data.x(j)) * (data.x(i) - data.x(j)) + (data.y(i) - data.y(j)) * (data.y(i) - data.y(j)))
These are all my types along with the definitions:
Code:
Option Explicit
Public Type LocationData
NumbLocations As Long ' number of locations that can be visited, as n in problem description
NumbClusters As Long ' number of clusters, as C in the problem description
TimeAvailable As Long ' time available T
x() As Long ' x coordinates
y() As Long ' y coordinates
d As Long ' value to fix priority allowance
Scores() As Long ' score for visiting all locations in each cluster
WhichCluster() As Long ' for each location which is the corresponding cluster
Distances() As Double ' distances between locations (rows: origin, columns: destination)
HowManyPerCluster() As Long ' how many locations in each cluster
End Type
Public Type SolutionTeam
SumScores As Long ' sum of the scores at visited locations (to be maximised in the objective)
Feasible As Boolean ' true if solution feasible, false otherwise
Duration As Double ' length (in distance of the route)
Sequence() As Long ' Sequence in which locations are visited (0 is starting and arrival point, -1 for empty visits)
End Type
I've tried adding in the constraints and feasibility into the Nearest Neighbour function to make it adhere to those constraints (as all solutions should come back feasible, this is NOT the case at the moment). When I add the constraints in it doesn't make any difference and the sequence is still 0 4 2 1 3 0 and I can't figure out why it's so wrong. Could it be because I have not set empty cells to -1? I also don't know where that is supposed to go in my code.
My desired output for this instance is 0 2 1 3 4 0.
Any help would be greatly appreciated as I am very new to VBA, so one would say it's quite a complex task for a newbie. The 'MainModule' is where all the functions are being called from and where the solution runs, specifically 'RescueTeam' and 'EvaluateSolution' will explain what the constraints are. 'ConstructiveHeuristics' module and function 'NearestNeighbour' are the two parts to look at.
