Pengembangan Lévy Ant Colony Optimization pada Multiple Traveling Salesman Problem

Putri, Emilia (2025) Pengembangan Lévy Ant Colony Optimization pada Multiple Traveling Salesman Problem. Sarjana thesis, UIN Sunan Gunung Djati Bandung.

Preview	Text (COVER) 1_cover.pdf Download (570kB) | Preview
Preview	Text (ABSTRAK) 2_abstrak.pdf Download (663kB) | Preview
	Text (SK BEBAS PLAGIARISM) 3_skbebasplagiarism.pdf Restricted to Repository staff only Download (345kB) | Request a copy
Preview	Text (DAFTAR ISI) 4_daftarisi.pdf Download (681kB) | Preview
Preview	Text (BAB I) 5_bab1.pdf Download (636kB) | Preview
	Text (BAB II) 6_bab2 (13).pdf Restricted to Registered users only Download (984kB) | Request a copy
	Text (BAB III) 7_bab3 (12).pdf Restricted to Registered users only Download (841kB) | Request a copy
	Text (BAB IV) 8_bab4.pdf Restricted to Registered users only Download (884kB) | Request a copy
	Text (BAB V) 9_bab5.pdf Restricted to Registered users only Download (645kB) | Request a copy
	Text (DAFTAR PUSTAKA) 10_daftarpustaka.pdf Restricted to Registered users only Download (657kB) | Request a copy
	Text (LAMPIRAN) 11_lampiran.pdf Restricted to Repository staff only Download (2MB) | Request a copy

Abstract

Multiple Traveling Salesman Problem (MTSP) merupakan salah satu bentuk perluasan dari Traveling Salesman Problem (TSP) yang mengharuskan beberapa salesman mengunjungi sejumlah kota, tanpa ada kota yang dikunjungi lebih dari satu kali dan kembali ke kota asal (depot), dengan rute yang efisien. Permasalahan ini tergolong kompleks dan termasuk ke dalam kategori masalah NP-Hard, sehingga metode eksak menjadi kurang efisien karena meningkatnya jumlah kombinasi solusi secara eksponensial. Oleh karena itu, diperlukan pendekatan metaheuristik yang mampu menyelesaikan masalah secara efisien dengan solusi yang mendekati optimal. Penelitian ini mengembangkan Algoritma Ant Colony Optimization (ACO) dengan menambahkan mekanisme Lévy Flight untuk meningkatkan kemampuan eksplorasi dalam ruang solusi. Mekanisme Lévy Flight dikenal dengan pola pergerakan acak dengan langkah besar, sehingga dapat membantu menghindari jebakan solusi lokal (eksploitasi). Selain itu, digunakan pula metode 2-Opt sebagai teknik local search yang secara efektif dapat memperbaiki solusi yang dihasilkan dengan menukar edge pada rute sehingga panjang rute menjadi berkurang. Eksperimen dilakukan menggunakan dataset dari TSPLIB dan dijalankan melalui GNU Octave. Hasil menunjukkan bahwa Algoritma Lévy ACO mampumemberikan hasil yang lebih baik dibandingkan Algoritma ACO klasik dalam hal total jarak dan kualitas rute berdasarkan masalah MTSP. Penggabungan antara ACO, Lévy Flight, dan 2-Opt terbukti efektif dalam menghasilkan solusi yang lebih optimal. Dengan demikian, pendekatan ini dapat dijadikan alternatif yang menjanjikan untuk menyelesaikan masalah Multiple Traveling Salesman Problem, serta dapat dikembangkan lebih lanjut untuk kasus optimasi rute lainnya.

Actions (login required)

View Item