Cover Image

Penyelesaian Travelling Salesman Problem (TSP) Menggunakan Algoritma Hill Climbing dan MATLAB

Main Author: Irfan, Muhammad
Format: Article info application/pdf
Bahasa: ind
Terbitan: Universitas Islam Bandung , 2018
Online Access: https://ejournal.unisba.ac.id/index.php/matematika/article/view/3090
https://ejournal.unisba.ac.id/index.php/matematika/article/view/3090/2381
ctrlnum article-3090
fullrecord <?xml version="1.0"?> <dc schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ http://www.openarchives.org/OAI/2.0/oai_dc.xsd"><title lang="id-ID">Penyelesaian Travelling Salesman Problem (TSP) Menggunakan Algoritma Hill Climbing dan MATLAB</title><creator>Irfan, Muhammad</creator><description lang="id-ID">Abstrak. Travelling Salesman Problem (TSP) adalah permasalahan dimana seorang salesman harus mengunjungi semua kota yang mana tiap kota hanya dikunjungi sekali, dan harus kembali ke kota asal. Masalah utama yang dihadapi sebuah TSP adalah bagaimana mencari rute terpendek dari perjalanan seorang salesman dengan biaya minimum. Penelitian ini bertujuan untuk mengetahui penyelesaian masalah TSP dengan menggunakan algoritma Hill Climbing baik Simple Hill Climbing (SHC) maupun Steepest-Ascent Hill Climbing (SAHC). Berdasarkan hasil kajian teori yang dilakukan, dapat disimpulkan bahwa algoritma Hill Climbing dapat digunakan untuk menyelesaikan TSP. Algoritma Hill Climbing dalam menyelesaikan masalah TSP yaitu: menentukan initial state, melakukan pengujian panjang lintasan, melakukan kombinasi penukaran dua kota, dan kemudian melakukan pengujian terhadap nilai heuristiknya. Penyelesaian masalah TSP dengan menggunakan algoritma Hill Climbing masing-masing mempunyai karakteristik yang berbeda-beda. Dalam menyelesaikan masalah TSP, SHC memilih keadaan yang lebih baik tanpa melakukan pengujian dikombinasi pertukaran kota pada iterasi yang sama. Sedangkan SAHC membandingkan keadaan yang lebih baik sebelum memilih keadaan tersebut sebagai new state. Selanjutnya untuk membantu proses komputasi pada saat menyelesaikan TSP, dibuat sebuah program dengan model algoritma Hill Climbing menggunakan MATLAB. Program yang terbentuk memberikan solusi berupa rute perjalanan yang disajikan dalam bentuk diagram.Kata kunci: Algoritma, Hill Climbing, Travelling Salesman ProblemAbstract. (Completion of Traveling Salesman Problem (TSP) Using the Hill Climbing and MATLAB Algorithms) Traveling Salesman Problem (TSP) is a problem where a salesman must visit all cities where each city is visited only once, and he/she must return to the hometown. The main problem facing a TSP is how to find the shortest route of a sales trip with minimum cost. This study aims to determine the solution of TSP problems using Hill Climbing algorithm both Simple Hill Climbing (SHC) and Steepest-Ascent Hill Climbing (SAHC). Based on the result of the theoretical study, it can be concluded that Hill Climbing algorithm can be used to solve TSP. Hill Climbing algorithm in solving TSP problem is: determining initial state, conducting track length test, performing combination of two city exchanges, and then testing the heuristic value. TSP problem solving using Hill Climbing algorithm each have different characteristics. In solving the TSP problem, SHC chooses a better state, without performing tests in combination of city exchanges on the same iteration. While SAHC compares the situation better before choosing the state as a new state. Furthermore, to assist the computing process when completing the TSP then made a program model Hill Climbing algorithm using MATLAB language. The program is formed to provide solutions in the form of travel routes presented in the form of diagrams.Keywordsi: Algorithm, Hill Climbing, Travelling Salesman Problem</description><publisher lang="en-US">Universitas Islam Bandung</publisher><contributor lang="id-ID"/><date>2018-05-28</date><type>Journal:Article</type><type>Other:info:eu-repo/semantics/publishedVersion</type><type>Journal:Article</type><type>File:application/pdf</type><identifier>https://ejournal.unisba.ac.id/index.php/matematika/article/view/3090</identifier><source lang="en-US">Matematika; Vol 17, No 1 (2018): Jurnal Matematika</source><source lang="id-ID">Matematika; Vol 17, No 1 (2018): Jurnal Matematika</source><source>2598-8980</source><source>1412-5056</source><language>ind</language><relation>https://ejournal.unisba.ac.id/index.php/matematika/article/view/3090/2381</relation><rights lang="en-US">Copyright (c) 2018 Matematika</rights><rights lang="en-US">http://creativecommons.org/licenses/by-nc-sa/4.0</rights><recordID>article-3090</recordID></dc>
language ind
format Journal:Article
Journal
Other:info:eu-repo/semantics/publishedVersion
Other
File:application/pdf
File
author Irfan, Muhammad
title Penyelesaian Travelling Salesman Problem (TSP) Menggunakan Algoritma Hill Climbing dan MATLAB
publisher Universitas Islam Bandung
publishDate 2018
url https://ejournal.unisba.ac.id/index.php/matematika/article/view/3090
https://ejournal.unisba.ac.id/index.php/matematika/article/view/3090/2381
contents Abstrak. Travelling Salesman Problem (TSP) adalah permasalahan dimana seorang salesman harus mengunjungi semua kota yang mana tiap kota hanya dikunjungi sekali, dan harus kembali ke kota asal. Masalah utama yang dihadapi sebuah TSP adalah bagaimana mencari rute terpendek dari perjalanan seorang salesman dengan biaya minimum. Penelitian ini bertujuan untuk mengetahui penyelesaian masalah TSP dengan menggunakan algoritma Hill Climbing baik Simple Hill Climbing (SHC) maupun Steepest-Ascent Hill Climbing (SAHC). Berdasarkan hasil kajian teori yang dilakukan, dapat disimpulkan bahwa algoritma Hill Climbing dapat digunakan untuk menyelesaikan TSP. Algoritma Hill Climbing dalam menyelesaikan masalah TSP yaitu: menentukan initial state, melakukan pengujian panjang lintasan, melakukan kombinasi penukaran dua kota, dan kemudian melakukan pengujian terhadap nilai heuristiknya. Penyelesaian masalah TSP dengan menggunakan algoritma Hill Climbing masing-masing mempunyai karakteristik yang berbeda-beda. Dalam menyelesaikan masalah TSP, SHC memilih keadaan yang lebih baik tanpa melakukan pengujian dikombinasi pertukaran kota pada iterasi yang sama. Sedangkan SAHC membandingkan keadaan yang lebih baik sebelum memilih keadaan tersebut sebagai new state. Selanjutnya untuk membantu proses komputasi pada saat menyelesaikan TSP, dibuat sebuah program dengan model algoritma Hill Climbing menggunakan MATLAB. Program yang terbentuk memberikan solusi berupa rute perjalanan yang disajikan dalam bentuk diagram.Kata kunci: Algoritma, Hill Climbing, Travelling Salesman ProblemAbstract. (Completion of Traveling Salesman Problem (TSP) Using the Hill Climbing and MATLAB Algorithms) Traveling Salesman Problem (TSP) is a problem where a salesman must visit all cities where each city is visited only once, and he/she must return to the hometown. The main problem facing a TSP is how to find the shortest route of a sales trip with minimum cost. This study aims to determine the solution of TSP problems using Hill Climbing algorithm both Simple Hill Climbing (SHC) and Steepest-Ascent Hill Climbing (SAHC). Based on the result of the theoretical study, it can be concluded that Hill Climbing algorithm can be used to solve TSP. Hill Climbing algorithm in solving TSP problem is: determining initial state, conducting track length test, performing combination of two city exchanges, and then testing the heuristic value. TSP problem solving using Hill Climbing algorithm each have different characteristics. In solving the TSP problem, SHC chooses a better state, without performing tests in combination of city exchanges on the same iteration. While SAHC compares the situation better before choosing the state as a new state. Furthermore, to assist the computing process when completing the TSP then made a program model Hill Climbing algorithm using MATLAB language. The program is formed to provide solutions in the form of travel routes presented in the form of diagrams.Keywordsi: Algorithm, Hill Climbing, Travelling Salesman Problem
id IOS5496.article-3090
institution Universitas Islam Bandung
institution_id 198
institution_type library:university
library
library Perpustakaan Universitas Islam Bandung
library_id 495
collection Matematika - Jurnal Teori dan Terapan Matematika
repository_id 5496
subject_area Mathematics/Matematika
Computer Modeling and Simulation/Model dan Simulasi Komputer
Mathematical Economic/Ekonomi Matematika
Applied mathematics/Matematika Terapan
city KOTA BANDUNG
province JAWA BARAT
repoId IOS5496
first_indexed 2019-05-08T16:32:15Z
last_indexed 2019-05-08T16:32:15Z
recordtype dc
_version_ 1686357132733054976
score 17.538404

Lihat Juga