My straight-line trip itinerary was off from real roads by 2 hours 28 minutes
An itinerary built on straight-line distance was 148 minutes off real road times. I switched to Kakao directions with a coordinate cache, estimate fallback and days split by area.
#Backend #Node #Algorithms #Maps #API #Caching
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.