Travelling Salesman problem (TSP)

on

ABSTRAKSI
Travelling Salesman problem (TSP) merupakan masalah kombinasi optimasi dalam operasi penelitian dan teori ilmu komputer. Dengan daftar kota-kota yang akan dikunjungi, cara ini sangat tepat untuk menemukan dengan sesingkat mungkin setiap kota yang akan dikunjungi dengan waktu, dan penggunaan biaya yang tepat, dan efisien.

Masalah ini pertama kali dirumuskan sebagai masalah matematika pada tahun 1930 dan merupakan salah satu masalah yang paling intensif dalam mempelajari masalah optimasi, dan digunakan sebagai patokan bagi banyak metode optimasi dalam jumlah besar dengan cara yang tepat, dan metode yang mudah untuk diketahui, sehingga beberapa kasus dengan puluhan ribu kota dapat diselesaikan dengan baik. TSP memiliki beberapa aplikasi, seperti perencanaan, logistik, dan manufaktur. Dalam aplikasi ini, TSP merupakan konsep jarak perjalanan waktu atau biaya. Dalam banyak aplikasi, dapat muncul kendala seperti keterbatasan sumber daya atau waktu.

Travelling Salesman Problem (TSP) adalah problem untuk mengoptimasi dan menemukan perjalanan (tour) yang paling terpendek. TSP adalah problem untuk menentukan urutan dari sejumlah kota yang harus dilalui oleh salesman, setiap kota hanya boleh dilalui satu kali dalam perjalanannya, dan perjalanan tersebut harus berakhir pada kota keberangkatannya dimana salesman tersebut memulai perjalananya, dengan jarak antara setiap kota satu dengan kota lainnya sudah diketahui. Salesman tersebut harus meminimalkan pengeluaran biaya, dan jarak yang harus ditempuh untuk perjalanannya tersebut.

TSP ini dapat dilakukan secara sederhana dengan beberapa metode algoritma. TSP adalah salah satu contoh permasalahan kombinatorial dengan kemungkinan penyelesaian yang sangat banyak.

 1.     PENDAHULUAN
  1. Traveling Salesman Problem (TSP) adalah suatu permasalahan dimana seorang sales harus melalui semua kota yang ditunjuk dengan jarak yang paling pendek dan setiap kota hanya boleh dilalui satu kali.
  2. Penyelesaian dalam TSP adalah jalur yang dilalui oleh salesman sesuai dengan batasan diatas. Penyelesaian terbaik adalah jalur dengan jarak terpendek.
  1. TSP adalah salah satu contoh permasalahan kombinatorial dengankemungkinan penyelesaian yang sangat banyak.
            ==> menentukan sirkuit Hamilton yang memiliki bobot minimum.

Aplikasi TSP:
  1. Pak Pos mengambil surat di kotak pos yang tersebar pada n buah lokasi  di berbagai sudut kota.
  2. Lengan robot mengencangkan n buah mur pada beberapa buah peralatan mesin dalam sebuah jalur perakitan.
  3. Produksi n komoditi berbeda dalam sebuah siklus.
 2.     ALGORITMA TSP
Algoritma exhaustive, yaitu dengan mencari semua kombinasi yang mungkin terjadi, kemudian memilih kombinasi perjalanan dengan jarak terdekat, algoritma ini mempunyai kompleksitas n!/2n.
Permasalahan :
·         Diberikan n buah kota serta diketahui jarak antara setiap kota satu dengan kota yang lain. Temukan perjalanan (tour) terpendek yang melalui setiap kota lainnya dengan hanya sekali melewati kota-kota tersebut dan kembali lagi ke kota asal keberangkatan.
·         Permasalahan TSP ini dimodelkan sebagai graf lengkap dengan n buah simpul. Bobot pada setiap setiap sisi menyatakan jarak antara dua buah kota yang bertetangga.
·         Permasalahan TSP tidak lain adalah menemukan sirkuit Hamilton dengan bobot paling minimum.
·         Algoritma exhaustive search untuk persoalan TSP :
A.    Enumerasikan (list) semua sirkuit Hamilton dari graf lengkap dengan n buah simpul.
B.     Hitung (evaluasi) bobot setiap sirkuit Hamilton yang ditemukan pada langkah 1.
C.     Pilih sirkuit Hamilton yang mempunyai bobot paling terkecil.

Implementasi TSP Pada Kota :
1.      TSP Dengan 3 Kota.
Ø  TSP dengan 3 kota (1, 2, 3) hanya mempunyai satu kemungkinan seperti gambar dibawah ini :

Ø  TSP dengan 3 kota tidak perlu diselesaikan menggunakan komputer.

2.      TSP Dengan 4 Kota.

Graf di atas memiliki 4!/2(4) = 3 sirkuit Hamilton Misalkan simpul a adalah kota tempat dimulainya perjalanan (starting city). Enumerasikan semua sirkuit hamilton sebagai berikut :
I1 = (a, b, c, d, a) atau (a, d, c, b, a)  ==> panjang = 10 + 12 + 8 + 15 = 45
I2 = (a, c, d, b, a) atau (a, b, d, c, a)  ==> panjang = 12 + 5 + 9 + 15 = 41
I3 = (a, c, b, d, a) atau (a, d, b, c, a)  ==> panjang  = 10 + 5 + 9 + 8 = 32

                       

Jadi, sirkuit Hamilton terpendek adalah I3 = (a, c, b, d, a) atau (a, d, b, c, a) dengan panjang sirkuit = 10 + 5 + 9 + 8 = 32.


3.     

 
TSP Dengan 5 Kota.



Graf di atas memiliki 5!/2(5) = 12 sirkuit Hamilton Misalkan simpul a adalah kota tempat dimulainya perjalanan (starting city). Enumerasikan semua sirkuit hamilton sebagai berikut :
I1 = (1, 2, 3, 4, 5,1) atau (1, 5, 4, 3, 2,1) 
I2 = (1,2,5,4,3,1) atau (1,3,4,5,2,1)
I3 = (1,2,3,5,4,1) atau (1,4,5,3,2,1 )
:
:
:
I12 =………………………………………



TSP dengan 5 kota mulai perlu diselesaikan menggunakan komputer. Teknik yang dipakai bisa berupa mencoba semua kemungkinan dan dibandingkan jaraknya untuk memperoleh jarak paling pendek. 

4.      TSP Dengan N Kota.
Ø  TSP dengan n kota (1, 2, 3, 4, 5,…, n) mempunyai n ! / 2n kemungkinan.
Ø  TSP dengan 15 kota mempunyai 15 ! / (15) atau 4,3589 x 1010 kemungkinan. Metode pencarian satu-satu memerlukan waktu yang sangat lama.
Ø  TSP dengan 20 kota mempunyai 19 ! / 2 atau 6,08 x 1016 kemungkinan, suatu jumlah yang sangat besar. Dengan menganggap bahwa komputer mampu menyelesaikan 1 Giga (109) proses per-detik maka untuk mencari semua solusi diperlukan 6,08 x 107 detik atau 1,69 x 104 jam atau 704 hari. Waktu yang sangat lama.

Kesimpulan :
1.      Travelling salesman problem adalah suatu permasalahan dalam menentukan sirkuit terpendek dari suatu simpul ke seluruh simpul lain tepat satu kali dan kembali ke simpul asal.
2.      Algoritma exhaustive, yaitu dengan mencari semua kombinasi yang mungkin terjadi, kemudian memilih kombinasi perjalanan dengan jarak terdekat, algoritma ini mempunyai kompleksitas n!/2n.
3.      Belum ada algoritma yang dapat menyelesaikan masalah  traveling salesman problem dengan  polynomial worst-case time complexity .Ini artinya untuk jumlah simpul yang banyak, penyelesaian traveling salesman problem adalah tidak praktis.

3.     REFERENSI
1.      http://www.digilib.ui.ac.id/opac/themes/libri2/detail.jsp?id=81280&lokasi=lokal
2.      http://www.tsp.gatech.edu/history/index.html
3.      http://en.wikipedia.org/wiki/Travelling_salesman_problem
4.      http://www.comp.nus.edu.sq/stevanha/programming/prog_greedy.html
5.http://stttelkom.ac.id/staf/fay/kuliah/DAA/20052/Tugas1/pdfs/09-DAA%2020052%20113030055%20113030037%20113030035%20Solusi%20TSP%20Menggunakan%20Algoritma%20Greedy.pdf
6.      Munir, Rinaldi. 2005. Strategi Algoritmik.Bandung. Institut Teknologi Bandung.

Comments

  1. febryfeb8 September 2015 at 16:44

    halo kak, software untuk menyelesaikan TSP dgn n=5 apa ya kak? terimakasih.

    ReplyDelete
  2. andi mauLidinna14 March 2016 at 09:00

    ass. ada listing atau bhs programnya buat bisa dipelajari? bs dishare makasih b4 :)

    ReplyDelete
  3. Unknown18 December 2016 at 06:48

    pake framework P5.js bisa gan solusi TSP

    ReplyDelete

Post a Comment

Terimakasih sudah singgah, jangan lupa tinggalkan jejak ya :)