Ai Septy Sitoresmi (2021) algoritma hybrid simulated annealing and tabu search untuk traveling salesman problem with time windows dan implementasinya / ai septy sitoresmi. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
Tujuan dari penelitian ini yaitu mengusulkan algoritma hybrid SA/TS baru untuk varian TSPTW yang tersusun dari dua algoritma yaitu algoritma Simulated Annealing (SA) dan algortima Tabu Search (TS). Algoritma hybrid SA/TS ini dipilih karena memiliki kemampuan untuk keluar dari jebakan minimum lokal. Algoritma hybrid SA/TS yang diusulkan berbeda dari yang ada sebelumnya karena menggunakan local search tambahan yaitu double-swap sehingga local search yang digunakan yaitu 1-shift 2-opt swapping dan double-swap. Implementasi algoritma hybrid SA/TS untuk TSPTW telah berhasil dibuat menggunakan bahasa pemrograman Python 3.8.8. Kemudian dilakukan uji coba program dengan beberapa data set dan dilakukan analisa hasil. Algoritma ini menghasilkan solusi yang sama dengan best known Contoh 3.3.1 dan Contoh 3.3.2 secara berturut-turut yaitu 22 km dan 60 05 km serta diperoleh solusi yang lebih minimum 1 45 km dari pada best known Contoh 3.3.3. Pengujian algoritma pada data set Gendreau n20w120 dan n40w120 diperoleh penyimpangan secara beturut-turut sebesar 0.25% dan 6.26%. Berdasarkan hasil uji coba pada beberapa data set penambahan double-swap ternyata berpengaruh terhadap solusi yang dihasilkan dan waktu komputasi yang dibutuhkan program untuk menjalankan perhitungan. Seperti pada perhitungan data acak 21 titik dengan algoritma hybrid SA/TS dengan double-swap diperoleh solusi terbaik yaitu 27 15 km dengan waktu komputasi 77 detik/iterasi sedangkan perhitungan dengan algoritma hybrid SA/TS tanpa double-swap diperoleh solusi terbaik 28 44 km dengan waktu komputasi 7 detik/iterasi. Dari hasil uji pengaruh perubahan nilai parameter Max_iter diperoleh nilai parameter terbaik Max_iter 100 untuk kasus dengan jumlah titik lebih dari 6 dan nilai parameter terbaik Max_iter 10 untuk kasus dengan jumlah titik sama dengan 6.
| Item Type: | Thesis (Diploma) |
|---|---|
| Subjects: | ?? ?? |
| Divisions: | Fakultas Matematika dan IPA (FMIPA) > Departemen Matematika (MAT) > S1 Matematika |
| Depositing User: | library UM |
| Date Deposited: | 02 Sep 2021 04:29 |
| Last Modified: | 09 Sep 2021 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/148511 |
Actions (login required)
 |
View Item |