E-Jurnal Matematika Vol. 8(4), November 2019, pp.285-288

DOI: https://doi.org/10.24843/MTK.2019.v08.i04.p266

ISSN: 2303-1751

APLIKASI ALGORITME BRANCH AND BOUND DALAM MODEL OPTIMISASI ROBUST

Lailatul Rizkiana1§, Ni Ketut Tari Tastrawati2, Ni Luh Putu Suciptawati 3

1Program Studi Matematika, Fakultas MIPA – Universitas Udayana [Email: la3larizqiana@gmail.com]

2Program Studi Matematika, Fakultas MIPA – Universitas Udayana [Email: tastrawati@unud.ac.id]

3Program Studi Matematika, Fakultas MIPA – Universitas Udayana [Email: suciptawati@unud.ac.id]

§Corresponding Author

ABSTRACT

Bali is one of the regions in Indonesia which is famous for its tourism. Vacationing in Bali seems to be a must for every tourist, both domestic and foreign tourists. For tourists who are on vacation many things are considered be it time, distance, cost and others. Travel time with a distance that is already known is something that can not be estimated with certainty, given the many factors that influence including traffic conditions, weather, or road infrastructure. Robust optimization is one area of optimization that solves problems with uncertainty which in this study uses a box uncertainty set approach. Optimization problems can be solved by a branch and bound algorithm, the results obtained in the form of tourist attraction routes should be chosen with a minimum time and influenced by indefinite factors.

Keywords: Branch and Bound Method, Box Uncertainty Set, Robust Optimization, Travelling Salesman Problem (TSP).

  • 1.    PENDAHULUAN

Permasalahan optimisasi merupakan salah satu bidang yang dibahas dalam pemrograman linear. Beberapa metode optimisasi yang sudah dikenal dan mengatasi permasalahan linear salah satunya adalah algoritme branch and bound. Algoritme ini dibuat untuk pemrograman linear (linear programming), namun algoritme ini mampu menyelesaikan permasalahan seperti travelling salesman problem (TSP) dan beberapa masalah lainnya.

Hasil yang diperoleh dalam penyelesaian linear programming terkadang dirasa kurang tepat saat harus diterapkan dalam dunia nyata mengingat permasalahannya yang kompleks dan dipengaruhi oleh faktor-faktor taktentu. Prawirosentono (2005) menjelaskan bahwa tingkat keberhasilan penyelesaian masalah model matematika yang lengkap tergantung pada tersedianya data yang tepat dan pasti. Bila datanya tidak diketahui dengan tepat, akan mengakibatkan rendahnya mutu penyelesaian masalah. Data yang dimaksud di sini adalah data yang berkenaan dengan permasalahan dalam suatu model matematika.

Masalah optimisasi taktentu (optimization under uncertainty) merupakan cabang ilmu

matematika bidang optimisasi dengan data masalah yang taktentu. Ketidaktentuan dapat disebabkan beberapa hal diantaranya kesalahan pengukuran, kesalahan dalam pemodelan, atau tidak tersedianya informasi yang diperlukan ketika keputusan harus diambil (Chaerani dkk. 2009). Kasus penentuan rute terbaik, waktu atau jarak tempuh antartempat sulit untuk diprediksi mengingat adanya faktor-faktor taktentu yang memengaruhinya, seperti kondisi cuaca atau kondisi lalu lintas yang menyebabkan solusi penentuan rute terbaik yang diperoleh akan menjadi kurang tepat untuk dijalankan.

Menurut Gorissen et al. (2015), terdapat dua metode optimisasi yang dapat mengatasi permasalahan linear dengan data taktentu, yaitu optimisasi stokastik dan model optimisasi robust. Berbeda dengan optimisasi stokastik, model optimisasi robust tidak mengasumsikan bahwa distribusi peluang data taktentu diketahui, melainkan terletak dalam himpunan taktentu (uncertainty set) yang dilambangkan dengan himpunan U . Uncertainty set merupakan himpunan nilai beranggotakan parameter taktentu (uncertain parameters) dalam permasalahan optimisasi robust.

Konsep    awal    optimisasi    robust

diperkenalkan oleh Mulvey et al. (1995) yang pada saat itu memperkenalkan optimisasi robust dengan desain rantai pasok (supply chain) yang optimal di dunia nyata dan lingkungan yang taktentu (uncertain environment) (Fereiduni dan Shahanaghi, 2016). Selanjutnya banyak peneliti yang membahas model robust ini diantaranya Ben-Tal dan Nemirovski (2002) yang mendefinisikan optimisasi robust sebagai metodologi pemodelan dimana data taktentu (uncertain data) terletak dalam himpunan taktentu (uncertainty set). Bertsimas et al (2011) yang menjelaskan aplikasi robust dalam beberapa bidang yaitu bidang finansial dengan permasalahan portofolio, bidang statistika, bidang manajemen persediaan barang, dan bidang teknik, sedangkan Chaerani dan Roos (2013) yang memberikan penjelasan singkat mengenai optimisasi robust dengan mengilustrasikan dalam contoh yang sederhana.

Penentuan rute terbaik menyerupai permasalahan travelling salesman problem (TSP). TSP adalah pencarian rute terpendek dari seorang salesman yang dimulai dari suatu titik awal (keberangkatan), kemudian mengunjungi kota lainnya dan kembali lagi ke titik awal tanpa melewati kota-kota yang sudah dilewati. Dengan kata lain setiap kota hanya dilewati satu kali. Serupa dengan contoh tersebut yakni pencarian rute terpendek dari sejumlah objek wisata yang dilalui wisatawan bila wisatawan berangkat dari terminal kedatangan dan keberangkatan (bandara) lalu menyinggahi setiap objek wisata tepat satu kali dan kembali lagi ke titik awal (bandara) tanpa melewati kembali objek wisata yang telah disinggahi.

  • 2.    METODE PENELITIAN

  • A.    Jenis dan Sumber Data

Jenis data yang digunakan adalah data kuantitatif, yakni waktu tempuh antar 10 objek wisata yang tersebar di wilayah Bali Selatan dengan satuan menit. Sumber data yang digunakan dalam penelitian ini adalah data sekunder yang diperoleh dari aplikasi Google Maps, yaitu jarak antar 10 objek wisata yang tersebar di wilayah Bali Selatan.

  • B.    Teknik Analisis Data

Langkah-langkah pada penelitian ini adalah:

  • 1.    Memilih sepuluh objek wisata yang ada di wilayah Bali Selatan.

  • 2.    Mengumpulkan data waktu tempuh (satuan menit) antar objek wisata menggunakan

aplikasi Google Maps.

  • 3.  Membuat  model deterministik  untuk

masalah waktu tempuh antar objek wisata.

  • 4.  Membuat model optimisasi robust untuk

masalah waktu tempuh antar objek wisata.

  • 5.  Membuat model optimisasi robust untuk

masalah waktu tempuh antar objek wisata dengan pendekatan box uncertainty set.

  • 6.    Melakukan perhitungan untuk memperoleh rute terpendek dengan waktu minimum menggunakan algoritme branch and bound

  • 3.    HASIL DAN PEMBAHASAN

Model Linear TSP untuk Kasus Pencarian Rute

n n

min Z =∑∑^ij xiJ , ^ij =∞,∀i=

I=O j=o n

S.t∑ xU=1,i=0,1,2,⋯,n

J=o n

(1)


∑ xU=1,j =0,1,2,⋯,n

i=o

xH = {0,1}

dengan ^ij adalah vektor kolom yang merepresentasikan waktu tempuh perjalanan dari objek wisata i ke objek wisata j, xij adalah vektor kolom yang memuat variabel keputusan perjalanan dari objek wisata i ke objek wisata j dilakukan atau tidak.

Model Optimisasi Robust TSP untuk Kasus Pencarian Rute

Pada sub bagian ini, digunakan box uncertainty dimana himpunan unsur taktentu U diasumsikan berbentuk box dan berpusat di t. Dalam penelitian ini, diasumsikan bahwa parameter data yang taktentu adalah koefisien pada fungsi objektif. Permasalahan tersebut dapat diformulasikan sebagai TSP taktentu seperti di bawah ini:

n n

min Z =∑∑^ij xiJ , ^iJ =∞,∀i=

n                                          (2)

S.t∑ xU=1,i=0,1,2,⋯,n

J=o

n

∑ xij=1,j =0,1,2,⋯,n i=o

xH = {0,1}

t∈U

Fungsi objektif pada persamaan (2) memuat unsur taktentu, maka fungsi objektif dikonstruksi menjadi sebuah fungsi objektif tentu dengan menghilangkan parameter taktentu dari fungsi objektif dan menyajikan dalam bentuk fungsi variabel tunggal σ, sehingga diperoleh,

min σ n n

S.t ∑∑ ^ij xij ≤σ

i=o j=o n

∑ xU=1,i =0,1,2,⋯,n

J=o n

∑ xU=1,j =0,1,2,⋯,n i=o

xU = {0,1}

t∈U

σ≥0

(3)


Diasumsikan U adalah himpunan tak tentu yang berbentuk box (persegi panjang), diperoleh U={t: =(t- γt,t+ γt)}. Data dalam kasus ini merupakan waktu, maka akan dipilih batas dengan kemungkinan terburuk yaitu ̂=t+ γt=(1+Y)t. Fungsi kendala pada model di atas memuat pertidaksamaan sehingga harus ditambah variabel slack.

min σ

n n

S.t  ∑∑(1+Y) ⅛ J xi J -σ+s=0

i=oJ=O

n

∑ xU=1,i =0,1,2,⋯,n

J=o n

∑ xij=1,j =0,1,2,⋯,n i=o

xiJ = {0,1} t∈U σ,s≥0

(4)


dengan σ merupakan nilai yang membatasi unsur ketidakpastian pada fungsi objektif, x merupakan variabel keputusan perjalanan

dilakukan atau tidak, S merupakan variabel

slack, Y merupakan nilai tertentu yang berpengaruh dalam pengambilan keputusan, dan

^iJ merupakan data waktu tempuh perjalanan

dalam satuan menit dari objek wisata i ke objek wisata j . Berdasarkan penjabaran di atas, maka dapat disimpulkan hasil pencarian rute optimal untuk wilayah Bali Selatan.

Data untuk wilayah Bali Selatan adalah (0) Bandara Internasional I Gusti Ngurah Rai, (1) Pantai Kuta, (2) Pantai Pandawa, (3) Pura Uluwatu, (4) Garuda Wisnu Kencana (GWK), (5) Pantai Nusa Dua, (6) Pantai Dreamland, (7) Pantai Legian, (8) Pantai Seminyak, (9) Tanjung Benoa, dan (10) Pantai Sanur.

  • a.    Tanpa Optimisasi Robust

Berdasarkan persamaan (1) yang telah disubstitusi data Wilayah Bali Selatan diperoleh:

  • (i) . Nilai fungsi objektif  (Z)=304

artinya total waktu tempuh untuk mengunjungi seluruh objek wisata adalah 304 menit.

  • (ii) . χo,4=   ,6=   ,3=   ,2=   , =

X9 ,5=   ,10 =    ,7=   ,1=   , =

, =1 artinya rute perjalanan yang

ditempuh adalah     (0) Bandara

Internasional I Gusti Ngurah Rai - (4) Garuda Wisnu Kencana (GWK) - (6) Pantai Dreamland - (3) Pura Uluwatu - (2) Pantai Pandawa - (9) Tanjung Benoa - (5) Pantai Nusa Dua - (10) Pantai Sanur - (7) Pantai Legian - (1) Pantai Kuta - (8) Pantai Seminyak -(0) Bandara Internasional I Gusti Ngurah Rai.

  • b.    Dengan Optimisasi Robust

Berdasarkan persamaan (4) yang telah disubstitusi data Wilayah Bali Selatan diperoleh:

  • (i) . Nilai fungsi objektif (Z) =364.8 artinya total waktu tempuh untuk mengunjungi seluruh objek wisata adalah 364.8 menit.

  • (ii) . χo,4=   ,6=   ,3=   ,2=   , =

X9 ,5=   ,10 =    ,7=   ,1=   , =

, =1 artinya rute perjalanan yang

ditempuh adalah     (0) Bandara

Internasional I Gusti Ngurah Rai - (4) Garuda Wisnu Kencana (GWK) - (6) Pantai Dreamland - (3) Pura Uluwatu - (2) Pantai Pandawa - (9) Tanjung Benoa - (5) Pantai Nusa Dua - (10) Pantai Sanur - (7) Pantai Legian - (1) Pantai Kuta - (8) Pantai Seminyak -(0) Bandara Internasional I Gusti Ngurah Rai.

Waktu tempuh dengan optimisasi robust didapatkan lebih lama dibanding tanpa optimisasi robust karena dipengaruhi oleh faktor

ketidaktentuan yang disimbolkan dengan nilai Y, namun hasilnya lebih tepat untuk diterapkan dalam kehidupan nyata karena dalam optimisasi robust memasukkan faktor ketidakpastian.

  • 4.    SIMPULAN DAN SARAN

  • A.    Simpulan

Dari pembahasan dan analisis yang telah dilakukan, maka dapat diambil kesimpulan bahwa rute objek wisata wilayah Bali Selatan yang sebaiknya dipilih agar dapat meminimumkan waktu dengan menggunakan model optimisasi robust adalah 0-4-6-3-2-9-510-7-1-8-0 dengan waktu yang dihabiskan selama 364,8 menit setara dengan 5 jam 4 menit 48 detik.

  • B.    Saran

Pada penelitian ini penulis menggunakan bentuk TSP simetris, untuk pengembangannya dapat digunakan bentuk TSP asimetris. Pada penelitian ini penulis menggunakan objek wisata sebagai tujuan utama, diharapkan bagi peneliti selanjutnya untuk mempertimbangkan penginapan dan faktor lainnya yang dapat memengaruhi waktu tempuh.

Gorissen, B. L., Yanikoglu, I., & Hertog, D. d. (2015). A Practical Guide to Robust Optimization. Omega Vol. 53, 124-137.

Mulvey, J. M., Vanderbei, R. J., & Zenios, S. A. (1995). Robust Optimization of Large-Scale Systems. Operations Research, Vol. 43, pp. 264-281.

Fereiduni, M., & Shahanaghi, K. (2016). A Robust Optimization Model for Distribution and Evacuation in the Disaster Response Phase. 121.

Ben-Tal, A., & Nemirovski, A. (2002). Robust Optimization - Methodology and Applications. Math. Program, 92:453-480.

Bertsimas, D., Brown, D. B., & Caramanis, C. (2011). Theory and Applications of Robust Optimization. SIAM Review, Vol. 53, pp. 464-501.

Chaerani, D., & Roos, C. (2013). Handling Optimization under Uncertainty Problem Using Robust Counterpart Methodology. Jurnal Teknik Industri, 15(2):111-118.

Google. Maps. Diakses 12 Februari 2019, dari https://www.google.com/maps

DAFTAR PUSTAKA

Prawirosentono, S. (2005). Riset Operasi dan Ekonofisika. Jakarta: Bumi Aksara.

Chaerani, D., Sudradjat, H., & Firdaniza. (2009). Karakteristik Metode Numerik Baru untuk Menyelesaikan Masalah Optimisasi Tak Tentu yang Melibatkan Variabel Biner. Laporan Akhir Penelitian Hibah Fundamental Dikti 2009. Bandung: Departemen     Pendidikan     Nasional

Universitas Padjadjaran Fakultas MIPA.

288