Penyelesaian Travelling Salesman Problem menggunakan algoritma Hungaria dan algoritma Hill Climbing (HC)

Lestari, Adelia (2022) Penyelesaian Travelling Salesman Problem menggunakan algoritma Hungaria dan algoritma Hill Climbing (HC). Sarjana thesis, UIN Sunan Gunung Djati Bandung.

[img]
Preview
Text (COVER)
1_cover.pdf

Download (112kB) | Preview
[img]
Preview
Text (ABSTRAK)
2_abstrak.pdf

Download (68kB) | Preview
[img]
Preview
Text (DAFTAR ISI)
3_daftarisi.pdf

Download (58kB) | Preview
[img]
Preview
Text (BAB I)
4_bab1.pdf

Download (165kB) | Preview
[img] Text (BAB II)
5_bab2.pdf
Restricted to Registered users only

Download (342kB) | Request a copy
[img] Text (BAB III)
6_bab3.pdf
Restricted to Registered users only

Download (280kB) | Request a copy
[img] Text (BAB IV)
7_bab4.pdf
Restricted to Registered users only

Download (2MB) | Request a copy
[img] Text (BAB V)
8_bab5.pdf
Restricted to Registered users only

Download (53kB) | Request a copy
[img] Text (DAFTAR PUSTAKA)
9_daftarpustaka.pdf
Restricted to Registered users only

Download (122kB) | Request a copy

Abstract

Penelitian ini dilatarbelakangi oleh Travelling Salesman Problem (TSP) yang merupakan salah satu bagian dari pemrograman linear yang sering dijumpai di kehidupan sehari-hari. Pada umumnya, masalah ini memetakan penjual dalam menjajakan barang dagangannya untuk mengunjungi setiap kota tepat satu kali dan kembali ke kota awal, dengan memperhatikan biaya atau jarak atau waktu perjalanan minimum. Algoritma Hungaria dan Algoritma Hill Climbing merupakan contoh algoritma yang dapat digunakan untuk menyelesaikan masalah tersebut. Tujuan dari penelitian ini adalah untuk dapat mengoptimalkan urutan perjalanan dari satu kota ke kota yang lain sehingga dapat meminimalkan total biaya atau jarak atau waktu yang ditempuh oleh seorang penjual. Algoritma Hungaria merupakan algoritma untuk menemukan solusi optimal dengan cara mengurangi entri terkecil dari setiap baris dan kolom dari semua entri baris dan kolom, lalu menarik garis seminimal mungkin untuk menutupi entri nol. Sedangkan Algoritma Hill Climbing merupakan algoritma untuk menemukan solusi optimal dengan cara membentuk lintasan awal sebagai keadaan awal (initial state), kemudian dilakukan pengujian dari keadaan awal tersebut, lalu dilakukan kombinasi pertukaran dua kota hingga mencapai kondisi goal. Kondisi goal terjadi saat panjang jalur baru < panjang jalur lama. Pada penelitian ini digunakan versi Simple Hill Climbing dan Steepest-Ascent Hill Climbing. Terdapat tiga contoh kasus data yang diperiksa oleh Algoritma Hungaria dan Algoritma Hill Climbing, yaitu data berukuran 10x10, 12x12 dan 16x16. Pada contoh kasus 10x10 dan 12x12 dihasilkan solusi optimal dengan nilai yang lebih kecil pada Algoritma Hill Climbing. Hasilnya diperoleh bahwa Algoritma Hill Climbing lebih baik dibandingkan dengan Algoritma Hungaria dalam menentukan solusi optimal dari Travelling Salesman Problem.

Item Type: Thesis (Sarjana)
Uncontrolled Keywords: Optimasi; Pemrograman Linear; Travelling Salesman Problem; Algoritma Hungaria; SHC; SAHC
Subjects: Applied mathematics
Applied mathematics > Mathematical Optimization
Applied mathematics > Special Topics of Applied Mathematics
Divisions: Fakultas Sains dan Teknologi > Program Studi Matematika
Depositing User: Adelia Lestari
Date Deposited: 12 Sep 2022 13:37
Last Modified: 12 Sep 2022 13:37
URI: https://etheses.uinsgd.ac.id/id/eprint/56332

Actions (login required)

View Item View Item