We are three PhD students in Computer Science who love graph algorithms. The potholes problem is a typical travelling salesman problem, so we went for it!
What it does
1) This app allows the public to report a problem with an open pothole. It improves upon the current interface of the City of Knoxville Pothole Patching website as it offers fields for submitting approximate size (in sq. meters), approximate depth and a photo of the pothole. 2) It calculates the optimal route (based on distance or time) for the pothole crew drivers to be routed to the open potholes which have been submitted the previous day, or earlier. 3) A pothole crew member can enter a completed pothole.
How we built it
1) Based on preliminary data analysis from the data provided, the pothole patching crew has patched at most 11 potholes per day. In addition, given that the crew consists of two trucks, we assumed that the maximum potholes that a truck can patch per day is upper bounded by 13. This seemed like a scenario where implementing an _ exact _ solution to the travelling salesman problem would be of practical importance, as the number of potholes that can be dealt with daily is fairly small. Thus, we implemented an exact dynamic programming TSP solution. The route that the trucks should take can be calculated beforehand, say the morning while the trucks get loaded. Thus the drivers can decide whether they will take the optimal route which minimizes distance or the route which minimizes time travelled. We used flask and Google maps API to pull up the distances between the locations of the potholes, as well as the time needed to drive between locations.
Challenges we ran into
We are quite new to Flask and web development so building the interface and pulling up information from Google maps was challenging.
Accomplishments that we're proud of
It's our first Hackathon! We built something :)
What we learned
We learned quite a lot about Flask, SQL Alchemy (the database we used), using Google Maps APIs, as well as the process of potholes patching :)
What's next for The Knox Pothole Guru
1) Polish the interface. 2) Allow to account for parameters such as size and depth of the pothole in calculating the route as patching a large pothole might results in a much higher cost (e.g. truck will have to be reloaded with material after patching it). 3) Allow to combine time and distance needed to drive between pothole locations in order to derive a weighted optimal route. 4) Use heuristic TSP methods if the number of potholes increases.