Implementation of Dijkstra Algorithm and Welch-Powell Algorithm for Optimal Solution of Campus Bus Transportation
DOI:
https://doi.org/10.15642/mantik.2021.7.1.31-40Keywords:
Shortest route, Optimal schedule, Dijkstra algorithm, Welch-Powell algorithmAbstract
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
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
How to Cite
Issue
Section
License
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work