My straight-line trip itinerary was off from real roads by 2 hours 28 minutes

The very last step in the travel planner is building an itinerary out of the places you've saved. It works out what time you go where, how many minutes it takes to get to the next place, and how many places fit in a day, and shows it as a timeline.

At first I calculated travel time roughly. I had coordinates, so I took the straight-line distance between two points, multiplied by 1.25 because roads wind more than a straight line, and divided by 45km/h. In code it's only a few lines.

const SPEED = { car: { kmh: 45, overhead: 5 }, transit: { kmh: 25, overhead: 12 } };

function estimateMove(a, b, transport) {
  const km = haversineKm(a, b) * 1.25;   // straight-line distance -> road distance correction
  if (km < 0.8) return { distanceKm: round1(km), minutes: Math.max(3, Math.round((km / 4) * 60)), mode: 'walk' };
  const s = SPEED[transport] || SPEED.car;
  return { distanceKm: round1(km), minutes: Math.round((km / s.kmh) * 60 + s.overhead), mode: transport === 'transit' ? 'transit' : 'car' };
}

It looked plausible, but I had never measured how accurate it actually was. So I measured it once, and after seeing the result I tore it out and rebuilt it on real roads. This is a record of that process.

This is what I got when I actually measured

I took 20 places in Gangwon Province pulled from one YouTube video, linked them in order, and for each segment printed the estimate and the real road time side by side.

Segment                                    Straight est.  | Real road      | Diff
Mandong Jegwa -> Sageunjin Beach             8.1km  16min |   8.2km  23min |  +7min
Sageunjin Beach -> Gangneung Gimbap          7.5km  15min |   8.5km  23min |  +8min
Gangneung Gimbap -> Yukgu Bangatgan         70.6km  99min |  71.9km  72min | -27min
Yukgu Bangatgan -> Sokcho Corn Salt Bread    0.7km   6min |   1.7km   9min |  +3min
Jorongbak -> Kare no Kare                   13.2km  23min |  12.7km  20min |  -3min
Sampo Beach -> Gangneung Gil Gamja          87.5km 122min |  89.8km  81min | -41min
Gangneung Gil Gamja -> Jogae Jupging        68.3km  96min |  63.3km  68min | -28min
Jumunjin Beach -> Kisa                      48.3km  69min |  54.6km  52min | -17min
Paddle -> Jeong Coffee                        79km 110min |  83.5km  72min | -38min
Chilsadang -> Saebarami Oneun Geuneul        0.3km   5min |   0.3km   1min |  -4min

Total for 17 segments: estimate 688min vs real road 540min (difference 148min)

On a two-day, one-night trip, that's two and a half hours off. That's big enough to decide whether you can fit two or three more places into a day or not, so I couldn't let it pass as roughly right.

Why is it this far off?

Looking closely at the numbers, it wasn't simply wrong. Two errors in opposite directions were mixed together.

For long segments the estimate comes out too large. The nearly 90km segment from Sampo Beach to Gangneung Gil Gamja was estimated at 122 minutes, but it's really 81. Distances like this are mostly driven on expressways or national roads, so they're much faster than an average of 45km/h.

Short segments are the opposite, with estimates that are too small. The 8km from Mandong Jegwa to Sageunjin Beach was estimated at 16 minutes, but it's really 23. In town you don't reach 45km/h because of traffic lights and waiting for left turns.

In the end, if you calculate everything with a single average speed, long segments and short segments both come out wrong. It wasn't a problem that tuning a constant could solve. Raise the 45 and in-town gets worse, lower it and the expressway gets worse.

So I hooked up real directions

I hooked up the Kakao Mobility directions API. Give it the origin and destination coordinates and it returns the real road distance, the travel time, and even the route line to draw on the map.

The problem was the number of calls. The free quota is 10,000 calls a day, and each time an itinerary is generated it makes as many calls as there are segments. On top of that, when the user presses "Regenerate", that many go out again. The combination of destinations differs from person to person, but it was obvious that recurring segments, like the one from Gangneung to Sokcho, would keep overlapping.

So I built a cache along with it from the start.

// Kakao Mobility directions: real road distance/travel time by car (+ DB cache)
// Free quota 10,000 calls/day. The same segment is reused from route_cache (30 days)
const CACHE_DAYS = 30;

// Round coordinates to 4 decimal places (about 10m) to build the key, so tiny differences don't split the cache
const f4 = (v) => Number(v).toFixed(4);   // DB DECIMAL arrives as a string, so convert to a number

The point here is that I didn't use the coordinates as the key as they are but rounded them to 4 decimal places. Four decimal places is roughly a 10m unit. If the same shop is stored with coordinates a few meters apart, the cache splits and a new call is made every time, and blurring that out prevents it. When I first wrote this post the cache had 88 segments, and now it has 233. For segments that hit it, the API isn't called at all.

The DECIMAL note in the comment is something I guarded against up front because I got burned by it once before. The driver returns MySQL DECIMAL columns as strings, so if you put them straight into a calculation you quietly get strange values.

What happens when it fails?

I think about this every time I hook up an external API, and I used the same principle here. If it fails, it goes back to the estimate I was using before.

async function moveBetween(a, b, transport, date) {
  const est = estimateMove(a, b, transport);        // build the estimate first
  if (est.mode === 'walk') return est;
  const real = await carRoute(a, b);
  ...
  return real ? { ...real, mode: 'car' } : est;     // fall back to the estimate on failure
}

In fact, even while measuring those 17 segments earlier, directions failed for 2 of them. That happens when a place can't be reached by road, like an island, or when there's a problem on the API side, but itinerary generation itself shouldn't fail because of that, so only that segment is filled in with the estimate. A slightly wrong itinerary is better than no itinerary at all.

The order was a problem too

Once travel times were accurate, something else caught my eye. It was the way places are divided across days.

At first I solved it with nearest neighbor. From the first place it goes to the closest one, then the closest one from there, chaining them into a single line and cutting it by the number of days. But done this way, a single day ends up mixing different areas. You get an itinerary that starts in Gangneung, goes up to Sokcho, then comes back down to Gangneung.

So I changed how it's cut. It takes the direction the places are spread along, in other words it projects the coordinates onto the axis with the largest variance and sorts them, then divides them into consecutive ranges, one per day.

// Project onto the principal axis of the place distribution (the direction of largest variance) and sort
//  a natural order going from south to north along the coastline
const theta = 0.5 * Math.atan2(2 * sxy, sxx - syy);

// 1) Group geographically: project onto the principal axis and sort -> consecutive ranges, one per day
//    (not the saved order or a single nearest-neighbor line, but 'same area on the same day')
// 2) Fill only within the daily time budget: if stay + travel goes over the limit, move to the next day
// 3) Within each day, refine in nearest-neighbor order

The east coast of Gangwon Province stretches long from north to south, so this naturally splits it into a southern group and a northern group. I kept nearest neighbor only for refining the order within each day.

The result

I made an actual two-day, one-night itinerary from 10 places saved from a YouTube video.

Generation took 2.6 seconds. All travel times are based on real roads.

The days split into Goseong and Sokcho, and then Yangyang. That's the principal axis projection I mentioned above actually working.

There's also a warning at the top saying "Day 1 is a tight schedule", which means it went over the daily time budget. I set it to 7 hours for relaxed, 9 hours for normal and 11 hours for packed, and it tells you when you go over. Showing a warning like this is only possible because the travel times are real values. If the estimates are off by two and a half hours, the warning itself means nothing.

On the timeline, each segment gets its real distance and time.

Each segment gets real road values, like 10.4km 22 min or 2.4km 10 min.

Distances short enough to walk are shown as walking, and segments traveled by car get a link that goes straight to Kakao Navi. People turn on their navigation after looking at the app anyway, so I figured it was better to remove the step in between.

Public transit is still an approximation

To be honest about it, driving is based on real roads but public transit still isn't accurate. I couldn't find a free API that calculates local bus routes in one go, so for now it adjusts from the real road time.

// Public transit has no dedicated API, so adjust from the real road distance and the driving time
//   (driving x 1.7 + 15 min for transfers and waiting)
// No route line, because the road route can differ from the bus route (the map shows a straight dotted line)
const base = real
  ? { distanceKm: real.distanceKm, minutes: Math.round(real.minutes * 1.7 + 15) }
  : { distanceKm: est.distanceKm, minutes: est.minutes };

For segments between different cities, though, I attached intercity bus and train timetables, and if there's a timetable it uses that value. Not drawing a route line on the map is also deliberate. If I drew the car route line, people could assume the bus goes that way, so I'd rather leave it as a straight dotted line and let it show that it isn't exact.

What's left in the same day's commits

If you look at the commit log from the day I switched to road time, performance work went in alongside it.

08-24  feat(itinerary): itinerary generation based on real road time, and filling empty time
08-24  perf(api): bootstrap cache, request limits and response compression

Adding the cache and the request limits on the same day wasn't a coincidence. The moment I switched to road time, I felt right away how sharply directions calls grow with the number of places. Straight-line distance was free, but road time has a cost on every call.

So in exchange for accuracy I took on a new problem, the number of calls. For now I'm getting by on the cache, but when the user changes even one place, every segment that place is part of has to be asked again, and the cache doesn't help much there.

I need to make it recalculate only the segments that changed, but that means rewriting the itinerary generation logic. I got the accuracy right, and I haven't got the cost right yet.