TRAVELLING SALESMAN PROBLEM

Travelling  salesman  problem  adalah  suatu      permasalahan  dalam  bidang  diskrit dan  optimasi kombinatorial.  Sebagai  permasalahan  kombinatorial, persoalan  ini  tergolong  memilingi  kemungkinan jawaban  yang  sangat  banyak.  Permasalahan  ini diilhami  oleh  masalah  seorang  pedagang  yang mengelilingi beberapa kota. Permasalahan matematik  yang  berkaitan  dengan Travelling  Salesman  Problem  mulai  muncul  sekitar tahun  1800-an.  Masalah  ini  dikemukakan  oleh  dua orang  matematikawan,  yaitu  Sir  William  Rowan Hamilton  yang  berasal  dari  Irlandia  dan  Thomas Penyngton Kirkman yang berasal dari Inggris. Bentuk umum dari persoalan TSP pertama kali dipelajari oleh para  matematikawan  mulai  tahun1930-an  oleh  Karl Menger  di  Vienna  danHarvard.  Persoalan  tersebut kemudian  dikembangkan  oleh  Hassler  Whitney  dan Merril Flood di Princeton.  Berdasarkan  kesesuaian  dengan  nama, deskripsi persoalan  adalah  sebagai  berikut:  diberikan  sejumlah kota,  tentukan  sirkuit  terpendek  yang  harus  dilalui oleh  seorang  pedagang  bila  pedagang  itu  berangkat dari  sebuah  kota  asal  dan  menyinggahi  setiap  kota tepat  satu  kali  dan  kembali  lagi  ke  kota  asal keberangkatan. Kota  dapat  dinyatakan  sebagai  sebuah  simpul graf, sedangkan  sisi  menyatakan  jalan  yang menghubungkan  antara  dua  kota.  Bobot  pada  sisi menyatakan  jumlah  antara  dua  buah  kota.  Persoalan ini  adalah  persoalan  yang  menentukan  sirkuit Hamilton  dengan  sisi memiliki  bobot minimum  pada suatu  graf  terhubung.  Selain  permasalahan  pedagang kelilingi,  terdapat  beberapa  kasus  yang  merupakan penerapan  dari  pencarian  sirkuit  Hamilton  dengan bobot minimum.

  Jika  setiap  simpul  pada  graf  bobot  mempunyai sisi  ke  simpul  lain  maka,  graf  tersebut  adalah  graf lengkap  berbobot.  Pada  sembarang  graf  lengkap dengan n buah simpul  (n>2),  jumlah sirkuit Hamilton yang berbeda adalah (n-1)!/2. Persoalan  TSP  adalah  persoalan  yang  sulit  jika dipandang  dari  segi  komputasi.  Secara  teoritis,  TSP dapat  diselesaikan  dengan  mengenumerasi  seluruh kemungkinan  sirkuit  Hamilton  yang  ada  lalu menghitung bobot total dari seluruh sirkuit Hamilton.