Algorithm to divide racing drivers into equal teams

Question

I have a list of drivers in a racing game and I want to assign the drivers to teams of 3 drivers each. Each driver has a rating (typically a number between roughly 500 and 5000, the higher the better), and I want to use this rating to match all teams equally. By equally I mean that the average rating of the drivers in each team should be as close together as possible.

There is one important additional constraint though: I want each team to consist of one highly ranked driver (high rating), one middle ranked driver and one low ranked driver. This is important because it affects the final scoring of the race. While a team can be fair by joining three middle ranked drivers in a team (average rating could be similar to other teams), the final scoring is based on the assumption that each time has one high ranked driver and one low ranked driver. If that is not true, the scoring will not be fair.

So to summarize, the requirements are:

• Start with a list of at most 39 drivers,
• Assign drivers to at most 13 teams of 3 drivers,
• Keep the average rating of each team as equal as possible to the other teams
• Make sure each time consists of one high ranked driver, one middle and one low ranked driver.

Without my additional constraint, I could pretty easily come up with some optimization algorithm (or even brute force it?) that tries to equal the average ratings of each team. But in that case I may end up with a lot of teams that have 3 equally ranked drivers, which is not what I want. How do I add my additional constraint to this optimization problem?

Even if I can brute force it (at most 39 drivers in 13 teams should be possible I think?), I still don't know how to decide which solution (== list of teams and assigned drivers) is best. How do I determine the "score" or "fitness" of each solution?

Answer 1

You have limits - 3 drivers/team, max 39 drivers, rating classification low/medium/high, one driver of every class in every team.

So, the number of drivers is 3xN. Is it so?

And you have the target to optimize - the mediums should be maximally close. As a number to be optimized, (the fitness you mentioned), use the square of standard of these mediums.

Teams Mediums=M_i, i - team number
N - number of teams
A - average of all mediums or all drivers (the same numbers)
A=sum(driver's rate)/(3*N)
S(Square of standard)= sum((M_i-A)²

The standard itself could be taken as sqrt, but you don't need it really.

You have N drivers of each class. Now simply try every triad combination and lower the S.

As a fast way I see the following:( take the best 1-class driver, and the worst 2 and 3-class ones. Repeat with the drivers left. It is if you won't follow my next advice)

The problem is, that normally the differences between better drivers is larger than that between worse ones. And the team of the 1st driver will be absolutely the best usually. If you want to escape this situation, you should change the rate gaining algorithm so, that the drivers will spread between 500 and 5000 relatively evenly.

Answer 2

I would order your driver list by the rating (highest first) and assign one drivers to each team from 1 - 13.

Then assign the next 13 drivers to the list backwards from 13 - 1, so the lowest rated team, number 13, would get the next highest rated driver.

Finally if you add the current driver ratings of each team together and sort them by lowest rating first, then you can add the last 13 drivers to the teams, where the team with the lowest total ranking would get the highest rated remaining driver.