Ahmad, Edwin Dwi (2019) Optimasi Rute Rencana Perjalanan dengan Pesawat Terbang Menggunakan Algoritma Tabu-Simulated Annealing untuk Menyelesaikan Permasalahan Travelling Salesman Challenge 2.0. Other thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
05211540000060-Undergraduate_Theses.pdf Download (2MB) | Preview |
Abstract
Travelling Salesman Problem (TSP) termasuk ke dalam golongan permasalahan Non-deterministic Polynomial NP-hard yang berarti belum ada algoritma eksak yang dapat menyelesaikannya dalam waktu polynomial. Tujuan TSP adalah untuk mencari rute perjalanan terpendek dimana perjalanan tersebut dimulai dari sebuah kota dan harus berakhir pada kota yang sama dengan kota keberangkatan dan setiap kota yang dilewati harus dikunjungi tepat satu kali. Selain menemukan rute perjalanan terpendek, TSP juga digunakan untuk mencari rute perjalanan dengan biaya seminimal mungkin. Salah satu permasalahan TSP terdapat di dalam kompetisi Travelling Salesman Challenge (TSC) 2.0 yang diselenggarakan pada tahun 2018. Tujuan TSC 2.0 adalah menemukan rute perjalanan menggunakan pesawat terbang dengan biaya termurah. Setiap rute yang diambil harus melewati seluruh area yang ditentukan. Masing-masing area terdapat satu atau lebih kota dan dimana dalam setiap area hanya boleh satu kota saja yang boleh dikunjungi. Tantangan dalam permasalahan ini adalah banyaknya batasan-batasan soft constraint maupun hard constraint yang harus dipenuhi. Oleh karena itu, untuk menyelesaikan permasalahan pada TSC 2.0 dalam tugas akhir ini akan digunakan algoritma hybrid Tabu Search dan Simulated Annealing. Pemilihan algoritma hybrid Tabu Search dan Simulated Annealing karena algoritma ini telah banyak dikembangkan untuk mengatasi permasalahan NP-hard. Hasil yang diperoleh dari penelitian tugas akhir ini menunjukkan algoritma tabu-simulated annealing dapat menyelesaikan permasalahan pada TSC 2.0 dengan mereduksi 48.54% biaya dari solusi awal dan mampu bersaing dengan algoritma great deluge yang hanya mampu mereduksi 41.33% dari solusi awal.
=================================================================================================================================
Traveling Salesman Problem (TSP) belongs to a group of Non-deterministic Polynomial NP-hard problems, which means there is no exact algorithm that can solve it in polynomial time. The purpose of TSP is to find the shortest distance where the journey starts from a city and must end in the same city as the city of departure and each city that is passed must be visited exactly once. In addition to finding the shortest distance, TSP is also used to find routes at minimum cost. One of the TSP problems is in the Traveling Salesman Challenge (TSC) 2.0 competition held in 2018. The purpose of TSC 2.0 is to find routes using airplanes at the lowest cost. Each route taken must pass the entire specified area. Each area has one or more cities and where in each area only one city can be visited. The challenge in this problem is the many constraints of soft constraints and hard constraints that must be met. Therefore, to solve problems in TSC 2.0 in this final project, a hybrid Tabu Search and Simulated Annealing algorithm will be used. The selection of hybrid Tabu Search and Simulated Annealing algorithms because this algorithm has been widely developed to overcome NP-hard problems. The results obtained from this final assignment show that the tabu-simulated annealing algorithm can solve the problems in TSC 2.0 by reducing 48.54% of the cost of the initial solution and able to compete with the great deluge algorithm which can only reduce 41.33% of the initial solution.
| Item Type: | Thesis (Other) |
|---|---|
| Additional Information: | RSSI 518.282 Ahm o-1 2019 |
| Uncontrolled Keywords: | Algoritma Simulated Annealing, Algoritma Tabu Search, Travelling Salesman Problem |
| Subjects: | T Technology > T Technology (General) > T57.6 Operations research--Mathematics. Goal programming T Technology > T Technology (General) > T58.5 Information technology. IT--Auditing T Technology > T Technology (General) > T58.62 Decision support systems |
| Divisions: | Faculty of Information and Communication Technology > Information Systems > 57201-(S1) Undergraduate Thesis |
| Depositing User: | Edwin Dwi Ahmad |
| Date Deposited: | 14 May 2024 05:45 |
| Last Modified: | 14 May 2024 05:45 |
| URI: | http://repository.its.ac.id/id/eprint/64548 |
Actions (login required)
 |
View Item |