JARINGAN SARAF TIRUAN SEBAGAI ALTERNATIF UNTUK PENYELESAIAN TRAVELLING SALESPERSON PROBLEM
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Petra Christian University
2001-01-01
|
| Series: | Jurnal Informatika |
| Subjects: | |
| Online Access: | http://puslit2.petra.ac.id/ejournal/index.php/inf/article/view/15801 |
| _version_ | 1818011779463118848 |
|---|---|
| author | Kartika Gunadi Peter Iksan |
| author_facet | Kartika Gunadi Peter Iksan |
| author_sort | Kartika Gunadi |
| collection | DOAJ |
| description | 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 |
| first_indexed | 2024-04-14T06:12:50Z |
| format | Article |
| id | doaj.art-102729b92e6a4972a2f593178322a688 |
| institution | Directory Open Access Journal |
| issn | 1411-0105 |
| language | English |
| last_indexed | 2024-04-14T06:12:50Z |
| publishDate | 2001-01-01 |
| publisher | Petra Christian University |
| record_format | Article |
| series | Jurnal Informatika |
| spelling | doaj.art-102729b92e6a4972a2f593178322a6882022-12-22T02:08:19ZengPetra Christian UniversityJurnal Informatika1411-01052001-01-0121pp.3032JARINGAN SARAF TIRUAN SEBAGAI ALTERNATIF UNTUK PENYELESAIAN TRAVELLING SALESPERSON PROBLEMKartika GunadiPeter IksanTraveling 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 Hopfieldhttp://puslit2.petra.ac.id/ejournal/index.php/inf/article/view/15801Traveling Salesperson Problem (TSP)Neural networkExhaustive algorithmaHopfield neural network. |
| spellingShingle | Kartika Gunadi Peter Iksan JARINGAN SARAF TIRUAN SEBAGAI ALTERNATIF UNTUK PENYELESAIAN TRAVELLING SALESPERSON PROBLEM Jurnal Informatika Traveling Salesperson Problem (TSP) Neural network Exhaustive algorithma Hopfield neural network. |
| title | JARINGAN SARAF TIRUAN SEBAGAI ALTERNATIF UNTUK PENYELESAIAN TRAVELLING SALESPERSON PROBLEM |
| title_full | JARINGAN SARAF TIRUAN SEBAGAI ALTERNATIF UNTUK PENYELESAIAN TRAVELLING SALESPERSON PROBLEM |
| title_fullStr | JARINGAN SARAF TIRUAN SEBAGAI ALTERNATIF UNTUK PENYELESAIAN TRAVELLING SALESPERSON PROBLEM |
| title_full_unstemmed | JARINGAN SARAF TIRUAN SEBAGAI ALTERNATIF UNTUK PENYELESAIAN TRAVELLING SALESPERSON PROBLEM |
| title_short | JARINGAN SARAF TIRUAN SEBAGAI ALTERNATIF UNTUK PENYELESAIAN TRAVELLING SALESPERSON PROBLEM |
| title_sort | jaringan saraf tiruan sebagai alternatif untuk penyelesaian travelling salesperson problem |
| topic | Traveling Salesperson Problem (TSP) Neural network Exhaustive algorithma Hopfield neural network. |
| url | http://puslit2.petra.ac.id/ejournal/index.php/inf/article/view/15801 |
| work_keys_str_mv | AT kartikagunadi jaringansaraftiruansebagaialternatifuntukpenyelesaiantravellingsalespersonproblem AT peteriksan jaringansaraftiruansebagaialternatifuntukpenyelesaiantravellingsalespersonproblem |