Skripsi

Penyelesaian traveling salesman problem dengan menggunakan metode cheapest insertion heuristic / Ahmad Lutfi

Abstrak
Teori graph merupakan salah satu cabang dari ilmu matematika yang mempunyai banyak aplikasi terutama untuk membantu menyelesaikan suatu permasalahan dalam kehidupan sehari-hari. Salah satu permasalahan yang dapat diselesaikan dengan bantuan teori graph adalah Traveling Salesman Problem (TSP) yaitu permasalahan seorang salesman yang harus mengunjungi semua kota dimana tiap kota hanya dikunjungi sekali dan dia harus mulai dari dan kembali ke kota asal. Tujuannya adalah menentukan rute dengan jarak yang paling minimum. Salah satu teknik yang digunakan untuk mempercepat pencarian solusi masalah TSP adalah dengan teknik heuristic. Heuristic adalah seni dan ilmu menemukan. Heuristic tidak selalu dapat memecahkan masalah tetapi sering kali memecahkan masalah dengan cukup baik dan lebih cepat dari pencarian solusi secara lengkap karena teknik heuristic bertujuan untuk mengurangi jumlah pencarian solusi Salah satu algoritma dalam heuristic yang cukup efektif digunakan untuk menyelesaiakan masalah TSP adalah algoritma penyisipan. Dalam algoritma penyisipan terdapat beberapa metode salah satunya adalah metode cheapest insertion heuristic yang dibahas pada skripsi ini. Metode cheapest insertion heuristic membangun suatu tour dari sikel-sikel kecil dengan bobot minimal dan secara berturut-turut ditambah dengan titik baru. Pemilihan titik baru tersebut dilakukan bersamaan dengan pemilihan sisi sehingga didapatkan nilai penyisipan minimum. Selanjutnya titik baru tersebut disisipkan di antara dua titik yang membentuk sisi yang telah terpilih. Untuk mempermudah perhitungan maka dibuat program komputer yang dapat merepresentasikan metode tersebut dengan Borland Delphi. Pada contoh aplikasi dalam mencari rute pendistribusain barang pos dari Kantor Pos dan Giro Ponorogo ke beberapa pondok pesantren dengan metode cheapest insertion heuristic didapatkan rute dengan jarak total 1038 1 km. Dalam contoh yang lain pemilihan titik awal berpengaruh pada rute yang terbentuk. Hasil perhitungan dengan metode cheapest insertion heuristic tidak selalu menghasilkan solusi yang lebih minimum jika dibandingkan dengan metode nearest insertion heuristic farthest insertion heuristic maupun arbitrary insertion heuristic tetapi metode ini seringkali memberikan solusi yang cukup baik karena untuk proses seleksi titik yang akan disisipkan dilakukan pada setiap titik di luar tour dan setiap sisi di dalam tour.

Informasi Detail

DDC

Rs 515.39 LUT p

Prodi

Skripsi (Sarjana)--Universitas Negeri Malang. Program Studi Matematika, 2008.

Deskripsi Fisik

ix, 107 hlm : il. : tab. ; 30 cm

Bahasa

Indonesia

No Reg

01054/KI/08

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang. 2008

Subjek

1. GRAPH, TEORI
2. CHEAPEST INSERTION HEURISTIC
3. TRAVELING SALESMAN PROBLEM

Pembimbing

1. SAPTI WAHYUNINGSIH ; 2. DARMAWAN SATYANANDA

Lampiran Berkas