Algoritma Clarke-Wright


Algoritma Clarke-Wright adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai menghubungkan semua titik dengan biaya terendah.



Diasumsikan ada 5 titik yang harus dihubungkan semuanya, yaitu titik A,B,C,D,E
semua titik terhubung secara langsung dengan titik-titik lainnya, dan memiliki biaya sendiri-sendiri
Tentukan jalur yang harus diambil untuk menghubungkan semua titik dengan biaya terendah
Diasumsikan data jalur yang tersedia adalah sebagai berikut

Titik awal Titik Tujuan Biaya
Titik A Titik B 6
Titik A Titik C 4
Titik A Titik D 2
Titik A Titik E 7
Titik B Titik C 5
Titik B Titik D 4
Titik B Titik E 8
Titik C Titik D 7
Titik C Titik E 3
Titik D Titik E 9

Jika diilustrasikan dalam gambar, maka model data awal adalah sebagai berikut
clarke-wright-awal



Sebelum masuk kedalam langkah-langkah pembahasan algoritma, ada beberapa konstanta atau parameter yang harus diketahui, yaitu:
* Tentukan jumlah titik yang harus dihubungkan
Diasumsikan dalam kasus ini, jumlah titik ada 5 buah

* Tentukan titik pusat sebagai acuan saat pencarian jalur
Diasumsikan dalam kasus ini, titik acuan yang digunakan adalah titik pertama


Langkah-langkah penggunaan algoritma ini adalah

1. Inisialisasi semua variabel yang diperlukan, yaitu variabel gambar, titik, dan garis
Penjelasan tentang masing-masing class akan dijelaskan pada skrip dibawah ini

* Agar dapat menjalankan skrip diatas, maka diperlukan sebuah 4 buah class
Class Titik digunakan untuk menampung data titik
Class Garis digunakan untuk menampung data titik awal, titik tujuan, biaya, dan nilai saving jalur tersebut
Class Gambar digunakan untuk menampung semua data titik dan semua data garis yang digunakan
Deklarasi masing-masing class adalah sebagai berikut:

2. Masukkan data titik dan garis kedalam masing-masing variabel yang tersedia

3 Hitung nilai saving dari masing-masing garis
Untuk titik pusat p, maka nilai saving antara titik i dan j dihitung dengan rumus:
s(i,j) = d(p,i) + d(p,j) – d(i,j)
dimana:
s(i,j) adalah nilai saving untuk garis diantara titik i dan j
d(0,1) adalah jarak atau biaya antara titik pusat dan titik i
d(0,j) adalah jarak atau biaya antara titik pusat dan titik j
d(i,j) adalah jarak atau biaya antara titik i dan titik j

* Gunakan fungsi ini untuk mencari garis yang memiliki titik awal dan titik tujuan tertentu

4. Lakukan pengurutan perhitungan sehingga garis yang dihitung lebih dulu adalah garis dengan nilai saving yang tertinggi sampai pada nilai saving yang terendah

5. Lakukan proses pencarian jalur sebanyak jumlah garis (poin 5a – 5c)

5a. Dapatkan garis yang akan dihitung

5b. Lakukan perhitungan apakah ditemukan titik awal garis pada jalur yang sudah ditemukan sebelumnya
Jika ditemukan, maka simpan indeks posisi titik pada jalur tersebut

5c. Lakukan perhitungan apakah ditemukan titik akhir garis pada jalur yang sudah ditemukan sebelumnya
Jika ditemukan, maka simpan indeks posisi titik pada jalur tersebut

5d. Jika garis ini tidak ditemukan dalam jalur manapun,
maka buat jalur baru dengan jalur:
titik pusat – titik awal garis – titik akhir garis – titik pusat

5e. Jika titik awal garis ditemukan pada jalur, maka lakukan perhitungan berikut (poin 5e1 – 5e3)

5e1. Jika posisi titik awal berada pada titik kedua,
maka lakukan pembalikan jalur yang sudah ditemukan sebelumnya
ambil semua titik selain titik terakhir
kemudian tambahkan titik tujuan dan titik pusat sebagai akhir jalur

5e2. Jika posisi titik awal berada pada titik kedua terakhir,
maka ambil semua titik selain titik terakhir
kemudian tambahkan titik tujuan dan titik pusat sebagai akhir jalur

5e3. Jika jalur yang ditemukan tidak kosong,
maka masukkan jalur baru menggantikan jalur yang sudah ada sebelumnya

5f. Jika titik tujuan garis ditemukan pada jalur, maka lakukan perhitungan berikut (poin 5f1 – 5f3)

5f1. Jika posisi titik tujuan berada pada titik kedua,
maka buat jalur baru dengan menambahkan titik pusat sebagai awal jalur dan titik awal
kemudian tambahkan dengan semua titik selain titik pertama pada jalur tersebut

5f2. Jika posisi titik tujuan berada pada titik kedua terakhir,
maka buat jalur baru dengan menambahkan titik pusat sebagai awal jalur dan titik awal
kemudian lakukan pembalikan jalur yang sudah ditemukan sebelumnya
dan tambahkan semua titik selain titik pertama

5f3. Jika jalur yang ditemukan tidak kosong,
maka masukkan jalur baru menggantikan jalur yang sudah ada sebelumnya

5g. Jika titik awal dan titik tujuan garis ditemukan pada jalur yang berbeda, maka lakukan perhitungan berikut (poin 5g1 – 5g5)

5g1. Jika jalur dimana titik awal garis berada sebelum jalur dimana titik akhir garis,
dan posisi titik awal adalah posisi titik kedua pada jalur tersebut
maka lakukan pembalikan jalur titik awal yang sudah ditemukan sebelumnya
dan tambahkan semua titik selain titik terakhir
kemudian tambahkan semua titik pada jalur titik akhir selain titik pertama

5g2. Jika jalur dimana titik awal garis berada sebelum jalur dimana titik akhir garis,
dan posisi titik awal adalah posisi titik kedua terakhir pada jalur tersebut
maka ambil semua titik pada jalur titik awal selain titik terakhir
kemudian lakukan pembalikan jalur titik akhir yang sudah ditemukan sebelumnya
dan tambahkan semua titik selain titik pertama

5g3. Jika jalur dimana titik awal garis berada sesudah jalur dimana titik akhir garis,
dan posisi titik tujuan adalah posisi titik kedua pada jalur tersebut
maka lakukan pembalikan jalur titik awal yang sudah ditemukan sebelumnya
dan ambil semua titik selain titik terakhir
kemudian tambahkan semua titik pada jalur titik akhir selain titik pertama

5g4. Jika jalur dimana titik awal garis berada sesudah jalur dimana titik akhir garis,
dan posisi titik tujuan adalah posisi titik kedua terakhir pada jalur tersebut
maka ambil semua titik selain titik terakhir pada jalur titik awal
kemudian lakukan pembalikan jalur titik tujuan yang sudah ditemukan sebelumnya
dan tambahkan semua titik pada jalur titik akhir selain titik pertama

5g5. masukkan jalur baru menggantikan jalur yang sudah ada sebelumnya
dan hapus jalur yang sudah tidak dipakai

5h. Jika sudah ditemukan jalur yang mengandung semua titik, maka hentikan perulangan

6. Catat hasil akhir untuk masing-masing jawaban garis yang ditemukan
Kemudian jumlahkan total biaya garis tersebut


Hasil akhir adalah: (klik untuk perbesar gambar)

Dengan menggunakan titik pertama sebagai pusat, maka
cmd152a

Jika diilustrasikan dalam gambar, maka model hasil akhirnya adalah sebagai berikut
clarke-wright-akhir-1

Dengan menggunakan titik kedua sebagai pusat, maka
cmd152b

Jika diilustrasikan dalam gambar, maka model hasil akhirnya adalah sebagai berikut
clarke-wright-akhir-2


Contoh modul / source code dalam bahasa VB (Visual Basic) dapat didownload disini:



Jika membutuhkan jasa kami dalam pembuatan program, keterangan selanjutnya dapat dilihat di Fasilitas dan Harga
Jika ada yang kurang paham dengan langkah-langkah algoritma diatas, silahkan berikan komentar Anda.
Selamat mencoba.

Tinggalkan sebuah komentar

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *