Skripsi

Algoritma branch and bound untuk traveling salesman problem with interval data / Miftahul Firdaus Islami

Abstrak
i RINGKASAN Islami Miftahul. F. 2018. Algoritma Branch and Bound untuk Travelling Salesman Problem with Interval Data. Skripsi Jurusan Matematika FMIPA Universitas Negeri Malang. Pembimbing Prof.Dr.Toto Nusantara M.Si. Kata Kunci Travelling Salesman Problem with Interval Data Algoritma Branch and Bound Algoritma Nearest Neighbour Heuristic Algoritma Cheapest Insertion Heuristic. Travelling Salesman Problem with interval data merupakan suatu permasalahan pencarian sikel Hamilton dengan bobot minimum dimana graph yang digunakan untuk merepresentasikan permasalahan mempunyai bobot yang berupa suatu interval [ 119906 119894 119895 119897 119894 119895 ] dengan 0 8804 119897 119894 119895 8804 119906 119894 119895 untuk semua 119894 119895 anggota himpunan titik pada Graph. Algoritma Branch and Bound adalah salah satu algoritma yang digunakan untuk menyelesaikan permasalahan Travelling Salesman Problem dengan data interval. Dalam algoritma ini juga dibutuhkan algoritma tambahan seperti Nearest Neighbour Heuristic dan Cheapest Insertion Heuristic. Tujuan penelitian ini adalah mengkaji ulang penyelesaian Travelling Salesman Problem dengan data interval data dengan menggunakan Algoritma Branch and Bound serta mengkaji dan menganalisis penggunaan algoritma tambahan yaitu Neighbour Heuristic dan Cheapest Insertion Heuristic untuk mencari tour terpendek di Skenario 119880 yang melewati semua titik di Skenario 119880 dan kembali ke titik awal dimana Skenario 119880 didefinisikan dengan skenario yang semua bobot sisinya merupakan batas atas dari interval [ 119906 119894 119895 119897 119894 119895 ] dan tour terpendek di Skenario 119878 ( 119889 ) yang melewati semua titik di Skenario 119878 ( 119889 ) dan kembali ke titik awal dimana Skenario 119878 ( 119889 ) didefinisikan dengan skenario yang semua bobot sisi yang dilarangnya merupakan batas bawah dari interval [ 119906 119894 119895 119897 119894 119895 ] dan bobot sisi lainnya adalah batas atas. dalam Algoritma Branch and Bound. Dalam perbandingan penggunaannya dapat diketahui bahwa penggunaan Nearest Neighbour Heuristic dalam Algoritma Branch and Bound menghasilkan hasil yang lebih minimum dibandingkan Cheapest Insertion Heuristic.

Informasi Detail

DDC

Rs 511.6 ISL a

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2018.

Deskripsi Fisik

viii, 95 lembar : il. , tab. ; 30 cm

Bahasa

Indonesia

No Reg

04849/KI/18

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang. 2018

Subjek

1. ALGORITMA BRANCH - PENERAPAN
2. GRAPH, TEORI
3. BRANCH ALGORITHM - APPLICATION

Pembimbing

1. Toto Nusantara

Lampiran Berkas