Traveling Salesman Problem (TSP) salah satu problem kelas "NP-complete"
1. SUATU MISTERI
Piere de Fermat (1601-1665) adalah matematikawan Perancis yang telah menyumbangkan dalam bidang geometri analitik. Tetapi salah satu "warisan" yang ditinggalkannya yang dikenal dengan "Teorema Terakhir Fermat"( Ultimo teorema Fermat) memberikan penasaran para matematikan. Teorema ini sederhana tapi sulit untuk dibuktikan. teorema telah menjadi suatu misteri selama lebih dari 350 tahun untuk membuktikannya. Misteri ini baru tarbuka setelah berhasil dibuktikan oleh matematikawan Ingrris lima tahun yang lalu.
2. SUATU OBSESI
Kini dunia Operations Research, matematika dan Computer Scince masih juga diselimuti dengan misteri kemampuan komputer. Pada umumnya kita mengetahui bahwa perkembangan kemampuan kecepatan komputer yang begitu hebat bagaikan kilat dengan kemampuan memory yang super, tetapi ternyata mengalami keterbatasan dan kegagalan karena ketidak mampuan untuk memecahkan problem yang ada didunia ini. Banyak problem yang belum ada solusinya dan bahkan tidak mungkin diselesaikan meskipun dibantu oleh super hyper komputer yang tercanggih didunia ini. Kelompok problem ini memerlukan waktu superpolynomial. Kelompok atau kelas problem ini dikenal dengan problem "NP-complete" . Beribu-ribu penelitian telah dikerahkan untuk mengusahakan memecahkan persoalan ini dengan waktu penyelesaian polynomial, ternyata mengalami kegagalan total atau dikatakan mandeg. Ini suatu misteri juga yang belum terpecahkan
Salah satu problem kelas "NP-complete " dan yang terkenal dan belum terpecahkan ialah Travelling Salesman Problem (atau dikenal dengan TSP). Problem ini erat hubungannya dengan problem hamiltonian- cycle. Problem ini dikenal sebagai NP-lengkap, dan tak dapat dipecahkan secara eksak dengan polynomial-time. Menurut Roger Penrose, ahli matematika dan fisika dari Inggris dan kolega Stephen Hawking( pemenang hadiah nobel ) bahwa TSP ini adalah persoalan yang sangat sulit untuk diselesaikan.
Dalam bukunya yang terkenal "The Emperor's New Mind" Dia menguraikan complexity theory atas "NP-complete' dan TSP ini. Dalam tulisannya :
"It is commonly believed by the experts that it is actually impossible with any Turing machine-like device,to solve an NP-complete problem in polynomial time, and that, consequently , P and NP are not the same. Very likely this belief is correct , but as yet no-one has been able to prove it. This remains the most important unsolved problem of complexity theory."
Roger Penrose mengenalkan persoalan TSP ini sebagai suatu soal yang berkaitan dengan complexity theory, yaitu persoalan matematik yang algoritmanya sangat sukar dipecahkan atau sangat lambat langkah-langkahnya karena jumlah langkah-langkah sangat banyak dan storage space dalam jumlah yang sangat besar. Makin besar jumlah variabel makin meningkat secara eksponensial untuk waktu pemecahannya.
Bila TSP ini dapat dipecahkan secara polynomial ,maka metode yang diketemukan ini akan membuat suatu kejutan dunia dan menjadi head line news. Tapi Roger Penrose sendiri menyatakan bahwa TSP tak mungkin dapat dipecahkan, karena melihat betapa berat kerjanya komputer untuk mencapai solusinya.
Demikian pula para matematikawan pada umumnya bersifat skeptis dan menyerah. Ini sungguh adalah suatu tantangan dan juga merupakan obsesi bagi para matematikawan untuk mencari solusinya. TSP dikenal sebagai jenis problem NP-complete yang telah menjadi obsesi para ahli matematika selama dua generasi karena 'kebandelannya' sebagai problem yang sangat sulit, karena memerlukan waktu yang begitu besar untuk mencapai solusi terbaiknya.
3. METODE PEMECAHAN TSP
TSP merupakan problem klasik yang sangat mudah dinyatakan namun sangat sulit dipecahkan. Problemnya adalah menemukan rute terpendek pada sebuah set N verteks-verteks sehingga seluruh verteks dikunjungi sekali saja, atau dengan gambaran yang sederhana yaitu :
Bilamana ada suatu penerbangan yang harus singgah N-kota dimana tiap-tiap kota dikunjungi satu kali saja sedangkan keberangkatan dan kembalinya hanya pada satu kota awal perjalanan tersebut. Persoalannya ialah kita harus memilih satu rute terpendek dari perjalanan penerbangan tersebut. TSP merupakan problem kombinatorial dimana yang memiliki alternatif kemungkinan rute yang banyak sekali yaitu, 1/2 (N-1)!. Menurut Helge Ritter, Thomas Martinetz dan Klaus Schulten dalam bukunya "Neural Computation and Self-Organizing Maps" :
"By testing all 1/2 (N-1)! possible tours, one can always find the shortes tour but the computational effort fot this "direct strategy" called "exhaustive search", rises exponentially with N and rapidly becomes unmanegable (for N = 30 the required processing time, even using a Cray-XMP supercomputer would exceed the age of universe".
TSP masih tetap tak terpecahkan dengan algoritma-algoritma polinomial. Sejumlah besar teknik-teknik pencarian solusi telah dikembangkan, tetapi tetap memiliki kemampuan terbatas oleh ukuran problemnya. Teknik-teknik programa matematika yang ada tak dapat menyelesaikan problem ini dengan cepat dan "baik". Jadi, dibutuhkan teknik yang "baik" dari segi kualitas solusinya, waktu komputasinya, maupun kesederhanaan dan kemudahan implementasinya.
Banyak pendekatan yang telah dikembangkan untuk memecahkan TSP ini. Tapi pada umumnya gagal total, karena memerlukan waktu yang begitu lama untuk mencapai solusi terbaik.
NP-problem muncul dalam banyak konteks, baik dalam matematika itu sendiri maupun didalam dunia praktek.
Bermacam-macam teknik dan metode telah dikembangkan untuk menyelesaikan TSP yaitu antara lain :
1. Heuristik (Approximation)
- Neural network
- Genetic algorithm
- Simulation annealing
- Branch and bound
- Tabu search
- Parallel processing
- Nearest neigbor
- Threshold algorithm
- dll
2. Solusi eksak :
- Linear programming (simplex)
- Integer programming
- Cutting plane
- Dynamic programming
- The minimum spanning tree
- Lagrange relaxation
- Ellipsoid algorithm
- Projective scaling algorithm
Metode simplex tak mampu menyelesaikan persoalan TSP karena jumlah iterasi meningkat dengan cepat sekali bersamaan dengan kenaikan ukuran persoalan dan membutuhkan memori yang sangat besar sekali. Sedangkan metode Ellipsoid algorithm (yang dikembangkan oleh L.B Kachian) dan metode ini Projective scaling algorithm (yang dikembangkan oleh Karmarkar) tak mampu memecahkan persoalan yang rumit. Ini disebabkan jumlah persamaan sangat besar yang tak mampu ditampung dalam memori komputer. Sebagai ilustrasi untuk N=50 jumlah persamaan constrains adalah 150 persamaan.
AZG
Indonesian Production and Operations Management Society (IPOMS).
http://www.ipoms.web.id
Bergabunglah dengan IPOMS di Facebook
http://www.facebook.com/home.php?ref=home#/group.php?gid=34994473375
===================================================================
Terlalu banyak email?
Kirimkan 1 email kosong ke :
APICS-ID-digest@yahoogroups.com <-- 1 email rangkuman saja perhari.
APICS-ID-nomail@yahoogroups.com <-- Libur panjang/cuti lebaran ==> no email
dan cek lewat web.
Lain-lain:
APICS-ID-normal@yahoogroups.com <-- kembali ke pengiriman email normal
APICS-ID-owner@yahoogroups.com <--- alamat moderator
APICS-ID-subscribe@yahoogroups.com <--- jika ingin berlangganan
Kirimkan 1 email kosong untuk bergabung dengan milis lainnya:
SIM-IPOMS-subscribe@yahoogroups.com <-- Simulation/Op. Research/Quantitative
Methods/Decision Sciences.
COST-IPOMS-subscribe@yahoogroups.com <-- Cost/Performance Mgmt
BPR-IPOMS-subscribe@yahoogroups.com <--- Business Process Reengineering
INDO-POM-subscribe@yahoogroups.com <-- Six Sigma dan Organisasi IPOMS
Indo-Job-subscribe@yahoogroups.com <-- Lowongan kerja
KOMPUTER-TEKNOLOGI-subscribe@yahoogroups.com <-- Komputer dan Teknologi
Informasi
Bisnis-Karir-subscribe@yahoogroups.com <-- Pengembangan karir dan bisnis
Free-English-Course-subscribe@yahoogroups.com <-- Belajar bahasa Inggris
HRD-POWER-subscribe@yahoogroups.com <--- Human Capital/Resource Development
Manajemen-Industri-subscribe@yahoogroups.com <-- Manajemen umum dan Industri
No comments:
Post a Comment