Optimasi Rute Travelling Salesman Problem pada 49 Kota di Inggris menggunakan Memetic Genetic Algorithm

Catherine  Stevani; Fitri Maya  Puspita; Sisca  Octarina

Authors

Catherine Stevani Universitas Sriwijaya Palembang
Fitri Maya Puspita Universitas Sriwijaya Palembang
Sisca Octarina Universitas Sriwijaya Palembang

Keywords:

Algoritma Genetika, Travelling Salesman Problem, Local Search 2-opt

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 (TSP) 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 (GA) 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 GA Normal dengan local search menyeluruh dan GA Cepat dengan mekanisme perbaikan minimal. Hasil eksperimen menunjukkan bahwa GA Normal mampu menghasilkan rute yang lebih optimal dengan jarak terpendek sekitar 305,004, meskipun waktu komputasinya lebih lama dibandingkan GA Cepat. Sementara itu, GA 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 GA memberikan peningkatan signifikan pada kualitas rute, dan pemilihan konfigurasi bergantung pada kebutuhan—apakah mengutamakan kualitas solusi atau efisiensi waktu komputasi.

Downloads

Download data is not yet available.

References

-[1] Y. Liu, L. Chen, and C. Huang, “Study on the Carbon Emission Spillover Effects of Transportation under Technological Advancements,” Sustainability, vol. 14, no. 17, p. 10608, Aug. 2022, doi: 10.3390/su141710608.

Rizki Putra Sinaga and Faridawaty Marpaung, “Perbandingan Algoritma Cheapest Insertion Heuristic Dan Nearest Neighbor Dalam Menyelesaikan Traveling Salesman Problem,” J. Ris. RUMPUN Mat. DAN ILMU Pengetah. ALAM, vol. 2, no. 2, pp. 238–247, July 2023, doi: 10.55606/jurrimipa.v2i2.1614.

B. Meniz and F. Tiryaki, “Genetic Algorithm Optimization with Selection Operator Decider,” Arab. J. Sci. Eng., vol. 50, no. 10, pp. 6931–6941, May 2025, doi: 10.1007/s13369-024-09068-5.

X. Wei, J. Sun, and H. Jiao, “New improved hybrid genetic algorithm for optimizing facility layout design of reconfigurable manufacturing system,” Sci. Rep., vol. 15, no. 1, p. 21416, July 2025, doi: 10.1038/s41598-025-97526-x.

V. Kralev and R. Kraleva, “Combining Genetic Algorithm with Local Search Method in Solving Optimization Problems,” Electronics, vol. 13, no. 20, p. 4126, Oct. 2024, doi: 10.3390/electronics13204126.

O. Cosma, P. C. Pop, and L. Cosma, “A novel memetic algorithm for solving the generalized traveling salesman problem,” Log. J. IGPL, vol. 32, no. 4, pp. 576–588, July 2024, doi: 10.1093/jigpal/jzae019.

K. Borna and V. H. Hashemi, “An improved genetic algorithm with a local optimization strategy and an extra mutation level for solving traveling salesman problem,” 2014, doi: 10.48550/ARXIV.1409.3078.

M. E. Krari and B. Ahiod, “A Memetic Algorithm Based on Breakout Local Search for the Generalized Travelling Salesman Problem,” 2019, doi: 10.48550/ARXIV.1911.01966.

K. S. Suryowati, M. Nahak, and R. D. Bekti, “Penerapan Model Spasial Menggunakan Matriks Pembobot Queen Contiguity dan Euclidean Distance Terhadap Kasus Gizi Buruk Balita di Provinsi Nusa Tenggara Timur,” J Stat. J. Ilm. Teori Dan Apl. Stat., vol. 16, no. 1, pp. 298–308, July 2023, doi: 10.36456/jstat.vol16.no1.a7871.

P. Zou, J. (Roger) Jiao, and F. Zhou, “A twofold update quantum-inspired genetic algorithm for efficient combinatorial optimal decisions in engineering system design and operations,” J. Eng. Des., vol. 34, no. 4, pp. 271–293, Apr. 2023, doi: 10.1080/09544828.2023.2188394.

M. El Krari, B. Ahiod, and B. El Benani, “A Memetic Algorithm Based on Breakout Local Search for the Generalized Traveling Salesman Problem,” Appl. Artif. Intell., vol. 34, no. 7, pp. 537–549, June 2020, doi: 10.1080/08839514.2020.1730629.