Analisis Algoritma: Combinatorial Problems

Combinatorial Problems atau Masalah Kombinatorial adalah salah satu pokok bahasan pada Matematika Diskrit yang berfungsi untuk menyusun, mengelompokkan, mengurutkan atau memilih sejumlah objek diskrit tertentu. Dalam perkembangan Matematika, dapat dilihat bahwa kajian kombinatorial sangat menarik bagi sebagian orang.

Berikut ini adalah beberapa kesulitan yang terdapat pada Combinatorial Problems :

1. Beberapa objek karbinatorik tumbuh dengan cepat seiring dengan bertambahnya masalah
2. Belum diketahuinya algoritma pasti yang dapat menyelesaikan masalah pada Combinatorial
Problems.

Combinatorial Problem memiliki beberapa contoh sebagai berikut :

1. Travelling Salesman Problems

Travelling Salesman Problem atau yg disingkat dengan TSP adalah sebuah masalah kombinasi optimasi dalam operasi penelitian dan teori ilmu komputer. Dengan daftar sejumlah kota yang akan dikunjungi, cara ini sangat bagus untuk menemukan dengan cepat kota yang akan dikunjungi. TSP adalah sebuah masalah untuk menentukan urutan dari sejumlah kota yang harus dilalui oleh salesman, setiap kota hanya boleh dilalui satu kali dalam perjalanannya, dan perjalanan tersebut harus berakhir pada kota keberangkatannya dimana salesman tersebut memulai perjalananya, dengan jarak antara setiap kota satu dengan kota lainnya sudah diketahui. Salesman tersebut harus meminimalkan pengeluaran biaya, dan jarak yang harus ditempuh untuk perjalanannya tersebut.

Algoritma TSP

Algoritma exhaustive, yaitu dengan mencari semua kombinasi yang mungkin terjadi, kemudian memilih kombinasi perjalanan dengan jarak terdekat, algoritma ini mempunyai kompleksitas n!/2n.
Permasalahan :

• Diberikan n buah kota serta diketahui jarak antara setiap kota satu dengan kota yang lain.
Temukan perjalanan (tour) terpendek yang melalui setiap kota lainnya dengan hanya sekali
melewati kota-kota tersebut dan kembali lagi ke kota asal keberangkatan.
• Permasalahan TSP ini dimodelkan sebagai graf lengkap dengan n buah simpul. Bobot pada
setiap setiap sisi menyatakan jarak antara dua buah kota yang bertetangga.
• Permasalahan TSP tidak lain adalah menemukan sirkuit Hamilton dengan bobot paling
minimum.

Algoritma exhaustive search untuk persoalan TSP :

A. Enumerasikan (list) semua sirkuit Hamilton dari graf lengkap dengan n buah simpul.
B. Hitung (evaluasi) bobot setiap sirkuit Hamilton yang ditemukan pada langkah 1.
C. Pilih sirkuit Hamilton yang mempunyai bobot paling terkecil.

2. Vehicle Routing Problem

Vehicle Routing Problem atau yang disingkat dengan VRP adalah sebuah perhitungan formulasi dengan mempertimbangkan masalah jumlah kendaraan dan rute yang akan dilalui. Pada permasalahan ini, ada sebuah depot awal dan sejumlah n tempat untuk dikunjungi dengan demand yang dapat berbeda-beda. Sebuah kendaraan diharapkan untuk memenuhi permintaan setiap tempat tersebut dari depot.

Berikut ini adalah beberapa dasar yang terdapat pada Vehicle Routing Problems (VRP):

1. Setiap rute berawal dan berakhir pada distribution center.
2. Setaip user hanya boleh menggunakan 1 kendaraan saja.
3. Total permintaan dari masing-masing rute tidak boleh melebihi kapasitas kendaraan rute
tersebut.
4. Total waktu yang dihabiskan kendaraan (waktu perjalanan dan waktu pelayanan) tidak boleh
melebihi batas yang telah ditentukan.
5. Total biaya yang dihasilkan tidak banyak.

Sumber :

https://en.wikipedia.org/