BitStop

BitStop: a better way to bus. BitStop is a dynamic, democratic, and intelligent bus route generation platform that utilizes foot traffic data, enabling planners to provide the bus routes people need.

Comment

Inspiration

Columbus, Ohio, where Thanish and Chethas come from, has a very poor public bus system. After coming to Atlanta and talking to Sujai, the team realized that ineffective public transport plagues cities all over the world. U.S. public transport is known to be particularly bad, causing congestion, pollution, and inequality.

What it does

BitStop is a website for planners to create efficient bus routes for their city. Users can enter their city and the desired number of stops, and the website will generate and display a colorful bus route on a map of their city using an optimization algorithm. A sidebar will display each stop and its address. Residents of the city can also request bus stop locations, which are added to the bus routes on the map. Stops are generated using city-wide foot traffic data to get popular areas, and routes are generated using our custom optimization algorithm.

How we built it

Getting Stops: When a user enters a city and a desired number of stops, the website queries the BestTime API to get the top x spots ranked by the level of foot traffic in the city. These stops are displayed on the sidebar and written into a .csv file.

Generating A Graph: Using the .csv of stops, our application generates a weighted graph to represent the city. Each node represents a stop, whose weight is calculated through min-max normalization based on its foot traffic rank. Edges are generated between every node, and their weights are calculated using standard deviation normalization of the travel times between the nodes. To get the travel time, the app queries the Distancematrix.ai API. A visualization of our initial graph structure is attached.

Generating Routes: We create the initial routes which have start nodes that were sampled randomly from all the nodes. The core of the algorithm is a cost function that assigns penalties based on the length of the route, driving time between the nodes that make up the route, and a lack of diversity in the routes. Our genetic algorithm starts with the initial routes created earlier and improves the routes across generations by selecting parent routes using a fitness level calculated using the cost function. We also apply random mutations to introduce variability in routes. Then, a simulated annealing optimization algorithm is applied to approximate the globally optimal route system. We use this algorithm specifically to account for large search spaces when generating more complete route networks for larger cities.

Displaying Info: BitStop utilizes the Google Maps API to display the generated routes live as they change. Stops are written to a sidebar using React and Chakra UI.

User Requests: Users can suggest a stop using an input field. The latitude and longitude of the address entered is found using the Google Maps API and the suggestion is added to the map and updated in the route.

The Stack

Front End: React
CSS/UI: Chakra UI
Back End: Django
Data Processing: Numpy, Pandas, sklearn
APIs: Google Cloud Maps/Places, BestTime, DistanceMatrix.ai

Challenges we ran into

The biggest challenge was optimizing the route generation algorithm and fine-tuning the countless parameters in our heuristic algorithm to account for edge cases. One specific issue was that our cost function initially incentivized the creation of a long bus route for bus stops for a small portion of the population. We fixed this issue by implementing a quadratic length threshold penalty that heavily penalizes excessively long routes in our optimization process. Another issue was that our simulated annealing algorithm wasn't finding some maximal optimizations because it was getting stuck in locally optimized paths. We fixed this issue by tuning and increasing the cooling rate parameter.

Accomplishments that we're proud of

Our route generation system works for any city and number of stops we input. We are able to generate bus route systems for large metro areas across the world like Atlanta, Chicago, and even Hyderabad, India, but also for smaller suburbs such as Peoria, Illinois, and Grimes, Iowa.

We created our own heuristic algorithm, not using any prebuilt machine learning packages, which was a new experience for us, and was very difficult, but proved rewarding in the end.

What we learned

Evin: HackGT is my first hackathon, and I had minimal front-end development experience before attending. My first day was a crash course in React, and I quickly learned how to integrate front-end with back-end development using the CORS framework to connect Django scripts with React, as well as use UI templates like Chakra UI to design the layout.

Thanish: I learned about creating API requests, storing and retrieving data, implementing components in React, and data preprocessing techniques. I also learned about graph generation in Python and normalization functions.

Chethas: I learned about optimizing method heuristic algorithms for the bus route creation. There is a lot of complex math that goes into optimization.

Sujai: I learned about various APIs that are available for use. We received API data of maps, distances, foot traffic, and latitude and longitude.

What's next for BitStop

User Requests: Implement a seperate form for user requested stops that counts the requests for a specific stop and factors this into our route generation algorithm

Improved Mapping: Optimize our mapping algorithm by including more data such as traffic, population density, and time of day

Visualization: Implement live visualization of the bus routes as they are generated on the map

Built With

Share this project:

Updates