The National Football League (NFL) in the United States will expand to 32 teams in 2002 with the addition of a team in Houston. At that point, the league will be realigned into eight divisions, each containing four teams. We describe a branch-and-cut algorithm for minimizing the sum of intradivisional travel distances. We consider first the case where any team can be assigned to any division. We also consider imposing restrictions, such as aligning the AFC and the NFC separately or maintaining traditional rivalries. We show that the alignment chosen by the NFL does not minimize the sum of intradivisional travel distances, but that it is close to optimal for an alignment that aligns the NFC and AFC separately and imposes some additional restrictions.
Citation
Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180 USA. November 2000. Revised: July 22, 2002. http://www.rpi.edu/~mitchj/papers/realign.html