Rabu, 18 Juli 2012

TRAVELLING SALESMAN PROBLEM

Masalah klasik yang dikenal sebagai Traveling Salesman Problem (TSP) menjadi pokok bahasan menantang yang dikaji secara intensif selama beberapa dasawarsa terakhir di bidang operational research, logistik dan sistem rantai pasok (supply chain systems), transportasi maupun theoretical computer science.

Sejarah TSP bisa ditelusur dari Euler yang mempelajari Knight Tour’s Problem (1759), Kirkman yang mempelajari grafik polihedron (1856) maupun Hamilton yang membuat game Icosian (1856) yang bertujuan mencari jalur sirkuit berbasis grafik polihedron yang memenuhi kondisi tertentu [2]. Istilah TSP sendiri diperkirakan berasal dari buku yang diterbitkan oleh seorang veteran salesman sekitar tahun 1930an di Jerman, meski dalam buku ini masalah TSP lebih dibahas dari aspek bisnis dan belum diformulasikan secara matematis.



Bentuk formulasi umum TSP sepertinya mulai dipelajari sekitar tahun 1930 oleh para matematikawan di Vienna dan Harvard, khususnya oleh Karl Menger, yang mendefinisikan problem ini sebagai berikut:

“We denote by messenger problem (since in practice this question should be solved by each postman, anyway also by many travelers) the task to find, for finitely many points whose pairwise distances are known, the shortest route connecting the points. Of course, this problem is solvable by finitely many trials. Rules which would push the number of trials below the number of permutations of the given points, are not known. The rule that one first should go from the starting point to the closest point, then to the point closest to this, etc., in general does not yield the shortest route.”(Schrijver, A., 2005, “On the history of combinatorial optimization (till 1960)”, in Handbook of Discrete Optimization, (K. Aardal, G.L. Nemhauser, R. Weismantel, eds.), Elsevier, Amsterdam, pp. 1—68, 2005. Paper bisa didownload di http://homepages.cwi.nl/~lex/ ) 

TSP bisa dibedakan menjadi simetris dan asimetris berdasar besaran jarak bolak-balik antar dua kota. Jika jarak J ke K sama dengan K ke J, maka persoalan ini tergolong simetris, sementara jika jaraknya tidak sama dapat diklasifikasikan sebagai problem asimetris. Contoh dari problem asimetris misalnya adalah jika jalan yang menghubungkan dua kota dibuat satu arah, sehingga tidak mungkin untuk balik (jarak untuk balik bisa dibilang mendekati tak terhingga).


Aplikasi TSP

TSP yang pada awalnya muncul sebagai bagian masalah logistik dan transportasi ini telah berkembang dan dimanfaatkan di berbagai sektor. Berikut disajikan sejumlah contoh aplikasinya di beberapa bidang:


  1. Logistik dan Supply Chain: Logistik, bersama-sama dengan Supply Chain, secara umum mengandung pengertian sebagai suatu sistem untuk mengelola orang, sumberdaya, aktivitas, teknologi dan sebagainya yang dibutuhkan guna mengantarkan barang dan jasa dari titik asal (pemasok/supplier) ke titik tujuan (pelanggan) sehingga tepat waktu, tepat jenis, tepat jumlah, tepat mutu, tepat lokasi, tepat sumberdaya dsb. (Catatan: secara khusus, pengertian logistik dapat dibedakan dari supply chain, namun tidak akan dibahas disini). Pemakaian TSP dalam logistik antara lain sangat vital bagi perusahaan pengiriman barang dan jasa, industri travel dan biro perjalanan atau divisi yang bertanggung jawab atas pasokan, distribusi dan pemasaran bahan baku dan bahan jadi suatu perusahaan. Problemnya bukan hanya menentukan rute terpendek, tapi juga menentukan jenis barang tertentu yang bisa disimpan di beberapa gudang tertentu berbasis konstrain tertentu (misal kapasitas persediaan/inventori, jam buka/tutup, dsb.). Untuk prosedur pengiriman barang yang rutin, pemilihan rute yang tepat akan menghemat ongkos dalam jumlah besar dalam waktu yang lama. Penulis pernah menyaksikan salah satu perusahaan travel di Tangerang yang juga menyadari pentingnya hal ini sehingga mereka melakukan survei langsung ke ruas-ruas jalan untuk menentukan rute optimum sebelum membuka jalur baru.
  2. Transportasi: Salah satu pionir TSP dalam bidang transportasi adalah Merril Flood, seorang matematikawan Amerika, yang merumuskan rute bis sekolah di New Jersey sekitar tahun 1940an. Flood yang pernah menjabat sebagai wakil presiden Institute of Industrial Engineer tahun 1962-1965 ini juga mengembangkan pendekatan analisis sistem yang inovatif dan benefit-cost analysis di bidang kebijakan publik[8]. Sekitar tahun yang sama, penggunaan TSP untuk memecahkan masalah transportasi peralatan pertanian (yang dipakai untuk menguji tanah) dikaji di tempat yang berbeda oleh Mahalanobis (di Bengal) dan Jessen (di Iowa). Salah satu modifikasi TSP yang sudah “advanced” diteliti oleh Zheng, Zhang dan Liu [9] yang menggunakan Ant Colony Algoritm (yang masih relatif baru) untuk mendapatkan solusi optimum guna menentukan interval keberangkatan bis kota dengan mengakomodasi faktor kepadatan penumpang. Lebih jauh, implementasi TSP juga telah dikaji untuk diterapkan di Google map.
  3. Manufaktur: Pemanfaatan TSP di bidang manufaktur misalnya dalam menentukan jalur penge-drill-an untuk membuat lubang pada printed circuit board. Untuk produksi secara masal, pemakaian jalur yang lebih pendek dapat meningkatkan kecepatan sekaligus menurunkan biaya produksi secara signifikan, dan TSP merupakan perangkat yang baik untuk mencapai efisiensi produksi yang maksimum.
  4. Pengurutan Gene Chromosome (Genome), termasuk DNA :Peneliti di bidang ini, misalnya di National Institute of Health, Amerika, menggunakan bantuan Concorde's TSP solver untuk menyusun peta radiasi hibrida sebagai upaya pengurutan genom. TSP menyediakan mekanisme untuk mengintegrasikan peta-peta lokal (“kota”) ke dalam sebuah peta radiasi hibrid tunggal, di mana “jarak” dinyatakan sebagai ukuran kecenderungan sebuah peta lokal akan bergabung dengan peta lokal yang lain. Penggunaan TSP juga diadopsi oleh sebuah grup penelitian di Prancis untuk membangun peta genom tikus. Sementara grup penelitian lainnya menggunakan Concorde untuk mengkalkulasi urutan DNA di sebuah proyek penelitian genetic engineering [5].
  5. Bidang lainnya: Beberapa contoh lain penerapan TSP misalnya penjadwalan pengiriman koran atau pos, pengambilan uang koin di sejumlah telepon umum, pemasangan jaringan telekomunikasi, penentuan urutan bintang oleh satelit interferometer dan sebagainya.


Solusi dan Kompleksitas Masalah TSP

Bagaimanakah solusi atas TSP? Untuk kasus di atas, pendekatan yang bisa dipakai adalah sebagai berikut:


  • Salah satu metode yang terlihat mudah secara kasat mata adalah dengan memilih kota tujuan berikut yang jaraknya paling pendek dari tempat asal. Misal dalam kasus di atas, jarak terpendek dari Jogja adalah Madinah, kemudian dari Madinah dipilih lagi yang terpendek (selain Jogja) adalah New Jersey, dan seterusnya Tapi metode seperti ini tidak menjamin solusi jarak tempuh keseluruhan yang optimal.
  • Pendekatan yang menjamin sepenuhnya keoptimalan solusi adalah dengan mencoba semua urutan satu persatu, artinya diperlukan permutasi sebanyak 5! = 120 alternatif jalur yang harus diperiksa dan dibandingkan untuk mencari yang terpendek. Pendekatan ini disebut brute force search dan menghabiskan banyak waktu jika jumlah masalah meningkat.
  • Jika jumlah masalah (misal jumlah kota atau jumlah lubang yang harus didrill pada printed circuit board) meningkat, maka alternatif yang harus diperiksa (begitu pula waktu yang diperlukan untuk memeriksa) akan meningkat secara eksponensial. Misal untuk 15 kota saja, diperlukan setidaknya pengecekan terhadap 10 pangkat 12 (alias 10 triliun) alternatif jalur untuk mendapatkan solusi optimal.

Oleh karena itu diperlukan suatu pendekatan algoritma heuristik untuk mendapatkan solusi yang mendekati atau sama dengan optimal. Hanya saja, sampai sejauh ini belum ditemukan algoritma yang “cukup efisien” untuk memecahkan masalah di atas. Ada beberapa algoritma heuristik yang mampu mencapai nilai optimal, tapi penggunaannya hanya terbatas pada sejumlah kota, sementara algoritma lainnya mampu memberikan hampiran optimal pada tingkat tertentu.

Lebih jauh mengenai pembahasan rumus matematisnya dan berbagai pendekatan heuristiknya dapat dilihat di banyak referensi, salah satunya adalah Pendekatan Penyelesaian TSP Menggunakan Algoritma Genetika yang akan dibahas pada tulisan saya selanjutnya.


Tidak ada komentar:

Poskan Komentar