Diposting pada 18 October 2019, 16:59 Oleh Agung R Pamungkas

Abstract— The distribution of development newspaper, which is carried out every 3 (three) months, is a routine agenda of the Department of Communication and Information of Tegal Regency. Each routine agenda, there are always problems where the tabloids must be distributed quickly and optimally. This can be overcome by selecting the shortest route (optimum) in the case of Traveling Salesman Problem using genetic algorithms. The research aims to complete the search for the shortest route using genetic algorithms with php language.

Intisari— Distribusi tabloid pembangunan yang dilaksanakan tiap 3 (tiga) bulan menjadi agenda rutin Dinas Kominfo Kab.Tegal. Tiap agenda rutin tersebut, selalu muncul masalah dimana tabloid harus terdistribusi dengan cepat dan optimal. Hal ini dapat diatasi dengan pemilihan rute terpendek (optimal) pada kasus Travelling Salesman Problem menggunakan algoritme genetika. Penelitian bertujuan  menyelesaikan pencarian rute terpendek menggunakan algoritme genetika dengan bahasa pemrograman php.

Kata Kunci— Tegal, TSP, GA, Algoritme Genetika, distribusi

I.      pendahuluan

Pencarian rute terbaik dalam melakukan suatu distribusi memiliki peranan yang sangat penting dalam hal efektifitas dan efisiensi terutama pada waktu dan biaya. Tak jarang suatu organisasi mengeluarkan biaya yang mahal hanya karena ketidak-efektifan dalam pendistribusian barang atau komoditas. Maka dari itu perlu dilakukan suatu optimasi dalam penentuan rute distribusi. Permasalahan dalam optimasi penentuan rute terpendek ini dinamakan dengan Travelling Salesman Problem (TSP).

Model kasus TSP yang sebenarnya yaitu terdapat seorang salesman yang akan mengunjungi sejumlah n lokasi. Namun, seluruh lokasi harus dikunjungi dan setiap lokasi hanya dapat dikunjungi tepatnya satu kali. Permasalahannya adalah bagaimana salesman tersebut dapat menentukan rute terpendek yang akan dilalui dalam mengunjungi seluruh lokasi dan kembali lagi ke lokasi awal. Model TSP ini dapat juga diimplementasikan pada kegiatan distribusi koran pertiwi (yang terbit 3 bulan sekali).Dalam penelitian ini, akan diselesaikan kasus TSP distribusi koran menggunakan algoritme genetika dengan sampel 8 kecamatan.

II.    LANDASAN TEORI

A.    Travelling Salesman Problem

TSP muncul  pada saat pertama kali dipelajari oleh seorang matematikawan Karl Menger di Vienna dan Harvard pada tahun 1930. Kemudian permasalahan ini dipublikasikan oleh Hassler Whitney dan Merrill Flood di Princeton. Pembicaraan detail tentang hubungan antara Menger dan Whitney, dan perkembangan dari TSP sebagai topik studi dapat dilihat di makalah Alexander Schrijver yang berjudul “On the history of combinatorial optimization (till 1960)” [1].

Hal yang perlu diperhatikan di dalam kasus TSP adalah perjalanan salesman dimulai dari kota awal sampai seterusnya ke kota n dan akhirnya akan kembali lagi ke kota awal. Namun, aturannya adalah setiap kota selain kota awal hanya dapat dikunjungi tepat satu kali. Persoalan yang dihadapi ialah bagaimana membangun jalur rute yang optimal dengan mempertimbangkan aturan tersebut agar didapatkan total jarak tempuh minimal sehingga akan berdampak pada penghematan biaya transportasi.

Persoalan yang dihadapi pada kasus ini tidak mudah, karena terdapat banyak kombinasi alur rute yang mungkin terjadi seiring dengan banyaknya titik yang akan dikunjungi dan juga harus memperhatikan aturan yang berlaku.

B.    Algoritme Genetika

Menurut Carwoto [2], algoritma genetika adalah algoritma pencarian yang berdasarkan mekanisme seleksi alam Darwin dan prinsip-prinsip genetika untuk menentukan struktur-struktur (yang masing-masing disebut individu) berkualitas tinggi yang terdapat dalam sebuah domain (yang disebut populasi). Carwoto [2] juga menjelaskan bahwa dalam ilmu komputer, algoritma genetika termasuk dalam kajian komputasi lunak (soft computing) dan kecerdasan buatan (artificial intelligence). Algoritma Genetika dapat digunakan untuk menyelesaikan permasalahan searching dan optimasi yang mempunyai kompleksitas tinggi yang banyak terjadi dalam dynamic programming seperti TSP dan Knapsack Problem.

Gambaran tentang proses Algoritma Genetika  yaitu dimisalkan terdapat suatu populasi yang didalamnya terdapat individu-individu yang merepresentasikan kumpulan solusi permasalahan. Individu-individu tersebut akan dievaluasi untuk mendapatkan nilai fitness dari tiap-tiap individu. Setelah dievaluasi, individu-individu ini akan menjalani proses seleksi. Hanya individu dengan nilai fitness tertinggi yang akan memiliki peluang lebih besar untuk terpilih ke proses berikutnya. Selanjutnya akan dilakukan proses reproduksi untuk menambah keanekaragaman individu-individu yang telah terseleksi. Proses reproduksi dikerjakan dengan melakukan perkawinan silang antara individu yang telah terpilih yang dinamakan proses crossover dengan harapan setelah mengalami perkawinan silang, akan lahir individu-individu baru yang lebih baik dari individu sebelumnya. Selanjutnya individu dari hasil crossover ini akan mengalami proses mutasi yang direpresentasikan sebagai proses berubahnya satu atau lebih nilai gen dalam kromosom. Pada akhirnya proses reproduksi ini akan menghasilkan populasi baru.

Gambar 1. Siklus algoritme genetika [3]

III. Metodologi

A.    Penentuan titik

Penelitian dimulai dengan memetakan 8 (delapan) kantor kecamatan yang akan menjadi rute distribusi yaitu 1.Slawi, 2.Adiwerna, 3.Pangkah, 4.Dukuhwaru, 5.Pagerbarang, 6.Lebaksiu, 7.Margasari dan 8.Talang dengan pangkal dan akhir Dinas Kominfo.

Gambar 2. Titik yang akan dikunjungi

Setelah didefinisikan semua titik yang akan dikunjungi dalam TSP, maka langkah selanjutnya adalah menghitung jarak antar semua titik. Hal ini diperlukan untuk menghitung nilai fitness di langkah selanjutnya. Penulis menggunakan google maps untuk menghitung jarak antar masing-masing titik dan hasilnya adalah sebagai berikut :

Tabel 1. Daftar jarak antar titik

B.    Pembangkitan kromosom dan populasi

Setelah titik dan jarak sudah didefinisikan, langkah selanjutnya adalah membangkitkan kromosom dan pembuatan populasi. Pada tahap ini, titik-titik yang ada dibuat menjadi gen dan membentuk kromosom. Dalam satu kromosom, terdapat 8 gen yang melambangkan titik TSP. pada saat pembangkitan kromosom, gen dibuat secara acak namun gen tersebut hanya bisa muncul sekali dalam pengacakan karena gen yang merupakan titik tersebut tidak akan dilalui 2 (dua) kali dalam TSP. Setelah kromosom bangkit, maka dibuat populasi. Pada penelitian ini, populasi yang dibuat sebanyak 4 (empat) populasi.

Gambar 3. Gen, kromosom dan populasi

Jadi pada langkah ini, titik-titik kantor kecamatan dibuat menjadi gen dengan dilambangkan nomor dari masing-masing kecamatan (1 -8) kemudian kumpulan dari 8 (delapan) gen tersebut digabungkan menjadi kromosom dengan posisi gen yang acak. Kromosom kemudian dibentuk menjadi 4 (empat) populasi

C.    Perhitungan nilai fitness

Kromosom dalam populasi kemudian dihitung nilai fitness dan fitness ratio untuk menentukan parent yang akan tetap dalam populasi dan akan mengeluarkan kromosom dengan fitness yang rendah. Pada penelitian ini, parent yang akan digunakan adalah 2 (dua) kromosom. Cara menghitung fitness masing-masing kromosom adalah dengan melakukan perhitungan jarak :

kominfo -> gen1 -> gen2 -> gen3 -> gen4 -> gen5 -> gen6 -> gen7 -> gen8 -> kominfo

kemudian fitness dihitung dengan rumus :

fitnes = 1 / Total jarak kromosom

sedangkan fitness ratio dihitung menggunakan :

fitness ratio = (fitness kromosom / Total fitnes kromosom) x 100%

dengan rumus diatas, maka dapat dihitung jarak dari masing-masing kromosom :

C1 = 6,8+14,3+19+19,2+29,7+26,8+7,8+11,4+6 = 141

C2 = 3,6 +5,9 +22,8 +29,7 +7,6 +14,3 +11,2 +20,8 +11 = 126,9

C3 = 11+7,8+15,3+11,2+14,3+32,2+22,8+9,8+7,6 = 132

C4 = 6+22,8+29,7+4,4+7,8+20,8+19+14,3+6,8 = 131,6

Dari jarak tersebut, dihitung fitness kromosom :

C1 = 1/141 = 0,00709

C2 = 1/126,9 = 0,00788

C3 = 1/132  = 0,00757

C4 = 1/131,6= 0,00759

Total fitness = 0,00709+0,00788+0,00757+0,00759 = 0,03013

Kemudian fitness ratio dari masing-masing kromosom adalah :

C1 = (0,00709/0,03013) x 100% =  23,531%

C2 = (0,00788/0,03013)  x 100% = 26,153%

C3 = (0,00757/0,03013)  x 100% = 25,124%

C4 = (0,00759/0,03013) x 100% = 25,190%

Dari perhitungan fitness dan fitness ratio dari kromosom diatas, maka didapatkan parent yaitu C2 dan C4 dengan menggunakan metode seleksi turnamen karena memiliki fitness dan fitness ratio yang paling tinggi.

D.   Crossover

Setelah parent didapatkan melalui perhitungan fitness dan fitness ratio, maka tahap selanjutnya adalah melakukan crossover antar parent guna menghasilkan child. Kromosom C2 dan C4 akan menjadi parent 1 dan parent 2 (P1 dan P2) dan akan menghasilkan Child 1 dan Child 2 (Ch1 dan Ch2)

Gambar 3. Proses Crossover

Yang perlu diperhatikan pada proses crossover dalam menyelesaikan masalah TSP adalah child hasil dari crossover antar parent tidak boleh memiliki gen ganda.

E.    Mutasi

Setelah proses crossover menghasilkan kromosom child, maka kromosom child tersebut dialakukan mutasi. Pada penelitian ini probabilitas mutasi yang digunakan adalah 0,8 dengan menggunakan metode swapping mutation. Proses mutasi dilakukan pada anak hasil Crossover dengan tujuan untuk memperoleh individu baru sebagai kandidat solusi pada generasi selanjutnya dengan fitness yang lebih baik, dan lama-kelamaan menuju solusi optimum yang diinginkan.

Gambar 4. Proses swapping mutation

Setelah kromosom child dilakukan mutasi, maka kromosom-kromosom tersebut dimasukkan kedalam populasi dan siap untuk dilakukan proses pada generasi selanjutnya.

Gambar 4. Populasi baru

F.    Pembuatan Program

Program untuk mencari rute terpendek dalam pendistribusian tabloid dibuat menggunakan bahasa pemrograman php. Pada penelitian ini antar muka yang digunakan adalah berbasis teks. Pembuatan program dilakukan dengan pembuatan fungsi-fungsi pada algoritme genetika yaitu fungsi pembangkitan kromosom dan populasi, fungsi perhitungan fitness dan fitness ratio, fungsi seleksi, fungsi crossover, fungsi mutasi dan fungsi utama yaitu perulangan generasi. Disamping itu juga dibuat fungsi pendukung yaitu fungsi penghitung jarak antar titik.

Gambar 5. Potongan kode program

Gambar 6. Tampilan program

G.   Pengujian

Uji coba dilakukan sebanyak 3 (tiga) kali dengan jumlah generasi sebanyak 500 iterasi dan didapatkan hasil sebagai berikut :

·         Uji coba pertama mendapatkan hasil jarak optimum sejauh 70,3 Km pada generasi ke 81.

·         Uji coba kedua mendapatkan hasil jarak optimum sejauh 70,3 Km pada generasi ke 210.

·         Uji coba kedua mendapatkan hasil jarak optimum sejauh 70,3 Km pada generasi ke 135.

Ketiga uji coba tersebut menghasilkan rute optimum yang sama yaitu  Kominfo->Lebaksiu-> Pagerbarang-> Margasari-> Dukuhwaru-> Adiwerna-> Talang-> Pangkah-> Slawi-> Kominfo.

Gambar 7. Grafik hasil uji coba

Gambar 7. Hasil rute optimum

IV.  HASIL DAN PEMBAHASAN

Dalam penelitian ini, rute terbaik yang dihasilkan melalui 500 generasi dalam menyelesaikan TSP menggunakan metode seleksi turnamen dengan Probability mutation 0,8 adalah sejauh 70,3 Km dengan rute Kominfo->Lebaksiu-> Pagerbarang-> Margasari-> Dukuhwaru-> Adiwerna-> Talang-> Pangkah-> Slawi-> Kominfo. Rute ini diyakini sebagai rute optimum karena grafik menunjukkan setelah jarak mencapai nilai 70,3Km, nilai tersebut tetap konsisten sampai dengan generasi terakhir yang ditentukan.

Referensi

[1]        http://www.math.uwaterloo.ca/tsp/history/. Diakses Oktober 2019

[2]        Carwoto. Implementasi Algoritma Genetika untuk Optimasi Penempatan Kapasitor Shunt pada Penyulang Distribusi Tenaga Listrik. Jurnal Teknologi Informasi DINAMIK, Vol. 12, No. 2, pp. 122-130. 2007

[3]        Basuki, Achmad. 2003a. Algoritma Genetika: Suatu Alternatif Penyelesaian Permasalahan Searching, Optimasi, dan Machine Learning. http://budi.blog.undip.ac.id/files/2009/06/algoritma_ genetika.pdf. Diakses Oktober 2019.

Oleh :

Agung R Pamungkas

Jurusan Magister Teknologi Informasi, Departemen Teknik Elektro Dan Teknik Informatika, Fakultas Teknik

Universitas Gadjah Mada

Jln. Grafika 2 Yogyakarta 55281 INDONESIA

 (telp: 0274-5555; fax: 0274-4321; e-mail: agung.pamungkas@mail.ugm.ac.id)