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:

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:

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:

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:

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:

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:

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.