`` If you’ve ever been on a road trip, you would know the real headache isn’t packing or arranging a vehicle.

Rather, it’s figuring out the best route so that you don’t waste time going back and forth between places. *assuming you have money to afford a road trip. if you can't afford a road trip, sorry, i won't be solving that problem in this video.

`` Say you are planning a trip across India to cover Spiti Valley, Pangi Valley, Ladakh, and Kashmir.

how do you decide which order to visit them so that your fuel cost stays low? Most of us rely on Google Maps, checking each location one by one, comparing distances, and then manually arranging them to make sense.

`` For me, this manual planning process is by far the most frustrating and  boring part of a road trip.

`` This motivated me to automate the route planning process. As I started researching, I realized I’d need two main tools. First, a digital map to calculate the shortest distance between any two locations. And second, an optimization solver for the Traveling Salesman Problem.

For those who aren’t familiar, the Traveling Salesman Problem in operations research identifies an efficient route for visiting multiple places. This is exactly what we need for an automated route planner. However, the catch is that solving the traveling salesman problem is NP-Hard. In simple words, as the number of places increase, time to compute the optimal solution also increases exponentially.

````  That’s why, for large number of places we would have to settle for near-optimal solutions. Mind you, for most practical cases, this sub-optimal solution would still beat a manually planned route.

```` With that in mind, I started looking for existing solvers that could handle the Traveling Salesman Problem, and that’s when I came across Google’s OR-Tools

—an efficient solver for standard discrete optimization problems.

```` To tackle the traveling salesman problem, OR-tools requires a two-dimensional distance matrix that stores the distance between every pair of locations.
`` For instance, if I plan to visit
Srinagar, Leh, Manali, the matrix would list the shortest path from each city to every other one.

`` So, The next challenge was to generating this distance matrix automatically,
which required a search for a digital map.

At this point, I had two choice: Google Maps or OpenStreetMap. I went with OpenStreetMap because it’s fully open-source, and unlike Google Maps, there are multiple free API providers.

```` This way I could keep the project cost close to zero while still having a reliable map data.

Now that the theory is clear,
`` let’s break down the system into smaller components.

Step one: the user types in their desired locations in a search box. For each new entry, the system fetches its GPS coordinates using geocoding service.

Step two:
`` once all places of interest are specified, the user clicks
a button to compute the optimal route. This triggers API call to calculate the shortest distance between every pair of locations. To do this efficiently, we should use Matrix API instead of the routing API, since it returns the entire distance matrix in a single call. This saves both time and reduces the number of API requests.

Step three: We pass the distance matrix to OR-Tools for solving the Traveling Salesman Problem. The output solution is the sequence in which one should visit the places of interest.

Step four: With the optimized location sequence, the next step is to visualize it.
```` For this, the sequence of places is sent to the routing API to fetch the actual route on a map.

I integrated the individual parts using JavaScript, PHP, and Python to make a working prototype.

`` I’ll be the first to admit that the UI still needs work. But since the code is open-sourced, I’m hoping someone can help improve that part. For now, let’s just see if the system works as expected.

`` Using the location search box, I’ll add a few of my favorite places so far: Starting With
Srinagar, Leh, Manali, Killar, Reckong Peo, Chitkul, Sonmarg, Padum, McLeodganj, and Tabo.

Once the places are added, let’s compute the optimal travel route.
```` This step takes a few seconds as the backend service builds the distance matrix and passes it to the OR-Tools solver to solve the Traveling Salesman Problem.

And here’s the result. You can see the map with all the destinations and highlighted paths showing the optimal route. If you scroll down, you’ll also see the optimal route listed as a sequence of place names. For this demo, I assumed that the first place is both the starting and the ending point. ```` This way, the system generates a round trip, bringing you back to where you started—which makes sense for most road trips.

That brings us to the end of this demonstration. Hopefully, this automated route planner will be helpful for your next road trip.
``  For you information, link to full codebase and instructions are available in the description. To use it, you’ll need a free API key from OpenRouteService. If you spot bugs or have ideas to improve the workflow, do write back and we can discuss further.