Progress 09/01/02 to 08/31/04
Outputs
1 Final Status Review We have an operational prototype of the school bus routing web system. The major technical research objectives have been achieved in conceptual design and our solutions have been operationalized in the prototype bus routing web system. 2 Test Cases This chapter describes the test cases for the GIS Workshop school bus routing algorithm. This involves the testing that has been completed thus far and the results from those tests. At this point, all scheduled testing has been accomplished. 3 Programmer's API The purpose of this chapter is to provide supplementary documentation for all of the code involved in the school bus routing algorithm. The code itself is well documented through the use of comments. 4 Distance Algorithm (Djikstra's) We used the vertex adjacency matrix and the distances between each vertex to run Djikstra's algorithm. 5 Clustering 5.1 Clustering algorithm 5.1.1 Preconditions * Distance Matrix outputted to file by Djikstra's within
Distance Matrix * Zero index in Distance Matrix represents the school 5.1.2 Process * Find sufficiently random seed points to use as the beginning of each cluster o Randomly choose number of initial seed points o Eliminate 1 of 2 closest seed points that has the lesser sum of distances from the other seed points o Add a seed points from all the available non-seed points that has the maximum sum of distances from the seed points o Iterate 10 times to ensure seed points are sufficiently random * Add each non-cluster student to the cluster end that saves the most traveling distance until none remain o Create matrix to store the benefit of adding each non-cluster student to either end of a cluster o Create cluster (stack) for each seed point o Add each non-cluster student to the cluster end that saves them most traveling distance 5.1.3 Constraints * Clusters cannot have more than # of students * Number of clusters is equal to the number of busses * Num
of busses * Capacity must be greater than or equal to the Number of Student 6 TSP Algorithm A genetic Traveling Salesman Problem (TSP) is run on each individual cluster of students. Using the list of students and the distance matrix from Djikstra's algorithm, the TSP determines the best route for that group of students. The genetic TSP is run for every student cluster, each time outputting the list of students in the most efficient order. 7 Future Enhancements At this time, the application is ready for beta testing deployment. No further enhancements are scheduled.
Impacts
In the school year of 1997/1998 in Nebraska, 85,877 students were transported 39,403,706 miles at a cost of $57,112,407 (Pupil Transportation Statistics, 1998), which works out to about $1.50 per mile. The number of miles traveled equates to approximately 7,880,740 gallons of fuel and 7,880 oil changes (each oil change is 4 gallons of oil). If the amount of miles traveled could be reduced just 10%, that would equal a savings of $5,910,556 in one school year for just one state. The proposed solution is a web-based bus routing application service designed specifically for rural communities, but could be used in urban areas as well. This software would allow rural communities to map the location of student addresses, either automatically or manually and then design routes that would be the most efficient. This efficiency would not only save the schools money, but also would also save travel time for the children, reduce the amount of natural resources consumed and
pollutants emitted, and increase the safety for children.
Publications
- No publications reported this period
|