Hasil Pencarian  ::  Simpan CSV :: Kembali

Abstrak :
Traveling Salesman Problem (TSP) merupakan permasalahan yang banyak ditemukan di bidang transportasi khusunya masalah perjalanan seorang salesman mengunjungi semua kota tepat satu kali sebelum salesman tersebut kembali ke kota awal atau depot. Perluasan dari TSP adalah Multiple Traveling Salesman Problem (MTSP) dengan jumlah salesman adalah lebih dari satu. Pada skripsi ini, penyelesaian MTSP dibahas dengan menggunakan metode algoritma Sweep dan Elite Ant System, dengan penyelesaian MTSP dilakukan dalam dua tahap. Tahap pertama, digunakan algoritma Sweep untuk membangun rute awal perjalanan salesman dan pada tahap kedua digunakan Elite Ant System untuk memperbaiki rute perjalanan awal yang diperoleh dari tahap pertama. Hasil implementasi dengan menggunakan 6 data dari TSPLIB, berdasarkan total jarak yang ditempuh, menunjukkan bahwa metode yang digunakan menghasilkan total jarak lebih baik dibandingakan dengan total jarak hasil metode MACO dan MGA untuk data yang sama. Selain itu, hasil yang diperoleh menunjukkan adanya peran pemilihan kota sebagai depot dalam menentukan total jarak.

---

Traveling Salesman Problem (TSP) is the most commonly problem that is found in transportation, especially the problem of visiting city by one salesman exactly once before the salesman back to the first city or depot. The Multiple Traveling Salesman Problem (MTSP) is an extension of TSP. This problem relates to accommodating real world problems where there is a need to account for more than one salesman. In this skripsi, MTSP will be discussed in Sweep algorithm and Elite Ant System methods, where the MTSP is solved in two stages. At the first stage, Sweep algorithm is used to construction route of salesman and the second stage, Elite Ant System is used to improving every route of salesman. The implementation results were tested using 6 benchmark problem taken from TSPLIB, based on the total distance travelled, shows that the methods produce a total distance better than the total distance of MGA and MACO methods. Moreover, the results indicate the existence of obtaining a city as the depot as the key factor in determining total distance.

Abstrak :
Traveling salesman problem (TSP) adalah permasalahan mencari rute perjalanan terpendek yang melalui sejumlah berhingga kota dengan syarat setiap kota hanya dikunjungi tepat satu kali dan perjalanan harus dimulai dan diakhiri pada kota yang sama. TSP dapat direpresentasikan dengan graf berbobot G = (V, E), dimana V adalah himpunan simpul yang menyatakan kota, E adalah himpunan busur yang menyatakan jalur penghubung antar kota, dan bobot tiap busur menyatakan jarak antar kota. TSP yang dibahas adalah TSP yang direpresentasikan dengan graf lengkap dan memenuhi ketaksamaan segitiga: untuk sembarang 2 simpul, bobot busur langsung lebih kecil dari total bobot melalui kota lain. Tiap busur pada graf TSP dapat diberikan nilai/label berupa bilangan bulat non negatif sedemikian sehingga untuk setiap simpul jumlah label busur-busur yang menempel pada simpul tersebut adalah sama, yaitu suatu konstanta k. Pemberian nilai seperti ini disebut sebagai pelabelan ajaib-k. Suatu graf berbobot dapat dilabel dengan banyak cara pelabelan ajaib-k. Skripsi ini membahas konstruksi batas bawah solusi optimal TSP yang memenuhi ketaksamaan segitiga menggunakan pelabelan ajaib. Pelabelan ajaib yang digunakan adalah pelabelan ajaib berkapasitas, yaitu kasus dimana diberikan batas atas label busur: r Î 6 - 2007).

Abstrak :
Traveling Salesman Problem (TSP) adalah masalah pencarian rute perjalanan dengan waktu tempuh perjalanan, biaya perjalanan, atau jarak tempuh perjalanan paling minimum. Pada skripsi ini, algoritma Random-key Cuckoo Search (RKCS) dengan 3-opt digunakan untuk menyelesaikan TSP. Algoritma Cuckoo Search (CS) didasarkan pada perilaku parasit burung cuckoo yang meletakkan telurnya di sarang burung lain (host nest) dengan tujuan telur burung cuckoo tersebut dierami dan ditetaskan oleh burung lain (host bird). Algoritma RKCS dengan 3-opt memuat Levy flights dan algoritma 3-opt. Levy flights digunakan dalam pembaruan bobot sedangkan algoritma 3-opt digunakan dalam perbaikan rute perjalanan. Berdasarkan hasil implementasi lima benchmark problems (eil51, berlin52, eil76, kroA100, dan eil101) yang diambil dari TSPLIB, penyelesaian TSP dengan algoritma RKCS dengan 3-opt menghasilkan solusi optimal berupa total jarak minimum yang sama dengan Best Known Solution (BKS). Total jarak minimum yang diperoleh tidak dipengaruhi oleh nilai parameter yang digunakan.

Abstrak :
Multiple Depot Multi Traveling Salesman Problem (MMTSP) merupakan bentuk umum dari masalah Traveling Salesman Problem (TSP), yaitu menentukan rute minimum dari perjalanan m salesman dengan n depot untuk menempuh semua kota dan kembali ke depot awalnya. Pada skripsi ini, dilakukan clustering pada kota-kota yang dilalui, sehingga pada setiap klaster masalah MMTSP dapat disederhanakan menjadi masalah MTSP Multiple Traveling Salesman Problem atau TSP. Algoritma clustering yang digunakan adalah Agglomerative Clustering dan K-Means Clustering. Selanjutnya dilakukan metode Ant Colony Optimization untuk mencari rute terpendek dari setiap klaster. Jumlah dari hasil rute terpendek dari setiap klaster merupakan solusi dari masalah MMTSP. Implementasi dilakukan dengan menggunakan sampel data TSPLIB, dan hasil yang didapat juga akan dibandingkan dengan penelitian yang telah dilakukan sebelumnya. Dari hasil simulasi, hasil algoritma Agglomerative Clustering ACO memberikan hasil yang terbaik dibandingkan algoritma K-Means Clustering ACO dan algoritma ACO saja.

---

Multiple Depot Multiple Traveling Salesman Problem MMTSP is a generalization of the common Traveling Salesman Problem TSP , whole purpose is to generate a minimum route of m traveling salesmen from n depots to explore all cities and back to their origins. In this skripsi, the cities will be clustered, so for every cluster, MMTSP will be simplified as MTSP Multiple Traveling Salesman Problem or TSP. The clustering algorithms that will be used are Agglomerative Clustering and K Means Clustering. Furthermore, for every cluster, the Ant Colony Optimization will be implemented to determine the shortest path. The distance of shortest path in every cluster will be summed as the solution of MMTSP. Implementation of the algorithm will be simulated by using the TSPLIB, and the solutions will be compared to previous research. The simulation results show that the Agglomerative clustering ACO is the best solution compared to the K Means ACO rsquo s and the only ACO algorithm.

Abstrak :
Multiple Traveling salesman problem MTSP merupakan perluasan dari TSP. MTSP adalah masalah optimasi dimana akan ditentukan total jarak minimum untuk m salesmen dalam melakukan perjalanan ke sejumlah kota tepat satu kali yang dimulai dari kota awal yang disebut depot kemudian kembali lagi ke depot setelah perjalanan selesai. Dalam tugas akhir ini, K-Means dan Crossover Ant Colony Optimization ACO akan digunakan untuk menyelesaikan MTSP. Implementasi dilakukan pada 3 data dari TSPLIB dengan menggunakan salesman berjumlah 2, 3, 4, dan 8. Analisa hasil dengan menggunakan K-Means dan Crossover ACO akan dibandingkan. Pengaruh terhadap pemilihan kota yang menjadi depot pada total jarak perjalanan yang dihasilkan, juga akan dianalisa.

---

Multiple Traveling Salesman Problem MTSP is a generalization of the Traveling Salesman Problem TSP . MTSP is an optimization problem to find the minimum total distance of m salesmen tours to visit several cities in which each city is only visited exactly by one salesman, starting from origin city called depot and return to depot after the tour is completed. In this skripsi, K Means and Crossover Ant Colony Optimization ACO are used to solve MTSP. The implementation is observed on three datasets from TSPLIB with 2, 3, 4, and 8 salesmen. Analysis of results using K Means and Crossover ACO will be compared. The effect of selecting a city as depot on the total travel distance of tour will also be analyzed.

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

Abstrak :
Density-Based Spatial Clustering of Application with Noise (DBSCAN) merupakan salah satu metode klastering berdasarkan kepadatan data yang menggunakan parameter radius jarak dari titik data tersebut dan jumlah minimal titik data untuk menghasilkan sebuah klaster. Traveling Salesman Problem (TSP) merupakan aplikasi dari optimasi yang menentukan sebuah rute yang diawali dan diakhiri di titik yang sama dengan hasil jarak paling minimum. Permasalahan konektivitas pelayaran perintis merupakan bagian yang sangat penting untuk menjaga agar daerah 3T (Terdepan, Terpencil, dan Tertinggal) terkoneksi. Wilayah Papua Barat memiliki moda transportasi yang terbatas dan Indeks Desa Membangun (IDM) yang paling rendah yaitu 0.5045 yang mengakibatkan tingginya angka desa 3T pada wilayah tersebut, untuk meningkatkan angka IDM di wilayah tersebut dibutuhkan moda transportasi yang dapat diakses secara rutin untuk merangsang perekonomian dan mobilitas penduduk. Penelitian ini bertujuan untuk mendapatkan rute pelayaran baru dengan meminimalkan jarak dan waktu tempuh. Dengan menggunakan DBSCAN dan TSP diperoleh 7 rute baru untuk 7 unit kapal perintis, dengan total jarak yaitu 3393 Nautical Miles dan rata-rata waktu pelayaran yaitu 3 hari, frekuensi kunjungan dapat dilakukan 4 kali dalam 12 hari pelayaran. ...... The Density-Based Spatial Clustering of Application with Noise (DBSCAN) is a clustering method based on data density that uses the radius parameter of the distance from the data point and the minimum number of data points to create a cluster. Traveling Salesman Problem (TSP) is an optimization application that determines a route that starts and ends at the same point with the minimum distance. The problem of pioneer ship connectivity is a very important for part of connecting the Isolated Places in Indonesia. The West Papua region is one of the regions in Indonesia that has limited transportation modes and the lowest Village Development Evaluation is 0.5045, Affecting the high number of underdeveloped villages in that region. Therefore, to increase the Village Development Evaluation number in West Papua, hence the underdeveloped villages can be accessed regularly to stimulate the economy and mobility. This research aims to obtain a new shipping route by minimizing the distance and travel time. By using DBSCAN and TSP, 7 new routes were obtained for 7 pioneer ships, with a total distance is 3393 Nautical Miles and an average voyage time are 3 days, the frequency of visits can be done 4 times in a 12-day cruise.

Abstrak :
Traveling salesman problem (TSP) adalah masalah membentuk sebuah rute perjalanan melewati sehimpunan berhingga kota (simpul) masing-masing tepat satu kali, berawal dan berakhir pada kota yang sama, dan jarak tempuh minimum. TSP euclidean adalah TSP dengan simpul berbentuk titik koordinat dan jarak antar simpul berupa jarak euclid antar titik koordinat. Hibrida algoritma genetik (GA) dan 2-opt local search (GA2-OPT) adalah metode heuristik yang diperoleh dengan cara mencangkokan 2-opt local search ke dalam GA sebagai operator mutasi. Untuk operator seleksi digunakan roulette wheel dan operator crossover digunakan edge recombination. Pada skripsi ini akan dilihat kinerja dari GA2-OPT dalam menyelesaikan TSP euclidean. Kinerja akan diukur berdasarkan kedekatan solusi yang diperoleh dengan Best Known Solution (BKS) dari masalah penguji yang diambil dari TSPLIB. Berdasarkan simulasi didapatkan hasil bahwa kinerja GA-2OPT cukup baik untuk menyelesaikan TSP dengan error relatif nilai fungsi tujuan solusi terbaik terhadap BKS kurang dari 1% untuk 6 dari 10 masalah penguji dan sisanya antara 1.4% - 4.5% dengan ukuran masalah antara 51 sampai 657 simpul.