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.

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.

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.

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.

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.