Skripsi

Studi algoritma cheapest insertion heuristic pada travelling salesman problem with time windows (tsptw) untuk mencari rute optimal / Ana Hamimatul Mangdhuroh

Abstrak
TSPTW merupakan salah satu varian dari TSP yaitu permasalahan semua kota dikunjungi oleh salesman dimana setiap kota dikunjungi hanya tepat sekali dalam satu perjalanan memiliki dan titik awal dan titik akhir yang sama dengan adanya penambahan time windows. Algoritma Cheapest Insertion Heuristic (CIH) disebut juga algoritma penyisipan dimana menyisipkan kota yang belum terlewati dengan tambahan jarak minimum hingga semua daerah terlewati. Penghitungan pada algoritma ini dengan jumlah tempat yang dikunjungi relatif banyak masih stabil untuk digunakan. Penelitian ini menggunakan data rute angkutan kota Malang jalur AMG. Rute optimal yang dihasilkan 0 ndash 3 ndash 9 ndash 11 ndash 14 ndash 13 ndash 12 ndash 10 ndash 5 ndash 4 ndash 8 ndash 7 ndash 6 ndash 2 ndash 1 ndash 0 dengan jarak 29.70 km dan waktu 165 menit. Selanjutnya pada penelitian ini juga membandingkan algoritma CIH dengan algoritma Nearest Neighbor dan Algoritma Clarke Wright dengan perbaikan local search dari penelitian terdahulu. Setelah dibandingkan algoritma Nearest Neighbor dengan perbaikan local search diperoleh total jarak 23 km dan waktu 93 menit algoritma Clarke Wright dengan perbaikan local search diperoleh total jarak 31 km dan waktu 101 menit sedangkan algoritma CIH diperoleh total jarak 22 km dengan waktu 92 menit. Solusi menggunakan algoritma CIH lebih efektif untuk digunakan mencari rute optimal dari pada kedua algoritma tersebut.

Informasi Detail

DDC

SKRIPSI DIGITAL

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2024.

Deskripsi Fisik

xi, 61 hlm. : ilus.

Bahasa

Indonesia

No Reg

2998/RS/24

Edisi

Skripsi (Sarjana)--Universitas Negeri Malang. 2024

Subjek

1. ALGORITMA - MENCARI RUTE
2. ALGORITMA - TRAVELLING SALESMAN
3. ALGORITHM - FINDING A ROUTE

Pembimbing

1. Prof. Dr. Toto Nusantara, M.si; 2. Lucky Tri Oktoviana, S.si, M.kom

Lampiran Berkas