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)

Rachmawati, Amalia
Amijaya, Fidia Deny Tisna
A’yun, Qonita Qurrota

Georeference: Jurnal Kajian Ilmu dan Pembelajaran Geografi
Vol 2, No 2 (2024)

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.