TSP DAN APLIKASINYA

Konsep Dasar Traveling Salesman Problem (TSP) dan Aplikasinya untuk Logistik, Transportasi Hingga Pengurutan Genom-DNA

Ilustrasi Kasus 

Alkisah, seorang salesman sedang bingung menentukan rute terpendek untuk menjual barangnya melalui sejumlah tempat. Sebut saja tempat tersebut adalah nama kota: Jogja (J), Khurasm (K), Lincolnshire (L), Madinah (M) dan New Jersey (N). New Jersey, USA merupakan tempat meninggalnya Frank Bunker Gilbreth, Sr., salah seorang peneliti perancangan sistem kerja dan ergonomi untuk mencapai efisiensi dan dipandang sebagai salah seorang pionir di bidang  management science  (yang kemudian melebur menjadi Industrial Enginering).  Madinah adalah tempat lahir Jafar Ash-Shadiq, salah seorang pembangun teori partikel yang juga guru dari Jabir Ibn Hayyan (yang kemudian hari dikenal sebagai salah seorang bapak Kimia). Lincolnshire merupakan sebuah tempat di Inggris tempat lahirnya ilmuwan peletak hukum gerak dan gravitasi, Sir Isaac Newton. Sementara Khurasm di Afganistan adalah tempat ahli matematika pencetus Algoritma, Abu Musa Al Khawarizm, dilahirkan. Jogja? Tempat lahirnya sang penulis artikel "Als ik eens Nederlander was" ("Seandainya Aku Seorang Belanda"), Ki Hadjar Dewantara; sekaligus tempat lahirnya tokoh yang filmnya tengah popular saat ini, “Sang Pencerah”, yaitu Muhammad Darwis atau yang lebih dikenal dengan K.H. Ahmad Dahlan. 

Kembali ke kisah sang salesman. Sang salesman berangkat dari suatu kota (anggaplah Jogja sebagai garis start) dan harus mengunjungi kota lainnya masing-masing satu kali sebelum kembali ke kota awal (Jogja lagi). Misal diketahui jarak antar kota dalam satuan kilometer, sang salesman ingin memilih rute sedemikian rupa agar total jarak tempuh.menjadi minimum, sehingga total waktu sekaligus ongkos perjalanannya juga dapat ditekan (dengan asumsi keduanya merupakan fungsi dari jarak tempuh). Ilustrasi permisalan masalah ini bisa dilihat pada tabel dan gambar berikut.

Pertanyaan: bagaimanakah urutan rute yang harus ditempuh oleh sang salesman untuk mendapatkan rute terpendek? (hint akan diberikan pada pembahasan selanjutnya)

Pengenalan Sekilas Tentang Traveling Salesman Problem

Alkisah di atas merupakan salah satu masalah klasik yang dikenal sebagai Traveling Salesman Problem (TSP), dan 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 misalnya 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. 

Gambar 2: Berbagai bentuk polihedron [7]

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.”

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 di drill 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 satu yang dianjurkan untuk bacaan pengantar adalah tulisan dari Hofman dan Padberg. (mungkin juga akan dilanjutkan untuk dibahas di sini kelak)

Penutup 

Terlepas dari kompleksitas yang ada, penelitian mengenai TSP masih menarik dan berkembang hingga saat ini. Pada tahun 2001, telah ditemukan solusi TSP untuk problem sekitar 15.000 kota, sebuah peningkatan yang sangat signifikan dibandingkan tahun 1954 yang “hanya” 49 kota. Sebuah program Concorde yang dipakai pada pemetaan genome pada contoh di atas misalnya, telah mampu memecahkan solusi hingga 15.112 kota. Begitu menariknya penelitian di bidang ini, hingga disediakan hadiah bagi yang bisa memecahkannya, misalnya Mona Lisa TSP Challenge, berhadiah $100 bagi penemu solusi optimal untuk 100.000 kota. Juga, the Clay Mathematics Institute sampai menyediakan hadiah $1.000.000,- untuk memecahkan masalah ini.

Tanggapannya :

Solusi yang di berikan pada kasus TSP ini sepertinya kurang efektif dan efisien, karena menghabiskan banyak waktu. Terlepas dari kompleksitas yang ada, penelitian mengenai TSP masih menarik dan berkembang hingga saat ini. Pada tahun 2001, telah ditemukan solusi TSP untuk problem sekitar 15.000 kota, sebuah peningkatan yang sangat signifikan dibandingkan tahun 1954 yang “hanya” 49 kota. Sebuah program Concorde yang dipakai pada pemetaan genome pada contoh di atas misalnya, telah mampu memecahkan solusi hingga 15.112 kota.

Semoga masih banyak lagi orang yang menemukan solusi untuk kasus ini. Bahkan begitu menariknya penelitian di bidang ini, hingga disediakan hadiah bagi yang bisa memecahkannya, misalnya Mona Lisa TSP Challenge, berhadiah $100 bagi penemu solusi optimal untuk 100.000 kota. Juga, the Clay Mathematics Institute sampai menyediakan hadiah $1.000.000,- untuk memecahkan masalah ini.