Skripsi

Penerapan metode pindah silang cycle crossover untuk Travelling Salesman Problem (TSP) / Rina Uktafiya

Abstrak
Kata Kunci Graph Travelling Salesman Problem (TSP) Metode Pindah Silang Cycle Crossover Metode Pindah Silang Partial Mapped Crossover Dalam ilmu matematika khususnya Teori Graph permasalahan optimasi rute kendaraan dikenal dengan Travelling Salesman Problem (TSP). TSP adalah suatu perjalanan salesman dari suatu depot ke n-outlet tepat satu kali dan kembali depot tersebut dengan jarak yang minimum. TSP dapat diterapkan pada graph komplit berbobot yang memiliki total bobot sisi minimum. Rute pada TSP ini memuat semua outlet pada graph tersebut. Banyak algoritma yang digunakan untuk menyelesaikan TSP salah satunya yaitu Algoritma Genetika. Terdapat beberapa tahap untuk menyelesaikan Algoritma Genetika yaitu tahap inisialisasi (pencarian rute) tahap evaluasi (pembobotan) tahap seleksi (pemilihan) tahap crossover (pindah silang) dan tahap mutasi (menukar outlet antar rute). Dalam Algoritma Genetika pada tahap crossover terdapat beberapa metode lagi diantaranya yaitu Metode Cycle Crossover (CX) dan Partial Mapped Crossover (PMX). Metode CX ini merupakan metode crossover dimana cara kerjanya dengan mengkopi outlet-outlet dari satu rute dan memilih outlet-outlet yang lain dari rute lainnya dengan mengingat pola cycle (rute). Sedangkan metode PMX merupakan metode persilangan dua outlet ditambah dengan prosedure perbaikan yaitu adanya hubungan pemetaan antara kedua rute. Dari dua hasil uji coba untuk beberapa titik dapat diketahui bahwa rute dan jarak yang dihasilkan oleh kedua metode yaitu Metode CX dan Metode PMX adalah berbeda. Perbedaan ini dikarenakan adanya proses pada pemilihan outlet yang dicrossover tidak sama dan dilakukan secara acak. Agar lebih mudah untuk menyelesaikan permasalahan TSP penerapan Metode CX dan PMX pada crossover ini akan diaplikasikan dalam program komputer menggunakan Borland Delphi 7.0.

Informasi Detail

DDC

Rs 511.5 UKT p

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2012.

Deskripsi Fisik

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

Bahasa

Indonesia

No Reg

04491/KI/12

Edisi

Skripsi ( Sarjana )--Universitas Negeri Malang, 2012

Subjek

1. TEORI GRAPH
2. TRAVELLING SALESMAN PROBLEM

Pembimbing

1. Sapti Wahyiningsih ; 2 Mohammad Yasin

Lampiran Berkas