Beberapa saat yang lalu saya mendapat project kecil berupa aplikasi android yang mengimplementasikan fitur Travelling Salesman Problem (TSP). Setelah saya pelajari lebih lanjut, TSP mungkin dapat dikatakan suatu cara untuk mengunjungi semua tujuan(lebih dari 1 tujuan) dengan menggunakan rute terpendek ataupun tercepat dan kembali lagi ke posisi awal ketika dia berangkat.
Apa itu Travelling Salesman Problem
Sebagai Contoh dalam dunia nyata:
Misal seorang pengantar pizza memiliki 5 alamat pemesan yang harus diantarkan dengan sekali berangkat. Pengantar pizza tersebut tidak boleh kembali sebelum semuat pesanan di antarkan. Untuk itu secara logika biasanya pengantar itu akan memilih rute yang paling cepat untuk mengunjungi ke 5 alamat itu supaya waktu yang ada lebih singkat dan setelah semuanya dikunjungi maka ia akan kembali ke toko pizza tempatnya ia bekerja lagi.
Misal seorang pengantar pizza memiliki 5 alamat pemesan yang harus diantarkan dengan sekali berangkat. Pengantar pizza tersebut tidak boleh kembali sebelum semuat pesanan di antarkan. Untuk itu secara logika biasanya pengantar itu akan memilih rute yang paling cepat untuk mengunjungi ke 5 alamat itu supaya waktu yang ada lebih singkat dan setelah semuanya dikunjungi maka ia akan kembali ke toko pizza tempatnya ia bekerja lagi.
Jika kita melihat ke Wikipedia maka Travelling Salesman Problem (TSP) menjawab permasalahan berikut:
Diketahui list kota dan jarak antara semua kota, rute terpendek manakah yang dapat digunakan untuk mengunjungi setiap kota tepat sekali dan kembali ke kota asal?
TSP sendiri dapat dimodelkan dengan menggunakan suatu graph yang tentunya terdiri dari edge dan vertex. Vertex biasanya menggambarkan suatu kota atau tujuan dan Edge menggambarkan suatu jarak antar Vertex yang ada.
Karena setiap Vertex terhubung dengan semua vertex lain melalui suatu edge, maka bisa dikatakan graph yang dihasilkan adalah suatu complete graph.
TSP sendiri dapat dimodelkan dengan menggunakan suatu graph yang tentunya terdiri dari edge dan vertex. Vertex biasanya menggambarkan suatu kota atau tujuan dan Edge menggambarkan suatu jarak antar Vertex yang ada.
Karena setiap Vertex terhubung dengan semua vertex lain melalui suatu edge, maka bisa dikatakan graph yang dihasilkan adalah suatu complete graph.
Solusi atau Algoritma untuk menyelesaikan TSP sendiri yang saya dapat:
Metode Brute Force : metode ini memeriksa semua kemungkinan cara untuk mengunjungi seluruh list tujuan dan kembali ke posisi asal.
Metode manual atau secara kasat mata : metode ini adalah yang paling gampang digunakan karena kita hanya mengira-ngira tujuan mana yang paling dekat terlebih dahulu, tetapi tidak menjamin dapat memberikan hasil yang optimal.
Metode Clonal Selection : ini lagi saya kerjakan, hhe. .
Manfaat TSP
- Logistik dan Supply Chain
- Transportasi
- Manufaktur
- Pengaturan Gene Chromosom (Genome) Termasuk DNA
- dll
Untuk lebih jelas dari manfaat dan aplikasi TSP dapat dikunjungi pada blog LIPI berikut
Sumber : Wikipedia & Lipi Blog
Sekian tutorial kali ini, semoga bermanfaat, GBU :)
 |
