Calculating Fastest Possible Time from Multiple swimmer for Relay Race

[Andy Donegan]

Hi,

I have been searching online for something to produce this in Excel and have only found one link which seems to be based for goodle docs only ? SAS and R: Example 9.18: Constructing the fastest relay team via enumeration

With the help from this forum and stealing as much as I can find via the search facility I have now moved on a great deal and learnt a lot.

Now this calculation I am trying to produce I just do not know were to start in excel.

I have a group of swimmers say 5 and they all have times registered (personal bests) for four individual events.

[TABLE="class: grid, width: 500"]
<tbody>[TR]
[TD]name[/TD]
[TD]Freestyle[/TD]
[TD]Backstroke[/TD]
[TD]Butterfly[/TD]
[TD]Breaststroke[/TD]
[/TR]
[TR]
[TD]Billy[/TD]
[TD]00:50.25[/TD]
[TD]00:40.29[/TD]
[TD]00:39.82[/TD]
[TD]00:45.62[/TD]
[/TR]
[TR]
[TD]Jed[/TD]
[TD]00:38.54[/TD]
[TD]00:45.28[/TD]
[TD]00:52.23[/TD]
[TD]00:31.23
[/TD]
[/TR]
[TR]
[TD]Geoffrey[/TD]
[TD]00:42.34[/TD]
[TD]00:40.14[/TD]
[TD]00:45.32[/TD]
[TD]00:41.23
[/TD]
[/TR]
[TR]
[TD]Gordon[/TD]
[TD]00:35.31[/TD]
[TD]00:38.41[/TD]
[TD]00:42.10[/TD]
[TD]00:50.29[/TD]
[/TR]
[TR]
[TD]Gareth[/TD]
[TD]00:48.23[/TD]
[TD]00:36.23[/TD]
[TD]00:44.91[/TD]
[TD]00:32.29[/TD]
[/TR]
</tbody>[/TABLE]

What I am trying to figure out is the best Relay Team combination of swimmers, 1 swimmer for each individual event and the calculation will give me the fastest team selection.

Now invariably I have more than 5 swimmers to choose from, so would love to be able amend the calculation to be able to filter through a larger group than 5 if possible, I understand this makes the maths problem very large indeed.

The link above shows something and I have found an old web page which does this, but I want to incorporate this into our Gala planning sheet so that we can ensure we pick fairly and correctly the teams for our galas.

This might be what they call a lego calculation, I have found some maths sites in my searches but nothing to put my mind on to the correct path in creating an excel solver for this.

Thank you for your help in advance.

Andy.

 

[bruderbell]

Since you’re looking for the best combination of people to give the best overall time, you wouldn’t want to put a swimmer in an event where they are marginally better than the next best swimmer, where at the same time the first swimmer is considerably better than the rest in a different event.

I actually started out with the intent to just let excel "brute force" the problem (hence the name of my UDF), solving every combination and selecting the best. Then I satisficed when I realized I was so close to just letting the user prioritize legs of the race. Since I'm a junkie, and enjoy teaching myself to code, I'll keep on the path of a simple brute force UDF. I don't see another way to do it - do you?

 

[Andy Donegan]

Bruderbell,

I like your approach. I started looking at it this way, but got stuck in a couple spots. I’m wondering if you can modify it to account for this bias:
“prioritizes strokes further to the left in the table.”

Since you’re looking for the best combination of people to give the best overall time, you wouldn’t want to put a swimmer in an event where they are marginally better than the next best swimmer, where at the same time the first swimmer is considerably better than the rest in a different event.

Consider the following simplified example, with swimmers Andy, Bob, Charlie and events (legs of the race) X and Y.
[TABLE="class: grid, width: 500"]
<tbody>[TR]
[TD][/TD]
[TD]X[/TD]
[TD]Y[/TD]
[/TR]
[TR]
[TD]Andy[/TD]
[TD]20[/TD]
[TD]20[/TD]
[/TR]
[TR]
[TD]Bob[/TD]
[TD]21[/TD]
[TD]45[/TD]
[/TR]
[TR]
[TD]Charlie[/TD]
[TD]26[/TD]
[TD]40[/TD]
[/TR]
</tbody>[/TABLE]

Obviously, you would want Andy in event Y and Bob in event X; for a total of 41. Your function as currently would put Andy in event X and Charlie in event Y; for a total of 60.

Bruderbell/Verald,

Thank you guys, yes Verald has hit it on the head, the problem is when say Billy is a national swimmer and has the four fastest times for each event, the calculation needs to be able to pull out the fastest possible swim time from all the data.

So sorry for the delay in coming back guys, School entry day for Yr7 and I have been running around ensuring I had everything in place.

 

[Verald]

I don't see another way to do it - do you?

Bruder,

The only other way I see to do it is to calculate the outcome of every combination of groups. And then choose the lowest. This is what I (tried) to describe in my first post. Doing the calculations isn't as bad as it sounds, since we are using Excel to quickly do the calculations. I certainly wouldn't want to do it this way by hand.

But even calculating all combinations (actually permutations) of groups has its limits. The number of possible groups increases exponentially as there are more swimmers (or if there were greater than 4 events).

 

[Andy Donegan]

Andy,

Since you’re using excel, you can calculate the outcome of all the possible permutations. This still only works for relatively small number of swimmers. 26 swimmers would give 358,800 different permutations.

What I did is assign each swimmer a letter (A,B,C,D, etc.), as below: The times are simplified, and I used conditional formatting to highlight the min for each event.

[TABLE="width: 500"]
<tbody>[TR]
[TD][/TD]
[TD]backstroke[/TD]
[TD]breaststroke[/TD]
[TD]fly[/TD]
[TD]free[/TD]
[/TR]
[TR]
[TD]A[/TD]
[TD]40[/TD]
[TD]45[/TD]
[TD]39[/TD]
[TD]40[/TD]
[/TR]
[TR]
[TD]B[/TD]
[TD]45[/TD]
[TD]31[/TD]
[TD]52[/TD]
[TD]38[/TD]
[/TR]
[TR]
[TD]C[/TD]
[TD]40[/TD]
[TD]41[/TD]
[TD]45[/TD]
[TD]42[/TD]
[/TR]
[TR]
[TD]D[/TD]
[TD]38[/TD]
[TD]50[/TD]
[TD]42[/TD]
[TD]35[/TD]
[/TR]
[TR]
[TD]E[/TD]
[TD]36[/TD]
[TD]32[/TD]
[TD]44[/TD]
[TD]48[/TD]
[/TR]
[TR]
[TD]F[/TD]
[TD]32[/TD]
[TD]48[/TD]
[TD]40[/TD]
[TD]34[/TD]
[/TR]
[TR]
[TD]G[/TD]
[TD]39[/TD]
[TD]36[/TD]
[TD]41[/TD]
[TD]36[/TD]
[/TR]
[TR]
[TD]H[/TD]
[TD]37[/TD]
[TD]51[/TD]
[TD]44[/TD]
[TD]37[/TD]
[/TR]
</tbody>[/TABLE]



In a different area, you list each permutation, where ABCD would be 1 relay group, ABCE would be another and so forth (I’ll get to creating the permutations in a bit).

Creating the permutations is done via VBA as a 4-part nested loop. The code is below. The map() function converts from a number to a letter. (note: you would need to modify the map() function if creating for greater than 26 swimmers)

Sub get_perms()
    Dim vrange As Range
    Set vrange = Range("A1")
    lev = 8 ' total number of swimmers
   
    For x = 1 To lev
     For y = 1 To lev
      For Z = 1 To lev
       For a = 1 To lev
            If Not (x = y Or x = Z Or x = a Or y = Z Or y = a Or Z = a) Then
                     
                vrange.Value = map(x) & map(y) & map(Z) & map(a)
                Set vrange = vrange.Offset(1)
            End If
        Next a
      Next Z
     Next y
    Next x
   
 
End Sub

Function map(val As Variant) As String
 
    Select Case (val)
    Case 1: map = "A"
    Case 2: map = "B"
    Case 3: map = "C"
    Case 4: map = "D"
    Case 5: map = "E"
    Case 6: map = "F"
    Case 7: map = "G"
    Case 8: map = "H"
    Case 9: map = "I"
    Case 10: map = "J"
    Case 11: map = "K"
    Case 12: map = "L"
    Case 13: map = "M"
    Case 14: map = "N"
    Case 15: map = "O"
    Case 16: map = "P"
    Case 17: map = "Q"
    Case 18: map = "R"
    Case 19: map = "S"
    Case 20: map = "T"
    Case 21: map = "U"
    Case 22: map = "V"
    Case 23: map = "W"
    Case 24: map = "X"
    Case 25: map = "Y"
    Case 26: map = "Z"
   
 
End Select
 
End Function

Be sure you're on a different tab in the workbook before you run the sub it will overwrite your data.

Now use vlookups to determine the outcome of ABCD, ABCE, etc. Then filter for the minimum. This may be a bit oversimplified. I can't figure out how to post a sample workbook, but I can send it to you if needed.

Hopefully this helps.

Hi Verald,

I may have made myself sound more inteligent than needed I have never used VBA before or gone into advanced stuff like this so please bear with me.

I have placed the code into VBA and run on a sheet which has given the full list of permutations which I am getting my head around, ABHG is swimmer A as butterfly b as backstroke h as breaststroke etc.

So the next bit is the vlookup part, how do I set this up, my apologies I am reading up on vlookup right now, but I am struggling.

I have now column a on a spreadsheet with approx 1600 variations

I now need column b to give me the total time of say ABCD and go down each permutation look on my sheet and do the maths.

I have saved the Macro on Sheet 2 and have pasted your demo on Sheet 3, Can you take the time to show me the Vlookup set up please, I pick up quickly honestly and will decifer how it works once I see it.

Thank you very much for taking all the time to reply back on this.

Andy.

 

[zhfgtj27]

This is a typical operations research(OR) problem, more specifically an integer programming problem in the industrial engineering area. You can use Excel Solver to solve this problem pretty quickly.

In the picture above, the highlighted yellow part is my variables, which are all binary (you don't have to input anything in the sheet for the yellow part, but you will have to set up them a binary constraint in Solver later). You will have to input the formula for the objective in cell I2, which is a total time for all four legs (basically a sumproduct of the time matrix and the variables matrix). Also you will have to input the formulas for each of the constraint in column I. After that, you will go to Solver to set them up and click Solve.

The results will show in the yellow area. So in this case, Gordon - Freestyle, Gareth - Backstroke, Billy - Butterly, Jed - Breaststroke, and Jed will sit out. And the optimal total time is 02:22.6
If you have more swimmers data added in later, you will have to create a variable matrix the same size as the time matrix, and add a swimmer constraint for each new swimmer. The constraint for each swimming style will be the same. The objective will be the sumproduct of the 2 new matrix.

Hi,

I have been searching online for something to produce this in Excel and have only found one link which seems to be based for goodle docs only ? SAS and R: Example 9.18: Constructing the fastest relay team via enumeration

With the help from this forum and stealing as much as I can find via the search facility I have now moved on a great deal and learnt a lot.

Now this calculation I am trying to produce I just do not know were to start in excel.

I have a group of swimmers say 5 and they all have times registered (personal bests) for four individual events.

[TABLE="class: grid, width: 500"]
<tbody>[TR]
[TD]name[/TD]
[TD]Freestyle[/TD]
[TD]Backstroke[/TD]
[TD]Butterfly[/TD]
[TD]Breaststroke[/TD]
[/TR]
[TR]
[TD]Billy[/TD]
[TD]00:50.25[/TD]
[TD]00:40.29[/TD]
[TD]00:39.82[/TD]
[TD]00:45.62[/TD]
[/TR]
[TR]
[TD]Jed[/TD]
[TD]00:38.54[/TD]
[TD]00:45.28[/TD]
[TD]00:52.23[/TD]
[TD]00:31.23[/TD]
[/TR]
[TR]
[TD]Geoffrey[/TD]
[TD]00:42.34[/TD]
[TD]00:40.14[/TD]
[TD]00:45.32[/TD]
[TD]00:41.23[/TD]
[/TR]
[TR]
[TD]Gordon[/TD]
[TD]00:35.31[/TD]
[TD]00:38.41[/TD]
[TD]00:42.10[/TD]
[TD]00:50.29[/TD]
[/TR]
[TR]
[TD]Gareth[/TD]
[TD]00:48.23[/TD]
[TD]00:36.23[/TD]
[TD]00:44.91[/TD]
[TD]00:32.29[/TD]
[/TR]
</tbody>[/TABLE]

What I am trying to figure out is the best Relay Team combination of swimmers, 1 swimmer for each individual event and the calculation will give me the fastest team selection.

Now invariably I have more than 5 swimmers to choose from, so would love to be able amend the calculation to be able to filter through a larger group than 5 if possible, I understand this makes the maths problem very large indeed.

The link above shows something and I have found an old web page which does this, but I want to incorporate this into our Gala planning sheet so that we can ensure we pick fairly and correctly the teams for our galas.

This might be what they call a lego calculation, I have found some maths sites in my searches but nothing to put my mind on to the correct path in creating an excel solver for this.

Thank you for your help in advance.

Andy.

 

[Verald]

Andy,

Glad to help.

First, on Sheet1, enter your swimmer’s name in Column A, an alphabetic list in column B, and then their times for each event in columns C, D, E and F.

On sheet2: Column A should be your permutation (ABCD).
Column B: formula should be =mid(a1,1,1)
Column C: formula should be =mid(a1,2,1)
Column D: formula should be =mid(a1,3,1)
Column E: formula should be =mid(a1,3,1)

This will give you 1 letter of the permutation: col B will be the first letter, col C will be the second, etc.

(A quick summary of vlookup: it has 4 parameters, says =vlookup(Find this value, in the first column of this range of cells, when you find it-display this many rows over, type of match)

Column F: =vlookup(B1,Sheet1!B:F,2,FALSE) – this says look in columns B thru F in sheet1. Look for the value of in B1, when I find it, return the 2^nd column. The false means only look for an exact match.
Column G: =vlookup(B1,Sheet1!B:F,3,FALSE)
Column H: =vlookup(B1,Sheet1!B:F,4,FALSE)
Column I: =vlookup(B1,Sheet1!B:F,5,FALSE)

This will give you the individual times for each swimmer in that event

Column J: =sum(f1:i1)

I gotta run to a meeting, but let me know if you need any other help.

 

[bruderbell]

That image won't be visible to anyone not sitting at your local machine.

Here's a true brute force method:

Function TrueBrute(DataRange As Range)
'datarange should just be data, no labels.  People as rows, legs of race as columns
Dim a As Integer, b As Integer, c As Integer, d As Integer
x = DataRange.Rows.Count
Dim permutations
ReDim permutations(1 To 2, 1 To WorksheetFunction.Fact(x))
Z = 1
Dim names()
ReDim names(1 To DataRange.Rows.Count)
    For i = 1 To UBound(names)
    names(i) = DataRange.Cells(i, 1).Offset(, -1).Value
    Next i
For a = 1 To x
 For b = 1 To x
  For c = 1 To x
   For d = 1 To x
        If Not (a = b Or a = c Or a = d Or b = c Or b = d Or c = d) Then
             permutations(1, Z) = a & "-" & b & "-" & c & "-" & d
             permutations(2, Z) = map(DataRange, a, 1) + map(DataRange, b, 2) + map(DataRange, c, 3) + map(DataRange, d, 4)
             Z = Z + 1
             
        End If
   Next d
  Next c
 Next b
Next a
m = WorksheetFunction.Match(WorksheetFunction.Min(WorksheetFunction.Index(permutations, 2, 0)), WorksheetFunction.Index(permutations, 2, 0), 0)
mm = WorksheetFunction.Min(WorksheetFunction.Index(permutations, 2, 0))
'find locations of - in best solution
a = WorksheetFunction.Search("-", permutations(1, m))
b = WorksheetFunction.Search("-", permutations(1, m), a + 1)
c = WorksheetFunction.Search("-", permutations(1, m), b + 1)
TrueBrute = names(Mid(permutations(1, m), 1, a - 1)) & ", " & names(Mid(permutations(1, m), a + 1, b - a - 1)) & ", " & names(Mid(permutations(1, m), b + 1, c - b - 1)) & ", " & names(Mid(permutations(1, m), c + 1, Len(permutations(1, m))))
End Function
Function map(r As Range, i As Integer, j As Integer)
map = r.Cells(i, j).Value
End Function

The returned names are who should swim the legs, in the order in which they appeared on the data input.

Again, save your sheet before you try weird things like selecting a datarange that isn't filled in, etc. Also, the code above isn't going to be happy if you try to setup a race with other than 4 legs...

 

[Andy Donegan]

Hi Verald,

Thank you, yes I have been sat working on that, I have now managed to have it search for the fastest time, report the minimum time and then pick the swimmers name and show them along with the time.

Thank you everyone, nearly everything I have just achieved I had no idea how to do, but thanks to all of your input, I have delved into Vlookup and am now using Index from something else I found on the forum to match the leters from my permutations to the minimum time to eventually display the list of swimmers that the coach should pick.

This is a cracking piece of code (ok my attempt is very long winded but it works excellently) anyone else involved in swimming or trying to pick this kind of thing I will gladly let them have my sheet to work on.

Here is a thumbnail of my screenshot


And the full screen shot here
http://s5.postimg.org/s5g6u6653/Proof_0001_30_10_2013.jpg

I have never done this before so I hope they work.

Thank you all so much.

 

[bruderbell]

Not to be outdone by the solver function, try this:

Function TrueBrute(DataRange As Range, OutPut As String)
'datarange should just be data, no labels.  People as rows, legs of race as columns
'output 1 = names, 2 = time
If OutPut = 1 Or OutPut = 2 Then Else Exit Function
Dim a As Integer, b As Integer, c As Integer, d As Integer
x = DataRange.Rows.Count
Dim permutations
ReDim permutations(1 To 2, 1 To WorksheetFunction.Fact(x))
Z = 1
Dim names()
ReDim names(1 To DataRange.Rows.Count)
    For i = 1 To UBound(names)
    names(i) = DataRange.Cells(i, 1).Offset(, -1).Value
    Next i
For a = 1 To x
 For b = 1 To x
  For c = 1 To x
   For d = 1 To x
        If Not (a = b Or a = c Or a = d Or b = c Or b = d Or c = d) Then
             permutations(1, Z) = a & "-" & b & "-" & c & "-" & d
             permutations(2, Z) = map(DataRange, a, 1) + map(DataRange, b, 2) + map(DataRange, c, 3) + map(DataRange, d, 4)
             Z = Z + 1
             
        End If
   Next d
  Next c
 Next b
Next a
m = WorksheetFunction.Match(WorksheetFunction.Min(WorksheetFunction.Index(permutations, 2, 0)), WorksheetFunction.Index(permutations, 2, 0), 0)
mm = WorksheetFunction.Min(WorksheetFunction.Index(permutations, 2, 0))
'find locations of - in best solution
a = WorksheetFunction.Search("-", permutations(1, m))
b = WorksheetFunction.Search("-", permutations(1, m), a + 1)
c = WorksheetFunction.Search("-", permutations(1, m), b + 1)
Select Case OutPut
Case 1
TrueBrute = names(Mid(permutations(1, m), 1, a - 1)) & ", " & names(Mid(permutations(1, m), a + 1, b - a - 1)) & ", " & names(Mid(permutations(1, m), b + 1, c - b - 1)) & ", " & names(Mid(permutations(1, m), c + 1, Len(permutations(1, m))))
Case 2
TrueBrute = permutations(2, m)
End Select
End Function
Function map(r As Range, i As Integer, j As Integer)
map = r.Cells(i, j).Value
End Function

So you can input a 1 for the names and a 2 for the time.
For instructino on creating UDFs, see here. How to Create a User Defined Function in Microsoft Excel

Bam!

 

[shg]

There's a workbook at https://app.box.com/s/tmvj4kcrn8ixyk0n2o62 that may do what you want. It shows an example where the fastest swimmer does not swim a particular leg because he has a better time on another stroke.