Skripsi

Penerapan algoritma genetika dalam penyelesaian Travelling Salesman Problem with Precedence Constraints (TSPPC) / Yayun Hardianti

Abstrak
Hardianti Yayun. 2013. Penerapan Algoritma Genetika dalam Penyelesaian Travelling Salesman Problem with Precedence Constraints (TSPPC). Skripsi Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Pembimbing Prof. Drs. Purwanto Ph.D. Kata Kunci Algoritma Genetika Travelling Salesma Problem With Precedence Constraints (TSPPC) Travelling Salesam Problem (TSP) merupakan permasalahan seorang sales yang harus mengunjungi beberapa kota dan harus melalui setiap kota tersebut tepat satu kali dan kembali lagi ke kota awal dengan jarak tempuh dan biaya minimal. Permasalahn TSP selama ini hanya melihat jarak antara depot dengan pelanggan atau antar pelanggan saja padahal pada kenyataanya permasalahan distribusi tidak hanya pada jarak tetapi juga adanya urutan titik yang harus dikunjungi terlebih dahulu sebelum titik yang lain. Untuk memecahkan masalah tersebut TSP dikembangkan menjadi TSPPC atau Travelling Salesman Problem with Precedence Constraints. TSPPC merupakan permasalahan untuk mencari perjalanan terpendek melalui semua titik dan tiap titik dilewati tepat satu kali dengan tambahan kendala yaitu adanya urutan titik yang harus dikunjungi terlebih dahulu (precedence constraints). TSPPC dapat dimodelkan dalam bentuk graph network. Dengan titik sebagai kota dan sisi berarah sebagai precedence relation. Salah satu metode yang digunakan dalam menyelesaiakan TSPPC adalah dengan menggunakan algoritma genetika. Algoritma genetika adalah algoritma pencarian heuristik yang didasarkan atas mekanisme evolusi biologis.Tahapan penyelesaian TSPPC dengan algoritma genetika yaitu tahap inisialisasi (pembentukan populasi awal) tahap perhitungan nilai fitnes tahap pemilihan (seleksi) dengan Roullete Wheel tahap pindah silang dengan moon crossover dan tahap mutasi (swapping mutation). Untuk mengatasi precedence constraints algoritma genetika digabungkan dengan konsep topological sort dalam menentukan lintasan yang fisibel. Topological sort adalah teknik mengurutkan titik-titik pada graph berarah sedemikian sehingga jika terdapat lintasan dari vi ke vj maka vj dilalui setelah vi . Untuk memudahkan dalam mencari penyelesaian TSPPC terutama saat harus mengunjungi banyak kota algoritma genetika diimplementasikan dalam bahasa pemrograman Borland Delphi 7. Dari hasil analisis didapat bahwa algoritma genetika yang digabungkan dengan konsep topological sort mampu manghasilkan lebih dari satu alternative solusi untuk TSPPC. Perhitungan secara manual menunjukkan algoritma genetika mampu menyelesaikan permasalahan TSPPC dengan 6 dan 10 titik. Perhitungan dengan menggunakan program GA-TSPPC mampu menyelesaikan permasalahan TSPPC 50 titik dan 20 generasi

Informasi Detail

DDC

Rs 519.62 HAR p

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2013.

Deskripsi Fisik

x, 143 lembar : il., tab. ; 30 cm

Bahasa

Indonesia

No Reg

02770/KI/13

Edisi

Skripsi ( Sarjana )--Universitas Negeri Malang, 2013

Subjek

1. ALGORITMA GENETIKA

Pembimbing

1. Purwanto

Lampiran Berkas