Hasil Pencarian  ::  Simpan CSV :: Kembali

"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."

"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."

"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."

"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."

"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."

"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."

"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."

"Traveling Salesman Problem (TSP) adalah masalah mencari jalur terpendek untuk mengunjungi setiap simpul tepat satu kali kecuali simpul awal kunjungan jika diberikan himpunan simpul yang harus dikunjungi. Tiga modifikasi dilakukan pada skripsi ini untuk menyelesaikan masalah TSP dengan menggabungkan metode Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO) dan 3-Opt Algorithm. ACO digunakan untuk mencari solusi TSP, PSO digunakan untuk mencari nilai paremeter terbaik 𝛼 dan 𝛽 yang digunakan pada ACO, dan 3-Opt digunakan untuk mengurangi total jarak tempuh solusi yang didapat dari ACO. Pada modifikasi pertama, 3-Opt digunakan untuk mengurangi total jarak tempuh dari solusi terbaik yang didapatkan setiap iterasi. Pada modifikasi kedua, 3-Opt digunakan untuk mengurangi total jarak tempuh seluruh solusi yang didapatkan pada setiap iterasi. Pada modifikasi ketiga, 3-Opt digunakan untuk mengurangi total jarak tempuh seluruh solusi yang berbeda yang didapatkan pada setiap iterasi.Hasil modifikasi diuji menggunakan 6 benchmark problems yang diambil dari TSPLIB dengan menghitung besarnya galat relatif terhadap best known solution dan running time percobaan. Setiap masalah diselesaikan dengan 10 kali percobaan, dengan masing-masing percobaan menggunakan 10 agen dan 50 iterasi. Hasil implementasi menunjukkan modifikasi pertama tidak memberikan hasil yang memuaskan, modifikasi kedua memberikan hasil yang memuaskan namun dengan running time yang cukup besar, serta modifikasi ketiga memberikan nilai galat yang tidak jauh berbeda dengan modifikasi kedua namun dengan running time yang jauh lebih kecil.

---

The Traveling Salesman Problem (TSP) is the problem of finding a shortest tour which visits all the vertices exactly once, except the first vertex, given a set of vertices. This thesis discusses three modification to solve TSP by combining Ant Colony Optimization (ACO), Particle Swarm Optimization (PSO) and 3-Opt Algorithm. ACO is used to find the solution of TSP, PSO is used to find the best value of parameters α and β that are used in ACO, and 3-Opt is used to reduce the total of tour length from the solution obtained by ACO. In the first modification, 3-Opt is used to reduce the total of tour length from the best solution obtained at each iteration. In the second modification, 3-Opt is used to reduce the total of tour length from the entire solutions obtained at each iteration. In the third modification, 3-Opt is used to reduce the total of tour length from different solutions obtained at each iteration.Results were tested using 6 benchmark problems taken from TSPLIB by calculating the relative error to the best known solution and the running time. Every problem was solved with 10 trials, where each trial uses 10 agents and 50 iterations. The implementation results showed the first modification did not provide satisfactory results, the second modification gave a satisfactory result, but the running time was quite large, and the third modification gave errors that were close to the second one but with smaller running time."

"Transportasi darat, khususnya truk, merupakan penyumbang utama biaya logistik secara keseluruhan, dibandingkan dengan kereta api dan udara. Untuk mengoptimalkan biaya logistik, kita perlu mengoptimalkan rute pengiriman. Namun, tantangan yang dihadapi adalah jumlah titik pengantaran juga berkembang dengan cepat seiring berkembangnya zaman, yang membuat banyak rute yang dapat dipilih untuk melakukan pengiriman dari depot ke tiap-tiap titik, sehingga meningkatkan kompleksitas untuk menemukan rute yang optimal. Masalah rute ini dapat didefinisikan sebagai VRP yang memiliki kendala kapasitas yaitu CVRP. Penelitian sebelumnya telah berhasil menyelesaikan CVRP skala besar dengan beberapa pendekatan algoritma. Dalam penelitian ini, penulis menggabungkan savings algorithm untuk meningkatkan solusi awal dengan Tabu Search yang sangat populer untuk menyelesaikan CVRP skala besar. Algoritma yang ditingkatkan ini diuji pada benchmark CVRP Arnold et al. [5] dan terbukti memiliki hasil yang cukup kompetitif dibandingkan dengan solusi terbaik yang diketahui.

---

Road transportation, particularly trucking, is the main contributor of logistic cost in total, compared to rail and air. To optimize the cost of road logistics, we need to optimize delivery routes. However, the challenges are that the number of delivery points are also growing rapidly, which makes many possible routes to deliver the package from the depot, and increasing the complexity to find the optimal one. This route problem could be defined as CVRP. Previous research has already proved to solve very large scale CVRP with several approaches to the algorithm. In this paper, we’re combining a Saving Algorithm to improve the initial solution and the very popular Tabu Search to solve very large scale CVRP. This improved algorithm is tested into Arnold et. al. [5] CVRP benchmark and proved to have competitive results compared to the best known solutions."

"Permasalahan transportasi dalam logistik untuk masa depan terus berkembang. Terutama di kota-kota yang terdapat pada negara berkembang, dimana pertumbuhan warung-warung atau disebut nanostores sangat pesat ditambah dengan perkembangan belanja online, menyebabkan jumlah pelanggan dalam industri pengiriman meningkat pesat. Dengan jumlah tujan pengiriman yang terus meningkat, muncul beberapa masalah dalam transportasi. Setiap pihak dalam sebuah sistem logistik memiliki tujuan umum yang sama yakni mengurangi biaya transportasi dan waktu pengiriman yang tepat. Dalam transportasi sendiri, ada banyak faktor yang mempengaruhi biayanya. Salah satu faktor yang sangat mempengaruhi biaya adalah jarak total yang dilalui untuk mencapai semua tujuan pengiriman. Total jarak itu sendiri bisa diubah dengan mengubah rute pengiriman. Dengan tujuan pengiriman yang semakin banyak, kombinasi rute yang memungkinkan juga akan semakin banyak. Ada satu permasalahan terkait pemilihan rute yang sering dibahas, yakni Vehicle Routing Problem. Penelitian ini akan membahas model untuk mendapatkan solusi optimal dari Vehicle Routing Problem khususnya jika jumlah pelanggan yang dilayani mendekati 40.000 pelanggan.

---

Transportation in logistics for the future is evolving. Especially in cities of developing countries which with the rapid growth of nanostores and online shopping, the number of customers in delivery services increased rapidly. With the number of destination keep increasing, emerges some problems in logistic transportation. Every member in logistic party have mutual goal to decrease the transportation costs and have the delivery on time.

In transportation itself, there are many factors that influence the costs. One factor that greatly influence the costs is total distance needed to cover all the destination target. Total distance itself can be manipulated by changing the route of the delivery. With more destination target, there will be also more combination of route. There is one popular problem that discussed about route selection, which is Vehicle Routing Problem. This paper will discuss the model to obtain the optimal solution of the Vehicle Routing Problem which will obtain the minimum total distance if the number of destination target is approaching 40.000 customers."