Planning a multi-day city trip shouldn't be this hard. You've got a list of 15 places you want to see scattered across Google Maps, TripAdvisor, and random blog posts. You know roughly when you'll be there, but you have no idea what order makes sense. Visit the Eiffel Tower first, then backtrack 3 kilometers to see the Louvre? That's hours wasted walking in circles.
CobbleRoutes started as a simple question: why is planning a walking trip so tedious? The answer led us down a fascinating path of optimization algorithms, infrastructure decisions, and real-world problem-solving.
When planning a city trip, you're dealing with information scattered across multiple sources:
Here's the thing: order matters enormously.
Imagine you're visiting Paris for 3 days with 15 places you want to see. If you visit them in a random order, you might walk 25 kilometers total. But if you optimize the route, you could cut that down to 15-17 kilometers. That's 8-10 kilometers saved—roughly 2 hours of walking time per day.
The math is brutal: with 15 POIs, there are 15! = 1,307,674,368,000 possible orders. Even if you could evaluate one route per second, it would take over 41,000 years to check them all. This is the Traveling Salesman Problem (TSP)—one of the most famous problems in computer science.
The consequences of poor route planning are real:
We needed a solution that could handle this complexity automatically.
CobbleRoutes solves this with a two-phase optimization pipeline that combines algorithmic efficiency with real-world routing accuracy.
The first challenge is finding the optimal order of POIs. Since TSP is NP-hard (meaning exact solutions become computationally intractable for large problem sizes), we use a heuristic approach that balances speed and quality.
#### Nearest-Neighbor Construction
We start with a nearest-neighbor heuristic:
This gives us an initial solution in O(n²) time, which is fast even for 50+ POIs. However, nearest-neighbor can create "crossings" where the route unnecessarily crosses over itself.
#### 2-Opt Improvement
To eliminate these crossings, we apply 2-opt swaps:
The 2-opt algorithm systematically tries reversing segments of the route. For a path like `[Start, A, B, C, D]`, it might try reversing the segment `[B, C]` to get `[Start, A, C, B, D]` and check if that's shorter.
// Simplified 2-opt improvement loop
while (improved && iterations < maxIterations) {
improved = false;
for (let i = 1; i < pathIndices.length - 1; i++) {
for (let k = i + 1; k < pathIndices.length; k++) {
// Try reversing segment from i to k
const newPath = reverseSegment(pathIndices, i, k);
if (calculateCost(newPath) < calculateCost(pathIndices)) {
pathIndices = newPath;
improved = true;
break;
}
}
}
}This doesn't guarantee the optimal solution, but in practice, it gets us within 5-10% of optimal for typical city-sized problems (10-20 POIs per day). More importantly, it runs in milliseconds, making it suitable for real-time route recalculation when users drag-and-drop POIs.
#### Why Not Exact Algorithms?
You might wonder: why not use branch-and-bound or other exact TSP solvers? The answer is performance:
TSP gives us an optimal *order*, but people don't walk in straight lines. We need actual walking paths along streets, with accurate time estimates.
This is where OSRM (Open Source Routing Machine) comes in. OSRM takes our ordered list of POIs and generates:
The workflow is:
This two-phase approach is crucial: we can't optimize route order without knowing real distances, and we can't visualize routes without getting the actual paths.
Real-world trip planning isn't just about distance—it's about time constraints:
CobbleRoutes includes a time-aware insertion heuristic that considers:
// Simplified time-aware scoring
const travelScore = 1000 / (1 + travelTimeMinutes);
const waitingScore = 500 / (1 + waitingTime);
const timeScore = 100 / (1 + actualArrivalTime / 60);
const score = travelScore + waitingScore + timeScore;This ensures routes are not just short, but also feasible given opening hours and visit durations.
For multi-day trips, we need to distribute POIs across days. We use k-means clustering to group POIs geographically, then optimize each day's route independently.
The algorithm:
The first version of CobbleRoutes was much simpler:
This worked for proof-of-concept but had significant limitations:
Today, CobbleRoutes uses:
The key insight is that order matters. By solving the TSP problem with real-world routing data, we can save travelers hours of unnecessary walking and help them make the most of their city visits.