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

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

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

Const jumlahTitik As Integer = 5

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

Const titikPusat As Integer = 1

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

Dim gmb As New Gambar(jumlahTitik)
Dim daftarTitik As Titik() = gmb.daftarTitik
Dim daftarGaris As New List(Of Garis)()
Dim grs As Garis

* 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:

Public Class Gambar
    Public daftarGaris As List(Of Garis) = Nothing
    Public daftarTitik As Titik() = Nothing

    Public Sub New(jumlahTitik As Integer)
        daftarTitik = New Titik(jumlahTitik - 1) {}
        For i As Integer = 0 To jumlahTitik - 1
            daftarTitik(i) = New Titik(Chr(i + 65))
        Next
    End Sub
End Class

Public Class Garis
    Private m_titikAwal As Titik
    Private m_titikTujuan As Titik
    Private m_biaya As Integer
    Private m_saving As Integer

    Public Property titikAwal() As Titik
        Get
            Return m_titikAwal
        End Get
        Set(value As Titik)
            m_titikAwal = value
        End Set
    End Property

    Public Property titikTujuan() As Titik
        Get
            Return m_titikTujuan
        End Get
        Set(value As Titik)
            m_titikTujuan = value
        End Set
    End Property

    Public Property biaya() As Integer
        Get
            Return m_biaya
        End Get
        Set(value As Integer)
            m_biaya = value
        End Set
    End Property

    Public Property saving() As Integer
        Get
            Return m_saving
        End Get
        Set(value As Integer)
            m_saving = value
        End Set
    End Property

    Public Sub New(titikAwal As Titik, titikTujuan As Titik, biaya As Integer)
        m_titikAwal = titikAwal
        m_titikTujuan = titikTujuan
        m_biaya = biaya
        m_saving = Integer.MinValue
    End Sub
End Class

Public Class Titik
    Private m_Label As String

    Public Property Label() As String
        Get
            Return m_Label
        End Get
        Set(value As String)
            m_Label = value
        End Set
    End Property

    Public Sub New(ByVal label As String)
        m_Label = label
    End Sub
End Class

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

grs = New Garis(daftarTitik(0), daftarTitik(1), 6)
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(0), daftarTitik(2), 4)
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(0), daftarTitik(3), 2)
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(0), daftarTitik(4), 7)
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(1), daftarTitik(2), 5)
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(1), daftarTitik(3), 4)
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(1), daftarTitik(4), 8)
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(2), daftarTitik(3), 7)
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(2), daftarTitik(4), 3)
daftarGaris.Add(grs)
grs = New Garis(daftarTitik(3), daftarTitik(4), 9)
daftarGaris.Add(grs)

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

For i As Integer = 0 To jumlahTitik - 2
	For j As Integer = i + 1 To jumlahTitik - 1
		If i <> titikPusat Or j <> titikPusat Then
			Dim garisTitikPusatKeTitikAwal As Garis = cariGaris(daftarGaris, daftarTitik(titikPusat - 1), daftarTitik(i))
			Dim garisTitikPusatKeTitikAkhir As Garis = cariGaris(daftarGaris, daftarTitik(titikPusat - 1), daftarTitik(j))
			Dim garisTitikAwalKeTitikAkhir As Garis = cariGaris(daftarGaris, daftarTitik(i), daftarTitik(j))
			If garisTitikPusatKeTitikAwal IsNot Nothing AndAlso garisTitikPusatKeTitikAkhir IsNot Nothing AndAlso garisTitikAwalKeTitikAkhir IsNot Nothing Then
				garisTitikAwalKeTitikAkhir.saving = garisTitikPusatKeTitikAwal.biaya + garisTitikPusatKeTitikAkhir.biaya - garisTitikAwalKeTitikAkhir.biaya
			End If
		End If
	Next
Next

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

Private Function cariGaris(daftarGaris As List(Of Garis), titikAwal As Titik, titikAkhir As Titik) As Garis
	For i As Integer = 0 To daftarGaris.Count - 1
		If (daftarGaris(i).titikAwal Is titikAwal AndAlso daftarGaris(i).titikTujuan Is titikAkhir) Or _
			daftarGaris(i).titikAwal Is titikAkhir AndAlso daftarGaris(i).titikTujuan Is titikAwal Then
			Return daftarGaris(i)
		End If
	Next

	Return Nothing
End Function

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

gmb.daftarGaris = daftarGaris.ToList().OrderByDescending(Function(p) p.saving).ToList()

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

5a. Dapatkan garis yang akan dihitung

Dim garis As Garis = gmb.daftarGaris(iterasi)

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

Dim idxJalurTitikAwal As Integer = -1
Dim idxTitikAwal As Integer = -1
For i As Integer = 0 To daftarJalur.Count - 1
	For j As Integer = 0 To daftarJalur(i).Count - 1
		If daftarJalur(i)(j) Is garis.titikAwal Then
			idxJalurTitikAwal = i
			idxTitikAwal = j
			Exit For
		End If
	Next

	If idxJalurTitikAwal > -1 Then Exit For
Next

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

Dim idxJalurTitikTujuan As Integer = -1
Dim idxTitikTujuan As Integer = -1
For i As Integer = 0 To daftarJalur.Count - 1
	For j As Integer = 0 To daftarJalur(i).Count - 1
		If daftarJalur(i)(j) Is garis.titikTujuan Then
			idxJalurTitikTujuan = i
			idxTitikTujuan = j
			Exit For
		End If
	Next

	If idxJalurTitikTujuan > -1 Then Exit For
Next

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

If idxJalurTitikAwal = -1 And idxJalurTitikTujuan = -1 Then
	Dim tmpDaftarJalur As New List(Of Titik)
	tmpDaftarJalur.Add(daftarTitik(titikPusat - 1))
	tmpDaftarJalur.Add(garis.titikAwal)
	tmpDaftarJalur.Add(garis.titikTujuan)
	tmpDaftarJalur.Add(daftarTitik(titikPusat - 1))

	daftarJalur.Add(tmpDaftarJalur)
	. . .

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

. . .
ElseIf idxJalurTitikAwal > -1 And idxJalurTitikTujuan = -1 Then
. . .

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

If idxTitikAwal = 1 Then
	For i As Integer = daftarJalur(idxJalurTitikAwal).Count - 1 To 1 Step -1
		tmpDaftarJalur.Add(daftarJalur(idxJalurTitikAwal)(i))
	Next
	tmpDaftarJalur.Add(garis.titikTujuan)
	tmpDaftarJalur.Add(daftarTitik(titikPusat - 1))
	. . .

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

. . .
ElseIf idxTitikAwal = daftarJalur(idxJalurTitikAwal).Count - 2 Then
	For i As Integer = 0 To daftarJalur(idxJalurTitikAwal).Count - 2
		tmpDaftarJalur.Add(daftarJalur(idxJalurTitikAwal)(i))
	Next
	tmpDaftarJalur.Add(garis.titikTujuan)
	tmpDaftarJalur.Add(daftarTitik(titikPusat - 1))
End If

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

If tmpDaftarJalur.Count > 0 Then
	daftarJalur(idxJalurTitikAwal) = tmpDaftarJalur
End If

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

. . .
ElseIf idxJalurTitikAwal = -1 And idxJalurTitikTujuan > -1 Then
. . .

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

If idxTitikTujuan = 1 Then
	tmpDaftarJalur.Add(daftarTitik(titikPusat - 1))
	tmpDaftarJalur.Add(garis.titikAwal)
	For i As Integer = 1 To daftarJalur(idxJalurTitikTujuan).Count - 1
		tmpDaftarJalur.Add(daftarJalur(idxJalurTitikTujuan)(i))
	Next
	. . .

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

. . .
ElseIf idxTitikTujuan = daftarJalur(idxJalurTitikTujuan).Count - 2 Then
	tmpDaftarJalur.Add(daftarTitik(titikPusat - 1))
	tmpDaftarJalur.Add(garis.titikAwal)
	For i As Integer = daftarJalur(idxJalurTitikTujuan).Count - 2 To 0 Step -1
		tmpDaftarJalur.Add(daftarJalur(idxJalurTitikTujuan)(i))
	Next
End If

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

If tmpDaftarJalur.Count > 0 Then
	daftarJalur(idxJalurTitikTujuan) = tmpDaftarJalur
End If

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

. . .
ElseIf idxJalurTitikAwal > -1 And idxJalurTitikTujuan > -1 And idxJalurTitikAwal <> idxJalurTitikTujuan Then
. . .

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

If idxJalurTitikAwal < idxJalurTitikTujuan AndAlso idxTitikAwal = 1 Then
	For j As Integer = daftarJalur(idxJalurTitikAwal).Count - 1 To 1 Step -1
		tmpDaftarJalur.Add(daftarJalur(idxJalurTitikAwal)(j))
	Next
	For j As Integer = 1 To daftarJalur(idxJalurTitikTujuan).Count - 1
		tmpDaftarJalur.Add(daftarJalur(idxJalurTitikTujuan)(j))
	Next
	. . .

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

. . .
ElseIf idxJalurTitikAwal < idxJalurTitikTujuan AndAlso idxTitikAwal = daftarJalur(idxJalurTitikAwal).Count - 2 Then
	For j As Integer = 0 To daftarJalur(idxJalurTitikAwal).Count - 2
		tmpDaftarJalur.Add(daftarJalur(idxJalurTitikAwal)(j))
	Next
	For j As Integer = daftarJalur(idxJalurTitikTujuan).Count - 2 To 0 Step -1
		tmpDaftarJalur.Add(daftarJalur(idxJalurTitikTujuan)(j))
	Next
	. . .

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

ElseIf idxJalurTitikAwal > idxJalurTitikTujuan AndAlso idxTitikTujuan = 1 Then
	For j As Integer = daftarJalur(idxJalurTitikAwal).Count - 1 To 1 Step -1
		tmpDaftarJalur.Add(daftarJalur(idxJalurTitikAwal)(j))
	Next
	For j As Integer = 1 To daftarJalur(idxJalurTitikTujuan).Count - 1
		tmpDaftarJalur.Add(daftarJalur(idxJalurTitikTujuan)(j))
	Next
	. . .

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

. . .
ElseIf idxJalurTitikAwal > idxJalurTitikTujuan AndAlso idxTitikTujuan = daftarJalur(idxJalurTitikTujuan).Count - 2 Then
	For j As Integer = 0 To daftarJalur(idxJalurTitikAwal).Count - 2
		tmpDaftarJalur.Add(daftarJalur(idxJalurTitikAwal)(j))
	Next
	For j As Integer = daftarJalur(idxJalurTitikTujuan).Count - 2 To 0 Step -1
		tmpDaftarJalur.Add(daftarJalur(idxJalurTitikTujuan)(j))
	Next
End If

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

daftarJalur(idxJalurTitikAwal) = tmpDaftarJalur
daftarJalur.RemoveAt(idxJalurTitikTujuan)

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

For i As Integer = 0 To daftarJalur.Count - 1
	If daftarJalur(i).Count >= jumlahTitik + 1 Then
		hasil = daftarJalur(i)
		Exit While
	End If
Next

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

Dim jumlahBiaya As Integer = 0
For i As Integer = 0 To hasil.Count - 2
	Dim garis As Garis = cariGaris(gmb.daftarGaris, hasil(i), hasil(i + 1))

	Console.WriteLine("Jalur " & i + 1 & " adalah dari titik " & garis.titikAwal.Label & " ke titik " & garis.titikTujuan.Label & " dengan biaya " & garis.biaya)
	jumlahBiaya += garis.biaya
Next

Hasil akhir adalah: (klik untuk perbesar gambar)

Dengan menggunakan titik pertama sebagai pusat, maka

Jika diilustrasikan dalam gambar, maka model hasil akhirnya adalah sebagai berikut

Dengan menggunakan titik kedua sebagai pusat, maka

Jika diilustrasikan dalam gambar, maka model hasil akhirnya adalah sebagai berikut

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.