Improving Route-Finding Performance of Dijkstra Algorithm and Maintaining Path Visual Cue Using Douglas-Peucker Algorithm

Aryo Pinandito · Agi Putra Kharisma · Muhammad Aminul Akbar

6 citations0/0 files storedInternational Conference on Sustainable Information Engineering and Technology (SIET)

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Transportation Planning and Optimization Geographic Information Systems Studies Complexity and Algorithms in Graphs

Abstract

Smartphones and their mobile applications have become an inseparable part of modern daily life. One of them is a public transportation app that helps people commute with public transportation. Many public transportation service providers have mobile applications as a companion for their customers to improve their quality of service. The application provides useful information and/or important features regarding their service, such as timetables or route finding for public transit. Such features run a slow algorithm to provide real-time or time-based information to the users. Dijkstra is one example of an algorithm that allows users to find the shortest path from one location to another in a public transit network. However, Dijkstra is categorized as a greedy algorithm because it looks at all possible solutions. It takes longer for Dijkstra to find the optimum solution when the number of points in a network graph is high. This study attempted to improve the overall route-finding processing time and reduce the memory footprint while keeping the visual cue of a route path reasonably consistent by utilizing Douglas-Peucker line simplification algorithm to simplify the path and reduce the number of points that Dijkstra algorithm processes. The result suggested that Douglas-Peucker simplification process took 0.5% additional memory footprint and put 5.13% additional processing time into the overall route-finding processing time. However, it reduces the overall memory footprint and processing time by 72.56% and 80.83%, respectively. The result conveyed a significant improvement in the practical implementation of Douglas-Peucker algorithm to reduce the input for the Dijkstra algorithm in finding the optimal route, thereby improving the overall route-finding performance.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 6 citations exist upstream.

References

2017Public transport route planning: Modified dijkstra's algorithm 2019Combining ITS and optimization in public transportation planning: state of the art and future research paths 2021Customer requirements for urban public transport mobile application 2022Dijkstra’s Shortest Path Algorithm and Its Application on Bus Routing 2022Graph Database-modelled Public Transportation Data for Geographic Insight Web Application

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.