PENCARIAN RUTE TERBAIK UNTUK DISTRIBUSI BANK
SAMPAH MENGGUNAKAN TRAVELLING SALESMAN
PROBLEM (TSP) STUDI KASUS KOTA DENPASAR
I Wayan Supriana Program Studi Teknik Informatika Fakultas Ilmu Kesehatan.
Sains dan Teknologi.
Universitas Dhyana Pura.
Bali.
supriana@undhirabali.
ABSTRACT
A garbage bank is a place used to collect disaggregated debris.
The high enthusiasm of the society to become a bank customer is inversely proportional to the real situation where there are still a few people who become customers of garbage bank.
The problem with the community is to collect their own garbage and deposit it to the garbage bank management.
This garbage collection process should be done optimally so that the purpose of the establishment of waste banks can be achieved and the growth of garbage bank customers increases.
So to overcome the problem of garbage picking done the best route search for waste bank distribution using Traveling Salasmen Problem (TSP).
The optimization method for best path determination using genetic algorithm.
Genetic algorithm is a method by utilizing variable speed in each path that influence the travel time in each way and utilizing natural selection process known as evolution process, cross breeding process or crossover function, mutation and individual improvement.
The result of the best route search of waste bank distribution using Traveling Salesman Problem (TSP) shows the best route that must be passed by Denpasar garbage bank in the 6th generation with 331 minutes travel time.
Keywords: Garbage Bank.
Genetic.
TSP.
Crossover ABSTRAK Bank sampah adalah suatu tempat yang digunakan mengumpulkan sampah-sampah yang sudah dipilah- pilah.
Antusias masyarakat yang tinggi menjadi nasabah bank sampah berbanding terbalik dengan keadaan sebenarnya dimana masih sedikit masyarakat yang menjadi nasabah bank sampah.
Hal yang menjadi kendala masyarakat adalah mengumpulkan sampah sendiri dan menyetornya ke pihak pengelola bank sampah.
Proses pengumpulan sampah ini haruslah dilakukan secara optimal agar tujuan dari dibentuknya bank sampah dapat tercapai dan pertumbuhan nasabah bank sampah meningkat.
Maka untuk mengatasi masalah penjemputan sampah dilakukan pencarian rute terbaik untuk distribusi bank sampah menggunakan Travelling Salasmen Problem (TSP).
Metode optimasi untuk penentuan jalur terbaik menggunakan algoritma Algoritma genetika merupakan metode dengan memanfaatkan variable kecepatan disetiap jalur yang mempengaruhi waktu tempuh disetiap jalan dan memanfaatkan proses seleksi alamiah yang dikenal dengan proses evolusi, proses perkawinan silang atau fungsi crossover, mutasi maupun perbaikan individu.
Hasil dari penelitian pencarian rute terbaik distribusi bank sampah menggunakan Travelling Salesman Problem (TSP) menunjukkan rute terbaik yang harus dilalui bank sampah kota Denpasar pada generasi ke 6 dengan waktu tempuh 331 menit.
Kata Kunci: bank sampah, genetika.
TSP, crossover 201 Jurnal Teknologi Informasi dan Komputer.
Volume 3.
Nomor 02.
Oktober 2017
PENDAHULUAN
Bank sampah adalah suatu tempat yang digunakan mengumpulkan sampahsampah yang sudah dipilah-pilah.
Hasil pemilihan dari sampah tersebut akan disetorkan kepada tempat kerajinan dari sampah atau kepada pengepul sampah.
Bank sampah dikelola seperti sistem perbankan.
Karena sistem bank sampah seperti perbankan maka setiap orang yang mengumpulkan sampah bisa disebut sebagai nasabah bank sampah.
Nasabah bank yang ingin mengumpulkan sampah pada bank sampah.
Belakangan ini minat masyarakat menjadi nasabah bank sampah meningkat.
Selain menawarkan sistem pembuangan sampah yang teratur, dengan adanya bank sampah ini diminati karena dapat menghasilkan uang.
Antusias masyarakat yang tinggi berbalik dengan keadaan masyarakat yang menjadi nasabah bank Hal yang menjadi kendala masyarakat tidak kurun menjadi nasabah bank sampah meski memiliki minat karena selama ini untuk menjadi nasabah bank sampah masyarakat harus mengumpulkan sampah sendiri dan menyetornya ke pihak Ada juga yang menawarkan persebaran nasabah di berbagai tempat maka proses penjemputan yang dilakukan bank sampah kurang optimal.
Proses pengumpulan sampah ini haruslah dilakukan secara optimal agar tujuan dari dibentuknya bank sampah dapat tercapai dan pertumbuhan nasabah bank sampah meningkat.
Maka untuk mengatasi masalah penjemputan sampah dilakukan pencarian rute terbaik untuk distribusi bank sampah menggunakan Travelling Salasmen Problem (TSP).
Distribusi bank sampah dengan rute terbaik akan mengumpulkan sampah secara optimal sehingga nasabah dapat dilayani dengan baik dan sampah terdistribusi lebih cepat.
TINJAUAN PUSTAKA
Algoritma Genetika Algoritma genetika dimulai dengan pembentukan sejumlah alternatif pemecahan yang disebut populasi.
Pembentukan populasi awal dalam algoritma genetika dilakukan secara acak.
Dalam populasi tersebut terdapat anggota populasi yang disebut dengan kromosom, yang berisikan informasi solusi dari sekian banyak alternatif solusi masalah yang dihadapi.
Kromosom-kromosom akan mengalami evolusi melalui sejumlah iterasi yang disebut Dalam setiap perjalanan proses generasi, kromosom- kromosom tersebut akan dievaluasi menggunakan suatu fungsi yang disebut dengan fungsi obyektif.
Setiap kromosom- kromosom yang baru yang dibentuk dari generasi sebelumnya dengan menggunakan operator reproduksi, kawin silang dan mutasi.
Kromosom- kromosom yang mempunyai nilai obyektif yang baik akan memiliki probabilitas yang lebih tinggi untuk terseleksi.
Setelah beberapa kali algoritma genetika akan menunjukkan kromosom yang terbaik, yang diharapkan merupakan solusi yang optimal ataupun mendekati optimal dari problem yang Hal lain yang perlu diperhatikan adalah representasi kromosom yaitu bagaimana mengkodekan suatu alternatif solusi itu menjadi kromosom yang akan .
Proses reproduksi merupakan suatu proses untuk membentuk keturunan baru dengan mewariskan sifat-sifat yang sama dari kromosom induk.
Proses reproduksi sebenarnya merupakan proses duplikasi dan tidak menghilangkan sifat kromosom induk yang lama.
Hal ini dilakukan dalam proses algoritma genetika untuk menjaga sifat-sifat induk yang baik tidak akan hilang begitu saja.
Algoritma genetika akan kehilangn kemampuan untuk belajar dari pencarian- pencarian sebelumnya.
Proses kawin silang memerlukan dua kromosom induk.
Proses ini dilakukan dengan menukar sebagian informasi pada kromosom induk pertama dengan informasi dari kromosom induk kedua.
Parameter yang penting dalam proses kawin silang adalah crossover rate yang merupakan nilai perbandingan jumlah kromosom yang diharapkan akan mengalami kawin silang terhadap jumlah kromosom dalam satu Crossover rate yang tinggi akan memungkinkan pencapaian alternatif solusi yang lebih bervariasi dan mengurangi kemungkinan menghasilkan nilai optimum yang tidak dikehendaki.
Tetapi bila nilai ini pemborosan waktu untuk melakukan perhitungan di daerah solusi yang tidak menjanjikan hasil yang optimal.
Supriana.
Pencarian Rute Terbaik Untk Distribusi Bank Sampah Menggunakan.
Proses mutasi merupakan salah satu dari operator genetika untuk menghasilkan perubahan acak pada satu kromosom.
Cara termudah untuk melakukan mutasi adalah dengan mengubah satu atau lebih bagian dalam kromosom dan hal ini tergantung pada mutation rate.
Mutation rate menentukan probabilitas jumlah bit di dalam satu populasi yang diharapkan mengalami Proses seleksi adalah proses evolusi yang menghasilkan generasi baru dari generasigenerasi sebelumnya.
Generasigenerasi yang baru dapat terdiri dari kromosomkromosominduk dan turunan.
Metode seleksi pada algoritma genetika ada RouletteWheel.
Elitism.
Sigma Scaling.
Boltzmann.
Rank Selection.
Tournament Selection.
Steady-State Selection, dan gabungan dari metode metode tersebut.
Gambar 1.
Alur Proses Algoritma Genetika
TSP
permasalahan ini menjadi tidak mudah.
Pada Gambar 1 terdapat tujuh kota yang Travelling Salesman Problem akan dilalui salesman dan satu titik Menurut Manggolgo et al.
didefinisikan sebagai rute awal dan rute Travelling Salesman Problem merupakan akhir perjalanan.
Untuk mencari rute permasalahan optimasi untuk mencari rute terpendek, terlebih dahulu harus diketahui terpendek bagi pedagang keliling .
ravelling jarak masing-masing titik.
Namun jika jarak salesma.
yang ingin mengunjungi beberapa masing-masing titik belum diketahui, dapat Travelling Salesman Problem merupakan topik yang banyak menarik digunakan koordinat masing-masing titik.
perhatian ahli matematika karena mudah Banyaknya kombinasi alur seiring dengan banyaknya kota yang Gambar 2.
Titik-titik kota yang dilwati 203 Jurnal Teknologi Informasi dan Komputer.
Volume 3.
Nomor 02.
Oktober 2017 Setelah jarak yang menghubungkan semua kota diketahui maka jarak terpendek dapat diketahui dengan mencoba semua kombinasi dan menjumlahkan jarak dari semua kombinasi tersebut.
Setelah itu, maka akan didapatkan jarak seperti pada Gambar 2 dbawah ini.
Gambar 3 Rute Terpendek Data Data diambil dari waktu tempuh dan pelayanan 9 lokasi pos bank sampah di daerah Denpasar.
Waktu pelayanan setiap pos bank sampah 30 menit.
Jadi input pada sistem merupakan waktu tempuh ditambah lama pelayanan.
Berikut tabel yang menggambarkan waktu tempuh setiap pos bank sampah.
Tabel 1.
Data Waktu Tempuh Bank Sampah Data kedua diambil dari jarak antar pos sampah yang ada di Denpasar dalam satuan Berikut menggambarkan jarak setiap pos bank Supriana.
Pencarian Rute Terbaik Untk Distribusi Bank Sampah Menggunakan.
Tabel 2.
Data Waktu Tempuh Bank Sampah
DESAIN
SISTEM
ALGORITMA
GENETIKA
Algoritma genetika merupakan suatu metode pencarian yang didasarkan pada mekanisme dari seleksi dan genetika natural.
Adapun tahapan-tahapan sistempencarian rute terbaik distribusi bank sampah menggunakan Travelling Salesman Problem (TSP) adalah sebagai Inisialisasi Populasi Algoritma genetika membangkitkan secara acak sejumlah individu sebagai suatu Inisialisasi populasi dilakukan dengan menentukan jumlah kromosom dalam setiap populasi.
Jumlah kromosom dalam permasalahan ini adalah 9, yaitu jumlah banyaknya pos bank sampah di Kota Denpasar.
Setiap direpresentasikan dengan angka 1-9.
Adapun representasi kromosom adalah sebagai berikut:
K1 = [ 3 1 7 8 5 2 4 6 9 ]
K2 = [ 8 2 5 4 3 9 1 7 6 ]
Evaluasi Individu Evaluasi individu dilakukan dengan menghitung nilai fitness.
Pada kasus ini nilai fitness ditentukan dengan mengukur waktu dan jarak yang harus dilalui dalam satu rute perjalanan bank sampah.
Fitness1 = total waktu Fitness2 = total jarak = .
9 1 2 6 4 5 7 .
Fitness = 51 45 46 36 47 38 37 43 Fitness = 333 Seleksi Roulette Wheel Seleksi roulette wheel merupakan seleksi yang memberikan kesempatan lebih besar bagi anggota populasi yang memiliki nilai fitness tinggi untuk melakukan Berikut ini adalah algoritma seleksi roulette wheel:
Hitung total nilai fitness .
Hitung probabilitas tiap individu.
Bangkitkan nilai acak 1-100 sebanyak populasi individu.
Perhitungan probabilitas setiap kromosom dapat dihitung dengan rumus:
K1 = total seluruh nilai fitness kromosom * 100 / nilai fitness K1 Pembangkitan Nilai Acak Bangkitkan nilai acak sebanyak populasi individu.
Pembangkitan nilai acak seperti berikut:
K1 Random 05 = K2 K2 Random 09 = K2 K3 Random 15 = K3 K4 Random 18 = K1 K5 Random 44 = K3 Crossover (Pindah Silan.
Crossover atau rekombinasi dilakukan apabila probabilitas crossover .
> nilai random yang dibangkitkan.
Setelah kondisi pc > random terpenuhi lakukan pemilihan Seandainya nilai random yang dibangkitkan adalah K3 dan K7.
Maka probabilitas crossover .
> nilai random yang Lakukan crossover dengan sepasang orang tua acak yaitu K3 dan K7.
Crossover yang digunakan ialah one Point Crossover.
Pada 205 Jurnal Teknologi Informasi dan Komputer.
Volume 3.
Nomor 02.
Oktober 2017 dengan memisahkan suatu string menjadi dua bagian dan selanjutnya salah satu bagian dipertukarkan dengan salah satu bagian dari string yang lain yang telah dipisahkan dengan cara yang Proses yang demikian dinamakan operator crossover satu titik.
Misalkan:
Induk 1: 39126 | 4578 Induk 2: 34725 | 8196 Diperoleh:
Anak 1: 39126 | 8647 Anak 2: 34725 | 8916 Elitsm Penentuan elitsm yang merupakan banyak berapa individu minimal yang nantinya tetap terjaga dan digunakan pada generasi selanjutnya.
Elitism digunakan karena tidak selamanya individu bernilai fitness tinggi terpilih.
Pada kasus ini elitsm yang digunakan adalah 2 agar random terhadap calon orang tua baru memiliki probabilitas yang lebih tinggi.
Mutasi Mutasi dilakukan apabila probabilitas mutasi .
> random yang Misalkan dibangkitkan suatu nilai random dan nilai random tersebut lebih kecil atau sama dengan nilai pm maka Mutasi digunakan ialah Permutation Encoding Order dengan memilih dua nilai dari gen dan menukarnya, contoh :
( 1 2 3 4 5 8 9 7 ) => ( 1 8 3 4 5 6 2 9 7 )
Populasi Baru Populasi populasi lama dalam proses iterasi .
romosom hasil seleksi, kromosom hasil crossover, kromosom hasil mutas.
Populasi baru merupakan hasil dari generasi yang HASIL DAN PEMBAHASAN Dari proses pencarian rute terbaik distribusi bank sampah menggunakan TSP pada sistem, hal pertama yang diinput ialah data berupa waktu dan jarak antar pos, jumlah populasi, generasi dan elitsm.
Setelah itu sistem akan menunjukkan pada generasi ke berapa rute terbaik untuk pendistribusian bank sampah di Denpasar.
Rute terbaik didapatkan apabila nilai fitness dan probabilitas seleksi roulette pada generasi tertentu sudah sama.
Berikut tampilan sistem dalam proses pencarian rute menggunakan TSP.
Gambar 4.
Tampilan Awal Sistem Supriana.
Pencarian Rute Terbaik Untk Distribusi Bank Sampah Menggunakan.
Gambar 5.
Tampilan Input Populasi.
Generasi dan Elitsm Gambar 4.
Tampilan Hasil Rute Terbaik Distribusi Bank Sampah Menggunakan TSP 207 Jurnal Teknologi Informasi dan Komputer.
Volume 3.
Nomor 02.
Desember 2017 Berdasarkan gambar 5 dapat dilihat hasil rute terbaik distribusi bank sampah menggunakan TSP studi kasus kota Denpasar ialah dengan waktu 331 menit dan roulette 10 % dengan rute pos 738916452 yaitu Renon.
Sanur Kauh.
Sanur.
Serangan.
Pemogan.
Pedungan.
Sidakarya Panjer.
Sanur Kaja.
Rute terbaik distribusi bank sampah menggunakan TSP studi kasus kota Denpasar ditemukan pada generasi ke 6.
SIMPULAN
Berdasarkan dari hasil penelitian dan hasil pengujian dengan sistem yang telah dibuat oleh penulis maka dihasilkan beberapa kesimpulan diantara lain:
A Pencarian rute terbaik distribusi bank sampah studi kasus kota Denpasar menggunakan Travelling Salesman Problem (TSP).
A Hasil dari penelitian pencarian rute terbaik distribusi bank sampah menggunakan Travelling Salesman Problem (TSP) menunjukkan rute terbaik yang harus dilalui bank sampah kota Denpasar pada generasi ke 6 dengan waktu tempuh 331 menit.
A Waktu merepresentasikan kromosom dan menghasilkan rute yang lebih DAFTAR PUSTAKA