Route Planner for my Friend's Business
My best friend is the owner of BreakfastFiesta which is a business that focuses on delivering breakfasts, flowers and other gifts for special occasions.
Her delivery process is normally pretty smooth. A normal day for her might involve delivering 2 or 3 arrangements. The process of choosing the best route for 2 or 3 points then back home is straightforward and almost automatic.
But what about when there's 50?
That was the case for her on Valentine's 2023, where she had the deliveries shown above. (I took out people's IDs and replaced her home coordinates for privacy). The difference between delivering 50 things strategically and non-strategically, in Miami traffic, is literally hours. And that was time she couldn't afford to lose since she's also doing other things like prepping everything and building the arrangements.
I wanted to help her, and I wanted to do it in a simple reproducible way. I opted for the simplicity and availability of Google Sheets and Google Colab. I designed a Google Sheet that had everything set up for capturing address data, making it uniform, and producing the latitudes and longitudes. Then I processed it in Colab.
Instead of invoking APIs to get driving distances, I used the Haversine formula to calculate the spherical distances between the latitudes and longitudes. It was a trade-off: by doing it this way, I didn't have the accuracy of a map API, but I also didn't have to pay for any API keys. I didn't need a whole lot of precision anyway. I worked based off of the assumption that "hey, if this point is further when measured along the surface of the Earth, then it's probably further when driving too."
After I had a distance matrix from every point to every other point, I wrote a simple algorithm to find the nearest location based on that Haversine distance, mark that location as visited, and repeat until there are no unvisited locations. This is a naive solution, and is graphically represented on the bottom left. There are better algorithms, like the one graphed on the bottom right. You can see that it takes a slightly different but fundamentally better path.
(If you're curious about what a state-of-the-art algorithm for this problem type looks like, check this out.)The program also generates an Excel file that shows the customer details in the recommended sequence order. This gives her the option of looking at the route in a checklist type of view.
This is an idealized model and in practice everything plays out differently. For example, she wouldn't be able to fit all 50 arrangements in her car and take them all in one go, so she does have to go back home periodically. Sometimes she hires other drivers so the one route may turn into many different subroutes taken by different people. These are all factors that diverge the ideal model from reality. But I think the app adds a lot of value regardless, it just may need some manual partitioning.
It's hard to quantify exactly how much time this has saved her on days with lots of orders, but as someone who has driven for her before and after implementing this tool, it feels like a lot. It's cool that I was able to give my friend not just a solution but a system that she can use to easily generate her own solutions whenever she needs to. It's as easy as filling out a Google Sheet and pressing run on the Colab. All in all I'm happy with this project. I got to witness a real change in the way my best friend runs her business, and I'm happy I was able to help her out.
Link to the Colab