PERBANDINGAN ALGORITMA BRANCH AND BOUND DAN ALGORITMA GENETIKA UNTUK MENGATASI TRAVELLING SALESMAN PROBLEM (TSP) (Studi Kasus PT. JNE Semarang)

  • Ari Yulianto Nugroho Universitas Negeri Semarang
  • Amin Suyitno Universitas Negeri Semarang
  • Riza Arifudin Universitas Negeri Semarang
Keywords: Algoritma Branch and Bound; Algoritma Genetika; Travelling Salesman Problem; Software Matlab.

Abstract

This study examines an optimum solution to the search of Travelling Salesman Problem (TSP). The purpose of this paper is finding the shortest route at PT. Jalur Nugraha Ekakurir (JNE) Semarang on condition that every town is just visited once, except for the beginning address. Branch and bound algorithm dan genetic algorithm, is proposed to solve optimization problems with using Matlab software. Measurement of the effectiveness of the work system is done by comparing the calculation results between the branch and bound algorithm and genetic algorithm which is the best modification. Population size, pc, pm, and the number of generations are used as modifications. The results showed that the length of the resulting circuit using genetic algorithm is smaller than the length of using circuit branch and bound algorithm. This shows that genetic algorithm is more effective in determining the shortest circuit for delivery of goods in PT. Jalur Nugraha Ekakurir (JNE) Semarang

References

Firmansyah, A. 2007. Dasar-dasar Pemograman MATLAB. IlmuKomputer.com. [diakses 21-1-2015]
Iqbal, M. 2009. Dasar Pengolahan Citra Menggunakan MATLAB. Departmen Ilmu dan Teknologi Kelautan IPB.
Philip A, A.A. Taofiki & O. Kehinde. 2011. A Genetic Algorithm for Solving Travelling Salesman Problem. International Journal of Advanced Computer Science and Applications (IJACSA). Tersedia di https://thesai.org/ Downloads/Volume2No1/Paper%204-A%20Genetic%20Algorithm%20for%20Solving%20Travelling%20Salesman%20Problem.pdf [diakses 01-08-2015].
Purnamasari, R.W, Dwijanto & E. Sugiharti. 2013. Implementasi Jaringan Syaraf Tiruan Backpropagation Sebagai Sistem Deteksi Penyakit Tuberculosis. Unnes Journal of Mathematics. Tersedia di http://journal.unnes.ac.id/sju/index.php/ujm/article/view/3247/2988 [diakses 14-05-2015].
Purnawanto, Y., D. Purwitasari, & A. W. Wibowo.2005.Implementasi dan Analisis Algoritma Pencarian rute terpendek di kota Surabaya. Jurnal Penelitian dan Pengembangan Telekomunikasi, Vol 10 No.2,94-101.Tersedia di http://ppm. ittelkom.ac.id/jurtel/images/Volume10Desember2005/implementasi%20dan%20analisis%20algoritma%20pencarian%20rute20terpendek.pdf [diakses 21-1-2015].
Saptono, F.& T. Hidayat. 2007. Perancangan Algoritma Genetika Untuk Menentukan Jalur Terpendek. Seminar Nasional Aplikasi Teknologi Informasi. Yogyakarta: Universitas Islam Indonesia.
Sari, F.A. Dwijanto. & E. Sugiharti. 2013. Implementasi Algoritma Genetika Untuk Menyelesaikan Travelling Salesman Problem. UNNES Journal of Matematics, Vol. 2, No.2, Nopember 2013. Tersedia di http://journal. unnes.ac.id/sju/index.php/ujm/article/view/3251 [22-1-2015].
Suharto,I.,B. Girisuta, & A. Miryanti. 2004. Perekayasaan Metodologi Penelitian. Yogyakarta: Andi.
Sutanto, J. S. R. Hendrawan & Y. Kurniawan. 2011. Algoritma Branch and Bound untuk Masalah Penjadwalan Mesin Paralel. Bandung: Laboratorium Ilmu dan Komputasi Departemen Teknik Informatika, Institut Teknologi Bandung. Tersedia di http://informatika.stei.itb.ac. id/~rinaldi.munir/Stmik/Makalah/MakalahStmik04.pdf [diakses 21-1-2015]
Published
2017-02-27
Section
Articles