OPTIMASI RUTE MULTIPLE-TRAVELLING SALESMAN PROBLEM MELALUI PEMROGRAMAN INTEGER DENGAN METODE BRANCH AND BOUND
SKRIPSI
Oleh Eka Poespita Dewi NIM 051810101068
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS JEMBER 2009
OPTIMASI RUTE MULTIPLE-TRAVELLING SALESMAN PROBLEM MELALUI PEMROGRAMAN INTEGER DENGAN METODE BRANCH AND BOUND
SKRIPSI diajukan guna melengkapi tugas akhir dan memenuhi salah satu syarat untuk menyelesaikan Program Studi Matematika (S1) dan mencapai gelar Sarjana Sains
Oleh Eka Poespita Dewi NIM 051810101068
JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS JEMBER 2009
i
PERSEMBAHAN
Teruntuk orang-orang yang saya sayangi, yang telah banyak berjasa dalam membimbing dan mengarahkan ke jalan yang benar dalam menjalani kehidupan di dunia ini. Semoga Allah memberikan balasan yang lebih baik. Amin.
1.
Kedua orangtua tercinta, Alm. Bapak Slamet Rahayu dan Ibu Titien Hayati, yang tiada henti-hentinnya mendoakan, mengarahkan, dan mendidik dengan penuh kasih sayang dan kesabaran.
2.
Adik Dwi Putri Poespita Rahayu, terimakasih atas dukungan, pengertian dan perhatiannya.
3.
Guru-guru sejak Taman Kanak-Kanak hingga Perguruan Tinggi, yang telah memberikan ilmu dan membimbing dengan penuh kesabaran.
4.
Almamater Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Jember.
ii
MOTTO
“Sesungguhnya Allah tidak merubah keadaan suatu kaum sehingga mereka merubah keadaan yang ada pada diri mereka sendiri” (QS. Ar Ra’d:11)
“Jadilah seperti pohon kurma; tinggi cita-citanya, kebal dari penyakit, dan bila dilempar dengan batu, ia membalas dengan buah kurmanya!” ( Dr. Aidh bin Abdullah Al-Qarni)
iii
PERNYATAAN
Saya yang bertanda tangan di bawah ini: nama : Eka Poespita Dewi NIM
: 051810101068
menyatakan dengan sesungguhnya bahwa skripsi yang berjudul Optimasi Rute Multiple-Travelling Salesman Problem melalui Pemrograman Integer dengan Metode Branch and Bound adalah benar-benar karya sendiri, kecuali jika disebutkan sumbernya dan belum pernah diajukan pada institusi manapun, serta bukan karya jiplakan. Saya bertanggung jawab atas keabsahan isinya sesuai dengan sikap ilmiah yang harus dijunjung tinggi. Demikian pernyataan ini saya buat dengan sebenarnya, tanpa adanya tekanan dan paksaan dari pihak manapun serta bersedia mendapat sanksi akademik jika ternyata di kemudian hari pernyataan ini tidak benar.
Jember, 13 Oktober 2009 Yang menyatakan,
Eka Poespita Dewi NIM 051810101068
iv
SKRIPSI
OPTIMASI RUTE MULTIPLE-TRAVELLING SALESMAN PROBLEM MELALUI PEMROGRAMAN INTEGER DENGAN METODE BRANCH AND BOUND
Oleh Eka Poespita Dewi NIM 051810101068
Pembimbing Dosen Pembimbing Utama
: Agustina Pradjaningsih, S.Si., M.Si.
Dosen Pembimbing Anggota : Drs. Moh. Hasan, M.Sc., Ph.D.
v
PENGESAHAN
Skripsi berjudul Optimasi Rute Multiple-Travelling Salesman Problem melalui Pemrograman Integer dengan Metode Branch and Bound telah diuji dan disahkan oleh Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Jember pada: hari
:
tanggal
:
tempat
: Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Jember Tim Penguji
Ketua,
Sekretaris,
Agustina Pradjaningsih, S.Si., M.Si. NIP 197108022000032009
Drs. Moh. Hasan, M.Sc., Ph.D. NIP 196404041988021001
Anggota I,
Anggota II,
Kosala Dwidja Purnomo, S.Si., M.Si. NIP 196908281998021001
Kristiana Wijaya, S.Si., M.Si. NIP 197408132000032004
Mengesahkan Dekan,
Prof. Drs. Kusno, DEA, Ph.D. NIP 196101081986021001
vi
RINGKASAN
Optimasi Rute Multiple-Travelling Salesman Problem melalui Pemrograman Integer dengan Metode Branch and Bound; Eka Poespita Dewi; 051810101068; 2009; 43 Halaman; Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Jember Multiple-Travelling Salesman Problem (m-TSP) merupakan sebuah persoalan pencarian rute terpendek, untuk sejumlah n kota dan ditambahkan m orang sales yang berkumpul dan berangkat dari kota yang sama dan selanjutnya n – 1 kota lainnya dikunjungi tepat satu kali oleh satu orang sales, dan akhirnya semua sales kembali ke kota asal. Beberapa metode penyelesaian m-TSP telah dikenalkan dan banyak dikembangkan. Dalam skripsi ini dibahas metode penyelesaian m-TSP yang diformulasikan dengan pemrograman integer. Tujuan yang ingin dicapai adalah mendapatkan rute optimal MultipleTravelling Salesman Problem (m-TSP) melalui pemrograman integer dengan metode Branch and Bound. Langkah-langkah yang dilakukan untuk mencapai tujuan tersebut yaitu merumuskan formulasi pemrograman integer m-TSP yang disusun oleh jumlah kota (n), jumlah sales (m), dan jumlah minimal kota yang harus dilewati oleh tiap sales (K); menyelesaikan pemrograman linier relaksasi dari pemrograman integer mTSP dengan LPSolve IDE 5.5.0.5; dan dilanjutkan langkah optimasi menggunakan metode Branch and Bound. Dalam metode Branch and Bound, jika batas atas dan batas bawah bernilai sama maka didapatkan solusi optimal m-TSP. Solusi optimal m-TSP berupa total jarak perjalanan terpendek dan rute perjalanan masing-masing sales. Untuk m-TSP 10 kota, 15 kota, dan 20 kota dengan jumlah sales yang divariasikan, solusi optimal diperoleh jika jumlah sales yang digunakan paling sedikit (2 sales). Dalam penggunaan sejumlah kota dan sales yang konstan bisa didapatkan nilai K yang tidak tunggal. Untuk nilai K yang berbeda, pada umumnya diperoleh total jarak perjalanan yang semakin pendek dengan semakin kecilnya nilai K.
vii
PRAKATA
Puji syukur penulis panjatkan kehadirat Allah SWT., atas segala rahmat, taufik, dan hidayah-Nya, sehingga penulis dapat menyelesaikan skripsi yang berjudul Optimasi Rute Multiple-Travelling Salesman Problem melalui Pemrograman Integer dengan Metode Branch and Bound. Shalawat dan salam semoga selalu tercurahkan kepada tauladan kita, Nabi Muhammad SAW., beserta keluarga, sahabat, dan orangorang yang tetap istiqomah menempuh jalan-Nya. Skripsi ini disusun guna memenuhi salah satu syarat untuk memperoleh gelar Sarjana Sains Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Jember. Penulisan skripsi ini tidak lepas dari bantuan berbagai pihak. Oleh karena itu, penulis menyampaikan terima kasih kepada : 1. Ibu Agustina Pradjaningsih, SSi., MSi. selaku Dosen Pembimbing Utama serta Bapak Drs. Moh. Hasan, MSc., PhD selaku Dosen Pembimbing Anggota dan Dosen Pembimbing Akademik yang tulus ikhlas telah meluangkan waktu, tenaga, dan pikirannya dalam pembimbingan untuk terselesaikannya skripsi ini; 2. Bapak Kosala Dwidja Purnomo, SSi., MSi. dan Ibu Kristiana Wijaya, SSi., MSi. selaku Dosen Penguji yang telah memberikan kritik dan saran sehingga skripsi ini menjadi lebih baik; 3. Mas Sabdo, mbak Anik ‘n The Photoshop, Nurul, dan Faiq serta seluruh rekan angkatan 2005 Jurusan Matematika atas segala kebersamaan dan dukungannya selama ini; 4. Semua pihak yang tidak dapat disebutkan satu per satu. Penulis memohon maaf kepada semua pihak apabila terdapat kesalahan penulisan dalam skripsi ini. Semoga skripsi ini bermanfaat bagi semua pihak.
Jember, Oktober 2009
Penulis
viii
DAFTAR ISI
Halaman HALAMAN JUDUL ................................................................................. i HALAMAN PERSEMBAHAN ............................................................... ii HALAMAN MOTTO .............................................................................. iii HALAMAN PERNYATAAN ................................................................... iv HALAMAN PEMBIMBINGAN .............................................................. v HALAMAN PENGESAHAN .................................................................. vi RINGKASAN ........................................................................................... vii PRAKATA ................................................................................................ viii DAFTAR ISI ............................................................................................. ix DAFTAR GAMBAR ................................................................................. xi DAFTAR TABEL ..................................................................................... xii BAB 1 PENDAHULUAN ...................................................................... 1 1.1 Latar Belakang ..................................................................... 1 1.2 Permasalahan ....................................................................... 3 1.3 Tujuan ................................................................................... 3 1.4 Manfaat ................................................................................. 4 BAB 2 TINJAUAN PUSTAKA .............................................................. 5 2.1 Teori Graf .............................................................................. 5 2.2 Pemrograman Integer .......................................................... 9 2.3 Multiple-Travelling Salesman Problem (m-TSP) ................ 14 BAB 3 METODE PENELITIAN ........................................................... 18 3.1 Langkah-langkah Penyelesaian ........................................... 18 3.2 Data ........................................................................................ 20 BAB 4 HASIL DAN PEMBAHASAN ................................................... 22 4.1 Hasil ....................................................................................... 22
ix
4.1.1 Formulasi pemrograman integer untuk m-TSP dengan n = 10 kota dan m = 2 orang sales ................................ 22 4.1.2 Penyelesaian manual dengan metode Branch and Bound ........................................................ 27 4.1.3 Penyelesaian dengan program optimasi LPSolve IDE 5.5.0.5 ..................................................... 34 4.2 Pembahasan .......................................................................... 40 BAB 5 KESIMPULAN DAN SARAN ................................................... 42 5.1 Kesimpulan ............................................................................ 42 5.2 Saran ...................................................................................... 42 DAFTAR PUSTAKA ................................................................................ 43 LAMPIRAN ............................................................................................... 44
x
DAFTAR GAMBAR
Halaman 2.1 Graf G ................................................................................................... 5 2.2 Digraf D ................................................................................................ 6 2.3 Ilustrasi jalan, lintasan berarah Hamilton, dan sirkuit Hamilton .......... 7 2.4 Contoh pseudodigraph (a) dan multiple digraph (b) ............................ 7 2.5 Contoh digraf simetrik .......................................................................... 8 2.6 Contoh digraf asimetrik ....................................................................... 8 2.7 Diagram alir (flow chart) metode Branch and Bound untuk menyelesaikan pemrograman integer................................................... 12 2.8 Travelling Salesman Problem (TSP) asimetrik dengan n = 4 ............... 13 2.9 Multiple-Travelling Salesman Problem (m-TSP) dengan n = 16 dan m = 3 .................................................................................. 14 3.1 Diagram alir (flowchart) penyelesaian m-TSP ..................................... 18 4.1 Pohon penyelesaiaan awal .................................................................... 29 4.2 Pohon penyelesaiaan iterasi 1 ............................................................... 31 4.3 Pohon penyelesaiaan pencabangan kedua............................................. 31 4.4 Pohon penyelesaiaan akhir .................................................................... 33 4.5 Tampilan awal LPSolve IDE 5.5.0.5 ..................................................... 34 4.6 Tampilan LPSolve IDE 5.5.0.5 format LINDO .................................... 34 4.7 Tamplian LPSolve IDE 5.5.0.5 saat menginputkan formulasi m-TSP .. 35 4.8 Tampilan LPSolve IDE 5.5.0.5 saat diperoleh hasil optimal m-TSP .... 35 4.9 Ilustrasi rute m-TSP 10 kota dengan 2 orang sales ............................... 37
xi
DAFTAR TABEL
Halaman 3.1 Jarak antar kota ..................................................................................... 21 4.1 Identifikasi solusi optimal m-TSP n = 10 dengan m = 2 ....................... 37 4.2 Nilai-nilai solusi optimal m-TSP 10 kota, 15 kota, dan 20 kota ........... 38
xii
