Optimasi Rute Rencana Perjalanan Dengan Pesawat Menggunakan Algoritma Artificial Bee Colony (Studi Kasus : Travelling Salesman Challenge 2.0)

Premananda, I Gusti Agung (2019) Optimasi Rute Rencana Perjalanan Dengan Pesawat Menggunakan Algoritma Artificial Bee Colony (Studi Kasus : Travelling Salesman Challenge 2.0). Other thesis, Institut Teknologi Sepuluh Nopember.

Text 05211540000104-Undergraduate_Theses.pdf - Accepted Version Restricted to Repository staff only Download (2MB) | Request a copy

Abstract

Traveling Salesman Problem (TSP) merupakan permasalahan yang sangat populer dalam bidang optimasi kombinatorik. Permasalahan TSP berisikan bagaimana cara mencari rute terpendek dari sejumlah kota yang jarak antar kotanya diketahui dan seorang salesman harus mengunjungi setiap kota tepat satu kali dan harus kembali ke kota asal. Permasalahan ini termasuk ke permasalahan non polynomial hard (NP-hard) dan dapat diselesaikan dengan metode heuristic. Salah satu yang termasuk dalam permasalahan TSP adalah pencarian rute penerbangan termurah ke beberapa kota dalam kompetisi Travelling Salesman Challenge 2.0 (TSC 2.0) tahun 2018. Tugas akhir ini bertujuan untuk menyelesaikan permasalahan TSC 2.0 dengan menggunakan algoritma artificial bee colony (ABC). Algoritma ABC merupakan algoritma yang terinspirasi oleh cara koloni lebah dalam mencari dan menentukan sumber makanan terbaik. Algoritma ini telah banyak diimplementasikan kepada permasalahan-permasalahan NP-hard. Hasil dari penelitian ini menunjukan algoritma ABC dapat menyelesaikan permasalahan TSC 2.0 dengan performa yang cukup baik dengan rata-rata penghematan biaya perjalanan sebesar 56,1 % dari solusi awal.
====================================================================================================================================
Traveling Salesman Problem (TSP) is a very popular problem in the field of combinatoric optimization. TSP problems contain how to find the shortest route from a number of cities where the distance between the two is known and a salesman will visit each city exactly once and return to the city of origin. This problem is included in non polynomial problems (NP-hard) and can be solved by heuristic methods. One of the problem included in the TSP is to search for the cheapest flight routes in several cities in the Traveling Salesman Challenge 2.0 (TSC 2.0) competition in 2018. This final project purpose to solve the problem of TSC 2.0 using artificial bee colony (ABC) algorithm. ABC algorithm is an algorithm that is inspired by the way the bee colonies find and determine the best food source. This algorithm has been widely implemented for NP-hard problems. The results of this study show ABC algorithms can solve TSC 2.0 problems with good performance with an average travel cost savings of 56.1% from the initial solution.

Item Type:	Thesis (Other)
Additional Information:	RSSI 005.1 Pre o-1 2019 3100019080961
Uncontrolled Keywords:	rute penerbangan, traveling salesman problem, artificial bee colony
Subjects:	T Technology > T Technology (General) > T57.6 Operations research--Mathematics. Goal programming
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Information System > 57201-(S1) Undergraduate Thesis
Depositing User:	I Gusti Agung Premananda
Date Deposited:	19 Dec 2025 02:08
Last Modified:	19 Dec 2025 02:08
URI:	http://repository.its.ac.id/id/eprint/64505

Actions (login required)

View Item