Vol. 02, No. 01 (2020), pp. 1-6 p-ISSN 2656-6303 – e-ISSN 2656-9876 URL:http://journal.unirow.ac.id/index.php/mv
Bidang Penelitian : Optimasi Tanggal Masuk: 27-02-2020; Revisi: 12-03-2020 Diterima: 19-03-2020

## OPTIMASI WAKTU TUNGGU LAMPU LALU LINTAS PADA SIMPANG LIMA KRIAN-SIDOARJO MENGGUNAKAN ALGORITMA
WELCH-POWELL
Wika Dianita Utami 1* , Ahmad Naufal DS 2 , Putroue Keumala Intan 3 Program Studi Matematika UIN Sunan Ampel Surabaya 1,2,3 wikadianita@uinsby.ac.id1 * , naufaldzaky38@gmail.com 2 , putroue@uinsby.ac.id 3
Abstrak – Simpang Lima Krian-Sidoarjo merupakan simpang lima dengan arah tujuan adalah  Mojokerto, Wonoayu, Legundi, Pacet dan Sidoarjo  sehingga  pada simpang tersebut sering terjadi kemacetan. Sehingga membutuhkan beberapa solusi, salah satunya adalah optimasi waku tunggu lampu lalu lintas.  Simpang Lima Krian-Sidoarjo  dapat direpresentasikan dalam sebuah graf, dengan simpul menyatakan jalur yang dapat dilewati dalam persimpangan dan sisi menyatakan hubungan dua simpul yang saling melintas atau bersebrangan. Pada penelitian ini, digunakan metode pewarnaan graf yaitu pewarnaan simpul menggunakan Algoritma Welch-Powell  untuk menentukan durasi yang optimum pada waktu tunggu lampu lalu lintas di Simpang Lima Krian-Sidoarjo.  Berdasarkan hasil pewarnaan simpul  diperoleh  5 bilangan kromatik. Hasil optimasi waktu tunggu lampu lalu lintas yaitu durasi lampu merah pada ruas simpang arah Mojokerto  efektif jika mengalami penurunan dan tidak efektif jika  durasi pada lampu hijau bertambah,  durasi lampu merah pada ruas simpang arah Wonoayu, Legundi, Pacet, Sidoarjo tidak efektif jika mengalami kenaikan dan  efektif jika durasi pada lampu hijau mengalami penurunan.  Penyelesaian optimasi waktu tunggu lampu lalu lintas menggunakan pewarnaan simpul Algoritma  Welch-Powell  memberikan keefektifan hingga 13.63%.
Kata Kunci – Welch-Powell, Pewarnaan Graf, Lampu Lalu Lintas

## I. PENDAHULUAN
Alat transportasi  merupakan  kebutuhan manusia  untuk mendukung kegiatan sehari- hari. Semakin berkembangnya zaman, manusia lebih memilih menggunakan alat transportasi pribadi, seperti motor dan mobil,
untuk menunjang kegiatan sehari-hari. Selain itu, dengan didukung perkembangan teknologi  menyebabkan produksi kendaraan bermotor  diproduksi  secara  massal. Hal tersebut,  menyebabkan  jalanan dipadati oleh manusia dan kendaraan bermotor  sehingga jalanan rawan akan kemacetan.
Kemacetan,  khususnya di kota-kota besar di Indonesia,  menimbulkan adanya aturan pada lalu lintas, seperti halnya pengaturan waktu tunggu  lampu lalu lintas (yaitu waktu lampu merah dan lampu hijau) dan rambu- rambu di sekitar lampu lalu lintas. Pada saat ini beberapa lampu lintas pada persimpangan jalan  memiliki fitur lampu LED yang dapat menunjukan durasi waktu yang harus ditunggu.  Akan tetapi  meskipun  memiliki fitur lampu LED , terkadang durasi lampu lalu lintas yang telah diatur kurang optimal. Kasus yang sering terjadi pada durasi waktu tunggu lampu lalu lintas adalah durasi lampu merah yang lama dan lampu hijau yang singkat. Lamanya durasi lampu merah menyebabkan antrian kendaraan pada perseimpangan jalan.
Secara matematis, permasalahan terkait lalu lintas dapat diselesaikan dengan teori graf. Teori graf dapat merepresentasikan persimpangan jalan dalam bentuk graf. Simpul graf merepresentasikan jalur yang dapat dilewati dalam persimpangan. Sisi graf merepresentasikan  hubungan dua simpul yang saling melintas  atau bersebrangan. Penelitian  [1]  menggunakan graf kompatibel untuk menentukan waktu tunggu yang
optimal pada lampu lalu lintas I-Dinas Perhubungan dan LLAJ -  Jl. Ahmad Yani Surabaya. Penelitian [2], [3], [4] menggunakan  metode  pewarnaan  graf  yaitu pewarnaan simpul sebagai solusi untuk permasalahan lalu lintas.
Pada  [3] menggunakan Algoritma Welch- Powell untuk  menyelesaikan  pembuatan jalur angkot di Tasikmalaya. Pada [4] menggunakan Algoritma Welch-Powell untuk menyelesaikan permasalahan lalu lintas di Yogyakarta.  Pewarnaan  simpul dengan Algoritma Welch-Powell dapat diaplikasikan untuk menyelesaikan perhitungan  durasi  waktu  pada traffic light . Langkah  yang  ditempuh  yaitu dengan mentransformasi persimpangan  jalan beserta  arusnya ke  bentuk  graf.  Simpul merepresentasikan arus dan sisi merepresentasikan  arus-arus yang uncompatible . Selanjutnya mewarnai  simpul pada  graf  dengan Algoritma Welch-Powell untuk mengetahui  arus  yang  dapat  berjalan bersamaan dan memperoleh bilangan kromatik  yang berfungsi untuk menentukan alternatif penyelesaian durasi waktu traffic light .  Hasil yang diperoleh bahwa durasi waktu pada traffic light memberikan alternatif  hasil  yang  lebih  efektif  hingga 78.64% dengan 5 bilangan kromatik.
Simpang  Lima Krian-Sidoarjo merupakan simpang lima yang arah  tujuannya adalah Mojokerto,  Wonoayu,  Legundi,  Pacet dan Sidoarjo, serta  memiliki akses yang baik dalam  mendukung perekonomian wilayah Jawa Timur. Selain itu, fakta bahwa pada Simpang Lima  Krian-Sidoarjo  juga dilewati oleh kendaraan berat. Sehingga sering terjadi kemacetan pada Simpang Lima Krian- Sidoarjo.  Berdasarkan sumber data    dari Dinas  Perhubungan Provinsi Jawa Timur diperoleh bahwa volume lalu lintas tahun 2011 yang melintas adalah 8722 kendaraan setiap harinya sedangkan kapasitasnya hanya mampu menampung 5540 kendaraan  [9]. Ketidakmampuan simpang inilah yang akhirnya  menyebabkan antrian yang cukup panjang  dan  memerlukan penanganan penyelesaian permasalahan. Permasalahan sederhana yang dapat diselesaiakan adalah
terkait dengan waktu tunggu lampu lalu lintas.  Sehingga pada penelitian ini akan menggunakan Algoritma Welch-Powell untuk menentukan optimasi waktu tungu lalu lintas pada  Simpang  Lima  Krian-Sidoarjo.

## II. HASIL DAN PEMBAHASAN

## A. Pewarnaan Graf
Graf 𝐺 adalah pasangan himpunan ( 𝑉 , 𝐸 ), dimana 𝑉 adalah himpunan semua vertec atau  simpul  dan 𝐸 adalah himpunan semua edges atau  sisi  yang menghubungkan sepasang vertec .  Pewarnaan  pada  graf  ada  3 macam  yaitu pewarnaan simpul, pewarnaan sisi dan pewarnaan bidang [5].
a. Pewarnaan Simpul
Pewarnaan  simpul  adalah pemberian warna pada simpul-simpul  suatu graf sedemikian hingga tidak adanya dua simpul  yang terhubung langsung yang memiliki warna yang sama.
Gambar 1: Pewarnaan Simpul
b. Pewarnaan Sisi Pewarnaan sisi  pada suatu graf dapat dilakukan dengan memberi warna untuk suatu sisi- 𝑘 pada graf 𝐺 dengan sebagian warna dari 𝑘 maupun seluruh warna untuk mewarnai seluruh sisi dari  graf 𝐺 sehingga setiap pasang sisi memiliki simpul persekutuan yang memiliki warna yang berbeda-beda.
Gambar 2: Pewarnaan Sisi
c. Pewarnaan Bidang
Pewarnaan bidang adalah pewarnaan yang berfokus pewarnaannya terhadap bidang sehingga tidak ada bidang yang bertetanggaan memiliki warna yang sama. Pewarnaan pada bidang dapat dilakukan dengan cara mengubah graf menjadi graf planar terlebih dahulu sehingga dapat dilakukan pewarnaan pada bidang, graf planar dapat dikatakan sebagai graf yang digambarkan pada bidang datar dengan sisi-sisi yang tidak saling bersilangan.
Gambar 3: Pewarnaan Bidang

## B. Algoritma Welch-Powell
Algoritma Welch-Powell digunakan untuk mewarnai simpul pada suatu graf yang berdasarkan derajat tertinggi dari simpul- simpulnya. Langkah-langkah Algoritma Welch-Powell sebagai berikut:
1. Mengurutkan simpul-simpul pada graf 𝐺
dalam derajat yang menurun.
2. Gunakan satu warna untuk mewarnai simpul pertama yang memiliki derajat paling tinggi dan simpul-simpul lain dalam urutan yang tidak bertetangga dengan simpul pertama.
3. Mulai lagi dengan simpul derajat paling tinggi berikutnya di dalam daftar terurut yang belum diberi warna dan dan ulangi proses pewarnaan simpul dengan menggunakan warna kedua.
4. Mengulangi penambahan warna pada semua simpul yang telah diberi warna.

## C. Data
Data dalam penelitian ini merupakan data sekunder  yaitu durasi lampu lalu lintas di Simpang Lima Krian-Sidoarjo yang dikumpulkan oleh peneliti pada tanggal 20 Oktober 2019 pukul 17.00 sampai 18.00 WIB yang bersumber dari Dinas Perhubungan Provinsi Jawa Timur.

## D. Optimasi Waktu Tunggu  Lampu Lalu Lintas Menggunakan Algoritma Welch- Powell
Lampu lalu lintas yang berada di Simpang  Lima Krian-Sidoarjo  memiliki permasalahan yang perlu untuk dicarikan solusi, salah satu solusinya adalah optimasi waktu tunggu lampu lalu lintas (yaitu durasi lampu hijau dan lampu merah). Pewarnaan simpul diterapkan untuk menentukan durasi optimal lampu hijau dan lampu merah. Berikut langkah-langkah penerapan pewarnaan graf pada lampu lalu lintas di Simpang Lima Krian-Sidoarjo.
1. Menggambarkan struktur graf jalan Simpang Lima Krian-Sidoarjo dan pemetaan arus yang akan terjadi pada Simpang Lima Krian-Sidoarjo.  Simpul merepresentasikan jalur yang dapat dilewati dalam persimpangan  dan sisi merepresentasikan  hubungan dua simpul yang saling melintas atau bersebrangan atau akan terjadi tabrakan jika lampu hijau menyala secara bersamaan.
2. Mewarnai setiap simpul pada graf dengan menggunakan  Algoritma Welch-Powell untuk  mengetahui arus mana saja yang dapat berjalan secara beriringan.
3. Memperoleh bilangan kromatik  (jumlah warna minimum untuk mewarnai simpul pada graf dimana simpul yang adjacent diberi warna yang berbeda) yang digunakan untuk menentukan  alternatif penyelesaian  durasi  lampu  hijau  dan lampu merah dengan siklus waktu tertentu. Caranya dengan membagi satu siklus yang terdiri  dari  total  durasi lampu  hijau  dan lampu  merah  dengan  bilangan  kromatik. Hasil  pembagiannya  menunjukkan  nyala durasi lampu hijau dan lampu merah baru.
Jalan Simpang Lima Krian-Sidoarjo diilustrasikan pada Gambar 4 dimana bagian utara merupakan jalur arah Legundi yang memiliki 2 jalur, bagian selatan yang pertama merupakan jalan arah Pacet yang memiliki 2 jalur, bagian selatan yang kedua merupakan jalan arah Wonoayu yang memiliki 2 jalur, bagian  timur  merupakan jalan arah kota Mojokerto yang memilik 2 jalur, bagian barat
merupakan jalan arah kota Sidoarjo  yang memiliki 2 jalur.
Gambar 4: Ilustrasi Simpang Lima Krian- Sidoarjo
Berdasarkan ilustrasi Gambar 4, diperoleh struktur graf dari Simpang Lima Krian- Sidoarjo  yang disajikan pada Gambar 5. Dimana A, B, C, D, E yang dimaksud disajikan dalam tabel berikut.
Tabel 1: Arus A, B, C, D, E
1 2 A Arah ke Mojokerto Arah dari Mojokerto B Arah ke Wonoayu Arah dari  Wonoayu C Arah ke Pacet Arah dari Pacet D Arah ke Legundi Arah dari Legundi E Arah ke Sidoarjo Arah dari Sidoarjo
Berdasarkan  Gambar 5 diperoleh bahwa simpul saling terhubung  dengan simpul lain jika terdapat kemungkinan tabrakan jika lampu hijau menyala bersamaan pada tiap ruang Simpang Lima Krian Sidoarjo.
Tahap berikutnya adalah pewarnaan pada simpul dengan algoritma Welch-Powell . Pewarnaan simpul diperoleh pada Gambar 6. Berdasarkan Gambar 6  diperoleh  5 bilangan kromatik . Berikut adalah beberapa kondisi jika arus berjalan bersama-sama pada hasil pewarnaan:
a. Arus A1:B1,  A1:C1,  A1:D1  dan A1:E2 akan berjalan beriringan pada saat lampu lalu lintas berwarna hijau.
b. Arus B2:A2,  B2:C1,  B2:D1  dan  B2:E2 akan berjalan beriringan pada saat lampu lalu lintas berwarna hijau.
c. Arus C2:A2,  C2:B1,  C2:D1  dan C2:E2 akan berjalan beriringan pada saat lampu lalu lintas berwarna hijau.
d. Arus D2:A2,  D2:B1,  D2:C1  dan D2:E2 akan berjalan bersama sama ketika lampu berwarna hijau.
e. Arus  E1:A2,  E1:B1,  E1:C1  dan E1:D1 akan berjalan bersama ketika lampu lalu lintas berwarna hijau.
Gambar 5: Struktur Graf Simpang Lima Krian-Sidoarjo
D2 E2 E1 A2 A1 C2 C1 B1 B2 D1 Jalan Arah Legundi Jal an A rah M o jo k er to Jalan Arah Wonoayu Jalan Arah Pacet Jal an A rah S id oa rj o U
Selanjutnya, menentukan alternatif durasi lampu hijau dan lampu merah.  Berikut  data sekunder dari Dinas  Perhubungan Provinsi Jawa Timur  pada Simpang Lima Krian- Sidoarjo.
Tabel 2: Durasi Lampu Lalu Lintas Simpang
Lima Krian-Sidoarjo Ruas Jalan Durasi (detik) Total Lampu Hijau Lampu Merah Arah Mojokerto 20 90 110 Arah Wonoayu 23 87 110
Satu siklus lampu  hijau dan lampu merah dari arah Mojokerto berdurasi 110 detik. Durasi 110 detik dibagi dengan bilangan kromatik =5  diperoleh  hasil 22 detik, yang berati  durasi lampu hijau baru  adalah 22 detik dan durasi lampu merah baru adalah 88 detik.  Hasil  yang sama untuk durasi lampu hijau dan lampu merah  dari  arah Wonoayu, Legundi, Pacet dan Sidoarjo.
Tingkat efektifitas durasi lampu hijau dan lampu merah baru dapat diukur dengan rasio, yaitu rasio  antara selisih durasi lampu hijau/lampu merah lama dengan durasi lampu
hijau/ lampu merah baru hasil penyelesaian pewarnaan simpul dengan Algoritma Welch- Powell dan durasi lampu hijau/ lampu merah baru tersebut.  Tingkat  efektifitas  pada arah Mojokerto yaitu untuk durasi lampu hijau = 20−22 22 × 100% = − 9.09% dan untuk durasi lampu merah  = 90−88 88 × 100% = 12.5% . Hal tersebut berarti durasi lampu merah  yang baru efektif dibandingkan durasi lampu merah lama. Akan tetapi, untuk durasi lampu hijau  menunjukkan bahwa penyelesaian menggunakan pewaranaan simpul Algoritma Welch-Powell tidak lebih efektif dibandingkan data yang ada, Berdasarkan hasil perhitungan tersebut, diperoleh bahwa durasi lampu hijau dan lampu merah baru pada Simpang Lima Krian-Sidoarjo  sebagai berikut:
1. Durasi lampu merah pada ruas simpang arah Mojokerto efektif  jika mengalami penurunan selama 2 detik dan durasi pada lampu hijau tidak efektif jika bertambah selama 2 detik.
2. Durasi lampu merah pada ruas simpang arah Wonoayu tidak efektif  jika mengalami kenaikan selama 1 detik dan durasi pada lampu hijau efektif  jika mengalami penurunan selama 1 detik.
Gambar 6: Hasil Pewarnaan Simpul Graf Simpang Lima Krian-Sidoarjo dengan Algoritma Welch-Powell
3. Durasi lampu merah pada ruas simpang arah Legundi tidak efektif jika mengalami kenaikan selama 1 detik dan durasi pada lampu hijau efektif jika mengalami penurunan selama 1 detik.
4. Durasi lampu merah pada ruas simpang arah Pacet tidak efektif jika mengalami kenaikan selama 3 detik dan durasi pada lampu hijau efektif  jika mengalami penurunan selama 3 detik.
5. Durasi lampu merah pada ruas simpang arah Sidoarjo tidak efektif jika mengalami kenaikan selama 2 detik dan durasi pada lampu hijau efektif jika mengalami penurunan selama 2 detik.

## III. KESIMPULAN
Kesimpulan yang didapat dari penelitian adalah pewarnaan simpul  menggunakan Algoritma Welch-Powell memberikan keefektifan hingga 13.63% pada optimasi waktu tunggu lampu lalu lintas di Simpang Lima Krian-Sidoarjo dengan bilangan kromatik yaitu 5. Dimana, durasi lampu merah pada ruas simpang arah Mojokerto efektif  jika mengalami penurunan selama 2 detik  dan durasi pada lampu hijau tidak efektif jika bertambah selama 2 detik. Durasi lampu merah pada ruas simpang arah Wonoayu  tidak efektif   jika mengalami kenaikan selama 1 detik dan durasi pada lampu hijau efektif  jika mengalami penurunan selama 1 detik.  Durasi lampu merah pada ruas simpang arah Legundi tidak efektif  jika mengalami kenaikan selama 1 detik dan durasi pada lampu hijau efektif jika mengalami penurunan selama 1 detik. Durasi lampu merah pada ruas simpang arah Pacet tidak efektif jika mengalami kenaikan selama 3 detik dan  durasi pada lampu hijau efektif jika mengalami penurunan selama 3 detik. Durasi lampu merah pada ruas simpang arah Sidoarjo  tidak efektif  jika mengalami kenaikan selama 2 detik dan durasi pada lampu hijau efektif jika mengalami penurunan selama 2 detik.

## REFERENSI
[1] A. Fanani, “Optimasi Waktu Tunggu Lampu Lalu Lintas Dengan Menggunakan Graf
Kompatibel Sebagai Upaya Mengurangi Kemacetan,”  Syst. Inf. Syst. Informatics J., vol. 2, no. 1, pp. 45–50, 2016, doi: 10.29080/systemic.v2i1.107.
[2] R. Jaiswal and S. Rai, “Application of Fuzzy Graph Coloring in Traffic Light Problem,” Int. J. Innov. Res. Sci. Eng., vol. 5, no. 5, pp. 6950–6956, 2016, doi: 10.15680/IJIRSET.2016.0505047.
[3] M. Kusmira and Taufiqurrochman, “Pemanfaatan Aplikasi Graf Pada Pembuatan Jalur Angkot 05 Tasikmalaya,” 2017.
[4] 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, doi: 10.14421/fourier.2013.22.73-79.
[5] Rinaldi, M. Matematika Diskrit. Bandung: Institut Teknologi Bandung.2017
[ 6] Ardiansyah, Efendi, F. S., Syaifullah, Pinto, M., Pujianto, & Tempake, H. S. Implementasi Algoritma Greedy untuk melakukan Graph
Colouring : Studi kasus peta propinsi Jawa
Timur. Jurnal Informatika, vol 4 no.2.2010
[7] Farhan, M. Aplikasi Graf Pada Pewarnaan Lalu Lintas. Bandung: Institut Teknologi Bandung.2017
[8] Muhib.  Bilangan Kromatik Pewarnaan titik pada Graf dual dari Graf Piramid. Malang: Universitas Islam Negeri Maulana Malik Ibrahim.2013
[ 9] Susanti,  A. Evaluasi Kinerja Simpang Lima
Krian Dan Upaya Penanganannya Di Kabupaten Sidoarjo. Rekayasa Teknik Sipil
Vol 1 No. 1. pp. 9 - 20. 2015