HOW DOES THE ALGORITHM WORK TO ASSIGN STUDENTS?

The Belmont-Redwood Shores School District assigns students to schools using an algorithm based on a linear optimization function known as minimum-cost flow formula. Companies use similar linear optimization functions (also called linear programming) to make important business decisions. For example, airlines use linear optimization to determine flight routes and minimize fuel costs. Shipping companies use a similar method to move packages from warehouses to stores to customers efficiently.

In our case, the District uses linear optimization to assign incoming students to schools close to their homes and within the limits of each school’s enrollment capacity. The assignment algorithm allows the District to find the optimal solution to minimize the total distance traveled by all students to their schools. One way to think about the District’s goal is to imagine a pedometer attached to every student for one morning’s walk to school; the optimal assignment would minimize the sum of the distances of all students’ walks to their schools. Instead of pedometers, however, the District uses a Web-based mapping service, such as Bing Maps, to determine the walking distance for all students.

The algorithm consists of two distinct phases.  In the first phase, the distance from each student’s home to each of the six elementary schools is calculated.  In the second phase, which can be run repeatedly with different parameters, these distances are used, along with minimum and maximum capacity of each school,  to perform an assignment that minimizes the total distance traveled.

To calculate distances, Bing Maps transforms the addresses of each student to a latitude and longitude. This location is then used to calculate the walking distance to each school entrance.  There are two schools that have multiple entrances; for those schools the distance used for assignment is the minimum distance to any of the school’s entrances.

Once the distances are calculated for each student, the assignment is performed according to the capacity constraints provided by the program operator. Microsoft Solver Foundation is used to minimize the total distance traveled by all students being assigned while respecting the capacity constraints at each school.