Hasil Pencarian  ::  Simpan CSV :: Kembali

"Perluasan dari Traveling Salesman Problem (TSP) adalah Multiple Traveling Salesman Problem (MTSP), yaitu menentukan kumpulan rute oleh 𝑚 salesman yang berawal dan kembali ke kota asal (depot). Jika terdapat lebih dari satu depot dan salesman yang berawal dan kembali ke depot yang sama, maka permasalahan tersebut dinamakan Fixed Destination Multi-depot Multiple Traveling Salesman Problem (MMTSP). Pada makalah ini, MMTSP akan diselesaikan menggunakan algoritma Ant Colony Optimization (ACO). ACO adalah algoritma optimisasi metaheuristic yang terinspirasi oleh perilaku semut dalam mencari jalur terpendek dari sarang menuju sumber makanan.Dalam penyelesaian MMTSP, akan diamati dengan memerhatikan pemilihan kota yang berbeda sebagai depot dan tiga parameter MMTSP non-random, banyaknya salesman (𝑚), minimum banyaknya kota yang harus dikunjungi salesman (𝐾), dan maksimum banyaknya kota yang dapat dikunjungi salesman (𝐿). Implementasi dilakukan dengan mengambil empat data dari TSPLIB. Hasil implementasi menunjukkan bahwa pemilihan kota yang berbeda sebagai depot dan tiga parameter MMTSP, di mana 𝑚 adalah parameter yang paling esensial, mempengaruhi solusi.

---

An extension of Traveling Salesman Problem (TSP) is the Multiple Traveling Salesman Problem (MTSP) in which, determining set of routes by 𝑚 salesmen who all start from and return to a single home city (depot). If there is more than one depot and salesmen start from and return to the same depot, then the problem is called Fixed Destination Multi-depot Multiple Traveling Salesman Problem (MMTSP). In this paper, MMTSP will be solved using the Ant Colony Optimization (ACO) algorithm. ACO is a metaheuristic optimization algorithm which inspired by the behavior of ants in finding the shortest path from the nest to the food source.

In solving the MMTSP, the algorithm is observed with respect to different chosen cities as depots and non-randomly three parameters of MMTSP, the number of salesmen (𝑚), the minimum number of cities a salesman must visit (𝐾), and the maximum number of cities that a salesman can visit (𝐿). The implementation is observed with four dataset from TSPLIB. The results show that both the different chosen cities as depots and the three parameters of MMTSP, in which 𝑚 is the most essential parameter, affect the solution."

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

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

"Firefly Algorithm (FA) adalah teknik optimisasi yang terinspirasi dari alam yang awalnya dirancang untuk memecahkan masalah optimisasi fungsi kontinu. Ada beberapa pendekatan yang menggunakan FA sebagai dasar metode untuk memecahkan masalah optimisasi diskrit, khususnya Traveling Salesman Problem (TSP). Dalam tesis ini, skema gerakan baru yang disebut dengan edge-based movement diajukan. Edge-based movement adalah sebuah operator mutasi yang menjamin bahwa perubahan suatu kandidat solusi akan menyerupai dengan solusi kandidat yang diinginkan. Hal ini membuat algoritma lebih berperilaku seperti FA. Kinerja Evolutinary Discrete Firefly Algorithm di ujicoba saat menggunakan edge-based movement, dan membandingkan hasilnya dengan metode sebelumnya. Simulasi komputer menunjukkan bahwa skema gerakan baru ini menghasilkan akurasi yang sedikit lebih baik namun dengan rata-rata waktu yang lebih cepat dengan nilai rata-rata faktor speedup 14,06 kali.

---

The Firefly Algorithm (FA) is a nature-inspired technique originally designed for solving continuous optimization problems. There are several existing approaches that apply FA also as a basis for solving discrete optimization problems, in particu-lar the Traveling Salesman Problem (TSP). In this thesis, a new movement scheme called edge-based movement is proposed. Edge-based movement is an operation which guarantees that a candidate solution more closely resembles another one. This leads to a more FA-like behavior of the algorithm. The performance of the Evolutionary Discrete Firefly Algorithm is investigated when using this new edge-based movement, and compare it against previous methods. Computer simulations show that the new movement scheme produces slightly better accuracy with much faster average time. The average speedup factor is 14.06 time"

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

"Pengiriman barang merupakan salah satu kegiatan umum masyarakat yang semakin sering dilakukan akibat peningkatan pengguna sarana belanja dalam jaringan (daring). Peningkatan kegiatan belanja daring mengakibatkan permintaan terhadap jasa pengiriman barang juga mengalami peningkatan. Hal ini juga berdampak pada meningkatnya masalah pengiriman barang terkait masalah lingkungan seperti meningkatnya polusi udara dan juga efisiensi pengiriman barang. Oleh karena itu, dibutuhkan suatu solusi untuk mengatasi masalah lingkungan serta menambah efisiensi pengiriman barang di tahap terakhirnya. Penelitian ini berfokus pada tahap last-mile delivery, yaitu tahap barang dikirimkan dari depot terakhir ke lokasi pelanggan dengan memanfaatkan penggunaan truk pengiriman dan digabung dengan drone. Kombinasi truk dan drone dipandang sebagai solusi yang inovatif. Drone yang menggantikan pengiriman dengan kendaraan bermotor tidak menghasilkan polusi yang biasanya dihasilkan oleh kendaraan berbahan bakar minyak bumi. Kemacetan juga dapat dihindari oleh drone sehingga waktu pengiriman bisa dipersingkat. Drone dapat dengan mudah melakukan pengiriman ke tempat-tempat yang tidak bisa dijangkau oleh kendaraan pengirim barang seperti truk. Dibalik semua kelebihannya, drone memiliki beberapa kendala yaitu harganya yang mahal sehingga menimbulkan keterbatasan kesediaan drone dan juga keterbatasan jangkauan terbangnya. Metode clustering diperkenalkan untuk mengatasi batasan tersebut. Pada penelitian ini digunakan metode Hierarchical Agglomerative Clustering (HAC) dengan mempertimbangkan jumlah drone yang tersedia dan jangkauan terbang maksimum dari drone. Hasil pengelompokkan kemudian digunakan untuk mencari rute optimal dengan metode Tabu Search (TS). Kedua metode ini diimplementasikan pada data simulasi sebanyak 90 pelanggan. Biaya pengiriman yang terdiri dari biaya operasional drone, biaya operasional truk, biaya penggunaan drone serta biaya penggunaan truk akan diminimalkan. Hasil berupa biaya pengiriman, jarak tempuh serta waktu tempuh yang diperoleh dibandingkan dengan hasil dari clustering data berdasarkan jarak tanpa memaksimalkan penggunaan drone serta memperhatikan batasannya. Implementasi HAC dan TS memberikan hasil pengurangan waktu sekitar 45%, pengurangan jarak sekitar 70% dan pengurangan biaya pengiriman sekitar 9%.

---

Goods delivery is a common activity in the society, and it’s becoming more frequent with the existence of online shopping. The surge in online shopping has led to a heightened demand for delivery services. This increase in demand impacts environmental concerns such as escalating air pollution and the efficiency of parcel delivery. Consequently, there’s a need for a solution to address environmental issues and enhance the efficiency of last-mile delivery. This research focuses on the last-mile delivery stage, specifically the movement of goods from the final depot to the customer’s location, utilizing a combination of delivery trucks and drones. The integration of trucks and drones is seen as an innovative solution. Drones, replacing motor vehicles in delivery, reduce pollution typically generated by fossil fuel-powered vehicles. Additionally, drones can evade traffic congestion, shortening delivery times, and easily access locations inaccessible to trucks. However, despite their advantages, drones have constraints, including high costs leading to limited availability and flight range limitations. Clustering methods are introduced to address these constraints. This study employs the Hierarchical Agglomerative Clustering (HAC) method, considering the available number of drones and their maximum flight range. The resulting clusters are then utilized to determine the optimal routes using the Tabu Search (TS) method. Both of this method is implemented on a simulation data of 90 customers. Delivery cost that includes drone operational cost, truck operational cost, drone cost, and truck cost is minimized. The result (delivery cost, distance traveled, and duration) are compared to clustering based on distance only without maximized drones available or consider its constraints. The implementation of HAC and TS provides a reduction in time of around 45%, a distance reduction of about 70%, and a shipping cost reduction of about 9%."

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

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

"Banyaknya pulau di Indonesia menyebabkan adanya tantangan untuk menjaga konektivitas antar pulaunya, mendorong untuk dibutuhkannya moda transportasi agar meningkatkan konektivitas antar pulau khususnya di wilayah 3T. Di masa ini pelayaran perintis menjadi moda transportasi yang ditugaskan oleh pemerintah guna melayani daerah 3T. Namun, pada penerapannya pelayaran perintis masih dinilai kurang optimal sehingga perlu dilakukannya optimasi. Optimasi merupakan aktifitas yang bertujuan untuk mendapatkan nilai maksimal atau minimal berdasarkan fungsi dan tujuan yang ingin dicapai, dengan tetap memenuhi fungsi kendala yang berlaku. Optimasi dinilai penting untuk keberlanjutan akses transportasi laut khususnya pelayaran perintis di Sulawesi Selatan-Nusa Tenggara. Seluruh Pelabuhan yang dilayani trayek pelayaran perintis diklasterkan menggunakan metode Density Based Spatial Clustering of Applications with Noise (DBSCAN). Penelitian ini ditujukan untuk memberikan rekomendasi untuk optimasi rute pelayaran perintis. Terdapat 3 klaster yang terbentuk untuk menyesuaikan ketersediaan kapal perintis yang berjumlah 3 kapal. Masing-masing klaster dilakukan optimasi menggunakan Travelling Salesman Problem (TSP). Hasil optimasi didapatkan lebih optimal dengan total jarak tempuh rata-rata di ketiga klaster yang terbentuk sebesar 630 NM dibandingkan dengan rute eksisting sebesar 1211 NM dengan penurunan sebesar 48%

---

The large number of islands in Indonesia poses a challenge to maintain connectivity between islands, encouraging the need for modes of transportation to increase inter-island connectivity, especially in the 3T region. At this time perintis shipping became a mode of transportation assigned by the government to serve the 3T areas. However, in its implementation, perintis shipping is still considered less than optimal, so optimization is needed. Optimization is an activity that aims to get the maximum or minimum value based on the function and goals to be achieved, while still meeting the applicable constraints. Optimization is considered important for the sustainability of access to sea transportation, especially perintis shipping in South Sulawesi-Nusa Tenggara. All ports served by perintis shipping routes are clustered using the Density Based Spatial Clustering of Applications with Noise (DBSCAN) method. This research is intended to provide recommendations for optimizing perintis shipping routes. There are 3 clusters formed to adjust the availability of perintis ships, which total 3 ships. Each cluster is optimized using the Traveling Salesman Problem (TSP). Optimization results obtained are more optimal with the total average mileage in the three clusters formed of 630 NM compared to the existing route of 1211 NM with a decrease of 48%."