Skripsi

Algoritma hybrid simulated annealing and tabu search untuk traveling salesman problem with time windows dan implementasinya / Ai Septy Sitoresmi

Abstrak
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.

Informasi Detail

DDC

Rs 518.1 SIT a

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2021.

Deskripsi Fisik

viii, 111 lembar : il. ; 30 cm.

Bahasa

Indonesia

No Reg

01065/KI/22

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang. 2021

Subjek

1. ALGORITMA - HYBRID SIMULATED ANNEALING AND TABU SEARCH
2. ALGORITHM - HYBRID SIMULATED ANNEALING AND TABU SEARCH

Pembimbing

1. Toto Nusantara ; 2. Mochammad Hafiizh

Lampiran Berkas