Publisher

IOINFORMATICIOINFORMATIC

Journal JUKI : Jurnal Komputer dan InformatikaJUKI : Jurnal Komputer dan Informatika Abstract

Penentuan rute perjalanan yang efisien menjadi tantangan penting dalam berbagai sistem logistik, terutama ketika jumlah lokasi yang harus dikunjungi semakin besar. Traveling Salesman Problem telah lama digunakan sebagai model dasar untuk permasalahan tersebut, namun sifatnya yang berskala NP-hard membuat metode eksak kurang efektif pada dataset berukuran menengah hingga besar. Penelitian ini mengeksplorasi penggunaan Genetic Algorithm yang dipadukan dengan teknik local search 2-opt untuk meningkatkan kualitas solusi. Dataset yang digunakan terdiri dari 49 kota di Inggris, dengan jarak antar kota dihitung menggunakan Euclidean Distance. Dua konfigurasi diuji, yaitu Genetic Algorithm Normal dengan local search menyeluruh dan Genetic Algorithm Cepat dengan mekanisme perbaikan minimal. Hasil eksperimen menunjukkan bahwa Genetic Algorithm Normal mampu menghasilkan rute yang lebih optimal dengan jarak terpendek sekitar 305,004, meskipun waktu komputasinya lebih lama dibandingkan Genetic Algorithm Cepat. Sementara itu, Genetic Algorithm Cepat memberikan hasil yang kurang optimal yaitu sekitar 312,630, namun dengan waktu pemrosesan jauh lebih singkat. Temuan ini menegaskan bahwa integrasi local search dalam Genetic Algorithm memberikan peningkatan signifikan pada kualitas rute, dan pemilihan konfigurasi bergantung pada kebutuhan—apakah mengutamakan kualitas solusi atau efisiensi waktu komputasi.

Conclusion

Penelitian ini menunjukkan bahwa penerapan Genetic Algorithm yang dipadukan dengan local search 2-opt mampu meningkatkan kualitas solusi pada permasalahan Traveling Salesman Problem dengan 49 kota di Inggris.GA Normal yang dilengkapi mekanisme perbaikan lokal secara selektif menghasilkan rute terbaik dengan jarak sekitar 305,004, lebih optimal dibandingkan GA Cepat yang hanya mencapai sekitar 312,630.Dengan demikian, pemilihan konfigurasi GA perlu disesuaikan dengan kebutuhan.apakah menekankan kualitas solusi atau kecepatan pemrosesan.

Future Research

Penelitian lanjutan dapat difokuskan pada eksplorasi teknik metaheuristik lain seperti simulated annealing atau tabu search, serta penggabungannya dengan strategi local search yang lebih canggih seperti 3-opt atau Lin-Kernighan. Selain itu, pengujian algoritma pada dataset yang lebih besar atau berbasis kondisi nyata, seperti jarak jalan sebenarnya, akan memberikan wawasan yang lebih aplikatif. Lebih lanjut, studi komparatif yang melibatkan berbagai variasi algoritma dan parameter optimasi dapat membantu mengidentifikasi konfigurasi terbaik untuk berbagai skenario permasalahan TSP, sehingga menghasilkan solusi yang lebih robust dan efisien dalam konteks praktis.

References

1. Perbandingan Algoritma Cheapest Insertion Heuristic Dan Nearest Neighbor Dalam Menyelesaikan Traveling... doi.org/10.55606/jurrimipa.v2i2.1614Perbandingan Algoritma Cheapest Insertion Heuristic Dan Nearest Neighbor Dalam Menyelesaikan Traveling doi 10 55606 jurrimipa v2i2 1614
2. [1409.3078] An improved genetic algorithm with a local optimization strategy and an extra mutation level... doi.org/10.48550/ARXIV.1409.30781409 3078 An improved genetic algorithm with a local optimization strategy and an extra mutation level doi 10 48550 ARXIV 1409 3078
3. [1911.01966] A Memetic Algorithm Based on Breakout Local Search for the Generalized Travelling Salesman... doi.org/10.48550/ARXIV.1911.019661911 01966 A Memetic Algorithm Based on Breakout Local Search for the Generalized Travelling Salesman doi 10 48550 ARXIV 1911 01966

Metadata

File size	4.19 MB
Pages	7
DMCA	Report