Ari Yulianto Nugroho , 4111411034 (2016) PERBANDINGAN ALGORITMA BRANCH AND BOUND DAN ALGORITMA GENETIKA UNTUK MENGATASI TRAVELLING SALESMAN PROBLEM (TSP) MENGGUNAKAN SOFTWARE MATLAB (Studi Kasus PT. JNE Semarang). Under Graduates thesis, Universitas Negeri Semarang.

Preview

PDF - Published Version Download (3MB) | Preview

Abstract

Travelling Salesman Problem (TSP) adalah problem pencarian rute optimal bagi seseorang salesman yang berkeliling mengunjungi n kota dengan setiap kota dikunjungi satu kali kecuali kota asal. Penelitian ini fokus pada masalah pendistribusian barang di PT. Jalur Nugraha Ekakurir (JNE) Semarang dengan tujuan 9 alamat pengiriman di wilayah Semarang. Pengukuran keefektifan hasil kerja sistem dilakukan dengan membandingkan hasil perhitungan algoritma branch and bound dengan hasil perhitungan algoritma genetika yang merupakan hasil modifikasi terbaik. 20 Modifikasi pada algoritma genetika dilakukan pada ukuran populasi, besar probabilitas crossover, besar probabilitas mutasi dan jumlah generasinya. Penelitian ini menghasilkan simpulan yaitu penerapan algoritma branch and bound dan algoritma genetika guna menentukan sirkuit terpendek dalam pengiriman barang di PT. Jalur Nugraha Ekakurir (JNE) semarang dimulai dengan mencari jarak antar alamat dengan bantuan Google Maps, kemudian dilanjutkan dengan pembangunan sistem TSP yang dilengkapi dengan koding pada software Matlab R2009a. Setelah sistem TSP berhasil dibuat selanjutnya inputkan data alamat yang telah disimpan dalam database, inputkan pula variabel-variabel masukan seperti ukuran populasi, probabilitas crossover, probabilitas mutasi dan generasi. Selanjutnya dilakukan pengujian sistem dengan melakukan modifikasi pada algoritma genetika. Hasil modifikasi pada algoritma genetika yang paling optimal digunakan untuk perbandingan dengan hasil perhitungan algoritma branch and bound. Selanjutnya akan didapatkan hasil perbandingan algoritma branch and bound dan algoritma genetika yang mempunyai panjang sirkuit terpendek. Berdasarkan solusi optimum yang diperoleh dengan menggunakan algoritma branch and bound dan dengan algoritma genetika diperoleh panjang sirkuit yang dihasilkan algoritma genetika lebih kecil dari panjang sirkuit yang dihasilkan algoritma branch and bound. Hal ini menunjukkan bahwa algoritma genetika lebih efektif dalam menentukan sirkuit terpendek untuk pengiriman barang di PT. Jalur Nugraha Ekakurir (JNE) Semarang.

Actions (login required)

View Item