Algoritma Jonker-Volgenant

Algoritma Jonker-Volgenant adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik dengan biaya terendah.
Algoritma ini merupakan pengembangan dari Algoritma Hungaria yang sudah dijelaskan sebelumnya, dan diklaim lebih efisien dari algoritma pendahulunya. Algoritma ini juga menggunakan Algoritma Dijkstra yang hanya akan dilakukan apabila memenuhi kondisi tertentu. Pada contoh kasus ini, proses perhitungan tidak melalui Algoritma Dijkstra karena tidak memenuhi kondisi tersebut, tetapi contoh skripnya tetap disertakan agar dapat digunakan pada contoh kasus yang lain.

Diasumsikan ada 5 titik yang harus dilalui semuanya, yaitu A,B,C,D,E
semua titik tidak terhubung secara langsung dengan titik-titik lainnya, melainkan hanya melalui jalur tertentu saja
setiap jalur juga memiliki biaya sendiri-sendiri
maka tentukan jalur yang harus diambil untuk mengelilingi semua titik dengan biaya terendah
Diasumsikan data jalur yang tersedia adalah sebagai berikut

Contoh data awal adalah sebagai berikut:
Jika tidak terdapat jalur diantara kedua titik,
maka beri nilai yang sangat besar pada jalur tersebut
dalam kasus ini digunakan angka 99 sebagai nilai yang sangat besar

daftarJarak=[99 12 99 99 99; ...
            10 99 15 7 99; ...
            99 20 99 5 8; ...
            99 6 14 99 13; ...
            11 9 99 99 99];

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

Langkah-langkah penggunaan algoritma ini adalah

* Lakukan proses perhitungan dengan menggunakan metode Jonker-Volgenant
Penjelasan tentang fungsi ini akan dijelaskan pada perhitungan dibawah ini (poin 1 – 10)

[solusiKolomPerBaris,totalBiaya]=JV(daftarBiaya);

Memasuki perhitungan pada fungsi JV

1. Tentukan nilai epsilon apabila belum ditentukan sebelumnya
Nilai default adalah nilai yang rendah sekali

if nargin<2
    maksBiaya=min(1e16,max(max(daftarBiaya)));
    epsilon=eps(maksBiaya);
end

2. Untuk matriks dengan ukuran baris dan kolom yang berbeda,
Lakukan transpos matriks sehingga ukuran yang lebih pendek akan menjadi baris dan ukuran yang lebih panjang menjadi kolom

[jumlahBaris,jumlahKolom] = size(daftarBiaya);
if jumlahBaris > jumlahKolom
    daftarBiaya = daftarBiaya';
    [jumlahBaris, jumlahKolom] = size(daftarBiaya);
    isTranspos=true;
else
    isTranspos=false;
end

3. Hitung biaya terendah dari semua jalur yang ada
Untuk matriks dengan ukuran tidak sama, tambahkan baris baru agar matriks berukuran sama
Kemudian beri nilai yang sangat besar untuk semua nilai 0 agar tidak terpilih sebagai jalur dengan biaya terendah

MinBiaya = min(min(daftarBiaya));
jumlahDimensi = jumlahKolom;
daftarBiaya = [daftarBiaya; 2*MinBiaya + zeros(jumlahKolom-jumlahBaris, jumlahKolom)];
daftarBiaya(daftarBiaya~=daftarBiaya)=Inf;
maksBiaya=max(daftarBiaya(daftarBiaya<inf))*jumlahdimensi+1; if="" isempty(maksbiaya)="" maksbiaya="Inf;" end="" daftarbiaya(daftarbiaya="=Inf)=maksBiaya;" <="" pre="">

* Proses pembuangan kolom

4. Lakukan proses perhitungan secara mundur dari kolom terakhir ke kolom pertama
Perhitungan secara mundur akan memberikan hasil yang lebih baik (poin 4a – 4e)

for j=jumlahDimensi:-1:1    
. . .

4a. Tentukan biaya terendah dari masing-masing baris

[v(j), idxBiayaTerendah] = min(daftarBiaya(:,j));

4b. Jika belum ada baris yang dihitung
Masukkan solusi baris dan kolom sebagai solusi
Perhitungan ini hanya akan berlakuk saat perulangan pertama kali dijalankan

if ~jumlahBarisTerhitung(idxBiayaTerendah)
	solusiKolomPerBaris(idxBiayaTerendah)=j;
	solusiBarisPerKolom(j)=idxBiayaTerendah;
	. . .

4c. Jika solusi yang ditemukan pada baris yang sama dan biayanya lebih rendah Maka ambil solusi baris dan kolom sebagai solusi yang baru

. . .
elseif v(j) < v(solusiKolomPerBaris(idxBiayaTerendah))
	idxXMin=solusiKolomPerBaris(idxBiayaTerendah);
	solusiKolomPerBaris(idxBiayaTerendah)=j;
	solusiBarisPerKolom(j)=idxBiayaTerendah;
	solusiBarisPerKolom(idxXMin)=-1;
	. . .

4d. Jika kedua kondisi diatas tidak terpenuhi,
Maka ada baris yang sudah terpilih, tetapi kolomnya belum terpilih
Sehingga beri nilai solusi untuk kolom yang belum terpilih dengan angka minus 1

. . .
else
	solusiBarisPerKolom(j)=-1;
end

4e. Hitung jumlah baris yang sudah terhitung

jumlahBarisTerhitung(idxBiayaTerendah) = jumlahBarisTerhitung(idxBiayaTerendah) + 1;

* Proses pengalihan nilai baris yang belum terpilih ke baris yang sudah terpilih

5. Lakukan perulangan sebanyak jumlah dimensi (poin 5a – 5b)

for barisBelumTerhitung=1:jumlahDimensi
. . .

5a. Jika baris tersebut belum terhitung,
Maka masukkan baris ini ke dalam daftar baris yang belum terhitung

if ~jumlahBarisTerhitung(barisBelumTerhitung)      
	jumlahBarisBelumTerhitung=jumlahBarisBelumTerhitung+1;
	daftarBelumTerhitung(jumlahBarisBelumTerhitung)=barisBelumTerhitung;
	. . .

5b. Untuk baris yang hanya terhitung sekali,
Lakukan proses pengalihan nilai yang ditampung pada matriks v

. . .
    else
        if jumlahBarisTerhitung(barisBelumTerhitung) == 1
            idxXMin = solusiKolomPerBaris(barisBelumTerhitung);
            x = daftarBiaya(barisBelumTerhitung,:)-v;
            x(idxXMin) = maksBiaya;
            v(idxXMin) = v(idxXMin) - min(x);
        end
    end

* Proses penambahan baris yang belum terhitung

6. Lakukan perulangan sebanyak 2 kali (poin 6a)

iterasi = 0;
while iterasi < 2
    iterasi = iterasi + 1;
	. . .

6a. Lakukan perulangan sebanyak jumlah baris yang belum dihitung (poin 6a1 – 6a6)

while k < tmpJumlahBarisBelumTerhitung
	k = k+1;
	barisBelumTerhitung = daftarBelumTerhitung(k);
	. . .

6a1. Hitung biaya minimum dan biaya minimum kedua pada masing-masing kolom

x = daftarBiaya(barisBelumTerhitung,:) - v;
[xMin, idxXMin] = min(x);
x(idxXMin) = maksBiaya;
[xMin2, idxXMin2] = min(x);

6a2. Simpan nilai solusi kolom dengan nilai minimal untuk digunakan pada perhitungan selanjutnya

i0 = solusiBarisPerKolom(idxXMin);

6a3. Jika nilai minimum dan nilai minimum kedua bernilai sama,
nilai pada kolom minimum akan dikurangi untuk memperbesar pengurangan nilai pada baris dengan nilai minimum kedua

if xMin2 - xMin > epsilon 
	v(idxXMin) = v(idxXMin) - (xMin2 - xMin);
	. . .

6a4. Jika nilai minimum dan nilai minimum kedua bernilai tidak sama,
maka lakukan pertukaran antara kolom yang mengandung nilai minimum dan nilai minimum kedua tersebut

. . .
else 
	if i0 > 0
		idxXMin = idxXMin2;
		i0 = solusiBarisPerKolom(idxXMin2);
	end
end

6a5. Lakukan update nilai dengan biaya terendah pada baris dan kolom yang berlum terhitung

solusiKolomPerBaris(barisBelumTerhitung) = idxXMin;
solusiBarisPerKolom(idxXMin) = barisBelumTerhitung;

6a6. Lakukan perhitungan berikut apabila i0 memiliki nilai (poin 6a6a – 6a6b)

if i0 > 0
. . .

6a6a. Jika nilai minimum dan nilai minimum kedua bernilai sama,
Masukkan nilai i0 ke dalam baris yang belum terhitung

if xMin2 - xMin > epsilon
	daftarBelumTerhitung(k)=i0;
	k=k-1;
	. . .

6a6b. Jika nilai minimum dan nilai minimum kedua bernilai tidak sama,
Berarti tidak ditemukan perkembangan
Simpan nilai i0 pada daftar yang belum terhitung untuk kemudian dihitung pada tahap selanjutnya

. . .
else
	jumlahBarisBelumTerhitung = jumlahBarisBelumTerhitung + 1;
	daftarBelumTerhitung(jumlahBarisBelumTerhitung) = i0;
end

7. Tahap pencarian solusi terbaik untuk setiap baris yang belum terhitung
Pencarian solusi terbaik akan dilakukan dengan metode Dijkstra
Tetapi dalam contoh kasus ini, semua baris sudah terhitung sebelumnya, sehingga proses ini dapat dilewati
Penjelasan lebih lanjut tentang proses ini dapat dilihat pada contoh skrip di bagian bawah halaman ini

for f=1:jumlahBarisBelumTerhitung
. . .
end

8. Lakukan perhitungan tambahan untuk parameter u dan v
Hitung total biaya yang pada jalur dengan biaya terendah
Kemudian lakukan update pada nilai daftar biaya sesuai dengan nilai parameter u dan v yang ditemukan

solusiKolomPerBaris = solusiKolomPerBaris(1:jumlahBaris);
u=diag(daftarBiaya(:,solusiKolomPerBaris))-v(solusiKolomPerBaris)';
u=u(1:jumlahBaris);
v=v(1:jumlahKolom);
totalBiaya = sum(u)+sum(v(solusiKolomPerBaris));
daftarBiaya=daftarBiaya(1:jumlahBaris,1:jumlahKolom);
daftarBiaya = daftarBiaya - u(:,ones(1,jumlahKolom)) - v(ones(jumlahBaris,1),:);

9. Untuk matriks yang sebelumnya sudah dilakukan transpos,
Maka nilai u dan v yang baru juga akan di transpos sebagai nilai akhir

if isTranspos
    daftarBiaya = daftarBiaya';
    t=u';
    u=v';
    v=t;
end

10. Jika total biaya melebihi nilai maksimal biaya,
maka jalur ini tidak sah, sehingga beri nilai total biaya dengan nilai yang sangat besar

if totalBiaya>maksBiaya
    totalBiaya=Inf;
end

Hasil akhir adalah:

Algoritma Jonker-Volgenant
Contoh: Pencarian jalur yang melalui semua titik dengan biaya terendah
Diasumsikan ada 5 titik yang harus dilalui semuanya, yaitu A,B,C,D,E
semua titik tidak terhubung secara langsung dengan titik-titik lainnya, melainkan hanya melalui jalur tertentu saja
setiap jalur juga memiliki biaya sendiri-sendiri
maka tentukan jalur yang harus diambil untuk mengelilingi semua titik dengan biaya terendah
Diasumsikan data jalur yang tersedia adalah sebagai berikut
Titik awal, Titik Tujuan, Biaya
Titik A   , Titik B     , 10
Titik A   , Titik E     , 11
Titik B   , Titik A     , 12
Titik B   , Titik C     , 20
Titik B   , Titik D     , 6
Titik B   , Titik E     , 9
Titik C   , Titik B     , 15
Titik C   , Titik D     , 14
Titik D   , Titik B     , 7
Titik D   , Titik C     , 5
Titik E   , Titik C     , 8
Titik E   , Titik D     , 13


Hasil akhir:
Jalur 1 adalah dari titik B ke titik A dengan biaya 12
Jalur 2 adalah dari titik D ke titik B dengan biaya 7
Jalur 3 adalah dari titik E ke titik C dengan biaya 8
Jalur 4 adalah dari titik C ke titik D dengan biaya 14
Jalur 5 adalah dari titik A ke titik E dengan biaya 11


Total biaya = 52

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

Contoh modul / source code menggunakan Matlab 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.

</inf))*jumlahdimensi+1;>