PENYELESAIAN TRAVELLING SALESMAN PROBLEM MENGGUNAKAN METODE SIMPLE HILL CLIMBING

Abstract

Salah satu metode yang digunakan untuk menentukan penyelesaian dari TSP yaitu Simple Hill Climbing. Simple Hill Climbing bekerja dengan cara memilih secara langsung lintasan baru yang memiliki jarak lintasan lebih kecil dari lintasan sebelumnya, tanpa melakukan pengujian dan tanpa melakukan penukaran titik pada level yang sama. Penyelesaian TSP pada contoh kasus dengan 10 kota menggunakan metode Simple Hill Climbing didapatkan lintasan terpendek atau tujuan dari penyelesaian TSP tersebut yaitu pada level ke-2 dengan titik tukar G,H dan lintasanABCEDFHGIJA=49km. Penyelesaian contoh kasus TSP dengan 6 kota menggunakan metode Simple Hill Climbing didapatkan lintasan terpendek pada level ke-1 dengan titik tukar 2,1 dan lintasan 4 "“ 6 "“ 5 "“ 3 "“ 1 "“ 2 "“ 4 =103,6 . Kelebihan dari metode Simple Hill Climbing tidak mengunjungi semua pencarian pada level yang sama. Oleh karena itu, pada setiap langkah harus dibuat keputusan yang terbaik dalam menentukan pilihan yaitu jarak tempuh lintasan yang lebih kecil.

Kata Kunci : Graph, Hill Climbing, Simple Hill Climbing