Penulis : Yozef Tjandra, S.Si, M.Sc.
Masalah Traveling Salesperson Problem (TSP) merupakan salah satu masalah klasik yang akan selalu muncul dalam hampir setiap buku teks ilmu komputer di setiap generasi. Masalah TSP begitu sederhana sehingga setiap murid sekolah menengahpun akan sanggup memahami duduk perkaranya. Namun di sisi lain, masalah ini juga telah menyisakan misteri tak terselesaikan kepada para pakar terbaik dunia di sepanjang sejarah ilmu komputer.
TSP telah memantik berbagai kelompok peneliti ilmu komputer untuk berlomba-lomba mencari penyelesaiannya. Pertama-tama, memang masalah ini mewakilli tantangan nyata muncul di berbagai bidang kehidupan, mulai dari perencanaan perjalanan wisata hingga desain optimal microchip. Namun, lebih lanjut lagi penyelesaian masalah ini akan mampu memberikan hasil dalam salah satu pencarian terbesar dalam ilmu komputer, yaitu masalah P vs NP, yang pemecahnya dijanjikan hadiah sebesar satu juta dolar oleh The Clay Mathematics Institute!
Tidak disangka, dalam awal dekade kedua dari abad ke-21 ini kita dikejutkan oleh munculnya terobosan penting mengenai perkembangan penyelesaian masalah TSP yang ditemukan oleh Nathan Klein, seorang mahasiswa doktoral di University of Washington, Amerika Serikat. Hasil tersebut dimuat oleh suatu makalah yang diterbitkan secara preprint pada Juli 2020 yang kemudian dengan cepat membangkitkan berbagai respon semarak dari komunitas ilmuwan komputer. Sebagaimana dikutip oleh majalah sains Quanta, Prof. David P. Williamson, seorang pakar ilmu teori kompleksitas dari Cornell University yang telah menekuni masalah TSP sejak 1980an, mengungkapkan bahwa ini merupakan prestasi terbesar yang selama ini diharapkan dapat ia hasilkan di sepanjang karir akademiknya. Tanpa diduga, prestasi ini justru dihasilkan oleh seorang mahasiswa!
Gambar 1 Nathan Klein (kiri) dengan kedua pembimbing doktoralnya Anna Karlin (tengah) dan Shayan Oveis Gharan (kanan). Sumber: https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/
Sebetulnya penyelesaian yang diberikan Klein tidak benar-benar telah menyelesaikan masalah TSP secara tuntas, melainkan hanya memberikan sebuah algoritma aproksimasi saja. TSP telah diketahui berada dalam kelas NP-Complete, yang berarti bahwa hingga saat ini belum ditemukan suatu algoritma dengan efisiensi polinomial yang dapat menyelesaikan masalah tersebut (dan jika algoritma demikian ditemukan maka masalah P vs NP juga ikut terselesaikan!) Dalam makalahnya yang memiliki tebal 89 halaman tersebut, Klein sebetulnya hanya memberikan algoritma untuk mencari perkiraan solusi yang secara absolut memang bukan nilai yang paling optimal. Lebih lanjut lagi, algoritma Klein juga tidak sepenuhnya berjalan untuk setiap kasus yang ada, namun hanya pada suatu subkelas permasalahan yang direstriksi untuk memenuhi suatu asumsi ideal tertentu, yang disebut sebagai masalah Metric TSP.
Yang lebih mengherankan lagi, rupanya hasil menghebohkan yang dipublikasikan Klein bersama kedua pembimbing doktoralnya, Anna Karlin dan Shayan Gharan ini sebetulnya hanya memiliki peningkatan sebesar kurang lebih 10-34 persen saja dari hasil penelitian yang sudah ada sebelumnya! Untuk memberikan gambaran, seorang kuintilioner adalah orang kaya yang memiliki harta sebesar satu juta trilyun rupiah. Anggaplah penyelesaian TSP pada penelitian sebelumnya membutuhkan dana sebesar harta kekayaan dari satu juta trilyun orang kuintilioner yang dikumpukan. Sementara itu, algoritma Klein sebetulnya hanya menghemat 1 rupiah saja di antara astronomi rupiah biaya yang sudah dihabiskan tersebut. Laju peningkatan ini luar biasa kecil, bahkan hampir dapat kita abaikan sebetulnya! Lantas mengapa pencapaian ini menjadi begitu berharga dan mendapatkan perhatian besar?
Untuk dapat melihat signifikansi besar atas pencapaian mikroskopis ini, mari kita menilik lebih detail mengenai permasalahan ini. Pertanyaan yang diajukan oleh masalah TSP, sebagaimana terjelaskan oleh judul masalahnya sendiri, terinspirasi dari diskusi mengenai bagaimana merencanakan perjalanan seorang salesman yang perlu mengunjungi sekian kota yang menjadi target penjualannya. Untuk memberikan konteks, anggaplah salesman ini perlu mengunjungi 34 provinsi di Indonesia dalam sebuah putaran yang bermula dan berakhir di DKI Jakarta. Tentu kita perlu memikirkan agar perjalanan yang direncanakan memiliki rute yang sependek mungkin untuk menekan biaya operasional. Permasalahan TSP menyelidiki bagaimana cara mencari rute yang termurah di antara semua rute keliling Indonesia yang mungkin.
Apakah ini adalah masalah yang mudah? Ya, mungkin terdengar mudah karena isu ini juga muncul dalam masalah sehari-hari yang tidak jarang kita hadapi pula bukan? Namun demikian, penyelidikan yang teliti akan mengungkap bahwa masalah ini menyimpan ruang solusi yang membesar secara faktorial untuk diselidiki setiap kemungkinannya. Sebagai gambaran, untuk memastikan optimalitas solusi rute keliling Indonesia, sebetulnya kita perlu menyelidiki seluruh kemungkinan rute yang ada, yaitu sebanyak rute. Jika seluruh populasi dunia diminta untuk memeriksa suatu rute dengan kecepatan pemeriksaan 1 detik per rute, maka sejuta trilyun tahun pun tidak cukup untuk menyelesaikan tugas ini!
Solusi optimal TSP berukuran terbesar yang berhasil diselesaikan sepanjang sejarah dihasilkan dari proyek PLA85900. Dalam proyek ini, TSP memberikan rute optimal untuk pemotongan 85.900 titik terminal dengan menggunakan LaserLogic untuk suatu chip komputer di AT&T Lab. Penyelesaian masalah ini dikerjakan oleh suatu fasilitas cluster komputasi di Georgia Institute of Technology yang dijalankan sejak Februari 2005 hingga April 2006 dengan total beban komputasi setara 136 tahun CPU.
Gambar 2 Visual Laser Logic pada proyek PLA85900 (sumber: http://www.math.uwaterloo.ca/tsp/pla85900/tours/pla8maze.gif)
Walaupun penyelesaian eksak atas TSP terlihat begitu jauh dari genggaman tangan kemanusiaan, sebetulnya sejak tahun 1976 kita telah memilliki suatu algoritma polinomial untuk menghitung solusi aproksimasi yang cukup mumpuni untuk digunakan hasilnya dalam praktek masalah nyata. Christofides dan Serdyukov secara independen menemukan algoritma dengan efisiensi kubik yang menjamin bahwa besar rute pengelilingan hasil aproksimasi tidak lebih buruk dari 150% solusi yang optimal. Tentu saja hal ini merupakan hasil yang signifikan pada zaman tersebut, karena secara pragmatis hasil ini telah membuka jalan untuk memberikan solusi yang ‘lumayan’ bagi berbagai permasalahan yang secara natural muncul sebagai TSP.
Sejak dipublikasikannya algoritma Christofides-Serdyukov, para ilmuwan komputer terus berupaya untuk meningkatkan akurasi solusi algoritma aproksimasi dengan menekan angka 150% di atas optimal agar menjadi makin dekat menuju 100% optimal. Namun demikian, sayangnya upaya ini tidak pernah membuahkan hasil yang secara esensial melampaui apa yang Christofides dan Serdyukov telah pasang sebagai standar yang tak terkalahkan selama beberapa dekade. Memang terdapat banyak grup peneliti yang dapat memberikan tingkat aproksimasi yang lebih baik, namun hal tersebut hanya berlaku untuk subkelas permasalahan yang terlalu spesifik seperti Euclidean TSP, planar TSP, dan low-genus metric TSP yang terselesaikan dalam jangka waktu 1990an hingga 2000an.
Algoritma Christofides-Serdyukov bersifat heuristik dan cukup dikenal sebagai algoritma klasik yang memiliki gagasan inti yang relatif sederhana. Untuk memulai pencarian sirkuit ke setiap kota, strategi yang dilakukan algoritma ini adalah mencari terlebih dahulu pohon yang merentang seluruh kota yang ada dengan bobot terkecil. Dari struktur pohon tersebut, jalan demi jalan ditambahkan hingga diperoleh sirkuit yang utuh yang mengelilingi setiap kota.
Dengan makin populernya teknik randomisasi dalam algoritma pada abad ke 21 ini, banyak ilmuwan komputer percaya bahwa teknik inipun akan dengan natural mampu mengoptimalkan strategi Christofides dan Serdyukov. Ola Svensson dari Swiss Federal Institute of Technology di Laussane mengungkapkan bahwa secara intuisi atas hal ini begitu sederhana dan meyakinkan, namun pembuktian formalnya begitu sulit untuk ditaklukkan.
Hal senada ini pula yang diperjuangkan oleh Klein, dan kedua pembimbing doktoralnya. Gharan, salah satu pembimbing Klein secara spesifik merupakan pakar dalam suatu disiplin ilmu matematika yang mengamati sifat geometris dari polinomial. Sejak studi doktoralnya pada tahun 2010, Gharan begitu yakin bahwa bidang ilmu ini menjadi kunci penting untuk mengalahkan algoritma Christofides-Serdyukov. Segera setelah Gharan bertemu dengan Karlin dan Klein, mereka sepakat untuk memulai penyelidikan yang lebih mendalam pada permasalahan ini. Tanpa disangka, kolaborasi mereka akhirnya telah menuntaskan visi Gharan yang telah ia gumuli selama hampir 10 tahun.
Fakta bahwa algoritma Karlin, Klein, dan Gharan berhasil memberikan aproksimasi yang secara faktual lebih baik dari algoritma Christofides-Serdyukov merupakan kenyataan yang terlalu mengejutkan untuk diterima oleh komunitas ilmu komputer. Laju peningkatan yang sebetulnya hanya mikroskopis tersebut sama sekali tidak menjadi bahan tertawaan, namun sebaliknya telah menjadi suluh yang menerangi jalan para peneliti untuk makin mengobarkan energi ke arah perkembangan TSP yang lebih signifikan. Karlin, Klein dan Gharan sendiri percaya bahwa algoritma mereka seharusnya dapat menghasilkan 4/3-aproksimasi, yang secara signifikan lebih baik dibanding 3/2-aproksimasi yang disediakan oleh Christofides-Serdyukov. Namun demikian, keyakinan ini masih sulit untuk mereka buktikan dan dengan demikian sepatutnya hal ini membuka lebar pintu undangan bagi berbagai peneliti ilmu komputer kelas dunia untuk berkolaborasi membuktikan konjektur tersebut.
Akankah gebrakan kecil yang mendunia ini mengakibatkan gelombang inovasi yang akan menuntun pada penyelesaian masalah yang lebih fenomenal lagi? Tidak ada yang tahu, namun hal ini memberikan alasan yang sangat baik untuk kita makin bertekun dalam kontribusi masalah ini. Kiranya artikel singkat ini dapat membangkitkan gairah kita dalam meneliti.