How to programatically group lap times into teams to minimize difference?

Question

Given the following (arbitrary) lap times:

John: 47.20
Mark: 51.14
Shellie: 49.95
Scott: 48.80
Jack: 46.60
Cheryl: 52.70
Martin: 57.65
Karl: 55.45
Yong: 52.30
Lynetta: 59.90
Sueann: 49.24
Tempie: 47.88
Mack: 51.11
Kecia: 53.20
Jayson: 48.90
Sanjuanita: 45.90
Rosita: 54.43
Lyndia: 52.38
Deloris: 49.90
Sophie: 44.31
Fleta: 58.12
Tai: 61.23
Cassaundra: 49.38 
Oren: 48.39

We're doing a go-kart endurance race, and the idea, rather than allowing team picking is to write a tool to process the initial qualifying times and then spit out the closest-matched groupings.

My initial investigation makes me feel like this is a clique graphing type situation, but having never played with graphing algorithms I feel rather out of my depth.

What would be the fastest/simplest method of generating groups of 3 people with the closest overall average lap time, so as to remove overall advantage/difference between them?

Is this something I can use networkx to achieve, and if so, how would I best define the graph given the dataset above?

Answer 1

When you're faced with a problem like this, one approach is always to leverage randomness.

While other folks say they think X or Y should work, I know my algorithm will converge to at least a local maxima. If you can show that any state space can be reached from any other via pairwise swapping (a property that is true for, say, the Travelling Salesperson Problem), then the algorithm will find the global optimum (given time).

Further, the algorithm attempts to minimize the standard deviation of the average times across the groups, so it provides a natural metric of how good an answer you're getting: Even if the result is non-exact, getting a standard deviation of 0.058 is probably more than close enough for your purposes.

Put another way: there may be an exact solution, but a randomized solution is usually easy to imagine, doesn't take long to code, can converge nicely, and is able to produce acceptable answers.

#!/usr/bin/env python3

import numpy as np
import copy
import random

data = [
  (47.20,"John"),
  (51.14,"Mark"),
  (49.95,"Shellie"),
  (48.80,"Scott"),
  (46.60,"Jack"),
  (52.70,"Cheryl"),
  (57.65,"Martin"),
  (55.45,"Karl"),
  (52.30,"Yong"),
  (59.90,"Lynetta"),
  (49.24,"Sueann"),
  (47.88,"Tempie"),
  (51.11,"Mack"),
  (53.20,"Kecia"),
  (48.90,"Jayson"),
  (45.90,"Sanjuanita"),
  (54.43,"Rosita"),
  (52.38,"Lyndia"),
  (49.90,"Deloris"),
  (44.31,"Sophie"),
  (58.12,"Fleta"),
  (61.23,"Tai"),
  (49.38 ,"Cassaundra"),
  (48.39,"Oren")
]

#Divide into initial groupings
NUM_GROUPS = 8
groups = []
for x in range(NUM_GROUPS): #Number of groups desired
  groups.append(data[x*len(data)//NUM_GROUPS:(x+1)*len(data)//NUM_GROUPS])

#Ensure all groups have the same number of members
assert all(len(groups[0])==len(x) for x in groups)

#Get average time of a single group
def FitnessGroup(group): 
  return np.average([x[0] for x in group])

#Get standard deviation of all groups' average times
def Fitness(groups):
  avgtimes = [FitnessGroup(x) for x in groups] #Get all average times
  return np.std(avgtimes) #Return standard deviation of average times

#Initially, the best grouping is just the data
bestgroups  = copy.deepcopy(groups)
bestfitness = Fitness(groups)

#Generate mutations of the best grouping by swapping two randomly chosen members
#between their groups
for x in range(10000): #Run a large number of times
  groups = copy.deepcopy(bestgroups)       #Always start from the best grouping
  g1 = random.randint(0,len(groups)-1)     #Choose a random group A
  g2 = random.randint(0,len(groups)-1)     #Choose a random group B
  m1 = random.randint(0,len(groups[g1])-1) #Choose a random member from group A
  m2 = random.randint(0,len(groups[g2])-1) #Choose a random member from group B
  groups[g1][m1], groups[g2][m2] = groups[g2][m2], groups[g1][m1] #Swap 'em
  fitness = Fitness(groups)                #Calculate fitness of new grouping
  if fitness<bestfitness:                  #Is it a better fitness?
    bestfitness = fitness                  #Save fitness
    bestgroups  = copy.deepcopy(groups)    #Save grouping

#Print the results
for g in bestgroups:
  for m in g:
    print("{0:15}".format(m[1]), end='') 
  print("{0:15.3f}".format(FitnessGroup(g)), end='')
  print("")
print("Standard deviation of teams: {0:.3f}".format(bestfitness))

Running this a couple of times gives a standard deviation of 0.058:

Cheryl         Kecia          Oren                    51.430
Tempie         Mark           Karl                    51.490
Fleta          Deloris        Jack                    51.540
Lynetta        Scott          Sanjuanita              51.533
Mack           Rosita         Sueann                  51.593
Shellie        Lyndia         Yong                    51.543
Jayson         Sophie         Tai                     51.480
Martin         Cassaundra     John                    51.410
Standard deviation of teams: 0.058