Implementation of Dijkstra Algorithm and Welch-Powell Algorithm for Optimal Solution of Campus Bus Transportation

Authors

  • Nurwan Nurwan Universitas Negeri Gorontalo, Gorontalo, Indonesia
  • Widya Eka Pranata Universitas Negeri Gorontalo, Gorontalo, Indonesia
  • Muhamad Rezky Friesta Payu Universitas Negeri Gorontalo, Gorontalo, Indonesia
  • Nisky Imansyah Yahya Universitas Negeri Gorontalo, Gorontalo, Indonesia

DOI:

https://doi.org/10.15642/mantik.2021.7.1.31-40

Keywords:

Shortest route, Optimal schedule, Dijkstra algorithm, Welch-Powell algorithm

Abstract

This research deals with applying the Dijkstra algorithm and Welch-Powell algorithm to on-campus bus transportation problems. This research aims to determine the optimal solution of campus bus transportation routes in the shortest routes and schedules. In determining the fastest way, each intersection represented as a node, and the path described as the sides. The shortest path obtained    V1 - V2 - V5 - V8 - V9 - V10 - V13 - V16.  In determining the optimal schedule, the number of buses represents the vertices, and the time expresses the side that connects each node. The optimal program of the bus starts from 06.30 am to 5.00 pm. Every bus gets four sessions of departure and four sessions return with travel time each session is 60 minutes.

Downloads

Download data is not yet available.

References

A. Y. Harsya and I. H. Agustin, “Pewarnaan Titik Pada Operasi Graf Sikel dengan Graf Lintasan Pendahuluan Teorema yang Digunakan,” in Journal University Of Jember, 2014, vol. 1, no. 1.

M. S. Yusuf, H. M. Az-zahra, and D. H. Apriyanti, “Implementasi Algoritma Dijkstra Dalam Menemukan Jarak Terdekat Dari Lokasi Pengguna Ke Tanaman Yang Di Tuju Berbasis Android ( Studi Kasus di Kebun Raya Purwodadi ),” J. Pengemb. Teknol. Inf. dan Ilmu Komput., vol. 1, no. 12, pp. 1779–1781, 2017.

Siswanto, Algoritma dan Struktur Data Non Linear dengan Java. Yogyakarta: Graha Ilmu, 2011.

A. Pitri, “Penerapan Metode Djikstra Pencarian Rute Terpendek Sekolah Luar Biasa ( SLB ) di Kota Medan,” J. Ris. Komput., vol. 5, no. 6, pp. 638–643, 2018.

P. Sembiring, A. S. Harahap, and K. S. Zalukhu, “Implementation of Dijkstra’s algorithm to find an effective route to avoid traffic jam on a busy hour,” J. Phys. Conf. Ser., vol. 1116, no. 2, 2018.

S. Maimunah, Ni’matuzahroh, S. Prasetyaningrum, and B. I. Suwandayani, “Implementasi Model Pendidikan Inklusi di Sekolah Dasar Kota Batu,” J. Pendidik. Surya Edukasi, vol. 4, no. 2, 2018.

T. Jimeng, S. Quanxin, and C. Zhijie, “A New Implementation of Dijkstra ’ s Algorithm on Urban Rail Transit Network,” 2016, no. Iccte, pp. 507–513.

I. P. W. Gautama and K. Hermanto, “Penentuan Rute Terpendek dengan Menggunakan Algoritma Dijkstra pada Jalur Bus Sekolah,” J. Mat., vol. 10, no. 2, p. 116, 2020.

M. Kubale, Graph Colorings. America: AMS Bookstore.

R. Diestel, Graph Theory, Electronic. New York: Springer-Verleg, 2000.

R. Munir, Matematika diskrit. Bandung: Informatika, 2012.

A. W. Bustan and M. R. Salim, “Implementation of Graph Colouring Using Welch-Powell Algorithm to Determine Student Mentoring Schedule,” THEOREMS (The Orig. Res. Math., vol. 4, no. 1, pp. 79–86, 2019.

U. M. Rifanti, “Pemilihan Rute Terbaik Menggunakan Algoritma Dijkstra Untuk Mengurangi Kemacetan Lalu Lintas di Purwokerto,” JMPM J. Mat. dan Pendidik. Mat., vol. 2, no. 2, p. 90, 2017.

M. K. Harahap and N. Khairina, “Pencarian Jalur Terpendek dengan Algoritma Dijkstra,” SinkrOn, vol. 2, no. 2, p. 18, 2017.

D. Ardana and R. Saputra, “Penerapan Algoritma Dijkstra pada Aplikasi Pencarian Rute Bus Trans Semarang,” in Seminar Nasional Ilmu Komputer (SNIK 2016), 2016, no. 978-602-1034-40–8, pp. 299–306.

I. Budayasa, Teori Graph dan Aplikasinya. Surabaya: Unesa University Press, 2007.

E. A. Sarwoko, “Perancangan Arsitektur Pemaralelan Untuk Mencari Shortest Path Dengan Algoritma Dijkstra,” Matematika, vol. 6, no. 3, pp. 137–143, 2003.

Y. Rusdiana and A. Maulani, “Algoritma Welch-Powell Untuk Pewarnaan Graf pada Penjadwalan Perkuliahan,” Sci. Phys. Educ. J., vol. 3, no. 1, pp. 37–47, 2019.

G. Chartrand, L. Lesniak, and P. Zhang, Graphs and Digraphs. California: Pacific Grove California, 2016.

R. Balakrishnan and K. Ranganathan, A Textbook of Graph Theory, Second Edi. Springer Science+Business Media New York, 2021.

A. M. Soimah and N. S. M. Mussafi, “Pewarnaan Simpul Dengan Algoritma Welch-Powell Pada Traffic Light Di Yogyakarta,” J. Fourier, vol. 2, no. 2, p. 73, 2013.

Downloads

Published

2021-05-31

How to Cite

Nurwan, N., Pranata, W. E., Payu, M. R. F., & Yahya, N. I. (2021). Implementation of Dijkstra Algorithm and Welch-Powell Algorithm for Optimal Solution of Campus Bus Transportation. Jurnal Matematika MANTIK, 7(1), 31–40. https://doi.org/10.15642/mantik.2021.7.1.31-40