How Konavi Finds the Optimal Route

Why Is Planning a Travel Route So Hard?

When visiting multiple tourist spots in Seoul, most people open a map and group nearby places together. Looking at straight-line distances alone, this seems like a reasonable approach.

But things change when you actually take public transit. Some places look right next to each other on the map, yet require two or three transfers because no subway line connects them directly. Conversely, places that seem far apart may sit on the same line and take just one ride. Seoul's transit network is complex, so the gap between straight-line distance and actual travel time is often larger than you'd expect.

On top of that, Seoul's public transit is asymmetric. The time from A to B is different from B to A. Depending on the subway transfer layout or bus route direction, one way can take significantly longer — so simply reversing the visit order can change total travel time dramatically.

In the end, you can't determine the optimal order just by looking at a map. Konavi solves this with real public transit travel time data and a mathematical optimization algorithm.

Step 1: Collecting Real Transit Times

Konavi pre-calculates the public transit travel time for every directional pair among all photo-enabled tourist spots and stores them in a database. New spots are added over time, and the cached pairs are updated accordingly.

This data comes from ODsay, a Korean public transit API. Since Google Maps cannot accurately calculate Korean transit routes, Konavi uses ODsay, which specializes in Korean transit data.

Thanks to this pre-cached data, Konavi doesn't need to make a flood of API calls when finding a route, so results come back fast. The only real-time calculation needed is the travel time from your starting point to each tourist spot — and only in one direction (starting point to spot). Since Konavi's route is an open path that starts at your origin and ends at the last spot, there's no need to calculate the return trip.

Step 2: Finding the Optimal Order (Held-Karp Algorithm)

Once all travel times between places are ready, Konavi uses the Held-Karp algorithm to find the optimal visit order.

This algorithm is one of the exact methods for solving the famous "Travelling Salesman Problem" in computer science. The key ideas are:

• It systematically explores all possible visit combinations
• It remembers (memoizes) results of partial routes already calculated, avoiding redundant work
• As a result, it finds the exact optimal solution much faster than brute-forcing every possible order

Konavi's route is an open path that starts at your origin and ends at the last tourist spot. It doesn't include the time to return to your starting point, so you're free to wrap up your day however you like — grab dinner near the last spot, head to your hotel, or keep exploring.

Step 3: Outlier Detection (Far-Away Spot Alert)

Even after calculating the optimal route, one of your selected places might be far removed from the rest, significantly increasing total travel time.

Konavi automatically detects these spots:

• It tries removing each place one at a time and recalculates the route without it
• If removing a specific place reduces total travel time by more than 30% and saves at least 40 minutes, it flags that place as an outlier

When an outlier is found, Konavi suggests removing it. Of course, you can keep it in your route, or swap it with a nearby alternative.

Step 4: Nearby Spot Recommendations

When you remove an outlier or want to swap a place, Konavi recommends tourist spots that can be inserted into your current route with the least additional travel time.

Rather than simply finding places close in straight-line distance, it looks for spots that create the smallest detour when inserted between any two consecutive stops. For example, inserting C between A → B creates A → C → B — Konavi ranks places by the added time (A→C + C→B − A→B), showing the best options first.

Summary

• Transit data — Real travel times for every directional pair of photo-enabled spots, pre-cached for fast, accurate calculations.
• Held-Karp optimization — Mathematically computes the shortest visit order, guaranteeing the optimal solution.
• Outlier detection — Automatically identifies spots that significantly increase total travel time.
• Nearby recommendations — Suggests alternative spots that can be inserted with minimal detour.