Combinatorial Problem adalah suatu permasalahan matematis dalam
menyusun, mengelompokan, mensorting, atau memilih sejumlah objek diskrit
tertentu.
Kesulitan dari Combinatorial Problem antara lain adalah:
1. Sejumlah objek Kombinatorik tertentu tumbuh dengan cepat seiring
peningkatan ukuran masalah.
2. Tidak diketahui algoritma pasti yang dapat menyelesaikan masalah
Combinatorial Problem.
Beberapa Combinatorial Problem memang dapat diselesaikan dengan
algoritma yang efisien, Tapi itu harus mengikuti aturan-aturannya. Berikut ini
adalah Contoh kasus dari Combinatorial Problem :
1.Vehicle Routing (VRP)
VRP atau Vehicle Routing merupakan permasalahan optimasi penentuan
rute dengan keterbatasan kapasitas kendaraan. Contoh dari permasalahan ini
adalah ketika terdapat salesman yang berangkat dari suatu kota kemudian
melakukan kunjungan ke sejumlah kota. Setiap kotanya hanya dapat dikunjungi oleh satu
salesman saja. Tujuan utamanya adalah meminimalkan total jarak atau total biaya
perjalanan. VRP merupakan permasalahan klasik yang sangat dekat dengan kehidupan
manusia. Contoh permasalahan yang dapat diselesaian dengan pendekatan VRP
antara lain penentuan rute pengiriman surat, paket, laundry, Koran dll.
Algoritma yang dapat menyelesaikan masalah Combinatorial Problem diantaranya
adalah Genetic Algoritm, Tabu Search, Simulated Annealing, Nearest Neighbor dan
CODEQ.
Dan
ini adalah salah satu step by step dalam memecahkan Vehicle Routing Problem
dengan menngunakan Algoritma Nearest
Neighbor :
a . Titik awal rute dimulai
dari depot atau gudang.
b . Mencari lokasi pelanggan
terdekat dari depot yang belum dikunjungi. Lokasi terdekat inilah yang menjadi
lokasi pertama yang akan dikunjungi.
c . Mencari lokasi lain yang
terdekat dari lokasi terpilih sebelumnya. Dalam mencari lokasi lain ini
terdapat beberapa pertimbangan yaitu:
1. Total
jumlah pengiriman tidak melebihi kapasitas kendaraan yang digunakan.
2. Jika terdapat
lokasi terpilih berikutnya dan masih terdapat sisa kapasitas kendaraan maka
ulangi langkah (b).
d . Apabila kendaraan tidak
memiliki sisa kapasitas, maka kembali ke langkah (1).
e . Algoritma berhenti jika
semua pelanggan telah dikunjungi tepat satu kali
2.Travelling Salesman Problem (TSP)
TSP atau Travelling Salesman Problem merupakan masalah kombinasi
optimasi dalam menemukan tour yang paling terpendek. TSP adalah problem untuk
menentukan urutan dari sejumlah kota yang harus dilalui oleh salesman, setiap
kota hanya boleh dilalui satu kali dalam perjalanannya, dengan jarak antara
setiap kota satu dengan setiap kota lainnya sudah diketahui. Salesman tersebut
harus meminimalkan biaya dan jarak yang harus ditempuh dalam perjalanan
tersebut.
Berikut adalah step by step dalam meyelesaikan Travelling Salesman
Problem:
a. Siapakan Matriks biaya untuk menghitung bobot. Jika biaya matriks yang dimasukkan tidak matriks persegi kemudian menambahkan kolom baru dengan nol elemen biaya.
b. Tentukan elemen minimum di setiap baris dan mengurangi elemen minimum disetiap baris dari semua elemen dari baris masing-masing.
c. Sekarang kita mempunyai matriks yang dihasilkan. Sekarang ulangi proses yang sama dari langkah b untuk semua kolom yaitu menentukan elemen minimum di setiap kolom dan kurangi yang nilai minimum dari semua kolom masing-masing untuk mendapatkan matriks yang baru dihasilkan.
a. Siapakan Matriks biaya untuk menghitung bobot. Jika biaya matriks yang dimasukkan tidak matriks persegi kemudian menambahkan kolom baru dengan nol elemen biaya.
b. Tentukan elemen minimum di setiap baris dan mengurangi elemen minimum disetiap baris dari semua elemen dari baris masing-masing.
c. Sekarang kita mempunyai matriks yang dihasilkan. Sekarang ulangi proses yang sama dari langkah b untuk semua kolom yaitu menentukan elemen minimum di setiap kolom dan kurangi yang nilai minimum dari semua kolom masing-masing untuk mendapatkan matriks yang baru dihasilkan.
d. Sekarang setelah baris
dan kolom operasi, menarik sejumlah minimum garis horizontal dan vertikal untuk
menutupi semua nol dalam menghasilkan matriks. Membiarkan menjadi jumlah
minimum bariis dan N urutan Matriks. Kemudian akan terjadi 2 kemungkinan yang
mungki terjadi
1. Jika a = n, maka tugas optimasi jalur bisa dilakukan
2. Jika N<n, kemudian lanjutkan.
e. Sekarang menemukan unsur
erungkap terkecil dalam matriks dengan garis “a”.
f. Kurangi minimum elemen
yang dapat diperoleh pada langkah 5 dari semua elemen ditemukan dan menambahkan
elemen yang sama di persimpangan garis horizontal dana vertical untuk
mendapatkan matriks menengah.
g. Ulangi langkah (b) ke
langkah (d) sampai kita endapatkan kasus a = n.
h. Periksa berturut-turut
baris demi baris sampai nol tunggal ditemukan. Lingkaran nol ini untuk membuat
tugas dan kemudian tandai silang(X) di semua nol jika berbaring dikolom yang
lingkari nol. Ini menunjukan bahwa mereka tidak dapat dipertimbangkan untuk
tugas di masa mendatang.
i. Lanjutkan dengan cara ini sampai semua nol telah
diperiksa. Ulangi prosedur yang sama untuk kolom juga.
j. Ulangi langkah (g)
berturut-turut sampai salah satu kondisi dibawah ini muncul:
1. Jika tidak
ada angka nol tanpa tanda terisis, maka akhiri proses.
2. Jika ada
terdapat lebih dari satu nol dalam kolom. Lingkari dan tandai di kolom yang
tersisa nol dan ulangi proses samapai tidak ada nol yang tidak ditandai dalam
matriks.
j. Jadi
tandai nol di setiap baris dan setiap kolom dari matriks yang diperoleh dan nol
yang ditandai akan memberikan penugasan yang optimal.
Daftar Pustaka:
Daftar Pustaka:
0 komentar:
Posting Komentar