APPLICATION OF GRAPH COLORING IN OPTIMIZING TRAFFIC LIGHT DURATION USING THE WELCH-POWELL ALGORITHM (CASE STUDY: SIMPANG EMPAT KAYU MAS KM 3 DAN SIMPANG TIGA YABIS KOTA BONTANG)

Authors

  • Amalia Rachmawati Universitas Mulawarman
  • Fidia Deny Tisna Amijaya Universitas Mulawarman
  • Qonita Qurrota A’yun Universitas Mulawarman

DOI:

https://doi.org/10.26418/gr.v2i2.82177

Keywords:

Welch-Powell algorithm, traffic lights, vertex coloring

Abstract

Traffic refers to the arrangement of traffic lights at road intersections to regulate vehicle flow. Traffic congestion is a frequent issue in various cities, including Bontang city. This congestion often occurs at several intersections such as Simpang Empat Kayu Mas KM 3 and Simpang Tiga Yabis in Bontang. There are many traffic lights with short green light duration and long red light duration. This study aims to optimize traffic light durations at Simpang Empat Kayu Mas KM 3 and Simpang Tiga Yabis using the Welch-Powell algorithm. Welch-Powell is a graph coloring algorithm based on largest degree. Secondary data obtained from the Transportation Department of Bontang City, including road segments, vehicle directions, red and green light durations. Based on calculations results, using the Welch-Powell algorithm for vertex coloring a chromatic number of 4 was obtained for the Simpang Empat Kayu Mas KM 3 graph, and a chromatic number of 3 was obtained for the Simpang Tiga Yabis graph. The effectiveness level revealed a 3.053% decrease in red light and a 10.435% increase in green light at Simpang Empat Kayu Mas KM 3. At Simpang Tiga Yabis, there was a 13.043% decrease in red light and a 42.857% increase in green light.

References

Abdullah, M. D., & Rahadjeng, B. (2022). Aplikasi Pewarnaan Titik pada Graf untuk Optimalisasi Durasi Lampu Lalu Lintas di Simpang Jalan Jemursari Kota Surabaya. MATHunesa: Jurnal Ilmiah Matematika, 10(2), 289–298. https://doi.org/10.26740/mathunesa.v10n2.p289-298

Amirah (2019). Aplikasi Pewarnaan Titik menggunakan Algoritma Welch-Powell pada Pengaturan Traffic Light (Skripsi). Universitas Lampung.

Budayasa, I. K. (2007). Teori Graph dan Aplikasinya. Unesa University Press.

Daniel, F., & Taneo, P. N. L. (2019).Teori Graf. Deepublish.

Devi, Jessica Fitriana. (2023).Optimasi Pengaturan Lampu Lalu Lintas dengan Menggunakan Metode Webster (Skripsi). Universitas Mulawarman.

Hapsari, M. I., & Sastrodiningrat, T. (2022). Kajian Rekayasa Lalu Lintas Persimpangan Jalan Pahlawan Kota Bandung. Prosiding FTSP Series, 98–104.

Maarif, S. (2017). Aplikasi Pewarnaan Titik pada Graph dalam Pembuatan Jadwal Pelajaran. Pi: Mathematics Education Journal, 1(1), 22–26. https://doi.org/10.21067/pmej.v1i1.2001

Miftahurrahmah. (2016). Aplikasi Teori Graf dalam Pengaturan Lampu Lalu Lintas (Skripsi). Universitas Islam Negeri Alauddin Makassar.

Munir, R. (2016). Matematika Diskrit (6th ed.). Bandung: Informatika Bandung.

Poernamasari, I., Tumilaar, R., & Montolalu, C. E. J. C. (2019). Aplikasi Optimasi Pengaturan Lampu Lalu Lintas dengan menggunakan Metode Webster (Studi Kasus Persimpangan Jalan Babe Palar). D’Cartesian Jurnal Matematika Dan Aplikasi.

Putri, B. A. (2017). Aplikasi Pewarnaan Titik Sejati pada Pengaturan Lampu Lalu Lintas (Skripsi). Universitas Snata Dharma Yogyakarta.

Qomaruddin, M., Bismi, W., & Hariyanto, D. (2022). Pewarnaan Graf Pada Peta Provinsi Jawa Barat Menggunakan Algoritma Welch-Powell. Jurnal Sistem Dan Teknologi Informasi (JustIN), 10(2), 258. https://doi.org/10.26418/justin.v10i2.53829

Runtunuwu, Y. I., Mananohas, M. L., & Montolalu, C. E. (2021). Derajat Laplacian dari Graf Lengkap, Graf Bipartisi Komplit, Graf Matahari dan Graf yang memiliki n-1 Derajat berbeda. d’CARTESIAN: Jurnal Matematika dan Aplikasi, 10(1), 15-23. https://ejournal.unsrat.ac.id/index.php/decartesian

Sari, N., & Saleh, K. (2022). Tinjauan Yuridis Penerapan Sanksi Pidana pada Kecelakaan Lalu Lintas Yang Menyebabkan Korban Jiwa Menurut Pasal 310 Undang-Undang Nomor 22 Tahun 2009 Tentang Lalu Lintas dan Angkutan Jalan. Jurnal Politik Dan Pemerintahan Daerah, 4(2), 282-292.

Sari, R. F., Cipta, H., & Munthe, E. F. (2022). Implementasi Algoritma Welch-Powell Terhadap Pengaturan Lalu Lintas Persimpangan Jalan Dalam Mengatasi Kemacetan. Jurnal Lebesgue: Jurnal Ilmiah Pendidikan Matematika, Matematika Dan Statistika, 3(3), 576–583. https://doi.org/10.46306/lb.v3i3.173

Wiladi, M., Wasono, W., Asmaidi, A. (2023). Penerapan Algoritma Dijkstra dan Algoritma Greedy Pada Optimasi Jalur Evakuasi Banjir. Basis: Jurnal Ilmiah Matematika, 2(1), 25-38.

Yusuf, R., Dewi, F. P., Firmansyah, & Mujib, A. (2022). Generalisasi Bilangan Kromatik Pada Beberapa Kelas Graf Korona. Jurnal Derivat: Jurnal Matematika Dan Pendidikan Matematika, 9(2), 192–201. https://doi.org/10.31316/jderivat.v9i2.3780

Downloads

Published

2024-10-01

Issue

Vol. 2 No. 2 (2024)

Section

Articles

License

  1. GEOREFERENCE: Jurnal Kajian Ilmu dan Pembelajaran Geografi  menerima artikel  dengan cakupan hasil penelitian dan kajian literatur (literature review) dalam bidang: 1) Pendidikan dan Pembelajaran Geografi; 2) Pengelolaan Lingkungan; 3) Kebencanaan; 4) Kependudukan; 5) Perencanaan dan Pengembangan Wilayah; dan 6) Penerapan Sistem Informasi Geografi dan Penginderaan Jauh.    
  2. Naskah diketik dengan program  Ms. Word, huruf  Garamond,  font size  12, menggunakan kertas A4 dengan batas atas 2,44 cm, kiri 2 cm, kanan 2 cm, dan bawah 2 cm.
  3. Naskah dikirim (submit) secara online melalui OJS GEOREFERENCE: Jurnal Kajian Ilmu dan Pendidikan Geografi di  https://jurnal.untan.ac.id/index.php/georeference
  4. Artikel ditulis dalam bahasa Indonesia. Jarak antar baris 1 spasi. Tiap awal paragraf menjorok ke kanan sekitar 10 ketukan.
  5. Sistematika artikel hasil penelitian: Judul, Identitas Penulis (Nama, Afiliasi, dan Email), Abstrak  disertai  Kata Kunci, Pendahuluan, Metode Penelitian, Temuan dan Pembahasan, Simpulan, Rekomendasi, Ucapan Terima Kasih  dan  Reference.
  6. Judul Artikel  tidak lebih dari 15 kata, diketik dengan huruf kapital di tengah-tengah (center), dengan ukuran huruf 14 pt, dan ditulis tebal (bold).
  7. Identitas  penulis  ditempatkan di bawah judul artikel, nama penulis ditulis tebal (bold) tanpa gelar akademik, disertai nama lembaga asal, dan dicantumkan juga  email  penulis.
  8. Abstrak dan kata kunci.  Abstrak berisi: permasalahan, tujuan, metode, temuan dan simpulan. Abstrak ditulis dalam bahasa Indonesia dan Inggris. Untuk abstrak berbahasa Inggris ditulis dengan format yang sama dengan bahasa Indonesia namun ditulis dengan cetak miring. Panjang masing-masing abstrak antara 150-200 kata dan kata kunci minimal 3 kata atau frasa, serta diketik dalam 1 spasi.
  9. Pendahuluan  berisi latar belakang, tujuan penelitian, dan kajian pustaka. Semua bagian pada pendahuluan ini dipaparkan secara terintegrasi dan menggunakan aturan penomoran yang benar.
  10. Metode Penelitian  berisi rancangan penelitian, sumber data, teknik pengumpulan data, dan teknik analisis data. Semua bagian ini dipaparkan secara terintegrasi dalam bentuk paragraf-paragraf.
  11. Temuan dan pembahasan  berisi paparan temuan hasil penelitian disertai dengan pembahasan mengenai hasil penelitian tersebut. Semua bagian ini dipaparkan secara terintegrasi dalam bentuk paragraf-paragraf.
  12. Simpulan  berisi simpulan penelitian dalam menjawab pertanyaan penelitian dan dibuat dalam bentuk paragraf.
  13. Penggunaan format in note dalam kutipan;  dengan aturan (Nama belakang, tahun terbit), misal: (Moleong, 2010)
  14. Daftar Pustaka  memuat referensi yang dirujuk dalam artikel dan diurutkan berdasarkan   alfabet. Pustaka yang digunakan berupa pustaka 10 tahun terakhir. Jenis pustaka yang digunakan minimal 80% bersumber dari jurnal nasional maupun internasional. Sumber rujukan yang disitasi minimal bejumlah 15 rujukan. Penulisan daftar pustaka mengikuti aturan  APA Style.
  15. Pengutipan, tabel, dan gambar mengikuti aturan  APA Style.
  16. Menggunakan  Reference Manager  dalam mengelola referensi dan         pengutipan seperti Mendeley, EndNote, dan lain-lain.
  17. Artikel ditulis mengikuti  template penulisan artikel GEOREFERENCE
  18. Menghindari duplikasi, pabrikasi, falsifikasi, dan plagiarisme.
  19. Penulis melampirkan  Surat Pernyataan Etika  pada tahap ke-4       proses submit artikel.
  20. Segala sesuatu yang terkait dengan perizinan pengutipan atau yang         lainnya yang terkait dengan HaKI yang dilakukan oleh penulis,     termasuk konsekuensi hukum yang mungkin muncul karenya, adalah       menjadi tanggung jawab penuh penulis.