COVID-19 Carpool Clustering

Inspiration

During the COVID-19 pandemic, education has transformed to reflect new social distancing guidelines and as such educators need new tools to operate schools effectively. One major problem is transportation as large school buses place students in close proximity to one another, making safe distancing impossible. In addition, the groups of students assigned to a bus are purely based on location rather than student behavior, which increases the number of out-of-group interactions. Our solution to this issue is to create a tool that matches students with each other in carpool/bus groups, providing parents with a means to transport their children to and from school, minimizing mixing of students in this part of the school day.

What it does

This tool examines a variety of factors such as student friendships, classes, and home locations to match groups of students in carpool groups. This allows parents, many of whom are now working at home, to safely and effectively work together to transport their children to school. It also allows schools to plan new bus routes with the focus being minimizing child mixing as opposed to just location-based approaches.

How we built it

This tool is accessible through a webpage where educators can upload a CSV file detailing their students’ addresses, classes, and friend preferences. The CSV is then parsed and the addresses are converted to latitude longitude pairs using Google’s geocoding API in order to find the distance between students. This information is then passed into a novel spectral clustering algorithm to determine the different carpool groups. Finally these groups are displayed on a map on the webpage. For the frontend, we built it with React and Material UI. We directly embedded Google Maps API and its associated APIs (such as Places API) to present a visual map in which the markers could be placed. We had a function that generated distinct colors based on the number of clusters returned from the backend. Finally, we plotted those points onto the map. At the root of the clustering algorithm is spectral clustering, which takes in a weighted graph of distances. The novel aspect is a re-definition of distance scaled by desired control factors. First, the distances are scaled by a factor of which class the students are in. All students in the same class have their pseudo-distances scaled to make them seem closer together. In addition, the students that they acknowledge they interact with frequently also scale the pseudo-distances. After this, you essentially have literal distance scaled by social distance. The final step of the algorithm is to optimize paths to the school. This is achieved by scaling the distances between students by factors of the distance and the degree of angle created by going from the first student’s house to the school then to the second student’s. This inherently makes the paths straighter because students along a linear path to the school will have smaller angles and therefore smaller scaled distances. This transformed notion of distance is then put into scikit-learn’s spectral clustering algorithm, which outputs a requested number of clusters.

Challenges we ran into

Initially our project idea was to optimize travel routes through areas with high air quality; however, we faced difficulties with air quality APIs which limited our number of requests making our analysis very difficult and eventually caused us to change our project. Additionally, the spectral clustering algorithm was conceptually difficult to implement and it took some time to debug.

Accomplishments that we're proud of

The app is very visually appealing since it utilizes the Google Maps API. We are proud that this project pushed us to make something difficult and that we were able to implement it successfully despite this difficulty. We are also pleased that we were able to make something that could potentially be useful in real-life.

What we learned

In this project we learned how to utilize google maps APIs to determine the physical location of addresses as well as to display the generated clusters on a map. This was some of our group members first time working with google APIs so this provided a valuable learning experience. Additionally, we also learned how to implement a spectral clustering algorithm to generate clusters of students based on a variety of weighted factors. We also learned how to use react to create a visually appealing UI and learned how to use flask to communicate between the frontend and python backend.

What's next for COVID-19 Carpool Clustering

We would like to expand the algorithm to take information about volunteer parent drivers and pair the drivers with the clusters. We would also like to balance the cluster sizes so they are more even. Additionally, we would be interested in implementing the flexibility for opt-in throughout the term.

We are entering the Education - Beginner Track