## Optimasi Kelayakan Kondisi Pembangunan Jalan di Kota Lhokseumawe Menggunakan Algoritma Greedy
Eva Darnila 1 , Mutammimul Ula 2 , Cut Dewi Aida Soraya 3
12,3 Teknik Informatika Universitas Malikussaleh Jl. Kampus Unimal BI Blang Pulo, Aceh Utara, Indonesia
1* eva.darnila@unimal.ac.id, 2 cutdewi58@gmail.com
Abstrak- Kota Lhokseumawe merupakan salah satu kota yang berada dipesisir timur aceh. Daerah Kota Lhokseumawe  merupakan hasil pemekaran  dari  kawasan  Aceh  Utara, dimana sarana dan prasarana  transportasi  yang telah ada  perlu  dioptimalkan  pembangunannya. Pembangunan  diharapkan  dapat  meningkatkan  perekonomian  penduduk  disekitaran  Kota  Lhokseumawe  terutama  dalam  sektor pembangunan jalan. Mengingat Pertumbuhan penduduk dikawasan Kota Lhoseumawe yang terus meningkat setiap tahunnya, Sehingga pembangunan  jalan yang optimal diharapkan  dapat memudahkan mobilitas  penduduk  sekitar dalam melakukan  kegiatan  sehari  –  hari. Untuk mengetahui kondisi  jalan yang ada  disekitaran  kota lhokseumawe  dalam  penelitian ini  akan  digunakan Manual  Kapasitas Jalan Indonesia (MKJI) untuk mengukur derajat kejenuhan suatu ruas jalan yang ada di kawasan Kota Lhokseumawe. Dan pengoptimalannya maka digunakan Algoritma Greedy, dimana algoritma greedy ini merupakan algoritma optimasi yang lazim digunakan untuk memecahkan persoalah optimasi meskipun hasilnya tidak selalu optimal. Algoritma Greedy yang dirterapkan pada aplikasi ini akan mencoba melakukan optimasi  dengan  cara  mencari  jalur  terdekat  dari  jalan  Simpang  Len  menuju  ke  Taman  Riyadhah  dengan  mengambil  titik  koordinat (latitude dan longitude) dari node – node yang akan dilewati. Dari hasil pencarian node yang digambarkan kedalam bentuk graf maka menghasilkan jalur yang optimal yang akan dilewati oleh user ialah A → B → C → D → F → G → K → L → M → Q dengan total jarak 9,8 km.
Kata kunci : Optimasi, Jalan, Algoritma Greedy, Jalur Terdekat
Abstract- Lhokseumawe City is one of the cities on the east coast of Aceh. The Lhokseumawe City area is the result of the expansion of  the North Aceh region, where existing transportation facilities and infrastructure need to be optimized for development. Development is expected to improve the economy of the population around Lhokseumawe City, especially in the road construction sector. Considering the population growth in the Lhoseumawe City region which continues to increase every year, so that optimal road construction is expected to facilitate the mobility  of the surrounding  population in  carrying out  daily  activities.  To find  out  the condition of the  existing  roads  around the  city of Lhokseumawe in this study, the Indonesian Road Capacity Manual (MKJI) will be used to measure the degree of saturation of a road section in the Lhokseumawe City area. And the optimization is then used Greedy Algorithm, where this greedy algorithm is an optimization algorithm commonly  used  to  solve  optimization  problems  even  though  the  results  are  not  always  optimal.  The  Greedy  algorithm  applied  in  this application will try to optimize by finding the nearest path from the Simpang Len road to Riyadhah  Park by taking the coordinates (latitude and longitude) of the nodes to be passed. From the search results of the node that is depicted into graphs then it produces the optimal path that will be passed by the user is A → B → C → D → F → G → K → L → M → Q with a total distance of 9.8 km.
Keywords : Optimization, Roads, Greedy Algorithms, Nearby Paths

## PENDAHULUAN
Kota  Lhokseumawe  merupakan  salah  satu  kota  yang  berada  di  kawasan  pesisir  timur  Aceh.  Secara Geografis Lhokseumawe merupakan daerah yang strategis di jalur Sumatera Utara dan Banda Aceh. Sebagai daerah  pemekaran  tentunya  Kota  Lhokseumawe  harus  memulai  dari  nol  terhadap  seluruh  aspek pembangunan. Terutama pada bidang pembangunan infrastruktur.
Pembangunan infrasruktur yang dilakukan oleh pihak pemerintahan maupun pihak swasta yang ada di kota  Lhokseumawe  hingga  saat  ini  terus  berkembang,  terutama  pada  sektor  pembangunan  jalan.  Jalan merupakan  prasarana  trasportasi  darat  yang  meliputi  segala  bagian  jalan,  termasuk  pelengkap  yang diperuntukkan  bagi  lalu  lintas.  Dengan  adanya  pembangunan  jalan  tentunnya  mempermudah  masyarakat disekitar dalam melakukan kegiatan sehari-hari.
Dalam  pembangunan  jalan  banyak  aspek-aspek  yang  perlu  diperhatikan.  Seperti  pembebasan  lahan, jalan sempit, satu jalur dua arah dan lain-lain. Sehinga pengoptimalan kelayakan kondisi pembangunan jalan sangat diperlukan untuk kenyamanan masyarakat. Dengan pengoptimalan pembangunan jalan maka dapat menigkatkan pertumbuhan ekonomi di Kota Lhokseumawe. Pengoptimalan ini  tidak  hanya berfungsi untuk pertumbuhan  ekonomi  saja,  namun  juga  dapat  mengurangi  jumlah  kemacetan  dijalan-  jalan  yang  sering diakses  oleh  masyarakat[1].  Banyak  cara  yang  bisa  dilakukan  untuk  menyelesaikan  masalah  optimasi, diantaranya algoritma Greedy.
Algoritma  Greedy  merupakan  salah  satu  cara  untuk  mendapatkan  solusi  optimal  dalam  proses penyimpanan. Algoritma Greedy merupakan algoritma yang lazim digunakan untuk memecahkan persoalan optimasi  meskipun  hasilnya  tidak  selalu  merupakan  hasil  yang  optimum.  Dalam  algoritma  ini
untuk  mendapatkan  solusi  optimal  dari  permasalahan  terdapat  dua  kriteria  yaitu  fungsi  tujuan/utama  dan nilai pembatas (Constrain). Fungsi tujuan hanya terdiri dari satu fungsi sedangkan fungsi pembatas dapat terdiri dari lebih satu fungsi [2]. Jadi, untuk mempermudahkan pengoptimalisasi pembangunan jalan penulis tertarik  untuk  melakukan  penelitian  dengan  judul  “Optimasi  Kelayakan  Kondisi  Pembangunan  Jalan  Di Kota Lhokseumawe Menggunakan Algoritma Greedy”.

## METODOLOGI PENELITIAN

## 2.1. Pengertian Jalan
Jalan  merupakan  infrastruktur  yag  sangat  dibutuhkan  bagi  transportasi  darat,  fungsi  jalan  adalah penghubung  sutu  wilayah  dengan  wilayah  lainnya.  Jalan  merupakan  infrastruktur  yang  berperan  dalam perekonomian nasional. Besarnya mobilitas ekonomi tahun 2002 yang melalui jaringan jalan nasional dan propinsi rata-rata perhari dapat  mencapai sekitar 201 juta kendaraan-kilometer[3].

## 2.2. Algoritma Greedy
Algoritma  Greedy  merupakan  metode  yang  paling  populer  untuk  memecahkan  persoalan optimasi[4].  Dalam  menyelesaikan  permasalahan,  Algoritma  Greedy  melakukannya  secara  bertahap[5]. Tahap penyelesainnya adalah:
1. Mengambil pilihan yang terbaik yang dapat diperoleh pada saat itu tanpa memperhatikan konsekuensi kedepan.
2. Berharap bahwa dengan memilih optimum local pada setiap langkah akan berakhir dengan optimum global..
Gambar 1. Diagram Alur Algoritma Greedy[6]

## 2.3. Perhitungan Jarak Dengan Metode Euclidean Distance
Euclidean  Distance adalah  sebuah  metode  yang  digunakan  untuk  mengukur  jarak  ( distance )[7]. Euclidean  distance adalah  perhitungan  jarak  dari  2  buah  titik  dalam Euclidean  space.  Euclidean  space diperkenalkan  oleh  Euclid,  seorang  matematikawan  dari  Yunani  sekitar  tahun  300  B.C.E.  untuk mempelajari hubungan antara sudut dan jarak. Euclidean Distance sebenarnya merupakan generalisasi dari teorema phytagoras secara formal perhitungan Euclidean Distance adalah sebagai berikut : ........................................................................................................................................... .......................(1)
Dimana : d = Nilai Jarak n = Banyaknya Nilai
Jika terdapat dua buah titik pada sebuah bidang dua dimensi, maka untuk mengukur jarak dari kedua titik tersebut dapat digunakan persamaan phytagoras.
….………….  …………………………………………………………………… ………………(2)
Dimana : = nilai titik x =nilai titik y
Sehingga dari persamaan  diatas dapat implementasi menjadi :
……………..……....................................................................
..............(3)
Hasil  perhitungan  ( Jarak )  diatas  masih  dalam  satuan decimal  degree (sesuai  dengan  format  longlat yang  dipakai)  sehingga  untuk  menyesuaikannya  perlu  dikalikan  dengan  111.319  km  (1  derajat  bumi  = 111.319 km).

## HASIL DAN PEMBAHASAN
Sistem yang akan dibangun akan melakukan pencarian jalur terdekat menggunakan algoritma greedy. Pencarian jalur terdekat akan dilalukan dengan menentukan titik awal dan titik akhir. Titik  awal merupakan posisi user sedang kan titik akhir adalah titik tujuan dari user dan ouput yang diberikan merupakan hasil dari pencarian  jalur  terdekat  menggunakan  algoritma  greedy.  Pencarian  Jalur  menggunakan  algoritma  greedy yang akan dibangun juga akan dilengkapi dengan API map untuk mememudahkan user untuk melihat jalur terdekat menuju kota Lhokseumawe.

## 3.1. Usecase Diagram

## Gambar 2 . Usecase Diagram
User  yang  berperan sebagai actor masuk kedalam  sistem dan dapat  mengakses sistem ketika user berhasil  login.  Kemudian  user  dialihkan  ke  tampilan  home.  Dimana  pada  halaman  home  terdapat  menu tentang data optimasi jalan, masp, cetak serta logout dari sistem. Data optimasi jalan merupakan informasi tentang tingkat kejenuhan jalan/volume lalu lintas, menu maps merupakan tampilan peta yang menunjukan jalur  terdekat  menuju  Kota  Lhokseumawe,  sedangkan  menu  cetak  optimasi  jalan  adalah  menu  untuk mencetak data optimasi jalan.

## 3.2. Perhitungan Jarak Menggunakan Metode Euclidean Distance
Pada perhitungan  ini, penulis  menggunakan data Jalur  yang akan dilewati oleh user  yang diambil dari titik koordinat dari setiap node-node yang akan dilewati oleh user.
Tabel 1. Hasil Pencarian Jarak dari node ke node No Node Titik Awal Titik Akhir Jarak Latitude Longitude Latitude Longitude 1 A→R 5.209484 97.07784 5.210412 97.082702 0.6km 2 R→S 5.210412 97.082702 5.215246 97.093456 1.3km 3 S→B 5.215246 97.093456 5.210477 97.10127 1.0km 4 B→C 5.210477 97.10127 5.201515 97.11091 1,5 km
5 C→D 5.201515 97.11091 5.196495 97.11433 0.7 km 6 C→E 5.201515 97.11091 5.209829 97.12142 1,5 km 7 E→I 5.209829 97.12142 5.202863 97.13567 1.8 km 8 E→H 5.209829 97.12142 5.191547 97.13009 2.3 km 9 H→I 5.191547 97.13009 5,202863 97,13567 1,4 km 10 H→M 5.191547 97.13009 5.182644 97.13854 1,4 km 11 D→F 5.196495 97.11433 5.188207 97.11981 1,1 km 12 F→G 5.188207 97.11981 5.180501 97.12265 1,0 km 13 G→K 5.180501 97.12265 5.176288 97.12686 0,7 km 14 K→L 5.176288 97.12686 5.175118 97.12827 0,2 km 15 L→Q 5.175118 97.12827 5.182149 97.14068 1,6 km 16 L→M 5.175118 97.12827 5.182644 97.13854 1,4 km 17 M→Q 5.182644 97.13854 5.182149 97.14068 0,2 km 18 I→J 5.182149 97.14068 5.192563 97.14746 1,4 km 19 I→O 5.182149 97.14068 5.191625 97.143476 1,1 km 20 J→N 5.192563 97.14746 5.179008 97.14788 1,5 km 21 J→O 5.192563 97.14746 5.183045 97.14193 1,2 km 22 N→O 5.179008 97.14788 5.183045 97.14193 0,8 km 23 O→Q 5.183045 97.14193 5.182149 97.14068 0,2 km 24 N→P 5.179008 97.14788 5.181184 97.14201 0,7 km 25 P→Q 5.181184 97.14201 5.182149 97.14068 0,2 km
Langkah-langkah yang dilakukan pada pencarian algoritma greedy untuk menentukan  jalur terdekat dari posisi user ke titik tujuan adalah dengan menghitung jarak yang terdapat pada tabel 1 yang telah dicari sebelumnya. Graf dapat dilihat seperti gambar 3 berikut ini:
1,4 I J E N P 2,9 1,5 A B C H O Posisi User D Q Tujuan M 1,1 0,7 F G K L
Gambar 3. Graf Posisi User Menuju Titik Tujuan
Berikut keterangan dari setiap node yang ada pada Gambar 3: Keterangan:
A : Jalan Simpang Len
B : SPBU Blang Panyang
C  : Jembatan Ujong Blang
D : Yayasan Sukma Bangsa E  : Jln. Ujong Blang F  : Samsat Kota Lhokseumawe G  : Polres Kota Lhokseumawe H : Jln. Kenari
I : Jln. Darusalam
J : Terminal Pertamina
K : Simpang Buloh L : Jln. Merdeka Barat
1 ,5 0 ,7
M : Simpang Kutablang N : Jln. Samudra
O : Jln. Listrik
P : Masjid Islamic Center
Q : Taman Riyadhah
Pada Gambar 3 menunjukkan posisi user berada pada node A dimana posisi user berada pada Jln. Simpang len sebagai titik awal. Langkah selanjutnya adalah memilih posisi yang terdekat dengan posisi user sekarang. Sehingga menemukan jalur terdekat dari proses perhitungan algoritma greedy. Maka didapat hasil seperti pada gambar 4 sebagai berikut:
1,4 I J E N P 2,9 1,5 A B C H O Q M D 1,1 0,7 F G K L
Gambar 4. Graf Hasil Pencarian Algoritma Greedy
Dari  gambar  4  dapat  disimpulkan  bahwa  Jalur  yang  paling  optimal  yang  didapatkan  dari  pencarian  jalur terdekat  dengan  algoritma  greedy  dengan  titik  awal  berada  pada  Jalan  Simpang  Len  menuju  Taman Riyadhah yang merupakan titik akhir (tujuan) menghasilkan jalur A→B→C→D→F→G→K→L→M→Q dengan total bobot sebesar 9,8 km.
Jalur yang dilewati merupakan Jalan Simpang Len (A) menuju SPBU Blang Panyang  (B) kemudian melewati jembatan Ujong Blang (C) kemudian melewati Yayasan Sukma Bangsa Lhokseumawe (D)  kemudian  melewati  Kantor  Samsat  Lhoseumawe  (F)  kemudian  melewati  Polres  Lhokseumawe  (G) kemudian melewati melewati Simpang Buloh (K) kemudian akan melalui jalan Merdeka Barat (L) kemudian melewati Simpang Kutablang (M) dan sampai ke tujuan yaitu Taman Riyadhah (Q). Dimana Bobot A→B = 2,9 km, B→C = 1,5 km, C→D = 0,7 km, D→F = 1,1 km, F→G = 1,1 km, G→K = 0,7 km, K→L = 0,2 km, L→M = 1,4 km, M→Q = 0,2 km. Jadi bobot yang didapatkan dari pencarian rute terdekat ialah 2,9 km +  1,5  km  +  0,7  km  +  1,1  km  +1,1  km  +  0,7  km  +  0,2  km  +  1,4  km  +  0,2  km  =  9,8  km  dengan  Jalur A→B→C→D→F→G→K→L→M→Q.
C. Desain Sistem
1 ,5 0 ,7
Keterangan :
Tampilan maps menunjukan informasi Jalur terdekat menuju taman riyadhah kota llhokseumawe dari posisi awal  user  yang  berada  disimpang  len,  dimana  pada  tampilan  peta  terseput  teah  diproses  menggunakan algoritma greedy.

## KESIMPULAN
Berdasarkan hasil penelitian dengan penerapan algoritma greedy pada pencarian jalur terdekat dari simpang len menuju ke taman riyadhah menghasikan jalur dari simpang len (A) akan melewati SPBU Blang Panyang (B) kemudian melewati jembatan Ujong Blang (C) kemudian melewati Yayasan Sukma Bangsa Lhokseumawe  (D)  kemudian  melewati  Kantor  Samsat  Lhoseumawe  (F)  kemudian  melewati  Polres Lhokseumawe (G) kemudian melewati melewati Simpang Buloh (K) kemudian akan melalui jalan Merdeka Barat  (L)  kemudian  melewati  Simpang  Kutablang  (M)  dan  sampai  ke  tujuan  yaitu  Taman Riyadhah  (Q). Dengan jalur A→B→C→D→F→G→K→L→M→Q dengan total jarak 9,8 km.

## R EFERENSI
[1] D. Mahamurah, M. Kaunang, and S. Sambiran, “OPTIMALISASI ALOKASI DANA DESA DALAM MENINGKATKAN PEMBANGUNAN DESA (Studi di Desa Nahepese Kecamatan Manganitu),” J. Eksek. , vol. 1, no. 1, 2017.
[2] E. N. Hayati and A. Yohanes, “Pencarian Rute Terpendek Menggunakan Algoritma Greedy,” Semin. Nas. IENACO , pp. 2337–4349, 2014.
[3] Y. P. Ma’ruf and J. Daud, “Pengaruh investasi infrastruktur jalan terhadap pertumbuhan ekonomi wilayah di kabupaten pesisir selatan provinsi sumatera barat,” J. Tek. Sipil USU , vol. 2, no. 3, pp. 1–13, 2013.
[4] R. Munir, “Algoritma & Pemrograman dalam Bahasa Pascal dan C Edisi Revisi,” Andi Yogyakarta , 2011. [Online]. Available:
https://openlibrary.telkomuniversity.ac.id/pustaka/21198/algoritma-pemrograman-dalam-bahasa-pascal-dan-c-edisi-revisi.html. [Accessed: 19-Feb- 2020].
[5] D. Rachmawati and A. Candra, “Implementasi Algoritma Greedy untuk Menyelesaikan Masalah Knapsack Problem,” J. SAINTIKOM , vol. 12, no. 3, pp. 185–192, 2013.
[6] S. A. Curtis, “The classification of greedy algorithms,” Sci. Comput. Program. , vol. 49, no. 1–3, pp. 125–157, Dec. 2003, doi:
10.1016/j.scico.2003.09.001.
[7] A. Ambarwari and N. Yanto, Penerapan Algoritma Greedy Pada Permasalahan Knapsack Untuk Optimasi Pengangkutan Peti Kemas . 2016.