Simplifying route geometry before the search can cut processing time by four fifths.
Public transport apps promise to find you a route in seconds. Under the hood, many of them run Dijkstra's algorithm, which walks through a network of stops and connections looking for the shortest way from A to B. It is reliable and well understood. It is also slow once the network gets big, because it keeps looking at every option it can reach.
A team at Universitas Brawijaya asked a different question. What if the network were smaller before the search even began? Their answer was to run the Douglas-Peucker line simplification algorithm over the route geometry first, thinning out the points that add detail without adding meaning.
Douglas-Peucker takes a line and drops points that sit very close to the straight line between their neighbours. What survives is a coarser shape that still follows the original path. Fewer points means fewer nodes for Dijkstra to work through.
The paper also checks that the drawn route still looks right. Aggressive simplification can turn a curving road into a straight line that cuts across buildings, so the authors tuned the process to keep the displayed path reasonably consistent with the real one. The visual cue survives, which matters because a route line that ignores the road is worse than a slow one.
Route finding is a feature users notice only when it is slow. Shaving four fifths off the processing time is the difference between a map that responds while you type and one that makes you wait. The overhead is paid once per simplify operation, while the savings apply to every search that follows.
Pinandito, Kharisma, and Akbar (2023). Improving Route-Finding Performance of Dijkstra Algorithm and Maintaining Path Visual Cue Using Douglas-Peucker Algorithm. Proceedings of the 8th International Conference on Sustainable Information Engineering and Technology.
