Best Student Project: School Bus Routing for Optimization of Cost and Coverage by Sachchit Kunichetty Featured

Rate this item
(2 votes)

During this conference week, we accept project submissions from students, in order to encourage learning Data Science in students at the university as well as high school levels. The best selected student project is "School Bus Routing for Optimization of Cost and Coverage" by Sachchit Kunichetty, from Fairfield Ludlowe High School, in Fairfield, CT, USA. Sachchit has developed a Java-based application to optimize school bus routing. The work was supervised by Mr. Robert Benjamin, and evaluated by an independent study board of Fairfield Ludlowe High School.

School Bus Routing for Optimization of Cost and Coverage

Sachchit Kunichetty

Objective: Optimization of school bus routing, in terms of capacity management and cost efficiency.

Salient features of objective are:

  • Every student to get nearest designated bus-stop and a seat
  • Reducing the cost by school bus availability
  • Scheduling buses within school time constraints

Rationale: In existing school bus systems, students may experience some of the following inconveniences:

  • Students may have to walk more than 5 minutes to use the bus, which can be inconvenient for some students, especially in extreme weather.
  • Buses may have a lack of seating for students
  • Some students are not given bus service at all, due to proximity to school

This algorithm aims address some of these issues.

sachchit0

 

Fig. 1: Flowchart for K-Means Clustering Process

Description: Input for the algorithm is a set of students in the school system, and the geocoordinate locations of their residences.

Student residences are clustered into bus stops using the K-Means clustering algorithm, an unsupervised machine learning algorithm. User locations are grouped by refining cluster locations through taking averages of cluster members. The center of these clusters are the bus stops for the student residences located within the cluster.

Bus Stops are linked together as Hamiltonian cycles as per the Travelling Salesman Problem framework, which is solved with a Genetic Algorithm. Simulating generational development of possible routes, the algorithm produces a set of optimized routes that have the shortest route lengths, translating to shortest time elapsed in routing, minimizing both time and cost per each bus route.

sachchit1

Fig. 2: Flowchart for Genetic Algorithm

Sets of stops, or zones, are determined by clustering bus stops using K-Means Clustering. While this clustering is done, if the number of users serviced exceeds that which can safely occupy a bus, the algorithm chooses to rezone the stops in order to manage capacity. Once all bus routes are created, scheduling is generated for each bus. The output of the algorithm is a set of bus routes for each student in the district, described through bus stop location, and with the time at which the bus reaches each stop.

Results: Algorithm was tested with 686 random locations in the city of Fairfield, CT. This data was selected to simulate an actual set of student information that would be expected to be serviced. These locations were converted from street addresses to geocoordinate locations through public geocode APIs.

A sample output of the algorithm is shown below. For this data, 20 zones and 100 bus stops were created. The program runtime was 15 minutes.

sachchit2

Fig. 3: Raw Program Diagram. Sets of same color dots represents bus stops on the route. Lines show connections between bus stops in terms of routes.

sachchit3

Fig 4: Program output overlaid over Fairfield, CT. Overlay positioned using location of Bus Depot (origin) and School Location (endpoint)

For a specific zone, bus stops are created where there are 4.6 students per stop, which means given student density, students are closely located to each of their stops, minimizing the distance between student and the stop. Each of the bus stops are located in generally acceptable locations, but the process is not entirely controlled. Route minimization performs well, minimizing one route which was 3.769 miles to operate in only 2.998 miles, a 21% decrease in length. This minimizes the operation cost of buses to $1.85 for diesel fuel costs. Through the capacity management algorithm, students per zone/route was reduced from 71 students to 50 students, that which maximizes the number of students serviced while still keeping buses safe for operation, and allowing for greater comfort on bus rides.

Conclusion: This algorithm, along with the geocoordinate data processing, was developed in Java, using the plugins Spring, Maven, Google Maps Free API. A user interface, as shown in above pictures, was developed to display the routing optimization steps and final solution. User interface was written in JavaScript, with the plugins d3.js and jQuery.

Please publish modules in offcanvas position.