Uktafiya, Rina (2012) Penerapan metode pindah silang cycle crossover untuk Travelling Salesman Problem (TSP) / Rina Uktafiya. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
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.
| Item Type: | Thesis (Diploma) |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Fakultas Matematika dan IPA (FMIPA) > Departemen Matematika (MAT) > S1 Matematika |
| Depositing User: | library UM |
| Date Deposited: | 23 Oct 2012 04:29 |
| Last Modified: | 09 Sep 2012 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/17155 |
Actions (login required)
 |
View Item |