A line simplification step before the search cuts memory use and computation time on resource limited phones.
Open a map app and ask for directions. Behind that tap, an algorithm walks through a graph of roads to find the shortest path. Most of the time it feels instant, but on a cheap phone with a dense route network it can crawl.
The Dijkstra algorithm is the workhorse of routing, and its cost scales with the data it receives. Every extra point on a route line is another node to examine. A bus line that curves through a city can carry hundreds of points that describe the shape of the road rather than a real decision point.
The team applied the Douglas-Peucker algorithm as a cleaning step before routing. The method walks along a line and removes points that sit close to the straight segment between their neighbours. What remains is a simpler line with the same overall shape. Feed that simpler graph into Dijkstra and there is far less to compute.
To test the idea, the researchers used public transport routes in Malang City, Indonesia. They measured how long the algorithm took and how much memory it used on an Android device, repeating each measurement many times so that a single slow run could not distort the result.
The result matters because the same trade-off shows up everywhere. Routing libraries are tuned for servers with plenty of headroom, while phones have far less. Anything that shrinks the input before the search begins buys performance without touching the parts of the system that already work.
Muhammad Yasir Anshari Haq, Riswan Septriayadi Sianturi, and Aryo Pinandito (2023). Enhancing the Efficiency of Navigation Systems: Dijkstra Algorithm Optimization Through Integration of Douglas-Peucker Line Simplification Technique. Proceedings of the 8th International Conference on Sustainable Information Engineering and Technology.
For anyone building transit or delivery apps, the lesson is cheap to apply. Simplify the line geometry before you search it. The picture on screen stays the same, and the device has less work to do on every single request.
