Perancangan algoritma Clarke Wright dan local search pada penyelesaian traveling salesman problem = Designing Clarke-Wright and local search Iteration algorithm to solve traveling salesman problem (TSP)
Parhusip, Sandiego Fransisco;
Komarudin, supervisor; Teuku Yuri M. Zagloel, examiner; Arian Dhini, examiner; Inaki Maulida Hakim, examiner
(Fakultas Teknik Universitas Indonesia, 2019)
|
|
Kemajuan industri menjadi suatu tantangan terhadap pengembangan ilmu pengetahuan dan teknologi. Industri akan semakin menuntut efisiensi dan efektifitas dalam berbagai aspek industri sebagai upaya meminimalkan biaya serta meningkatkan produktivitas. Oleh karena itu, diperlukan pengembangan berbagai metode solusi yang dapat menghasilkan nilai optimal namun juga dengan waktu penyelesaian yang relatif singkat.Travelling Salesman Problem atau yang sering disingkat dengan TSP merupakan salah satu permodelan masalah optimasi yang memiliki banyak aplikasi pada dunia industri seperti logisitik perkotaan, Job Scheduling, dan pembuatan Integrated Circuit. TSP diilustrasikan sebagai permasalahan seorang sales yang akan mengunjungi seluruh kota tujuan sebanyak satu kali dengan melalui jarak paling minimal dan kembali ke kota awal keberangakata. Namun pada penyelesaiannya TSP sebagai permasalahan sulit non-determistik polinomial sangatlah kompleks. Metode eksak akan memakan waktu iterasi yang lama dan meningkat secara eksponensial terhadap jumlah kota pada permasalahan TSP.Output dari penelitian ini adalah model optimasi TSP yang dapat menghasilkan rute dengan nilai mendekati optimal serta waktu penyelesaian yang relatif singkat. Model akan dikembangkan dengan algoritma heuristik komposit yakni Clarke-Wright Savings Heuristic untuk mengembangkan solusi awal yang kemudian ditingkat melalui operasi local search. Model akan dibuat dalam tiga buah variasi local search dan diujicobakan pada 30 data set dengan rentang 131 hingga 85.900 titik. Industrial development is a challenge to the development of science and technology. The industry will increasingly demand efficiency and effectiveness in various aspects of the industry as an effort to minimize costs and increase productivity. Therefore, it is necessary to develop various solution methods that can produce optimal values but also with relatively short computation times.Traveling Salesman Problem or often abbreviated as TSP is one of the optimization problem modeling that has many applications in the industrial world such as urban logistic, job scheduling, and the manufacture of integrated circuits. TSP is illustrated as a problem of a salesman who will visit the entire destination city once by going through the minimum distance and returning to the initial city. But TSP as one of non polynomial complete hard problem, is very complex to solve. The exact method will take a long iteration time and increase exponentially to the number of cities in TSP problems.The output of this study is a TSP optimization model that can produce routes with near optimal values and relatively short computation times. The model will be developed with a composite heuristic algorithm of clarke-wright savings heuristic to develop initial solutions then will be improve through local search operations. The model will be made in three varians and tested on 30 data sets with a range of 131 to 85,900 points. |
 S-Sandiego Fransisco Parhusip.pdf :: Unduh
|
| No. Panggil : | S-Pdf |
| Entri utama-Nama orang : | |
| Entri tambahan-Nama orang : | |
| Subjek : | |
| Penerbitan : | Depok: Fakultas Teknik Universitas Indonesia, 2019 |
| Program Studi : |
| Bahasa : | ind |
| Sumber Pengatalogan : | LibUI ind rda |
| Tipe Konten : | text |
| Tipe Media : | computer |
| Tipe Carrier : | online resource |
| Deskripsi Fisik : | xiii, 48 pages : illustration ; 28 cm + appendix |
| Naskah Ringkas : | |
| Lembaga Pemilik : | Universitas Indonesia |
| Lokasi : | Perpustakaan UI, Lantai 3 |
| No. Panggil | No. Barkod | Ketersediaan |
|---|---|---|
| S-Pdf | 14-20-660680675 | TERSEDIA |
| Ulasan: |
| Tidak ada ulasan pada koleksi ini: 20489864 |
