Determining Travel Time and Fastest Route Using Dijkstra Algorithm and Google Map

Suardinata Suardinata, Rusdisal Rusmi, Muhammad Amrin Lubis

Abstract


Dijkstra's algorithm is commonly used to determine the shortest route connecting a point as a starting node to another which acts as the end node. In this study, the UNP student dormitory acted as the starting node, while the library which is frequently visited by students was sampled from the campus as the end node. Due to the fact that students generally live around campus and move on foot, an alternative route is needed to determine the fastest travel time. Therefore, this study aims to determine the route with the fastest travel time from the start to the end of nodes using the Dijkstra algorithm, in comparison with the route displayed by Google Map. Data were obtained from Google Map, which showed the availability of many routes with the possibility of students taking the fastest travel time. The result showed that the fastest route using the Dijkstra algorithm and Google Map were 14 and 3 alternatives at 15 and 21 minutes intervals. Based on these data, it is concluded that the travel time through the fastest route obtained using the Dijkstra algorithm was 6 minutes faster than data found in the Google Map.


Full Text:

PDF

References


R. Bellman, “On a routing problem,” Tech. report, DTIC Doc., 1956.

T. J. M. and P. L. Frana, “An interview with Edsger W. Dijkstra,” Commun. ACM, vol. Vol. 53, N, pp. 41-47., 2010.

R. W. Floyd, “‘Algorithm 97: shortest path,’” Commun. ACM, vol. Vol. 5, No, p. 345., 1962.

D. B. Johnson, “Efficient algorithms for shortest paths in sparse networks.,” J. ACM, vol. Vol. 24, N, pp. 1–13, 1977.

Q. Abbas, Q. Hussain, T. Zia, and A. Mansoor, “Reduced solution set shortest path problem: Capton algoritm with special reference to Dijkstra’s algorithm,” Malaysian J. Comput. Sci., vol. 31, no. 3, pp. 175–187, 2018, doi: 10.22452/mjcs.vol31no3.1.

F. Ardiani, “Penentuan jarak terpendek dan waktu tempuh menggunakan algoritma Dijkstra dengan pemrograman berbasis objek.,” Skripsi Univ. Islam Negeri Sunan Kalijaga, 2011.

KBBI, “Kamus Besar Bahasa Indonesia,” 2019. .

Google, “Google Map,” 2019. .

L. Lutfi, “Permasalahan Dalam Penetapan Level Uang.” Univesitas Negeri Padang, Padang, p. 2, 2013.

D. Ardana and R. Saputra, “Penerapan Algoritma Dijkstra pada Aplikasi Pencarian Rute Bus Trans Semarang,” no. Snik, pp. 299–306, 2016.

L. Joni, E. Dewi, and T. Lot, “Pencarian Rute Terpendek Tempat Wisata Di Bali Dengan Menggunakan Algoritma Dijkstra,” vol. 2010, no. Snati, pp. 2008–2011, 2010.

Y. Purwananto, D. Purwitasari, and W. A. Wibowo, “Implementasi dan Analisis Algoritma Pencarian Rute Terpendek di Kota Surabaya,” J. Penelit. dan …, vol. 10, no. 2, pp. 94–101, 2005.

B. F. Search and B. First, “Algoritma Branch _ And _ Bound Untuk Mencari Jarak Terpendek,” pp. 3–5, 2008.

D. A. N. Kuliner, M. Metode, D. Sekitar, and U. D. Nuswantoro, “Aplikasi pencarian rute gedung udinus, kos-kosan dan kuliner menggunakan metode dijkstra sekitar Universitas Dian Nuswantoro,” 2016.

G. Kumar, R. Kumar, and N. Gandotra, “Algorithm for Shortest Path Problem in a Network with Interval-valued Intuitionistic Trapezoidal Fuzzy Number,” vol. 70, pp. 123–129, 2015, doi: 10.1016/j.procs.2015.10.056.

R. Munir, Diktat Kuliah IF2251 Strategi Algoritmik. Departemen Teknik Informatika, Institut Teknologi Bandung, 2007.

W. Shu-xi, “Procedia Engineering The Improved Dijkstra ’ s Shortest Path Algorithm and Its Application,” vol. 29, pp. 1186–1190, 2012, doi: 10.1016/j.proeng.2012.01.110.

Y. Z. Chen, S. F. Shen, T. Chen, and R. Yang, “Path optimization study for vehicles evacuation based on Dijkstra algorithm,” Procedia Eng., vol. 71, pp. 159–165, 2014, doi: 10.1016/j.proeng.2014.04.023.

R. Munir, Matematika Diskrit. Bandung: Informatika, 2007.

J. J. Siang, Matematika Diskrit dan aplikasinya pada ilmu komputer. Yogyakarta: Andi, 2002.

U. S. R. Bondy, J.A. and Murty, Graph Theory With Applications. NorthHolland, New York: University of Waterloo, 1982.

“Geographic Information Technology Training Alliance (GITTA).” .




DOI: https://doi.org/10.32520/stmsi.v11i2.1836

Article Metrics

Abstract view : 121 times
PDF - 67 times

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.