Melola Discovery

← Melola Discovery

Jurnal SINTA 2

Optimasi Rute Rencana Perjalanan Pesawat Menggunakan Algoritma Late Acceptance Hill Climbing (Studi Kasus: Travelling Salesman Challenge 2.0)

Jurnal Teknologi Informasi dan Ilmu Komputer (JTIIK) · Vol. 10 No. 4 (2023) · hlm. 893–898

DOI
10.25126/jtiik.2024106842
ISSN
2528-6579, 2355-7699
Terbit
2023-08-30
Penerbit
Fakultas Ilmu Komputer, Universitas Brawijaya
Bahasa
id

Abstrak

Permasalahan Traveling Salesman Problem (TSP) merupakan permasalahan klasik yang popular diteliti dalam bidang optimasi kombinatorika. Permasalahan ini bertujuan menentukan rute perjalanan terpendek untuk mengunjungi setiap lokasi tepat satu kali dan diakhir perjalanan harus kembali ke lokasi awal perjalanan dimulai. Permasalahan ini telah digolongkan sebagai permasalahan NP-Hard, sehingga membutuhkan algoritma non-deterministic untuk dapat menyelesaikan permasalahan ini. Dalam permasalahan nyata, salah satu penerapan TSP ada pada permasalahan untuk menentukan rute perjalanan termurah untuk mengunjungi beberapa kota di beberapa negara. Kompetisi Travelling Salesman Challenge 2.0 (TSC 2.0) mengangkat permasalahan ini dalam sebuah kompetisi pada tahun 2018. Untuk menyelesaikan studi kasus tersebut, penelitian ini menyembangkan algoritma Late Acceptance Hill Climbing (LAHC) menggunakan metode hiper-heuristik. Algoritma LAHC merupakan algoritma yang sederhana namun telah terbukti mampu mengoptimasi dengan baik pada beberapa permasalahan TSP. Algoritma LAHC diuji coba pada 14 dataset dari TSC 2.0. Hasil penelitian menunjukan algoritma LAHC menghasilkan solusi yang kompetitif dengan mampu menurunkan biaya perjalanan dengan rata-rata 58% dan menghasilkan hasil yang lebih baik dengan rata-rata 9% dari algoritma Threshold Acceptance (TA) yang digunakan sebagai algoritma pembanding. AbstractThe Traveling Salesman Problem (TSP) is a classic problem that is popularly researched in the field of combinatorics optimization. This problem aims to determine the shortest travel route to visit each location exactly once and, at the end of the trip, must return to where the trip started. This problem has been classified as an NP-Hard problem. Therefore it requires a non-deterministic algorithm to solve it. In the real world, one of the applications of TSP is the problem of determining the cheapest travel routes to visit several cities in several countries. The Traveling Salesman Challenge 2.0 (TSC 2.0) competition raised this issue in a competition in 2018. This study developed the Late Acceptance Hill Climbing (LAHC) algorithm using the hyper-heuristic method to complete the case study from TSC 2.0. The LAHC algorithm is simple but has been proven to optimize well for several TSP problems. The LAHC algorithm was tested on 14 datasets from TSC 2.0. The results show that the LAHC algorithm produces competitive solutions by reducing travel costs by an average of 58% and making better results by an average of 9% than the Threshold Acceptance (TA) algorithm used as a comparison algorithm.

Jaringan kolaborasi para penulis

15 penulis · 42 tautan kepenulisan bersama

Arahkan kursor atau ketuk sebuah nama untuk menyorot rekan penulisnya. Klik dua kali untuk membuka halaman penulis.

  • Institut Teknologi Sepuluh Nopember
  • Organisasi berbeda
  • Organisasi sama
  • Afiliasi tidak diketahui
  • Garis lebih tebal = lebih banyak artikel bersama · lingkaran lebih besar = lebih banyak artikel
Tampilkan sebagai tabel
Rekan penulisOrganisasiArtikel bersama
Edwin RiksakomaraInstitut Teknologi Sepuluh Nopember3
Retno Aulia VinartiInstitut Teknologi Sepuluh Nopember2
Faizal MahanantoInstitut Teknologi Sepuluh Nopember2
Raras TyasnuritaInstitut Teknologi Sepuluh Nopember2
Shof Rijal Ahlan RobbaniInstitut Teknologi Sepuluh Nopember2
Yusnardo TendioInstitut Teknologi Sepuluh Nopember2
Helena Angelita DepariInstitut Teknologi Sepuluh Nopember2
Muhammad Arif NurimanInstitut Teknologi Sepuluh Nopember2
Anang FirdausInstitut Teknologi Sepuluh Nopember1
Vicha Azthanty SupoyoInstitut Teknologi Sepuluh Nopember1
Muhammad Reza PahlawanInstitut Teknologi Sepuluh Nopember1
Wiwik AnggraeniInstitut Teknologi Sepuluh Nopember1
Mursyidatun NabilahInstitut Teknologi Sepuluh Nopember1

Afiliasi berasal dari OpenAlex; metadata OAI-PMH jurnal tidak memuatnya. Penulis tanpa ID OpenAlex dicocokkan berdasarkan nama, sehingga dua orang bisa tergabung atau satu orang bisa terpisah.

Sumber metadata: OAI-PMH (metadata jurnal) https://jtiik.ub.ac.id/index.php/jtiik/en/oai, pertama di-harvest 27 Okt 2026, terakhir terlihat 15 Nov 2026.
Metadata asli (oai_dc)
<oai_dc:dc xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/  http://www.openarchives.org/OAI/2.0/oai_dc.xsd">
	<dc:title xml:lang="id">Optimasi Rute Rencana Perjalanan Pesawat Menggunakan Algoritma Late Acceptance Hill Climbing (Studi Kasus : Travelling Salesman Challenge 2.0)</dc:title>
	<dc:creator xml:lang="id">Muklason, Ahmad</dc:creator>
	<dc:creator xml:lang="id">Premananda, I Gusti Agung</dc:creator>
	<dc:description xml:lang="id">Permasalahan Traveling Salesman Problem (TSP) merupakan permasalahan klasik yang popular diteliti dalam bidang optimasi kombinatorika. Permasalahan ini bertujuan menentukan rute perjalanan terpendek untuk  mengunjungi setiap lokasi tepat satu kali dan diakhir perjalanan harus kembali ke lokasi awal perjalanan dimulai. Permasalahan ini telah digolongkan sebagai permasalahan NP-Hard, sehingga membutuhkan algoritma non-deterministic untuk dapat menyelesaikan permasalahan ini. Dalam permasalahan nyata, salah satu penerapan TSP ada pada permasalahan untuk menentukan rute perjalanan termurah untuk mengunjungi beberapa kota di beberapa negara. Kompetisi Travelling Salesman Challenge 2.0 (TSC 2.0) mengangkat permasalahan ini dalam sebuah kompetisi pada tahun 2018. Untuk menyelesaikan studi kasus tersebut, penelitian ini menyembangkan algoritma Late Acceptance Hill Climbing (LAHC) menggunakan metode hiper-heuristik. Algoritma LAHC merupakan algoritma yang sederhana namun telah terbukti mampu mengoptimasi dengan baik pada beberapa permasalahan TSP. Algoritma LAHC diuji coba pada 14 dataset dari TSC 2.0. Hasil penelitian menunjukan algoritma LAHC menghasilkan solusi yang kompetitif dengan mampu menurunkan biaya perjalanan dengan rata-rata 58% dan menghasilkan hasil yang lebih baik dengan rata-rata 9% dari algoritma Threshold Acceptance (TA) yang digunakan sebagai algoritma pembanding. AbstractThe Traveling Salesman Problem (TSP) is a classic problem that is popularly researched in the field of combinatorics optimization. This problem aims to determine the shortest travel route to visit each location exactly once and, at the end of the trip, must return to where the trip started. This problem has been classified as an NP-Hard problem. Therefore it requires a non-deterministic algorithm to solve it. In the real world, one of the applications of TSP is the problem of determining the cheapest travel routes to visit several cities in several countries. The Traveling Salesman Challenge 2.0 (TSC 2.0) competition raised this issue in a competition in 2018. This study developed the Late Acceptance Hill Climbing (LAHC) algorithm using the hyper-heuristic method to complete the case study from TSC 2.0. The LAHC algorithm is simple but has been proven to optimize well for several TSP problems. The LAHC algorithm was tested on 14 datasets from TSC 2.0. The results show that the LAHC algorithm produces competitive solutions by reducing travel costs by an average of 58% and making better results by an average of 9% than the Threshold Acceptance (TA) algorithm used as a comparison algorithm.</dc:description>
	<dc:publisher xml:lang="en">Fakultas Ilmu Komputer, Universitas Brawijaya</dc:publisher>
	<dc:date>2023-08-30</dc:date>
	<dc:type>info:eu-repo/semantics/article</dc:type>
	<dc:type>info:eu-repo/semantics/publishedVersion</dc:type>
	<dc:format>application/pdf</dc:format>
	<dc:identifier>https://jtiik.ub.ac.id/index.php/jtiik/article/view/6842</dc:identifier>
	<dc:identifier>10.25126/jtiik.2024106842</dc:identifier>
	<dc:source xml:lang="id">Jurnal Teknologi Informasi dan Ilmu Komputer; Vol 10 No 4: Agustus 2023; 893-898</dc:source>
	<dc:source xml:lang="en">Jurnal Teknologi Informasi dan Ilmu Komputer; Vol. 10 No. 4: Agustus 2023; 893-898</dc:source>
	<dc:source>2528-6579</dc:source>
	<dc:source>2355-7699</dc:source>
	<dc:source>10.25126/jtiik.2024104</dc:source>
	<dc:language>id</dc:language>
	<dc:relation>https://jtiik.ub.ac.id/index.php/jtiik/article/view/6842/pdf_1</dc:relation>
	<dc:rights xml:lang="en">Copyright (c) 2023 Jurnal Teknologi Informasi dan Ilmu Komputer</dc:rights>
</oai_dc:dc>