Penyelesaian Asymmetric Traveling Salesman Problem Menggunakan Gabungan Algoritma Genetika dengan Algoritma Nearest Neighbor (Studi Kasus Kontrol SPBU)

Solichin, Imam Mansyur (2025) Penyelesaian Asymmetric Traveling Salesman Problem Menggunakan Gabungan Algoritma Genetika dengan Algoritma Nearest Neighbor (Studi Kasus Kontrol SPBU). Other thesis, Institut Teknologi Sepuluh Nopember.

Text 05211840000057-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only Download (1MB) | Request a copy

Abstract

Asymmetric Traveling Salesman Problem (ATSP) merupakan salah satu varian dari TSP di mana biaya perjalanan antar titik bersifat tidak simetris, sehingga lebih merepresentasikan kondisi nyata seperti arah lalu lintas satu arah. Penelitian ini mengusulkan pendekatan hibrida antara algoritma genetika (Genetic Algorithm/GA) dengan algoritma nearest neighbor (NNA) untuk menyelesaikan ATSP. Strategi ini bertujuan meningkatkan efisiensi waktu dan kualitas solusi dengan menginisialisasi populasi awal menggunakan solusi heuristik dari NNA. Evaluasi dilakukan terhadap dataset benchmark TSPLIB dan studi kasus kontrol distribusi SPBU di Surabaya. Hasil pengujian pada dataset TSPLIB menunjukkan bahwa GA-NNA mampu menghasilkan solusi dengan rerata eror sebesar 14% dibandingkan GA murni yang sebesar 33%. Waktu konvergensi GA-NNA juga lebih cepat 58% dibandingkan GA murni pada dataset benchmark. Pada studi kasus SPBU, GA-NNA mencatat peningkatan efisiensi konvergensi sebesar 29,25% dan waktu eksekusi 11,20% lebih cepat dibandingkan GA, dengan kualitas solusi yang tetap setara. Dengan demikian, GA-NNA terbukti lebih efisien dan stabil dalam menyelesaikan ATSP pada berbagai ukuran permasalahan.
==================================================================================================================================
The Asymmetric Traveling Salesman Problem (ATSP) is a variant of TSP where travel costs between nodes are not symmetrical, better reflecting real-world constraints such as one-way traffic. This research proposes a hybrid approach combining the Genetic Algorithm (GA) and Nearest Neighbor (NN) heuristic to solve ATSP instances. The hybrid GA-NNA method enhances performance by initializing the population with heuristic NN solutions to improve early convergence and solution quality. Experiments were conducted on benchmark datasets from TSPLIB and a real-world case involving fuel distribution route planning in Surabaya, Indonesia. Tests on TSPLIB datasets show that GA-NNA achieved an average error of 14%, compared to 33% for standard GA. The convergence time of GA-NNA was also 58% faster than that of standard GA on benchmark datasets. In the SPBU case study, GA-NNA achieved a 29.25% improvement in convergence efficiency and 11.20% faster execution time, while maintaining comparable solution quality. These results demonstrate that GA-NNA is more efficient and stable in solving ATSP across various problem sizes.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Genetic Algorithm, Nearest Neighbor Algorithm, Traveling Salesman Problem, Hybrid Algorithm.
Subjects:	Q Science > QA Mathematics > QA402.5 Genetic algorithms. Interior-point methods.
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Information System > 57201-(S1) Undergraduate Thesis
Depositing User:	Imam Mansyur Solichin
Date Deposited:	29 Jul 2025 06:59
Last Modified:	29 Jul 2025 06:59
URI:	http://repository.its.ac.id/id/eprint/122634

Actions (login required)

View Item