icomit

Just another WordPress.com site

Traveling Salesman Problem (TSP) dalam definisi

TSP atau Traveling Salesman Problem adalah salah satu masalah distribusi yang cukup lama dibahas dalam kajian optimasi. Masalahnya adalah bagaimana seorang salesman mengunjungi seluruh kota di suatu daerah dan kembali ke kota awal keberangkatan dengan aturan bahwa tidak boleh ada kota yang dikunjungi lebih dari satu kali.

Berikut adalah aturan-aturan yang mengidentifikasikan bahwa permasalahan tersebut adalah TSP:

  1. Perjalanan dimulai dan diakhiri di kota yang sama sebagai kota asal sales.
  2. Seluruh kota harus dikunjungi tanpa satupun kota yang terlewatkan.
  3. Salesman tidak boleh kembali ke kota asal sebelum seluruh kota terkunjungi.
  4. Tujuan penyelesaian permasalahan ini adalah mencari nilai optimum dengan meminimumkan jarak total rute yang dikunjungi dengan mengatur urutan kota.

Perhatikan contoh berikut:

Seorang salesman akan mengawali perjalanannya di kota asal(Kota A) untuk mengunjungi seluruh kota yakni kota A-F. Perhatikan gambar berikut.

Dari studi kasus tersebut didapatkan salah satu kemungkinan jalur yang paling optimum dengan jalur urutan kota A->E->F->C->D->B->A.  tentunya hasil tersebut dengan mempertimbangkan jarak dari masing-masing kota hingga menghasilkan kombinasi urutan kota dengan jarak yang optimum. Perhatikan gambar berikut.

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: