Ambarita, Handy Frank Wily (2018) Penerapan Algoritma Discrete Cuckoo Search Pada Multiple Travelling Salesman Problem. Masters thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
TesisHandy (2).pdf - Accepted Version Download (1MB) | Preview |
Abstract
Pada penelitian ini salah satu variasi dari Travelling Salesman Problem (TSP) yaitu Multiple Travelling Salesman Problem (MTSP) diselesaikan dengan algoritma Discrete Cuckoo Search dan algoritma k-means++. Untuk menyelesaikan permasalahan MTSP ini, pertama-tama dilakukan klustering dengan menggunakan k-means++ untuk mendapatkan kota yang membentuk rute dari setiap salesman.Kemudian setelah mendapatkan kluster-kluster, dilakukan pembentukan dan pengoptimalan rute pada kluster-kluster tersebut satu per satu menggunakan Discrete Cuckoo Search. Dari hasil percobaan didapat bahwa parameter: jumlah populasi (pop) dan banyak generasi (ngen), berpengaruh pada jarak terpendek yang didapat serta waktu komputasi. Sedangkan untuk parameter fraksi Cuckoo yang jelek (pa), tidak berpengaruh terhadap jarak terpendek yang dihasilkan, tetapi berpengaruh pada waktu komputasi. Jika nilai fraksi yang diberikan semakin mendekati satu, waktu komputasi semakin bertambah dengan pa= 0 memiliki rerata waktu komputasi terkecil dan pa = 1 adalah fraksi dengan rerata waktu komputasi terbesar. Selain itu kombinasi k-means++ dan Discrete Cuckoo Search dibandingkan dengan Ant Colony Optimization dan Genetic Algorithm dari penelitian lain.
==============================================================================
In this thesis writer combine Discrete Cuckoo Search and k-means++ to
solve Multiple Travelling Salesman Problem (MTSP) with single depot which
is nondeterministc polynomial-hard problem. k-means++ is used to find the
city for route of every salesman. Once the route is found, Discrete Cuckoo
Search is used to create route and optimize route. From the experiments it
gets parameters such as number of population (
pop
) and number of generation
(
ngen
) affect the solution from Discrete Cuckoo Search and its time of
computation. Fraction of the worst Cukoo (
p
a
) does not affect the algorithm to
get solution. It only affects the time of computation. Every increasing of value
of
p
a
, get the time of computation bigger. The smallest time of computation is
found on
p
a
= 0
and the biggest is on
p
a
= 1
. Also, the combination of method
is compared with Ant Colony Optimization and Genetic Algorithm.
| Item Type: | Thesis (Masters) |
|---|---|
| Additional Information: | RTMa 511.8 Amb p |
| Uncontrolled Keywords: | Discrete cuckoo search, Multiple travelling salesman problem, K-means++ |
| Subjects: | Q Science > Q Science (General) > Q180.55.M38 Mathematical models Q Science > QA Mathematics > QA336 Artificial Intelligence Q Science > QA Mathematics > QA9.58 Algorithms |
| Divisions: | Faculty of Mathematics, Computation, and Data Science > Mathematics > 44101-(S2) Master Thesis |
| Depositing User: | Handy Frank Wily Ambarita |
| Date Deposited: | 13 Nov 2020 12:26 |
| Last Modified: | 29 Dec 2020 06:32 |
| URI: | http://repository.its.ac.id/id/eprint/59019 |
Actions (login required)
 |
View Item |