I have been looking for houses. When I add open houses to my Google Calendar, I am able to request direction to whatever house is open next in time, but I was thinking…
“What if two houses are significantly far apart, open at similar times, and there are other houses in each of their respective neighborhoods that open at different times? Is there a way I can plan my day of house hunting so that I can attend all of the open houses?”
The program allows the user enter a series of open houses and finds a route that will allow the user to visit the maximum number of open houses given the constraints of travel time between locations and when the open houses are open.
My focus on this project was getting the backend logic working. I've started the learn some about frontend work, but I am still an extreme novice. If I have time before the end of the Spring 2019 semester, I will make an attempt to get something put together, but it is only a stretch goal.
The Open House Route Planner has been broken down into two major pieces: querying and computation.
I have a limited number of Esri Developer Credits and I want to limit the number of credits I use. To do this, I
- cached the addresses, the geocoded addresses, and the driving directions between all houses houses,
- and before a query to Esri is made, I have
- checked if a given address has already been geocoded,
- and checked if a the directions between two given points has already been fetched
- Given n houses to visit, create a fully connected directional graph.
- Iterate over each house and then recursively search the graph for a set of acyclic edges.
- To travel to another edge, keep a version of the current time (scoped to the open house in question) to detemine if you arrive at the open house either early or during the designated hours; adjust time accordingly.
- If you arrive to late, procede to the next acyclic edge.
- When a path has been exhausted, return that path to the recursive level above and keep traveling the graph.
- Once all potential routes have been identified, identify and return the longest routes.
When thinking about spending a day visiting open houses, you might be lucky to have enough time in the day to visit 7 or 8 houses. With that in mind, my approach is close to a brute force strategy for solving the routing problem. Since the number of houses you can visit is fairly finite, brute force does not take all that long.
Given 10 locations, Open House routing calculations took 0.04648470878601074 seconds to execute.
The maximum number of houses that could be visited was 6.
This output was provided by the test function within the OpenHouseRouting class.
- MongoDB - for simplified storage of data during the ETL process.
- Flask - for providing an endpoint for the program's location data to be parsed and performing queries to the Esri Developer API.
- Docker - for compartmentalization of the work. In addition to making the work more portable, containers also provide a convenient way of breaking a problem down into its simplest parts.
- Docker-compose - to put the containers on the same network and so each container can call the others out by name.
A Python graph class from https://www.python-course.eu/graphs_python.php. Changes to include weighted edges from https://towardsdatascience.com/to-all-data-scientists-the-one-graph-algorithm-you-need-to-know-59178dbb1ec2 and additional modification to the author's adaptation that I didn't agree with.
TODO
| Name | Version | Link |
|---|---|---|
| Docker | 18.09.2 | https://docs.docker.com/install/ |
| docker-compose | 1.23.2 | https://docs.docker.com/compose/install/ |
| Esri Developer Account | N/A | https://developers.arcgis.com/ |
I would like to acknowledge the initial help I received in starting this project to those listed below. I refer to their LinkedIn pages as I do not have all of their GitHub profiles available.