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:
- 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.
- 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.
- 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.
- 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].
- 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.
