Booth Id:
SOFT015
Category:
Systems Software
Year:
2017
Finalist Names:
Duan, Jiedong (School: North Attleboro High School)
Abstract:
Purpose:
To investigate more efficient school bus routing techniques and the possibility of dynamically generating school bus routes using a genetic algorithm and other metaheuristics.
Procedure:
Control data for one Niles North after-school route, the I/L route, was compiled and put into ArcGIS Pro. Static routes were generated with 10,15, and 20 stops and their costs compared against the currently existing route. Then, random samples of 20 and 10 points were chosen as test samples for a simulation of dynamic routing. Routes were generated for each test scenario using the Network Analyst tool in ArcGIS, which uses a proprietary Tabu Search metaheuristic. After testing the feasibility of adaptive routing in ArcGIS, a bus routing simulation was created in Python using the package DEAP (Distributed Evolutionary Algorithms). A genetic algorithm was implemented and tested for its convergence speed and route quality vs. an exact one in a scenario with 20 students and 7 stops. All routes in both the ArcGIS part of the project and the Python part were evaluated based on a cost function that considered the value of the driver’s time, the bus’ operating cost (fuel, maintenance, etc.), and the opportunity cost of the students’ time.
Conclusion:
Dynamic school bus routes were able to be generated in ArcGIS that had costs of over 25% less compared to the currently used route studied. Furthermore, the routes generated in the low demand scenarios were even more efficient. In the Python routing simulation, the genetic algorithm was able to converge to fairly good routes relatively fast and able to scale up to a scenarios with 50 students and 15 stops and 100 students and 30 stops.