PERBANDINGAN ALGORITMA GREEDY , ALGORITMA CHEAPEST INSERTION HEURISTICS DAN DYNAMIC PROGRAMMING DALAM PENYELESAIAN TRAVELLING SALESMAN PROBLEM

Gea Aristi

Abstract


Travelling Salesman Problem is one of problems to find shortest route from travelling a salesman from first city and then to destination cities and finally back to first city, but one city just only once visited. There are some algorithms to solving travelling salesman problem,such as Greedy Algorithm, Artificial Bee Colony Algorithm, Cheapest Insertion Heuristics Algorithm, Genetic Algorithm and many more. In this paper, only greedy algorithm, cheapest insertion heuristics algorithm and dynamic programming are discussed. After compared using an example case with 5 cities and solved by third of algorithm, shortest route is same but the way to solving is different. They have advantages and disadvantages of each, and has the characteristics of each. Greedy algorithm is more suitable when used for a number of cities that are not too much because  the process is more simple, but cheapest insertion heuristics algorithm is more suitable to case with more city throught the process more complicated than greedy algorithm. Counting in Dynamic programming must be right because it will be influence for the next counting result.  


Full Text:

PDF

References


Dian. 2013. Algoritma Optimasi Untuk Penyelesaian Travelling Salesman Problem (Optimization Algorithm For Solving Travelling Salesman Problem). Jurnal Transformatika. Jurusan Teknologi Informasi Fakultas Teknologi Informasi dan Komunikasi, Universitas Semarang. Volume 11, No.1, Juli 2013.

Dian, dkk. 2008. Evaluasi Kinerja Algoritma Travelling Salesman Problem Dengan Teknik Pemrograman Dinamik. Proceeding, Seminar Ilmiah Nasional Komputer dan Sistem Intelijen (KOMMIT 2008)

Auditorium Universitas Gunadarma, Depok, 20-21 Agustus 2008

Kusrini dan Istiyanto, J.E.. 2007. Penyelesaian Travelling Salesman Problem dengan Algoritma Cheapest Insertion Heuristic dan Basis Data. Jurnal Informatika. Jurusan Teknik Informatika, Fakultas Teknologi Industri, Universitas Kristen Petra, Vol. 8, No. 2, Nopember 2007, 109-114.

Rusdi dan Siti. 2010. Studi Perbandingan Algoritma Cheapest Insertion Heuristic dan Ant Colony System Dalam Pemecahan Travelling Salesman Problem. Seminar Nasional Aplikasi Teknologi Informasi 2010 (SNATI 2010). Yogyakarta, 19 Juni 2010.

Winston, Wayne L. dan Goldberg, Jeffrey

B. 2004. Operations Research Application And Algorithms 4th Edition. United States of America : Duxbury




DOI: https://doi.org/10.31294/p.v16i2.779

Dipublikasikan oleh LPPM Universitas Bina Sarana Informatika

Jl. Dewi Sartika No. 289, Cawang, Jakarta Timur Telp : 021-8010836, ext. 202
Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License