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

Islami, Miftahul Firdaus (2018) Algoritma branch and bound untuk traveling salesman problem with interval data / Miftahul Firdaus Islami. Diploma thesis, Universitas Negeri Malang.

Full text not available from this repository.

Abstract

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 [𝑢𝑖𝑗,𝑙𝑖𝑗] dengan 0≤𝑙𝑖𝑗≤ 𝑢𝑖𝑗 untuk semua 𝑖,𝑗 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 𝑈 yang melewati semua titik di Skenario 𝑈 dan kembali ke titik awal dimana Skenario 𝑈 didefinisikan dengan skenario yang semua bobot sisinya merupakan batas atas dari interval [𝑢𝑖𝑗,𝑙𝑖𝑗] dan tour terpendek di Skenario 𝑆(𝑑) yang melewati semua titik di Skenario 𝑆(𝑑) dan kembali ke titik awal dimana Skenario 𝑆(𝑑) didefinisikan dengan skenario yang semua bobot sisi yang dilarangnya merupakan batas bawah dari interval [𝑢𝑖𝑗,𝑙𝑖𝑗], 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.

Item Type: Thesis (Diploma)
Subjects: Q Science > QA Mathematics
Divisions: Fakultas Matematika dan IPA (FMIPA) > Jurusan Matematika (MAT) > S1 Matematika
Depositing User: Users 2 not found.
Date Deposited: 29 Aug 2018 04:29
Last Modified: 09 Sep 2018 03:00
URI: http://repository.um.ac.id/id/eprint/17564

Actions (login required)

View Item View Item