PENYELESAIAN MASALAH RUTE PERJALANAN KARYAWAN PDAM DENGAN MENGGUNAKAN ALGORITMA BRUTE FORCE

AISAL, JAFNI (2008) PENYELESAIAN MASALAH RUTE PERJALANAN KARYAWAN PDAM DENGAN MENGGUNAKAN ALGORITMA BRUTE FORCE. Masters thesis, UNIVERSITAS ANDALAS.

Preview

Text (Thesis) 2008_06215021_S2SKRIP0469.pdf - Published Version Download (9MB) | Preview

Abstract

Persoalan pedagang keliling (Traveling Salesman Problem - TSP) sangat terkenal dalam teori graf. Salah satu terapannya adalah perjalanan karyawan PDAM untuk memeriksa sambungan pipa induk yang tersebar pada n buah lokasi di wilayah Koto Baru Solok. Rute yang dilalui oleh karyawan tersebut adalah sebuah perjalanan mengunjungi setiap sambungan pipa hanya satu kali dan kembali lagi ke sambungan awal. Untuk mengefisienkan waktu karyawan tersebut harus memilih rute dengan total jarak yang minimum. Dalam menentukan rute tersebut, biasanya karyawan hanya memprediksi jarak tempuh. Total jarak yang diperoleh oleh karyawan tersebut belum tentu merupakan total jarak yang minimum. Untuk mempermudah dalam menentukan rute dengan total jarak minimum, maka perlu digunakan sebuah algoritma, salah satunya adalah Algoritma Brute Force. Berdasarkan permasalahan tersebut maka dilakukan penelitian. Tujuan penelitian ini adalah menentukan solusi optimal pada perjalanan karyawan dalam memperbaiki sambungan pipa induk PDAM dan mengetahui kompleksitas waktu asimptotik dari pemakaian Algoritma Brute Force pada kasus TSP. Penelitian ini dilakukan dari bulan Januari hingga bulan Mei 2008 di perpustakaan jurusan Matematika Universitas Andalas dengan langkah-langkah yang dilakukan adalah mengumpulkan data jarak antar lokasi sambungan pipa induk, membuat graf lengkap untuk data jarak tersebut, merubah graf lengkap ke dalam graf Hamilton , merubah graf Hamilton ke dalam bentuk pohon berakar dengan salah satu titik sebagai akarnya, menentukan total jarak berdasarkan pohon berakar yang terbentuk dan menentukan rute total jarak yang paling minimum. Adapun langkah-langkah Algoritma Brute Force adalah memodelkan masalah ke dalam bentuk graf, buat sebuah pohon yang cabang-cabangnya berupa titik pada graf, ekspansi titik-titik pada tiap cabang-cabang sampai semua titik telah dipilih, hitung total jaraknya kemudian tentukan sirkuit Hamilton yang mempunyai jarak terpendek. Untuk menghitung total jarak digunakan metode Breadth First- Search. Dari hasil penelitian ini dapat disimpulkan bahwa total jarak minimum rute perjalanan karyawan PDAM dalam memperbaiki sambungan pipa induk adalah 11,25 km dengan rute perjalan yang dilalui adalah komplek UMMY, Kelurahan Kajai, Kelurahan Bukit Kili Timur. Kelurahan Bukit Kili Barat. Komplek Perumnas, Komplek UMMY dengan kompleksitas waktu asimptotik 71(5) = 0(5!) dengan c = I dan n0 > 3. Untuk mempermudah penentuan solusi optimum dengan menggunakan algoritma Brute Force diharapkan peneliti selanjutnya dapat menerapkan algoritma Brute Force kedalam bentuk sebuah program.

Actions (login required)

View Item