## PENERAPAN PEWARNAAN GRAF MENGGUNAKAN ALGORITMA WELCH-POWELL UNTUK KEEFEKTIFAN PENGATURAN TRAFFIC

## LIGHT DI SIMPANG MAJESTIK
Faridawaty Marpaung*) Surel: farida2008.unim@gmail.com

## ABSTRACT
The  research  method  includes  several  stages,  namely  data  retrieval from DISHUBKOMINFO, namely the red and green light duration data at  the  Majestik  intersection,  transforming  the  intersection  with  the current into a graph, coloring each node in the graph using the Welch- Powell algorithm. Based on the calculation of the level of effectiveness of the total duration of the secondary data traffic arrangement with the new data at the Majestik intersection, it can be seen that at the interval of  15.00  -  20.00  the  effectiveness  of  the  green  light  duration  increases by  6.81%  and  the  red  light  duration  decreases  by  26.01%  vehicle concentration is low.
Keywords: Traffic Light, Graph Coloring, Welch – Powell

## PENDAHULUAN
Masalah  transportasi  secara umum dan lalu lintas pada khususnya merupakan  fenomena  yang  terlihat sehari- hari dalam kehidupan manusia, Jika peningkatan perjalanan ini  tidak  diikuti  dengan  peningkatan prasarana transportasi yang memadai maka akan terjadi suatu ketidakseimbangan antara permintaan ( demand ) dan
penyediaan  ( supply )  yang  akhirnya
akan  menimbulkan  suatu  ketidak- lancaran dalam mobilitas yang berupa kemacetan (Nugroho 2008).Kemacetan timbul karena adanya  konflik  pergerakan  yang  ada di persimpangan dan untuk mengurangi konflik ini  banyak dilakukan pengaturan untuk mengoptimalkan persimpangan dengan  menggunakan  lampu  lalu lintas ( traffic light ).
*) Fridawaty Marpaung,S.Si., M.Si., Dosen Jurusan Matematika FMIPA UNIMED
Kemacetan  lalu  lintas  adalah masalah  yang  menakutkan  yang dapat mempengaruhi kehidupan
sehari-hari  dari  miliaran  orang  di seluruh dunia.(Rusheng Zhang, 2018). Pendeteksian lampu lalu lintas adalah  hal  yang  penting  dalam lingkungan perkotaan selama transisi ke  mengemudi  sepenuhnya  otonom. Banyak  literatur  telah  dihasilkan dalam beberapa tahun terakhir mendekati pola yang berbeda strategi pengenalan.  (Danang  dkk,  2016). Sistem  kontrol  lampu  lalu  lintas banyak  digunakan  untuk  memantau dan  mengendalikan  aliran  mobil melalui persimpangan jalan,yang
bertujuan untuk mewujudkan gerakan  lambat  mobil  di  rute transportasi.  Namun,  sinkronisasi sistem lampu lalu lintas di
persimpangan yang berdekatan
merupakan hal yang rumit,
mengingat masalah
berbagai parameter  yang  terlibat.  Sistem konvensional  yang  tidak  menangani aliran  variabel yang  mendekati persimpangan.
Lalu  lintas  adalah  masalah utama  yang  dihadapi  setiap  negara karena peningkatan jumlah
kendaraan di seluruh dunia, khususnya di daerah perkotaan besar.
Oleh  karena  itu  kebutuhan  muncul untuk memaksimalkan dan mengoptimalkan  algoritma  control lalu  lintas  menjadi  lebih  baik mengakomodasi peningkatan permintaan.  (Javed  Alam,  2013). Lampu lalu lintas menandakan waktu kendaraan harus berjalan dan berhenti secara bergantian dari berbagai  arah. Ada beberapa ditemui lampu  lalu  lintas  dengan  durasi lampu  merah  yang  lama  dan  durasi lampu  hijau  yang  singkat.  Hal  ini menimbulkan antrian yang menumpuk  sehingga  sering  terjadi kemacetan,  misalnya  pada  simpang majestik. Oleh karena itu dibutuhkan pengoptimalisasi  pengaturan  lampu lalu lintas.
Teori  graf  merupakan  pokok bahasan  yang  mempunyai  manfaat besar dalam kehidupan sehari – hari. Salah  satu  bagian  dari  teori  graf adalah  pewarnaan  graf.  Ada  tiga macam pewarnaan graf, yaitu pewarnaan  simpul,  pewarnaan  sisi, dan  pewarnaan  wilayah  ( region ). Fungsi pewarnaan graf pada penelitian ini adalah untuk
menentukan  arus  mana  saja  yang dapat berjalan bersamaan atau tidak . Di  dalam  persoalan  pewarnaan  graf tidak hanya sekedar mewarnai simpul  –  simpul  dengan  warna  yang berbeda dari warna simpul tetangganya saja. Namun juga mengingatkan  jumlah  warna  yang digunakan  untuk  mewarnai  simpul disebut  bilangan  kromatik  graf G (As’ad 2008).
Algoritma
yang diimplementasikan  di  penelitian  ini adalah  Algoritma  Welch  –  Powell yang    digunakan  untuk  mengatur pergantian  nyala  lampu  hijau  dan merah, sehingga tidak terjadi tabrakan  kendaraan  dari  empat  arah maupun tiga arah. Algoritma Welch- Powell  merupakan  salah  satu  teknik pewarnaan  dari  graf yang digunakan untuk  mewarnai  simpul  suatu  graf berdasarkan  derajat  tertinggi  dari simpul-simpulnya. Algoritma Welch- Powell  tidak  selalu  memberikan jumlah warna minimum yang diperlukan  untuk  mewarnai  graf, tetapi  algortima  ini  cukup  praktis untuk  digunakan  dalam  pewarnaan simpul sebuah graf. Algoritma
Welch- Powell hanya cocok
digunakan  untuk  graf  dengan  orde yang kecil. (As’ad 2008)
Permasalahan  yang  diangkat dalam penelitian ini adalah Bagaimana  penerapan  pewarnaan graf menggunakan
Algoritma Welch-  Powell untuk  efektifitas pengaturan traffic  light di  simpang Majestik.

## METODE PENELITIAN
Metode  penelitian  yang  dilakukan dalam penelitian ini meliputi beberapa  tahap  yaitu  studi  pustaka, pengumpulan  data,  pengolahan  data, dan penarikan kesimpulan.
Adapun langkah-langkah yang digunakan  dalam  penelitian  ini adalah:
1. Mengumpulkan  data  sekunder dari  Dinas  Perhubungan  kota Medan  tahun  2018  yaitu  data durasi lampu merah, kuning dan hijau  menyala  pada  simpang Majestik dan Glugur
2. Mentransformasikan persimpangan jalan beserta arusnya ke bentuk  graf . Simpul merepresentasikan arus dan garis  merepresentasikan  arus arus  yang  tidak  boleh  berjalan
bersamaan,  yang  selanjutnya simpul  –  simpul  tersebut  saling dihubungkan.
3. Mewarnai  setiap  simpul  pada graf dengan menggunakan
Algoritma  Welch  –  Powell. Selain  untuk  mengetahui  arus mana  saja  yang  dapat  berjalan bersamaan, diperoleh juga
jumlah bilangan kromatik.
4. Menentukan
alternative
penyelesaian  durasi  lampu  hijau dan  lampu  merah  menyala dengan  siklus  tertentu.  Hal  ini dapat dilakukan dengan membagi satu siklus yang terdiri
dari  total  durasi  lampu  merah dan lampu hijau menyala
dengan  bilangan  kromatik  yang telah diperoleh, hasil pembagiannya menunjukkan
durasi  lampu  hijau  menyala. Adapun  durasi  siklus  waktu pada  setiap  persimpangan  yang diteliti merujuk pada data sekunder dari Dinas Perhubungan  kota  Medan  tahun 2018 5. Menarik kesimpulan HASIL DAN PEMBAHASAN
Permasalahan ini dapat  dikaji pengaturannya  menggunakan  prinsip pewarnaan simpul. Algoritma penyelesaian  pengaturan traffic  light di persimpangan jalan adalah sebagai berikut (1) Mentransformasikan persimpangan  jalan  beserta  arusnya ke bentuk graf.
Simpul merepresentasikan  arus  dan  garis merepresentasikan  arus-arus  yang tidak  boleh  berjalan  bersamaan,  (2) Mewarnai  setiap  simpul  pada  graf dengan menggunakan algoritma Recursive  Large  First.  Penggunaan algoritma  untuk  mengetahui  arus mana  saja yang  bisa  berjalan bersamaan  dan  jumlah  bilangan kromatik  yang  dapat  digunakan untuk langkah berikutnya, (3) Menentukan  alternatif  penyelesaian durasi lampu hijau dan lampu merah menyala.  Hal  ini  dapat  dilakukan dengan  membagi  durasi  lampu  hijau dengan  bilangan  kromatik,  hasil pembagiannya  menunjukkan  durasi lampu  hijau  menyala  baru.  Langkah selanjutnya adalah menghitung tingkat  keefektivitasan  data  baru dibanding  data  primer.  Berikut  akan dipaparkan penyelesaian kasus
pengaturan traffic light
pada
beberapa persimpangan di Medan Simpang Majestik
Gambar 1.Sistem arus lalu lintas persimpangan Majestik
Keterangan :
𝑣 1 = arus  dari  Guru  Patimpus menuju Kapt.Maulana Lubis 𝑣 2 = arus  dari  Guru  Patimpus menuju Gatot Subroto
𝑣 3 = arus  dari  Guru  Patimpus menuju Adam Malik
𝑣 4 = arus  dari  Adam  Malik  menuju Kapt Maulana Lubis
𝑣 5 = arus  dari  Adam  Malik  menuju Gatot Subroto
𝑣 6 = arus  dari  Gatot  Subroto menuju Adam Malik
𝑣 7 = arus dari Gatot subroto menuju
Kapt Maulana Lubis
Arus – arus yang tidak boleh berjalan bersamaan adalah :
- Arus 𝑣 1 tidak boleh berjalan bersamaan dengan 𝑣 4 , 𝑣 5 , 𝑣 7
- Arus 𝑣 2 tidak boleh berjalan bersamaan dengan 𝑣 4 , 𝑣 5 , 𝑣 7
- Arus 𝑣 3 tidak boleh berjalan
bersamaan dengan 𝑣 4 , 𝑣 5 , 𝑣 7
- Arus 𝑣 4 tidak boleh berjalan
bersamaan dengan 𝑣 1 , 𝑣 2 , 𝑣 3 , 𝑣 7
- Arus 𝑣 5 tidak boleh berjalan
bersamaan dengan 𝑣 1 , 𝑣 2 , 𝑣 3 , 𝑣 7
- Arus 𝑣 7 tidak boleh berjalan bersamaan dengan
𝑣 1 , 𝑣 2 , 𝑣 3 , 𝑣 4 , 𝑣 5
Data traffic light di simpang Majestik sebagai berikut
Tabel 1. Tabel data sekunder simpang  Majestik
Waktu Nama Jalan Pengaturan traffic light Total Merah (detik) Kuning (detik ) Hijau (detik) 05.00 – 09.00 Gatot Subroto 153 4 50 207 Adam Malik 133 4 70 207 Guru Patimpus 128 4 75 207 Total 414 12 195 621 09.00 – 15.00 Gatot Subroto 160 5 45 210 Adam Malik 140 5 65 210 Guru Patimpus 120 5 85 210 Total 420 15 195 630 15.00 – 20.00 Gatot Subroto 180 5 50 235 Adam Malik 145 5 85 235 Guru Patimpus 145 5 85 235 Total 615 15 220 705 20.00 – 24.00 Gatot Subroto 155 5 45 205 Adam Malik 135 5 65 205 Guru Patimpus 120 5 80 205 Total 410 15 190 615

## Transformasi dalam bentuk  graph
Transformasi  graf  di  atas terlihat  simpul 𝑣 6 tidak  saling
terhubung dengan simpul  lain ,  yang berarti  dapat  langsung  beriringan dengan  arus  lain.  Selanjutnya  untuk simpul  yang  lain  diberi  warna dengan  algoritma  Recursive  Large
First. Dari pewarnaan graph diperoleh bilangan kromatikya = 3 Dengan melakukan pembagian bilangan kromatik Berdasarkan dan algoritma Recursive Large First maka
diperoleh  durasi  lampu  lalu  lintas yang baru di simpang Majestik Tabel 2. Data Baru Traffic Light Simpang Majestik
Waktu Nama Jalan Pengaturan traffic light
Total Merah (detik) Kuning (detik ) Hijau (detik) 05.00 – 09.00 Gatot Subroto 138 4 65 207 Adam Malik 138 4 65 207 Guru Patimpus 138 4 65 207 Total 414 12 195 621 09.00 – 15.00 Gatot Subroto 140 5 65 210 Adam Malik 140 5 65 210 Guru Patimpus 140 5 65 210 Total 420 15 195 630 15.00 – 20.00 Gatot Subroto 151,67 5 78,33 235 Adam Malik 151,67 5 78,33 235 Guru Patimpus 151,67 5 78,33 235 Total 455,01 15 234,99 705
20.00 – 24.00 Gatot Subroto 136,67 5 63,33 205 Adam Malik 136,67 5 63,33 205 Guru Patimpus 136,67 5 63,33 205 Total 410,01 15 189,99 615
Menghitung  tingkat  keefektifitas  durasi traffic  light pada  simpang Majestik dengan membandingkan data primer dengan data baru.
Tabel 3. Tingkat keefektivitas durasi traffic light simpang Majestik Interval Waktu Lampu Tingkat keefektifitasan 05.00 – 09.00 Hijau 0 Merah 0 09.00 – 15.00 Hijau 0 Merah 0 15.00 – 20.00 Hijau 6,81% Merah -26,01% 20.00 – 24.00 Hijau -0,005% Merah 0,002%

## SIMPULAN
Berdasarkan hasil anaisis dan pembahasan dapat diambil  simpulan  bahwa  penerapan graf pada persimpangan menggunakan  algoritma  Recursive Large First untuk optimalisasi
pengaturan traffic  light yaitu  dengan cara (1) Mentransformasikan
persimpangan  jalan  beserta  arusnya ke  bentuk  graf,  (2)  Mewarnai  setiap simpul pada graf dengan menggunakan  Algoritma  Recursive Large First, (3) Menentukan alternative penyelesaian durasi
lampu  hijau  dan  lampu  merah menyala,  (4)  Menghitung  tingkat keefektifitasan  durasi  total traffic light .  Berdasarkan  perhitungan tingkat  keeektifitasan  durasi  total pengaturan  lalu  lintas  data  sekunder dengan data baru pada persimpangan Majestik terlihat bahwa pada interval waktu  15.00  –  20.00  menghasilkan tingkat  efektifitas  pada  durasi  lampu hijau  bertambah  sebesar  6,81%  dan durasi lampu merah berkurang sebesar  26,01%    yang  mengaki- batkan konsentrasi kendaraan menjadi  rendah.  Untuk  interval waktu yang lain tingkat keefektifitasannya  tidak  lebih  baik
dari  data  sekunder  karena  sudah memiliki  perhitungan  paling  efektif yang dibuat oleh DISHUBKOMINFO kota Medan.

## DAFTAR PUSTAKA
Asad, N., (2008): Aplikasi Pewarnaan Graf Pada Pemecahan Masalah Penyusunan Jadwal.
Chartrand, G., dan P., Z., (2009):
Chromatic Graph Teory , Series Editor KENNETH H. ROSEN, CRC Press, New York.
Danang  ,  Amin  Suyitno  dan  Riza (2016) : Penerapan Graf  Pada Persimpangan  Menggunakan algoritma  Welch  Powel  untuk
Optimalisasi Pengaturan TRAFFIC  LIGHT , UNNES Journal of Mathematics
Javed  alam,  Prof.  (Dr.)  M.  K.
Pandey,  Husain  Ahmed  (2013) Intellegent Traffic Light
Control  System  for  Isolated
Intersection Using  Fuzzy Logic
(Conference Paper) ·
Nuggroho,  A.  D.  2008.  Analisis
Penerapan Belok Kiri
Langsung  Terhadap  Tundaan
Lalu  Lintas  pada  Pendekatan
Persimpangan  Bersinyal.  Tesis Semarang:  Program  Magister
Teknik Sipil Universitas Diponegoro. Purnamasari,  D.,  Ilman,  M.  Z.,  dan Wulandari, D., (2012): Algoritma Welch-Powell untuk  Pengendalian  Lampu Lalu Lintas, Universitas
Gunadarma , 6 (03), 1–7.
Rusheng  Zhang  ,  Frank  Schmutz  ,
Kyle Gerard , Aur´elien Pomini
,  Louis  Basseto  ,  Sami  Ben
Hassen  ,  Akihiro  Ishikawa  ,
Inci  Ozgunes  ,  and  Ozan Tonguz  (2018) Virtual  Traffic
Lights:  System Design  and
Implementation (Conference
Paper).