Kartika Gunadi, Peter Iksan


Traveling Salesperson Problem (TSP) is one among the NP-complete problem. TSP is defined as follows. A traveling salesperson has a number of cities to visit. The sequence in which the salesperson visits diffrents cities is called a tour. A tour should be such that every city is visited once and only once. The goal is to find a tour that minimize the total distance of a tour. TSP can be solved by Exhaustive algorithm, but this algorithm is no efficient for large number of cities. A neural network can be used to solve this optimization problem by choosing appropriate architecture to find optimal solution. A Neural network can be used to solve optimization by chosing apropriate architecture to find optimal solution. Algorithm of Neural network reduced a signifcant execution time for number of cities more than 9, and has optimization 83% of best solution from exhaustive algorithm.

Abstract in Bahasa Indonesia :

Traveling Salesperson Problem (TSP) adalah problem optimasi kombinasional yang tergolong dalam NP-complete problem. TSP adalah problem untuk menentukan urutan dari sejumlah kota yang harus dilalui oleh seorang sales, setiap kota hanya boleh dilalui sekali dan hanya sekali dalam perjalanan, dan perjalanan berakhir pada kota awal dimana seorang sales memulai perjalananya. TSP ini dapat dilakukan secara sederhana dengan Algorithma Exhaustive, yaitu dengan mencari semua kombinasi yang mungkin terjadi, kemudian memilih kombinasi dengan jarak terdekat. Algorithma Exhaustive ini menjadi tidak efisien bila jumlah kota yang besar, karena mempunyai kompleksitas sebesar n!/2n. Jaringan saraf tiruan (JST) dapat digunakan untuk menyelesaikan problem optimasi dengan memilih arsitektur jaringan yang sesuai untuk mendapatkan solusi yang optimal. Algorithma dengan menggunakan jaringan saraf tiruan memberikan reduksi waktu eksekusi yang sangat signifikan untuk jumlah kota lebih besar 9, dan dapat memberikan persentase optimasi sebesar 83 % dari solusi yang terbaik yang didapatkan dengan algorithma exhaustive.

Kata kunci: Traveling Salesperson Problem (TSP), Jaringan saraf tiruan (JST), Algorithma Exhaustive, JST Hopfield


Traveling Salesperson Problem (TSP), Neural network, Exhaustive algorithma, Hopfield neural network.

Full Text: PDF

The Journal is published by The Institute of Research & Community Outreach - Petra Christian University. It available online supported by Directorate General of Higher Education - Ministry of National Education - Republic of Indonesia.

©All right reserved 2016.Jurnal Informatika, ISSN: 1411-0105


free hit counters
View My Stats

Copyright © Research Center Web-Dev Team