Rekan2,
Berdasarkan jawaban-jawaban yang masuk, maka pemenang lomba TSP ditetapkan
adalah rekan Eddy Santoso karena yang berhasil menemukan rute dengan jarak
tempuh yang paling pendek, dimana rute dan jarak total sbb:
Rute :
1-57-56-3-4-55-63-5-52-51-23-22-21-20-19-18-16-17-26-27-24-25-29-28-30-31-36
-64-35-32-33-37-34-39-38-14-15-13-6-62-7-8-9-12-10-11-40-41-42-44-43-45-46-4
7-48-49-50-53-54-61-58-60-59-2-1
Total jarak : 1058
Jawaban dari peserta lain dan juga cara/metoda yang digunakan untuk
memecahkan soal bisa dilihat di bawah.
Kami mengucapkan selamat kepada rekan Eddy Santoso, dan kepada peserta lomba
lainnya kami ucapkan terima kasih atas partisipasinya.
Salam hormat,
M. Syarwani
Panitia lomba
=========Hasil-hasil jawaban lomba TSP n=64 ========================
Panitia :
Rute :
1-57-56-3-4-55-63-5-52-51-23-22-21-20-19-18-16-17-26-27-24-25-29-28-30-31-36
-64-37-34-39-38-14-15-13-6-62-7-9-8-12-10-11-40-32-33-35-42-41-44-43-45-46-4
7-48-49-50-53-54-61-58-60-59-2-1
Total jarak : 1057
Cara/metoda :
Assignment problem (sub tour TSP) + cutting plane (untuk memecah subtour
TSP) menjadi tour TSP.
Harry Gunawan (1) :
Rute :
1-2-59-60-58-61-54-53-52-51-50-49-48-47-46-45-44-43-42-41-40-11-10-12-9-8-62
-6-7-13-15-14-38-39-34-37-33-32-35-64-36-31-30-28-29-25-24-27-26-17-16-18-19
-20-21-22-23-5-63-55-4-3-56-57-1
Total jarak : 1064
Harry Gunawan (2) :
Rute:
1-2-59-60-58-61-54-53-52-51-50-49-48-47-46-45-43-44-42-41-40-11-10-12-9-8-62
-6-7-13-15-14-38-39-34-37-33-32-35-64-36-31-30-28-29-25-24-27-26-17-16-18-19
-20-21-22-23-5-63-55-4-3-56-57-1
Total jarak : 1062
Cara/metoda :
metoda yang digunakan dengan bantuan grafis.
Mula2 saya mencoba untuk menggunakan cara mathematic, tetapi melihat
kemungkinannya yang sangat banyak, jelas ngak mungkin, kecuali sudah punya
softwarenya. Jadi saya ubah menggunakan pendekatan grafis yang kebetulan
toolsnya telah Bapak siapkan [yaitu sheet lembar jawaban].
Dg tools tsb kita bisa buat trial and error route alias hanya mencoba
beberapa kombinasi saja.
Ini sangat menghemat waktu karena banyak sekali kombinasi yang tidak perlu
dicoba karena sudah pasti tidak efficient.
Dalam keadaan riil pun, tanpa software saya rasa cara ini yang paling
praktis dan murah.
Kesalahan yang diperoleh [dibandingkan dengan route yang paling efficient]
tidak akan besar, sehingga kerugian akibat kesalahan masih lebih kecil
dibandingkan waktu [atau biaya software] untuk mendapatkan jarak efficient
yang mutlak.
Eddy Santoso (1) :
Rute :
1-57-56-3-4-55-63-5-52-51-23-22-21-20-19-18-16-17-26-27-24-25-29-28-30-31-36
-64-35-32-33-37-34-39-38-14-15-13-6-62-7-8-9-12-10-11-40-41-42-44-43-45-46-4
7-48-49-50-53-54-61-58-60-59-2-1
Total jarak : 1058
Cara/metoda :
Jawaban yang saya dapat dari cara melihat titik
terjauh dan jarak yang terdekat.
Prinsipnya adalah:
1. Tidak ada garis yang berpotongan
2. Dicari pola yang mendekati bentuk lingkaran. (jika
bentuk persegi lebih banyak memakan jarak)
3. Jika ada tiga sampai lima titik yang berdekatan,
dicari kombinasi jarak terpendek.
Dalam hal ini banyak sekali pola yang bisa ditemukan
tapi setelah dicoba, yang paling utama adalah
mengambil titik-titik paling luar terlebih dahulu.
Okke Oktianto :
Rute :
1-2-59-60-58-57-56-3-4-55-63-53-54-61-52-51-23-22-21-20-27-26-19-17-16-18-28
-29-30-31-36-64-35-34-37-33-32-39-38-15-13-7-6-9-8-62-14-12-10-11-40-41-42-4
3-44-45-46-47-48-49-50-24-25-5-1
Total jarak : 1228
Cara/metoda:
Dengan membandingkan kota No. 1 sebagai acuan pertama untuk mendapatkan
kota kedua mana yang mempunyai jarak terdekat demikian dengan kota kedua
dipakai sebagai acuan kedua untuk mendapatkan kota ketiga mana yang mempunyai
jarak terdekat, demikina seterusnya.
Apabila ada 2 kota tujuan yang mempunyai jarak tempuh yang sama, maka
disimulasikan ke jarak kota berikutnya untuk menentukan antara 2 kota
tsb.
Rizal Arryadi :
Rute :
1-57-56-3-4-55-63-5-23-22-21-20-19-18-16-17-26-27-24-25-29-28-30-31-36-64-37
-34-39-38-14-15-13-6-62-7-9-8-12-10-11-40-32-33-35-42-41-44-43-45-46-47-48-4
9-50-51-52-53-54-61-58-60-59-2-1
Total jarak : 1059
Cara/metoda :
Metoda heuristik yg saya pakai adalah campuran antara:
- Divide and conquer (i.e., tiap sub-bagian menjadi masalah shortest
path problem)
- Hill Climbing menggunakan greedy method utk solusi keseluruhan.
Menjadikan complexity nya menjadi O(n2).
Gratia J. Handi (1) :
Rute:
1-2-59-57-58-60-61-55-54-63-53-52-51-23-50-49-48-47-46-45-43-44-41-42-35-33-
32-40-11-10-12-9-8-62-7-6-13-15-14-38-39-34-37-64-36-31-30-28-29-24-25-27-26
-17-16-18-19-20-21-22-5-4-3-56-1
Total jarak : 1087
Gratia J. Handi (2) :
Rute:
1-2-59-57-58-60-61-55-54-50-49-48-47-46-45-43-44-41-42-35-33-32-40-11-10-12-
9-8-62-7-6-13-15-14-38-39-34-37-64-36-31-30-28-29-24-25-27-26-17-16-18-19-20
-21-22-23-51-52-53-63-5-4-3-56-1
Total jarak : 1082
Cara/metoda :
Cara yang saya gunakan adalah dengan mencari the shortest path saja dari
matriks data jarak
Kresna Gumilar (1):
Rute:
1-61-63-5-50-49-48-47-46-45-43-44-42-41-35-37-34-39-38-17-16-18-15-13-6-7-9-
8-62-14-12-10-11-40-32-33-64-36-31-30-29-28-25-24-27-26-19-20-21-22-23-51-52
-53-54-55-4-3-56-57-58-60-59-2-1
Total jarak : 1060
Cara/metoda:
Cara yang saya gunakan untuk mencari rute terpendek :
Memulai dari sebuah titik kemudian mencari titik
berikut dengan jarak terdekat dari titik sebelumnya
kemudian dari titik kedua ini pun dicari titik
berikutnya dengan jarak terdekat dari titik kedua dan
seterusnya hingga semua titik dilalui .
Saya lakukan langkah tersebut dengan 64 titik sebagai
titik pertama. Dan didapat jarak terpendek adalah
1160.
Muliandy Nasution (1):
Rute:
1-57-56-3-4-5-23-22-21-20-19-18-16-17-26-27-24-25-29-28-30-31-36-64-35-32-33
-37-34-39-38-14-15-13-6-62-7-9-8-12-10-11-40-41-42-44-43-45-46-47-48-49-50-5
1-52-53-54-63-55-61-58-60-59-2-1
Total jarak : 1066
Cara/metoda:
Metode yang digunakan algoritma genetic, langkah pengerjaannya :
1. Dipilih 1 rute awal dengan menggunakan metode nearest neighbourhood
2. Kemudian rute awal tersebut di-SWAP dan menghasilkan rute yang baru,
sehingga kita mempunyai 2 rute utama yang biasa disebut dengan orangtua
(ayah dan ibu)
3. Berikutnya 2 rute utama dioptimasi dengan menggunakan algoritma genetic
4. Selanjutnya ke-2 rute utama di Cross Over untuk menghasilkan 50 rute baru
(biasa disebut dengan anak) dengan lebih dari 3000 literasi
5. Ke-50 rute baru ini, diambil 2 rute (individu) secara acak untuk
selanjutnya di cross over (dikawinkan) dan menghasilkan 2 rute baru (cucu)
6. Ke-2 rute baru (cucu) tadi dioptimasi kembali, rute terbaik akan
dimasukkan kedalam populasi sedangkan yang jelek akan dibuang
7. Dari populasi (kumpulan cucu-cucu terbaik) dipilih rute yang menghasilkan
jarak terdekat.
Sebenarnya ada beberapa rute (cucu) yang mengasilkan rute terdekat dan
menghasilkan angka jarak yang sama, yakni 1066. Namun, kami hanya memilih
satu secara acak.
Darmawan Shi (1) :
Rute :
1-2-59-60-58-61-54-53-50-49-48-47-46-45-43-44-42-41-40-11-10-12-8-9-7-62-6-1
3-15-14-38-39-34-37-33-32-35-64-36-31-30-29-24-25-28-17-16-18-26-27-19-20-21
-22-23-51-52-5-63-55-4-3-56-57-1
Total jarak : 1071
Cara/metoda:
N/A
Lego Haryanto (1):
Rute:
1-2-59-60-58-61-54-53-52--51-50-49-48-47-46--45-43-44-42-41-40-11-10-12-9-8-
7-62-6-13--15-14-38-39--34-37-33-32-35-64-36-31-30-28--29-25-24-27-26-17-16-
18-19-20-21-22-23-5--63-55-4-3-56-57-1
Total jarak : 1060
Cara/metoda :
Karena contoh soal yg diberikan ini mengandung koordinat-koordinat 64
titik, saya yakin sebenernya tidak perlu program komputer. Dengan
dilihat secara manual dan kesabaran, mestinya bisa mendapatkan solusi
yg oke (ngga harus optimal, tapi secara intuitif sih lumayan bagus).
Metode yang saya pake ya campuran manual ngeliatin koordinat
titik-titiknya, plus sedikit programming (pada dasarnya saya suka
bikin program beginian).
Programmingnya sih pake metode branch-and-bound, ditambah memoization
untuk simpen sub-solution yg ditemukan pada waktu search. Pada
dasarnya, program saya buat untuk lebih meyakinkan solusi manual saya
dan juga untuk memuaskan hobi, hahahah.
Tidak bisa dijadikan patokan apakah solusi tersebut optimal atau
tidak, karena memang pada dasarnya ini problem NP-hard. Tapi saya
senang mengerjakannya. Saya yakin kalo soalnya tidak mengandung
koordinat tiap titik, pasti jauh lebih sulit.
MSY
Mohon bantuannya untuk mengisi survei daya saing Indonesia di
http://www.ips.or.kr/site/IPS/mail/survey/20110120/26.html
*****************************************************************
Indonesian Production and Operations Management Society (IPOMS).
http://blog.ipoms.web.id/
Bergabunglah dengan IPOMS di Facebook
http://www.facebook.com/home.php?ref=home#/group.php?gid=34994473375
********************************************************************
No comments:
Post a Comment