Seminar Nasional matematıka

Seminar Nasional mATEmATıKA

VOL. 11 TH. 2016

ISSN 1907-3909

UNIVERSITAS KATOLIK PARAHYANGAN PARAHYANGAN CATHOLIC UNIVERSITY

FAKULTAS TEKNOLOGI INFORMASI DAN SAINS FACULTY OF INFORMATION TECHNOLOGY AND SCIENCE Jalan Ciumbuleuit 94, Bandung 40141, Indonesia

Seminar Nasional mATEmATıKA VOL. 11 TH. 2016

ISSN 1907-3909

REVIEWERS Dr. J. Dharma Lesmono

Benny Yong, MSi

Dr. Ferry Jaya Permana, ASAI

Farah Kristiani, MSi

Iwan Sugiarto, MSi

Livia Owen, MSi

Agus Sukmana, MSc

Maria Anestasia, MSi

Erwinna Chendra, MSi

Liem Chin, MSi

Taufik Limansyah, SSi, MT

Alamat Redaksi: Jurusan Matematika, FTIS - UNPAR Gedung 9, Lantai 1 Jl. Ciumbuleuit No. 94, Bandung - 40141

KATA PENGANTAR Puji syukur kami panjatkan ke hadirat Tuhan Yang Maha Esa atas terselenggaranya Seminar Nasional Matematika UNPAR 2016. Seminar ini merupakan kegiatan rutin tahunan yang diselenggarakan oleh Jurusan Matematika, Universitas Katolik Parahyangan, yang dimulai sejak tahun 2005 dan tahun ini merupakan tahun ke-12 penyelenggaraannya. Seminar Nasional Matematika UNPAR ini merupakan wadah pertemuan ilmiah antara matematikawan, guru, peneliti, dan praktisi yang tidak hanya terbatas di bidang matematika saja, melainkan juga penerapannya dalam berbagai bidang ilmu, antara lain dunia medis, ekonomi, lingkungan hidup, gejala alam dan penanganan risiko. Seminar tahun ini mengambil tema “PERANAN MATEMATIKA DALAM PENGELOLAAN RISIKO”. Pemilihan tema ini dilatarbelakangi oleh perkembangan yang cukup pesat dari penerapan matematika di industri keuangan termasuk di dalam pengelolaan risiko suatu perusahaan. Melalui seminar ini diharapkan para peserta dapat saling berbagi pengetahuan dan informasi terbaru sehingga berdampak pada kesiapan yang lebih baik dari Indonesia dalam menghadapi tantangan ini.

Seminar kali ini mengundang tiga orang pembicara dari kalangan akademisi dan praktisi yang akan berbagi pengalaman, gagasan, dan pikiran. Pada sesi pararel, akan dipresentasikan 59 makalah yang merupakan hasil karya dosen, peneliti, dan mahasiswa dari berbagai instansi di tanah air.

Kami atas nama panitia Seminar Nasional Matematika UNPAR 2016 mengucapkan terima kasih atas partisipasinya, semoga bermanfaat bagi semua pihak.

Bandung, September 2016 Ketua Panitia

Dr. J. Dharma Lesmono

i

DAFTAR ISI Kata Pengantar Daftar Isi

...i ...iii-ix

ALJABAR DAN ANALISIS PRIMITIF FUNGSI TERINTEGRAL HENSTOCK-STIELTJES BERNILAI DI RUANG HILBERT Made Benny Prasetya Wiranata dan Ch. Rini Indrati – UGM

...AA 1-8

IDENTITAS BILANGAN FIBONACI DAN BILANGAN LUCAS PADA Z6 Sri Gemawati, Musraini M., Asli Sirait, dan Muslim – Universitas Riau

...AA 9-16

BATAS ATAS PADA NORM-TAK HINGGA DARI INVERS MATRIKS NEKRASOV Euis Hartini – Universitas Padjadjaran

...AA 17-22

PEMBANGKIT SEMIGRUP DAN GRUP Aloysius Joakim Fernandez – Universitas Katolik Widya Mandira

...AA 23-28

STATISTIKA MEMBANGUN APLIKASI STATISTIK DENGAN R SHINY GUI Zulhanif – Universitas Padjadjaran

...ST 1-7

ANALISIS METODE PENGUMPULAN DATA PRODUKTIVITAS BAWANG MERAH DAN CABAI BESAR Anita Theresia – BPS

...ST 8-16

BAYESIAN SPATIAL AUTOREGRESSIVE (BSAR) DALAM MENAKSIR ANGKA PREVALENSI DEMAM BERDARAH (DB) DI KOTA BANDUNG I Gede Nyoman Mindra Jaya, Zulhanif, dan Bertho Tantular – Universitas Padjadjaran …ST 17-24 ESTIMASI REGRESI SEMIPARAMETRIK DENGAN RESPON HILANG MENGGUNAKAN ESTIMATOR TERBOBOT SKOR KECENDERUNGAN Nur Salam – Universitas Lambung Mangkurat

iii

...ST 25-32

PERBANDINGAN METODE ROBUST MELALUI LEAST MEDIAN SQUARE DAN M-ESTIMATOR DALAM MENENTUKAN MODEL WAKTU KELANGSUNGAN HIDUP (SURVIVAL TIME) Soemartini dan Enny Supartini – Universitas Padjadjaran

…ST 33-40

DESAIN SPLIT-BALLOT MTMM UNTUK EVALUASI KUALITAS INSTRUMEN PENGUKURAN Achmad Bachrudin – Universitas Padjadjaran

…ST 41-48

SPARSE MULTINOMIAL LOGISTIC REGRESSION (Studi Kasus Data Kredit Macet di Bank Nasional “N”) M. Fajar Jamiat – Skadron Pendidikan 201 Lanud Sulaiman TNI AU Nusar Hajarisman – Universitas Negeri Islam Bandung Anna Chadidjah – Universitas Padjadjaran

...ST 49-56

ANALISIS KETERTINGGALAN DAERAH DI INDONESIA MENGGUNAKAN REGRESI LOGISTIK BINER Titi Purwandari dan Yuyun Hidayat – Universitas Padjadjaran

…ST 57-62

PENDEKATAN TRUNCATED REGRESSION PADA TINGKAT PENGANGGURAN TERBUKA PEREMPUAN Defi Yusti Faidah, Resa Septiani Pontoh, dan Bertho Tantular – Universitas Padjadjaran

…ST 63-68

ANALISIS VARIANS MULTIVARIATE UNTUK DATA LONGITUDINAL DENGAN PENGUKURAN DATA DILAKUKAN SECARA BERURUT BERDASARKAN WAKTU (REPEATED MEASURE) Enny Supartini dan Soemartini – Universitas Padjadjaran ...ST 69-76 APLIKASI ALGORITMA BOOSTING DALAM REGRESI LOGISTIK Zulhanif – Universitas Padjadjaran …ST 77-81 PENYESUAIAN BAGAN KENDALI ATRIBUT KHUSUSNYA GRAFIK c DENGAN PENDEKATAN EKSPANSI CORNISH-FISHER Irmina Veronika Uskono – Universitas Katolik Widya Mandira ...ST 82-85

MATEMATIKA PENDIDIKAN MENINGKATKAN AKTIVITAS BELAJAR MAHASISWA MELALUI TEKNIK MIND MAP PADA MATA KULIAH MATEMATIKA DISKRIT Ririn Widiyasari – Universitas Muhammadiyah Jakarta ...MP 1-8

iv

PENGEMBANGAN PEMBELAJARAN MATEMATIKA DENGAN PENDEKATAN METAKOGNITIF UNTUK MENINGKATKAN KEMAMPUAN BERPIKIR LOGIS DAN SIKAP POSITIF SISWA SMP Kms. Muhammad Amin Fauzi, Sri Lestari Manurung, dan Arnah Ritonga – Universitas Negeri Medan ...MP 9-17 PENGEMBANGAN BAHAN AJAR MATEMATIK BERBASIS INKUIRI BERBANTUAN MULTI MEDIA UNTUK MENINGKATKAN KEMAMPUAN BERPIKIR KRITIS SISWA SMA SE-PROVINSI SUMATERA UTARA Waminton Rajagukguk, Kms. Muhammad Amin Fauzi, dan Yasifati Hia – Universitas Negeri Medan ...MP 18-25 ANALISIS KESULITAN MAHASISWA DALAM MENYELESAIKAN SOAL KEMAMPUAN ABSTRAKSI MATEMATIS PADA MATA KULIAH STATISTIKA MATEMATIKA Andri Suryana – Universitas Indraprasta PGRI Jakarta ...MP 26-34 PENGEMBANGAN SOAL TIPE PISA DENGAN KONTEKS BATU AKIK Rika Octalisa, Ratu Ilma, dan Somakim – Universitas Sriwijaya ...MP 35-43 FAKTOR PENYEBAB KESALAHAN YANG DILAKUKAN MAHASISWA DALAM MENYELESAIKAN SOAL KEMAMPUAN PEMECAHAN MASALAH MATEMATIS PADA MATA KULIAH TEORI PELUANG Georgina Maria Tinungki – Universitas Hasanuddin

...MP 44-51

PENGEMBANGAN SOAL HOT UNTUK SISWA SMP Indah Sari Kastriandana – Universitas Sriwijaya

...MP 52-58

PEMBELAJARAN MATEMATIKA ANAK BERKEBUTUHAN KHUSUS DI SEKOLAH INKLUSI Chatarina Febryanti dan Ari Irawan – Universitas Indraprasta PGRI Jakarta

...MP 59-64

ALAT PERAGA IRISAN KERUCUT Eyus Sudihartinih dan Tia Purniati – Universitas Pendidikan Indonesia

...MP 65-70

PERBEDAAN PENGARUH BENTUK TES FORMATIF TERHADAP HASIL BELAJAR MATEMATIKA DITINJAU DARI TINGKAT KREATIVITAS SISWA Lasia Agustina – Universitas Indraprasta PGRI

...MP 71-76

v

REPRESENTASI VISUAL PENYELESAIAN SOAL CERITA PECAHAN SISWA SMP Kristoforus Djawa Djong – Universitas Katolik Widya Mandira, Mahasiswa Pasca Unesa

...MP 77-82

PENGARUH PENDEKATAN RECIPROCAL TEACHING TERHADAP KEMAMPUAN BERPIKIR KREATIF MATEMATIKA SISWA Ulfah Hernaeny dan Febrina Lia Dahlia – Universitas Indraprasta PGRI Jakarta ...MP 83-88 PENGARUH GAYA BELAJAR TERHADAP KEMAMPUAN PEMAHAMAN MATEMATIKA Seruni dan Nurul Hikmah – Universitas Indraprasta PGRI

...MP 89-95

PENERAPAN ASESMEN KINERJA MELALUI “PBM” UNTUK MENINGKATKAN KEMAMPUAN BERPIKIR KRITIS, KREATIF MATEMATIK Erik Santoso – Universitas Majalengka

...MP 96-102

PENERAPAN MODEL PEMBELAJARAN TREFFINGER DALAM MENINGKATKAN KEMAMPUAN BERPIKIR KREATIF Roida Eva Flora Siagian – Universitas Indraprasta PGRI Jakarta

...MP 103-109

PENGEMBANGAN BAHAN AJAR BERBASIS PROBLEM BASED LEARNING UNTUK SISWA SMP Asri Nurdayani, Darmawijoyo, dan Somakim – Universitas Sriwijaya

...MP 110-116

ANALISIS PENGARUH SIKAP MAHASISWA PADA MATA KULIAH MATEMATIKA EKONOMI DAN BISNIS TERHADAP PRESTASI BELAJAR Herlina – Universitas Bunda Mulia ...MP 117-121 PENGARUH PENGUASAAN TEKNOLOGI INFORMASI DAN KOMUNIKASI DAN DISIPLIN KERJA TERHADAP PRODUKTIVITAS KERJA GURU Yuan Andinny dan Indah Lestari – Universitas Indraprasta PGRI ...MP 122-130

vi

MATEMATIKA TERAPAN ANALISIS PENGARUH TINGKAT PENGANGGURAN TERBUKA DAN ANGKA MELEK HURUF TERHADAP TINGKAT KEMISKINAN MENGGUNAKAN MODEL FIXED EFFECT (Studi Kasus Wilayah Kabupaten Propinsi Jawa Barat) Ani Andriyati dan Rini Rakhmawati – Universitas Pakuan ...MT 1-8 PENYEBARAN PENYAKIT DEMAM BERDARAH DI SURABAYA MENGGUNAKAN METODE K-MEANS Suzyanna, Purbandini, Indah Werdiningsih, dan Miswanto – Universitas Airlangga Surabaya

...MT 9-16

ENKRIPSI DAN DEKRIPSI TEXT.TXT MENGGUNAKAN KRIPTOSISTEM ELLIPTIC CURVE CRYPTOSYSTEM (ECC) Akik Hidayat, Mira Suryani, dan Akmal – Universitas Padjadjaran

...MT 17-26

PREMI ASURANSI JIWA DWIGUNA LAST SURVIVOR DENGAN DISTRIBUSI PARETO Hasriati, Ihda Hasbiyati, dan T. P. Nababan – Universitas Riau

…MT 27-36

ANALISA PERILAKU KONSUMEN DALAM MENENTUKAN STRATEGI PEMASARAN MENGGUNAKAN CONFIGURAL FREQUENCY ANALYSIS Resa Septiani Pontoh, Defi Yusti Faidah, dan Bertho Tantular – Universitas Padjadjaran

…MT 37-42

MODEL OPTIMASI VAKSINASI Jonner Nainggolan – Universitas Cenderawasih Jayapura

...MT 43-48

PEMANFAATAN FUNGSI MODIFIKASI WEIL PAIRING PADA SKEMA PROXY SIGNATURE Annisa Dini Handayani – Sekolah Tinggi Sandi Negara

...MT 49-54

KONTROL OPTIMUM PADA POPULASI TUMOR DAN WAKTU PENGOBATAN BERDASARKAN MODEL RADIOVIROTHERAPY Embay Rohaeti dan Susi Susanti – Universitas Pakuan

...MT 55-61

INVERS MATRIKS VANDERMONDE Handi Koswara dan Iwan Sugiarto – Universitas Katolik Parahyangan

...MT 62-70

vii

MAHASISWA DISTRIBUSI BETA-PARETO Adrianus Rambe, Siti Nurrohmah, dan Ida Fithriani – Universitas Indonesia

…MS 1-8

PERSAMAAN DIFUSI PADA ZOOPLANKTON Rahmat Al Kafi, Sri Mardiyati, dan Maulana Malik – Universitas Indonesia

…MS 9-16

DISTRIBUSI RAYLEIGH Fitria Andaryani, Siti Nurrohmah, dan Ida Fithriani – Universitas Indonesia

...MS 17-24

PEMILIHAN PORTOFOLIO YANG OPTIMAL DENGAN MENGGUNAKAN METODE ANT COLONY OPTIMIZATION Joseph Martua Nababan dan Liem Chin – Universitas Katolik Parahyangan

...MS 25-32

PENERAPAN ALGORITMA BEE COLONY UNTUK MENYELESAIKAN TRAVELING SALESMAN PROBLEM Refy Kusumah dan J. Dharma Lesmono – Universitas Katolik Parahyangan

...MS 33-40

PEMODELAN PERHITUNGAN PREMI ASURANSI JIWA DWIGUNA UNIT LINK DENGAN GARANSI Bernika Setiawan dan Ferry Jaya Permana – Universitas Katolik Parahyangan

...MS 41-48

PENENTUAN HARGA OPSI SAHAM KARYAWAN (OSK) MODEL HULL-WHITE DENGAN METODE BINO-TRINOMIAL (BTT) Natasha Magdalena dan Erwinna Chendra – Universitas Katolik Parahyangan

...MS 49-58

EKSISTENSI BIONOMIK EQUILOBRIUM PADA MODEL INTERAKSI INDUSTRIALISASI BIOMASSA DAN HEWAN LINDUNG Ganjar, E. Hertini, dan A. K. Supriatna – Universitas Padjadjaran ...MS 59-67 IMPLEMENTASI MODEL HYBRID ARIMA-ANN MENGGUNAKAN FILTER MOVING AVERAGE PADA PERAMALAN NILAI TUKAR DOLAR AS TERHADAP RUPIAH Dian Nurhayati, Bevina D. Handari, dan Fevi Novkaniza – Universitas Indonesia …MS 68-76

viii

MODEL PENYEBARAN PENYAKIT SARS DENGAN PENGARUH VAKSINASI Putri Efelin, Benny Yong, dan Livia Owen – Universitas Katolik Parahyangan

...MS 77-85

STABLE AGE DISTRIBUTION PADA MODEL BACK-CROSSING PERSILANGAN TERNAK LOKAL DAN TERNAK EKSOTIS A. U. Raihan, A. K. Supriatna, dan N. Anggriani – Universitas Padjadjaran

...MS 86-92

MODEL PERSEDIAAN P(R,T) MULTI ITEM DENGAN DISTRIBUSI PERMINTAAN UMUM Handi Koswara dan J. Dharma Lesmono – Universitas Katolik Parahyangan

...MS 93-99

DISTRIBUSI EXPONENTIATED EXPONENTIAL Ridho Okta Pawarestu, Siti Nurrohmah, dan Ida Fithriani – Universitas Indonesia

...MS 100-106

PENENTUAN JARAK MINIMUM DALAM SUATU JARINGAN DENGAN ALGORITMA PRIM DAN PEMROGRAMAN BILANGAN BINER Robby Hardiwinata dan J. Dharma Lesmono – Universitas Katolik Parahyangan

…MS 107-113

ALGORITMA SWEEP DAN ELITE ANT SYSTEM UNTUK MENYELESAIKAN MULTIPLE TRAVELING SALESMAN PROBLEM (MTSP) Karina, Gatot F. Hertono, dan Bevina D. Handari – Universitas Indonesia

…MS 114-119

PENAKSIRAN PARAMETER SKALA DARI DISTRIBUSI NAKAGAMI MENGGUNAKAN METODE BAYES Siti Nur Noviyani Witayati, Ida Fithriani, dan Siti Nurrohmah – Universitas Indonesia

...MS 120-127

ix

PENERAPAN ALGORITMA BEE COLONY UNTUK MENYELESAIKAN TRAVELING SALESMAN PROBLEM Refy Kusumah1 dan J. Dharma Lesmono2 1,2

Jurusan Matematika, Universitas Katolik Parahyangan email : [email protected], [email protected]

Abstrak. Traveling Salesman Problem (TSP) merupakan suatu permasalahan optimasi klasik yang berkaitan erat dengan pencarian rute terpendek. Permasalahan ini dimulai ketika sebuah perusahaan mengirimkan seorang salesman untuk menjajakan produknya secara langsung kepada konsumen yang berada di kota yang berbeda-beda dan salesman tersebut harus melewati setiap kota tepat satu kali. Untuk menyelesaikan masalah TSP digunakan dua metode, yaitu metode optimasi dan metode pendekatan. Lamanya waktu untuk menyelesaikan permasalahan TSP dengan metode optimasi, membuat perkembangan penyelesaian masalah TSP secara efisien (solusi baik dan waktu penyelesaian cepat) dengan menggunakan suatu metode pendekatan. Metode pendekatan penyelesaian TSP dibagi menjadi dua yaitu metode heuristik dan metode metaheuristik. Salah satu metode yang tergolong ke dalam metode metaheuristik adalah algoritma Bee Colony. Metode ini merupakan suatu metode pencari nilai optimal yang dapat digunakan untuk menyelesaikan permasalahan TSP yang terinspirasi dari kehidupan koloni lebah. Lebah merupakan makhluk hidup yang dapat dikatakan memiliki tatanan kehidupan yang sangat baik. Di dalam sebuah koloni ada pembagian tugas atau kerja yang sangat teratur. Kebiasaan lebah dalam mencari makanan menjadi inspirasi bagi algoritma ini. Jalur menuju sumber makanan terdekat merupakan solusi jika dikaitkan dengan permasalahan TSP. Dalam makalah ini diterapkan Algoritma Bee Colony untuk menyelesaian permasalahan TSP dimana solusi yang diperoleh merupakan solusi yang baik. Kata kunci : Traveling Salesman Problem, Algoritma Bee Colony, metode metaheuristik, rute terpendek

1. PENDAHULUAN Dewasa ini, dunia usaha tumbuh dengan pesat di berbagai negara, termasuk di Indonesia. Seiring dengan perkembangannya, perusahaan harus memiliki cara yang efektif dalam memasarkan produknya. Salah satu cara yang paling efektif adalah dengan mengirimkan seorang salesman untuk menjajakan produk secara langsung ke konsumen. Selanjutnya, yang menjadi permasalahan adalah bahwa konsumen berada di lokasi yang berbedabeda sehingga akan ada biaya yang harus dikeluarkan oleh perusahaan untuk transportasi dari tempat konsumen yang satu ke tempat konsumen yang lain. Maka berdasarkan permasalahan tersebut, penting adanya untuk menentukan rute terpendek bagi seorang salesman untuk menjajakan produknya dari tempat keberangkatan hingga tempat setiap konsumen (tujuan) berada. Hal ini dimaksudkan untuk meminimumkan biaya dan waktu yang ada. Masalah seperti ini disebut Traveling Salesman Problem (TSP). Dalam penerapannya, menghitung solusi dari permasalahan TSP (dalam hal ini jarak terpendek) menggunakan metode eksak maupun metode heuristik cukup sulit. TSP adalah permasalahan dimana seorang salesman melakukan perjalanan untuk menjajakan suatu produk dari satu kota ke kota lain dengan syarat satu kota hanya dilalui tepat satu kali. Artinya, banyak kemungkinan rute yang mungkin dilalui seorang salesman adalah sebanyak 𝑛! namun karena salesman harus pergi dan pulang ke kota yang sama maka banyak kemungkinan adalah (𝑛 − 1)!. Permasalahan TSP MS - 33

menjadi sulit untuk diselesaikan baik dengan metode optimasi maupun metode heuristic ketika jumlah kota yang semakin banyak, dan memerlukan waktu komputasi yang cukup lama. Sebagai ilustrasi, masalah TSP dengan 8 kota memerlukan proses pencarian rute dari 5.040 rute yang ada [1]. Lamanya waktu yang dibutuhkan untuk menyelesaikan suatu permasalahan TSP dengan menggunakan metode optimasi ataupun metode heuristik membuat perkembangan penyelesaiannya dengan metode metaheuristik yang merupakan suatu metode pendekatan untuk menyelesaikan suatu permasalahan dengan efisien (hasilnya adalah solusi yang baik dan waktu penyelesaiannya cepat). Ada banyak metode metaheuristik, namun yang digunakan di dalam makalah ini adalah algoritma Bee Colony. Metode ini merupakan metode pencari nilai optimal untuk permasalahan TSP yang terinspirasi dari kehidupan koloni lebah dalam mencari makanan [2]. Panjang jalur menuju sumber makanan terdekat merupakan solusi jika dikaitkan dengan permasalahan TSP.

2. KAJIAN PUSTAKA 2.1. TRAVELING SALESMAN PROBLEM Secara historis, TSP merupakan sebuah permasalahan yang berhubungan dengan pencarian jalur terpendek dari 𝑛-kota dengan kondisi dimana setiap kota dikunjungi tepat satu kali [3]. Sebagai sebuah permasalahan optimasi, tentunya TSP sendiri memiliki fungsi tujuan dan kendalanya. Fungsi tujuan dan kendalanya adalah sebagai berikut : Min 𝑧 = ∑𝑛𝑖=1 ∑𝑛𝑗=1 𝑑𝑖𝑗 𝑥𝑖𝑗 dengan 𝑑𝑖𝑗 = ∞ untuk semua 𝑖 = 𝑗 dengan kendala :

∑𝑛𝑖=1 𝑥𝑖𝑗 = 1, 𝑖 = 1,2, … , 𝑛 ∑𝑛𝑗=1 𝑥𝑖𝑗 = 1, 𝑖 = 1,2, … , 𝑛 1, jika kota 𝑗 dicapai dari kota 𝑖 𝑥𝑖𝑗 = { 0, lainnya

Keterangan : 𝑧 = fungsi tujuan 𝑑𝑖𝑗 = jarak kota 𝑖 ke kota 𝑗 Solusi optimum dari permasalahan TSP diperoleh ketika terbentuk sebuah tour dari kota-kota yang ada di permasalahan TSP tersebut. Jika yang diperoleh adalah sebuah sub-tour, maka solusi dari permasalahan TSP belum diperoleh.

Gambar 1. Permasalahan TSP

Gambar 2. Solusi berupa Tour

MS - 34

Gambar 3. Solusi berupa Sub-Tour

2.2. METODE PENYELESAIAN TRAVELING SALESMAN PROBLEM Dalam penyelesaian TSP terdapat beberapa metode untuk menyelesaikannya. Metode-metode tersebut kemudian dikelompokkan menjadi dua kelompok besar yaitu metode optimasi dan metode pendekatan. Perbedaan yang paling mencolok dari dua metode ini adalah solusi yang didapat. TSP dapat diselesaikan dengan metode optimasi karena memenuhi beberapa kriteria, yaitu memiliki fungsi tujuan dan kendala. Fungsi tujuan yang dimaksud ialah meminimumkan rute perjalanan seorang salesman dan kendala yang ada ialah setiap kota harus dilewati tepat satu kali. Metode optimasi akan menghasilkan solusi yang optimal karena menggunakan perhitungan eksak di dalamnya, sedangkan metode pendekatan akan menghasilkan solusi yang baik (mendekati optimal). Yang termasuk metode optimasi diantaranya adalah metode Complete Enumeration dan metode Branch and Bound. Metode pendekatan dibagi menjadi dua, yaitu metode heuristik dan metode metaheuristik. Perbedaan utama antara metode heuristik dan metaheuristik adalah sifat yang dimiliki keduanya. Metode heuristik bersifat problem dependent sedangkan metode metaheuristik bersifat problem independent. Problem dependent artinya bergantung pada permasalahan, jadi metode heuristik itu hanya dapat digunakan untuk jenis permasalahan tertentu [5]. Misalnya, metode Nearest Neighbourhood yang digunakan untuk menyelesaikan permasalahan TSP termasuk metode heuristik karena hanya dapat digunakan untuk menyelesaikan permasalahan TSP saja. Sedangkan problem independent berarti tidak bergantung pada jenis permasalahan. Jadi penerapan metode metaheuristik tidak bergantung pada jenis permasalahan, atau dengan kata lain dapat digunakan untuk berbagai jenis permasalahan. 2.2.1. METODE NEAREST NEIGHBOURHOOD Metode Nearest Neighbourhood (tetangga terdekat) adalah metode yang digunakan untuk menentukan jarak terpendek atau terdekat. Metode ini merupakan metode yang cukup mudah digunakan untuk menyelesaikan suatu permasalahan TSP. Metode ini memanfaatkan jarak ketetanggaan terdekat untuk mencari solusi bagi permasalahan TSP. Solusi bagi permasalahan TSP dari metode Nearest Neighbourhood ini akan langsung menghasilkan sebuah tour [3]. Karena termasuk salah satu metode heuristik, solusi yang diberikan dari metode ini adalah solusi yang baik, bukan solusi optimum. Solusi untuk masalah TSP didapatkan dengan menghubungkan kota yang ditentukan sebagai kota keberangkatan ke kota yang paling dekat dengannya. Hal ini dilakukan terus menerus hingga didapatkan sebuah tour.

3. ALGORITMA BEE COLONY 3.1. LEBAH DAN KOLONINYA Lebah merupakan hewan jenis serangga yang memiliki kehidupan sosial yang sangat teratur. Setiap lebah saling mempengaruhi hidup lebah yang satu dengan yang lainnya di dalam sebuah koloni. Ada pembagian tugas/kerja yang sangat terorganisir di dalam sebuah koloni lebah. Ada yang mengurus hal yang berkaitan dengan reproduksi, makanan, membangun sarang, berpatroli untuk menjaga daerah teritorialnya dan lain sebagainya. Persoalan makanan adalah salah satu hal yang penting untuk menjaga keberlangsungan hidup suatu koloni. Dalam mencari makanan ada tiga kelompok kerja dimana setiap kelompok memiliki peranan penting dalam menentukan sumber makanan yang tepat bagi koloni mereka. Tiga kelompok kerja tersebut yaitu [2] : a. Lebah Pekerja (Employed Bees) Lebah-lebah yang tergolong dalam kelompok kerja ini bertugas untuk mencari sumber makanan pada wilayah tertentu dan pernah dikunjungi sebelumnya. Masing-masing lebah pekerja memiliki wilayah pencarian masing-masing untuk mendapatkan sumber makanan bagi koloninya.

MS - 35

b. Onlooker Bee Lebah-lebah yang tergolong dalam kelompok kerja ini bertugas untuk menghimpun segala informasi dari setiap lebah pekerja kemudian berkumpul dengan sesama onlooker dan kemudian saling bertukar informasi mengenai sumber makanan yang didapat para lebah pekerja. Kemudian masing-masing onlooker tersebut akan memutuskan sumber makanan mana yang akan mereka tuju setelah sebelumnya mencapai sebuah sumber makanan. c. Scouts Bee Lebah-lebah yang tergolong dalam kelompok kerja ini bertugas untuk mencari sumber makanan pada wilayah tertentu yang belum pernah dikunjungi sebelumnya. Lebah-lebah yang mencari sumber makanan ini kemudian akan kembali ke sarang dan berkomunikasi dengan lebah-lebah lainnya melalui sebuah tarian. Tarian lebah (waggle dance) ini merupakan alat komunikasi di dalam suatu koloni. Dengan menggunakan tarian ini lebah yang lain akan menerima informasi mengenai jumlah dan kualitas nektar, jarak sumber makanan dari sarang, dan arah untuk mencapai sumber makanan tersebut. 3.2. TAHAPAN ALGORITMA BEE COLONY Berikut ini adalah beberapa tahapan penting yang harus ada di dalam sebuah algoritma Bee Colony [2] : a. Forage Pada awalnya ditentukan jumlah lebah. Jumlah lebah ini harus sama dengan jumlah kota pada masalah TSP. Tahapan ini akan diterima setiap lebah yang akan mengunjungi sumber makanan ke-𝑖 dan diterapkan ketika lebah tersebut berada dalam situasi dimana harus memilih beberapa pilihan sumber makanan yang lainnya. Pengambilan keputusan ke sumber makanan yang mana lebah akan bergerak ditentukan oleh nilai peluang yang sangat bergantung pada arc fitness dan jarak antar sumber makanan (dalam permasalahan TSP berarti jarak antarkota). Arc fitness dihitung untuk setiap kemungkinan lebah bergerak dari sumber makanan 𝑖 ke sumber makanan 𝑗 pada transisi ke-𝑛 melalui persamaan berikut [4]: , 𝑗 ∈ 𝐹𝑖,𝑛 , |𝐴𝑖,𝑛 | > 1 𝜌𝑖𝑗,𝑛 =

1− |𝐴𝑖,𝑛 ∩ 𝐹𝑖,𝑛 | 𝐴𝑖,𝑛 −𝐹𝑖,𝑛

,

𝑗  𝐹𝑖,𝑛 , |𝐴𝑖,𝑛 | > 1

|𝐴𝑖,𝑛 | = 1 { 1, Keterangan:  : probabilitas dari sebuah kota yang diikuti seekor lebah 𝐴𝑖,𝑛 : deretan kota (yang belum dikunjungi) yang dapat dicapai dari 𝑖 pada transisi ke-𝑛 𝐹𝑖,𝑛 : Himpunan kota yang dapat dikunjungi berdasarkan rekomendasi preferred path Setelah itu, lebah harus mengikuti aturan dalam membuat keputusan dalam memilih kota kunjungan berikutnya. 𝑃𝑖𝑗,𝑛 adalah besarnya kemungkinan lebah bergerak dari kota i ke kota j setelah transisi ke-n yang dirumuskan sebagai berikut [4]: 1 𝛽 [𝜌𝑖𝑗,𝑛 ]𝛼 [ ] 𝑑𝑖𝑗 𝑃𝑖𝑗,𝑛 = 1 𝛽 ∑𝑗∈𝐴𝑖,𝑛 [𝜌𝑖𝑗,𝑛 ]𝛼 [ ] 𝑑 𝑖𝑗

Keterangan: 𝜌𝑖𝑗,𝑛 : arc fitness dari kota i ke kota j setelah transisi ke-n 𝑑𝑖𝑗 : jarak antara kota i dengan kota j 𝐴𝑖,𝑛 : deretan kota (yang belum dikunjungi) yang dapat dicapai dari i pada transisi ke-n  : faktor skalar pengendali arc fitness MS - 36

 : faktor skalar pengendali jarak antar sumber makanan (jarak antarkota). Pada tahapan ini scouts bee dan onlooker bee berperan penting sehingga seringkali disebut tahapan scouts bee dan onlooker bee. b. Waggle Dance Lebah dalam kelompok kerja pencari sumber makanan kemudian akan melakukan tarian saat kembali ke sarang, tarian lebah ini akan berlangsung dalam durasi tertentu. Panjang durasi tarian dipengaruhi oleh jumlah nektar yang ditemukan oleh lebah dari sumber makanan ke-i dan ratarata profitabilitas koloni lebah tersebut. Jumlah nektar dinotasikan sebagai 𝑃𝑓𝑖 dan profitabilitas koloni lebah dinotasikan sebagai 𝑃𝑓𝑐𝑜𝑙𝑜𝑛𝑦 Keduanya didefinisikan sebagai berikut [4] : 𝑃𝑓𝑖 =

1 𝐿𝑖

dengan 𝐿𝑖 = panjang tour

𝑃𝑓𝑐𝑜𝑙𝑜𝑛𝑦 =

1 𝑁 ∑ 𝑃 𝑁 𝑖=1 𝑓𝑖

Lamanya durasi dinotasikan sebagai 𝐷𝑖 dengan K adalah skala faktor yang mengendalikan panjang durasi dan memenuhi persamaan berikut : 𝑃𝑓𝑖 𝐷𝑖 = 𝐾 𝑃𝑓𝑐𝑜𝑙𝑜𝑛𝑦 𝑃𝑓𝑖 dapat ditafsirkan sebagai kuantitas nektar yang dikumpulkan oleh lebah i. Kuantitas nektar yang lebih tinggi/banyak akan dikumpulkan jika lebah melakukan perjalanan dengan rute lebih pendek. Dengan demikian, 𝑃𝑓𝑖 didefinisikan berbanding terbalik dengan panjang tour. Sebelum lebah meninggalkan sarangnya, lebah akan melakukan pengamatan dan mengikuti tarian dari penari sebelumnya dengan probabilitas 𝑃𝑓𝑜𝑙𝑙𝑜𝑤 Probabilitas 𝑃𝑓𝑜𝑙𝑙𝑜𝑤 disesuaikan secara dinamis mengikuti skor profitabilitas lebah dan koloninya berdasarkan Tabel 1. Lebah kemungkinan besar melakukan pengamatan secara acak dan mengikuti mengikuti waggle dance jika rating probabilitasnya rendah jika dibandingkan dengan probabilitas rata-rata koloninya [4]. Tabel 1. Nilai 𝑃𝑓𝑜𝑙𝑙𝑜𝑤 Nilai Probabilitas 𝑃𝑓𝑖 < 0.95𝑃𝑓𝑐𝑜𝑙𝑜𝑛𝑦 0.95𝑃𝑓𝑐𝑜𝑙𝑜𝑛𝑦 ≤ 𝑃𝑓𝑖 < 0.975𝑃𝑓𝑐𝑜𝑙𝑜𝑛𝑦 0.975𝑃𝑓𝑐𝑜𝑙𝑜𝑛𝑦 ≤ 𝑃𝑓𝑖 < 0.99𝑃𝑓𝑐𝑜𝑙𝑜𝑛𝑦 0.99𝑃𝑓𝑐𝑜𝑙𝑜𝑛𝑦 ≤𝑃𝑓𝑖

𝑃𝑓𝑜𝑙𝑙𝑜𝑤 0.8 0.2 0.02 0

Berdasarkan tahapan-tahapan yang harus ada maka dirancanglah algoritma Bee Colony seperti pada Gambar 4. 3.3. HASIL DAN PEMBAHASAN Pada bagian ini akan diterapkan algoritma Bee Colony untuk permasalahan berikut [3]. Seorang penjual buku yang tinggal di kota Basin harus mengunjungi 4 pelanggannya setiap satu bulan sekali yang berada di kota yang berbeda-beda. Sang penjual berada di kota Basin, sementara pelanggannya berada di kota Mena, Kiln, Wald, dan Bon. Diberikan tabel berikut untuk melihat jarak tiap kota :

MS - 37

Tabel 2. Permasalahan TSP untuk 5 Kota Basin Wald Bon Mena Kiln Basin 0 120 220 150 210 Wald 120 0 80 110 130 Bon 220 80 0 160 185 Mena 150 110 160 0 190 Kiln 210 130 185 190 0 Akan dicari rute terpendek bagi penjual buku tersebut.

Gambar 4. Flowchart Algoritma Bee Colony Dengan menggunakan metode Nearest Neighborhood diperoleh solusi awalnya adalah sebesar 760. Solusi awal ini memiliki rute sebagai berikut : Basin-Wald-Bon-Mena-Kiln-Basin. Dengan menggunakan algoritma Bee Colony akan diselesaikan permasalahan tersebut. Sebelumnya kita input terlebih dahulu nilai paramaternya sebagai berikut N = 5 karena jumlah kota ada 5, K = 10, α = 1, β = 1, dan λ = 0.35.. Dengan bantuan program Matlab diperoleh hasil sebagai berikut : Tabel 3. Solusi TSP 5 Kota dengan Algoritma Bee Colony Iterasi keRute Panjang Tour 0 Basin-Wald-Bon-Mena-Kiln-Basin 760 1 Basin-Wald-Bon-Kiln-Mena-Basin 725 2 Basin-Wald-Bon-Kiln-Mena-Basin 725 3 Basin-Wald-Bon-Kiln-Mena-Basin 725 MS - 38

4 5

Basin-Wald-Bon-Kiln-Mena-Basin Basin-Wald-Bon-Kiln-Mena-Basin

725 725

Solusi yang dihasilkan menggunakan metode Algoritma Bee Colony merupakan solusi yang optimum jika kita bandingkan dengan penyelesaian menggunakan metode Branch and Bound yang tergolong metode optimasi. Selanjutnya akan dilihat analisis sensitivitas parameter dari algoritma Bee Colony. Analisis sensitivitas parameter dilakukan untuk mengetahui parameter mana yang paling berpengaruh yang dapat mengakibatkan perubahan pada solusi yang diperoleh menggunakan Algoritma Bee Colony apabila parameter tersebut diubah. Di bawah ini diperlihatkan tabel-tabel yang menunjukan pengaruh parameter terhadap solusi yang dihasilkan untuk permasalahan di atas apabila parameter tersebut diubah. Ada 3 parameter yang akan kita analisis yaitu  (peluang dari kota yang diikuti lebah),  (faktor skalar pengendali arc fitness), dan  (skalar faktor pengendali jarak antarkota). Tabel 4. Nilai  berubah,  dan  tetap Percobaan Panjang Nilai  keTour 1 0.25 735 2 0.35 725 3 0.5 760 4 0.75 760 5 0.95 760

Tabel 5. Nilai  berubah,  dan  tetap Percobaan Panjang Nilai  keTour 1 2 725 2 5 725 3 10 725 4 100 725 5 1000 725

Tabel 6. Nilai  berubah,  dan  tetap Percobaan Panjang Nilai  keTour 1 1 725 2 2 725 3 5 760 4 10 760 5 55 760

Tabel 7. Nilai , ,  berubah-ubah Percobaan Panjang Nilai , , keTour dan  1 λ = 0.25, α = 10, 735 β=5 2 λ = 0.45, α = 5, 725 β=2 3 λ = 0.5, α = 2, 760 β=2

Dari Tabel 4 dapat diketahui bahwa parameter  memberikan pengaruh yang cukup signifikan, nilainya sebaiknya pilih yang cukup kecil. Dari Tabel 5 dapat diketahui bahwa parameter  tidak memberikan pengaruh yang cukup siginifikan terhadap solusi yang diperoleh. Tabel 6 menunjukkan bahwa parameter  juga memberikan pengaruh yang cukup signifikan terhadap solusi yang diperoleh, sebaiknya kita pilih nilai parameter  yang kecil saja. Dari Tabel 7 dapat dilihat bahwa diantara ketiga parameter yang ada, parameter  dan  memberikan pengaruh yang cukup signifikan terhadap panjang tour. Hal ini mengindikasikan bahwa untuk menyelesaikan permasalahan TSP dengan jumlah kota yang semakin banyak, hendaknya memilih nilai yang tepat untuk parameter  dan  dengan memperhatikan hasil dari analisis sensitivitas pada Tabel 7.

4. KESIMPULAN Dari pembahasan pada makalah ini, diperoleh kesimpulan sebagai berikut: 1. Masalah TSP dapat diselesaikan dengan menggunakan algoritma Bee Colony dengan catatan bahwa solusi yang dihasilkan merupakan solusi yang baik (mendekati optimum).

MS - 39

2. Berdasarkan hasil analisis sensitivitas parameter, pemilihan parameter terutama  atau peluang dari kota yang diikuti lebah dan parameter  atau faktor skalar pengendali jarak antarkota sangat mempengaruhi solusi yang dihasilkan algoritma ini.

DAFTAR PUSTAKA [1] Andri Suyandi dan WinWin (2013), Aplikasi Traveling Salesman Problem dengan Metode Artificial Bee Colony, Jurnal Sifo Mikroskil 2013, 14; 59–68. [2] Karaboga, D and Basturk, B (2007). A Powerful and Efficient Algorithm for Numerical Function Optimization: Artificial Bee Colony (ABC) Algorithm, Journal of Global Optimization 2007, 39; 459–471. [3] Taha, H.A.(2010). Operations Research: An Introduction, Pearson Education, Upper Saddle River, New Jersey. [4] Wong, L. P, Low, M.Y.H, and Chong C.S (2009), An Efficient Bee Colony Optimization Algorithm for Traveling Salesman Problem Using Frequency-Based Pruning, IEEE International Conference on Industrial Informatics, 7; 775–782. [5] Sugioko, A (2012). Modifikasi Bee Colony Algorithm dengan Tabu List pada Penjadwalan Job Shop dengan Kriteria Biaya Keterlambatan, Tesis., Universitas Indonesia, 2012.

MS - 40

I SSN 1907 - 3909

9 771907 390914

Alamat Redaksi: Jurusan Matematika, FTIS - UNPAR Gedung 9, Lantai 1 Jl. Ciumbuleuit No. 94, Bandung - 40141

PROSIDING SEMINAR NASIONAL MATEMATIKA 2016