Eksperimen dilakukan dengan menjalankan program GLS yang telah dibuat. Panjang edge dan penalti dari data problem TSP yang dipakai pada eksperimen ini dibuat secara random. Banyaknya penalti yang dibuat untuk setiap problem sebanyak 20% dari banyaknya edge. Untuk problem yang dibuat diberi nama AP020 untuk problem dengan 20 kota, AP050 untuk problem dengan 50 kota, dan seterusnya. Setiap problem yang dibuat kemudian disimpan dalam file yang diberi nama sesuai dengan nama problemnya dan ditambah akhiran .GPF. sebagai contoh untuk problem AP020 disimpan dengan nama AP020.GPF, AP050 disimpan dengan nama AP050.GPF dan seterusnya. Berikut adalah hasil eksperimen yang diperoleh dengan menjalankan program pada komputer AMD K6-2 500 MHz, RAM 128 MB serta sistem operasi Microsoft Windows ® Milenium Edition.
Gambar 1. Contoh tampilan eksekusi program GLS TSP
Gambar 1. Contoh tampilan form data GLS TSP
1. Tour Construction Heuristic
Data yang ada pada tabel 1 diperoleh dari hasil eksekusi nearest neighbor sebanyak α = 50 kali. Pada tabel tersebut terlihat bahwa untuk problem dengan 20 kota (AP020) memiliki waktu eksekusi 0,017 detik dengan biaya tour rata-rata 87.915,7 serta biaya tour minimum yang dapat diperoleh adalah 80.922,0 (biaya tour terbaik lebih kecil 7,955 % dibanding biaya tour rata-rata).
Tabel 1. Hasil Eksperimen Tour Construction Heuristic (Nearest Neighbor)
2. Local Search
Untuk operator Local Search yang digunakan, dilakukan eksekusi sebanyak α = 50 kali. Berikut adalah hasil eksekusi dari local search.
Tabel 2. Hasil Eksperimen penggunaan local search
Berdasarkan tabel 2 di atas dapat dilihat bahwa dengan menggunakan local search operator maka untuk AP020 dapat dihasilkan biaya tour terbaik yang lebih kecil sekitar 3,255% dari biaya tour rata-rata yang dihasilkan. Selain itu, untuk biaya tour terbaik terjadi perbaikan sebesar 5,740% bila dibandingkan dengan biaya tour terbaik yang dihasilkan dengan menggunakan Nearest Neighbor.
3. Genetic Local Search
Data hasil eksperimen untuk genetic local search (GLS) yang tampak pada Tabel 3 diperoleh dengan melakukan eksekusi GLS dengan nilai parameter jumlah individu, regenerasi dan mutation rate untuk populasi A adalah 50, 3 dan 15%, sedangkan untuk populasi B adalah 50, 3 dan 10% serta maksimum iterasi = 4 dan iterasi dianggap konvergen = 4.
Tabel 3. Hasil Eksperimen genetic local search
Berdasarkan tabel 3 dapat dilihat bahwa dengan menggunakan GLS biaya tour terbaik yang dihasilkan lebih kecil sekitar 4,077% bila dibandingkan dengan biaya tour rata-ratanya. Sedangkan perbaikan biaya tour terbaik sebesar 5,740% bila dibandingkan biaya tour terbaik yang dihasilkan dengan menggunakan nearest neighbor, atau 0% bila dibandingkan dengan local search.
Berdasarkan data yang ada dalam ketiga buah tabel di atas, dapat dibuat grafik untuk problem berdasarkan waktu penyelesaian (gambar 1) dan biaya tour yang dihasilkan (gambar 2).
Gambar 1. Grafik waktu penyelesaian
Dari grafik tersebut terihat bahwa bila dilihat dari sisi waktu penyelesaian, maka untuk Genetic Local Search kebutuhan akan waktu penyelesaian akan meningkat dengan drastis seiring dengan semakin banyaknya jumlah kota yang digunakan. sedangkan bagi untuk local search walaupun ada peningkatan kebutuhan waktu tetapi tidak sedrastis GLS. Sementara untuk nearest nighbor,sekalipun jumlah kota ditambah tetapi waktu yang dibutuhkan cenderung tidak mengalami perubahan yang berarti.
Gambar 2. Grafik biaya tour
Bila dilihat secara sekilas maka tour terbaik yang dihasilkan berturut-turut berasal dari genetic local search, local search dan nearest neighbor.
Sehingga dengan memperhatikan grafik yang ada pada gambar 1 dan 2 dapat ditarik beberapa kesimpulan :
• Secara umum biaya tour rata-rata yang dihasilkan oleh local search lebih baik dibandingkan dengan biaya tour rata-rata yang dihasilkan oleh GLS.
• Biaya tour rata-rata dari GLS dan local search masih lebih baik dari biaya tour minimum (terbaik) yang dihasilkan oleh nearest neighbor.
• Biaya tour minimum yang dihasilkan oleh GLS masih “sedikit” lebih baik bila dibandingkan dengan biaya tour minimum yang dihasilkan oleh local search.
Dengan memperhatikan grafik yang ada pada gambar 5.14 dapat ditarik beberapa kesimpulan :
• Proses pencarian solusi dengan menggunakan nearest neighbor membutuhkan waktu yang paling singkat bila dibandingkan dengan local search ataupun GLS.
• Untuk peningkatan jumlah kota (yang digunakan sebagai problem) secara konstan, terjadi peningkatan secara drastis waktu yang dibutuhkan oleh GLS untuk menyelesaikannya. Sedangkan pada nearest neighbor dapat dikatakan hampir tidak berpengaruh.
.
