Example problem with highlighted solution.
Cell phones are increasingly prevalent in third world countries. For example, roughly 80% of individuals in African countries have a cellphone. This technology can be utilized to streamline access to medical professionals. Traveling doctors typically go wherever they are needed, but certain patients may be in more urgent need than others. A doctor can only visit so many patients in one day, hence the need for a routing algorithm to assist in planning the best way for a doctor to maximize impact on patients.
What it does
Patients can access an online portal through their phones that allows them to alert doctors in the region to their medical needs. The web app will automatically determine a route for the doctor that prioritizes more serious medical issues while attempting to maximize the number of patients visited. The route will be displayed for the doctor on a Google Maps display.
How I built it
We used Python in order to code quickly and thus django was a natural fit to get this web app running. We deployed on AWS (Amazon Web Services). As far as the algorithm, we employed a localized optimization heuristics with randomized perturbations in order to achieve an algorithm that performs nearly as well as an optimal solution in many cases.
Challenges I ran into
This problem is a variant of TSP with additional variables to consider which actually make this a more difficult problem to solve than an already NP-complete problem.
Accomplishments that I'm proud of
We achieved, in under 36 hours, an approximation for an NP-complete problem that is much more efficient than brute force and which provides nearly optimal solutions that could be very useful to planning patient routes for doctors in third world countries.
What I learned
We used the idea proposed by the Chained Lin-Kernighan Heuristic for the normal TSP combined with our localized optimization techniques in order to produce an efficient algorithm.
What's next for Traveling Surgeon Problem
We can continue to improve the UI/UX and also experiment with adding heuristics to our randomization along with the use of neural nets to combine multiple heuristics.