Mangdhuroh, Ana Hamimatul Mangdhuroh (2024) Studi algoritma cheapest insertion heuristic pada travelling salesman problem with time windows (tsptw) untuk mencari rute optimal / Ana Hamimatul Mangdhuroh</p>. Diploma thesis, Universitas Negeri Malang.
Full text not available from this repository.Abstract
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.
| Item Type: | Thesis (Diploma) |
|---|---|
| Divisions: | Fakultas Matematika dan IPA (FMIPA) > Departemen Matematika (MAT) > S1 Matematika |
| Depositing User: | library UM |
| Date Deposited: | 05 Jul 2024 04:29 |
| Last Modified: | 09 Sep 2024 03:00 |
| URI: | http://repository.um.ac.id/id/eprint/352735 |
Actions (login required)
 |
View Item |