In the creation and evolution of my algorithm, a couple of "variables" have been created. The two most powerful and confusing variables are the Strength Factor and the Discourage Factor. These two factors are analysed in this excel spreadsheet used to create the graphs below.
The Strength Factor, one of the earliest discoveries, is needed to force road teams to leave the city they are currently in. Of course the schedule with the shortest distance will achieve this goal by placing teams in a city where they will remain as long as possible. This allows them to play game while not adding miles. in this way the miles per game rate drops dramatically. While this is good for decreaing the distances for each team, and also for the league, it results in very undesirable schedules. In particular one team could likely spend 4 or 5 games in a row in the same city. While this is desirable in some sports, most notably baseball, this is undesirable in other sports, such as hockey and football.
By increasing the Strength Factor, a team is more likely to leave the city it is in to visit another city. On the algorithm level, this is caused by multiplying the Strength factor by the Demand Matrix. The Demand Matrix keeps up with all of the remaining match ups and allows some form of "look ahead" for the algorithm. Decreasing the Strength Factor makes the Demand Matrix less important in decision making, and results in teams staying in the same location for longer periods of time.
The Discouraging factor, a recent discovery, was needed to increase the number of games the assignment algorithm was selecting. It is difficult to explain the situation that required this value:
Lets assume we have 5 teams, A-E, and teams A-C all have available home dates. After the assignment algorithm is run we have the following results:
What results is the B at A game is picked. Because team B was to host team C, that game is ignored, or canceled. Because team A was to play at C, that game is also canceled. The pairing of A and B (both in the group with available home dates) other selections became impossible.
What causes this is the way the Assignment algorith is designed to work. The assignment algorithm assumes that the "Supply" locations (Road teams) and the "Demand" locations (home teams) are in two different sets, as indicated in the diagram to the right.
In the origional version of my program, the home teams and road teams were kept in seperate groups. If I team requested a home game, it was removed from the group of possible road teams. It was also required that the size (cardinality) of the set of road teams be greater than or equal to the size of the set of home teams. This resulted in a set up similar to the diagram to the right.
The problem with this was that it forced very early decisions to be made on the home teams, which may have forced poor choices when choosing road teams later. The solution was to allow all teams to be possible road teams. This resulted in an arrangement similar to the diagram to the right.
The problem from the example above is caused by teams inside the home teams set choosing other teams inside the home team set. We wish to "discourage" these types of selections, however, we do not want to prohibit them. If we prohibit these types of selections we are back to the same situation as the first diagram.
We want to encourage teams inside the inner circle to pair with teams outside the inner circle. The Discourage Factor is a mathematical representation of how strongly we wish to encourage this type of pairing. A low "Discouraging factor" will allow 2 teams inside the inner circle to select each other. A higher "Discouraging Factor" will increase the likelyhood of Home and Non-Home team pairings.
By manupilating these two factors we can create a variety of results. The graphs below, which are derived from this excel spreadsheet demonstrate these factors.
The graph below shows the results of using different Strength Factors and Discouraging Factors on the number of games. The X-axis are the different Strength factors from 1 to 51. The 11 different sets (The key is on the right hand side) are selected Discouraging Factors (1-51, by fives). The points in the graph are the number of games the program scheduled. Each team submitted 45 "possible home dates" scattered randomly over 5 months. The league requires 192 games, which are the points at the very top of the graph.
As can be seen, a discouraging factor of 1 is completely unusable, never coming close to 192 games, and rarely break above 182. A Discouraging factor of 51 (the highest value used for the chart) results in a very high number of games on average, but oddly only 1 times did it schedule all 192 games. This was with the strength factor of 15, which also coincidently was the same place that all but the lowest 2 discouraging factors placed all 192 games. From this chart, the best Strength factor appears to be 15, and the best Discouraging Factor appears to be 11. While lower values for each are clearly undesirable, there is not easy way to choose the "best" value.
The following graph shows the distances produced from the schedules above. All of the schedules that did not produce enough games have been ignored, leaving only a handfull of points. The distances for these usable schedules are graphed below, with the axis the same as the previous graph.
It is difficult to see on the graph but the blue spot at Strength of 15 is actualy a point from each of the sets of Discouraging factors 16-51. Also at a Strength of 18 are points for the Discouraging factors 6 and 11. As this chart clearly shows, A lower Strength Factor produces lower distances. This is because teams are not forced to leave a city they are currently in. This reduces that teams milage by allowing them to play many games with no travel. While this is good for reducing milage, for our purposes, the "quality" of this schedule is likely to be poor.
At the other extreme, with a Strength factor of 37, the total distance is almost 17000 miles higher for the season. This increase in distance is caused by teams being forced to leave a city they are currently in to go play in other cities. This results in more travel between games.
I will load each of these schedules once I decide on a good format for them, so that you can compare each of the schedules for "quality."
The big decision will be which of these schedules to choose and this can be a very subjective decision. The following table allows easy comparison of the distances from the three schedules above, and also included are the distances from the actual 1995-96 schedule that the generated schedules were bades on.
|SF 37 DF 6||9687||16417||12029||17200||9699||15463||80495|
As the table shows, even the worst case schedule generated by the program saves milage over the actual schedule. Since we wish to decrease total distance as much as possible it is comforting to knwo that we have several different schedules we can pick from with an eye towards quality, that all have significant savings over the actual schedule from tht season.