Hasil Pencarian  ::  Simpan CSV :: Kembali

"Imagine Cup adalah kompetisi di bidang teknologi yang menantang para pelajar dan mahasiswa di seluruh dunia untuk memecahkan suatu permasalahan. Kompetisi ini diselenggarakan setiap tahun dan telah dimulai sejak tahun 2002. Kompetisi ini telah diikuti oleh lebih dari 100 negara, termasuk Indonesia. Project Hoshimi adalah salahsatu dari 9 kategori yang diperlombakan dalam Imagine Cup sejak tahun 2005.Pada Project Hoshimi 2007 terdapat beberapa jenis permasalahan yang harus diselesaikan. Salah satu permasalahan yang penulis kerjakan sebagai Tugas Akhir adalah Unique Navigation Objective, dimana peserta akan diberikan koordinat titik-titik yang tersebar pada jaringan untuk dikunjungi satu per satu oleh sebuah objek bergerak yang disebut nanobot. Penyelesaian dari permasalahan ini adalah mengunjungi setiap titik navigasi yang tersebar satu per satu dalam batasan waktu tertentu.Unique Navigation Objective adalah model permasalahan yang hampir dapat digolongkan sebagai Travelling Salesman Problem. Hanya saja pada permasalahan ini, biaya yang dikenakan untuk mengadakan perjalanan dari masing-masing titik ke titik lainnya belum diketahui. Untuk itu, diperlukan metode untuk mencari jalur terdekatantara 2 titik pada sebuah peta. Sehingga setelah diketahui setiap jarak antara 2 titik pada Unique Navigation Objective, maka model permasalahan Travelling Salesman Problem dari Unique Navigation Objective telah didapatkan. Pada penelitian ini, penulis mengimplementasikan algoritma A* untuk mencari jalur terdekat antara 2 buah titik yang dapat ditempuh oleh objek nanobot. Sedangkan untuk mencari solusi Travelling Salesman Problem dari Unique Navigation Objective, penulis mengimplementasikan Genetic Algorithm. Landasan teori selengkapnya mengenai algoritma A* dan Genetic Algorithm dijelaskan pada Bab II."

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

"Self-Organizing Map (SOM) yang dikenal juga dengan Kohonen Feature map merupakan algoritme Jaringan Saraf Tiruan yang merepresentasikan arsitektur Topological Preserving Map. Algoritma tersebut menggunakan pembelajaran dengan metode unsuperised learning. Dari sisi topologi jika terdapat sekumpulan data yang dimasukkan ke dalam SOM maka akan terbentuk kumpulan neuron yang merupakan representasi dari data tersebut. Dan ketika memasuki proses learning, neuron neuron tersebut dengan sendirinya akan menempati tempatnya masing-masing secara statistik dan topologis.Dengan kata lain pada setiap iterasi dicari strategi dengan memanfaatkan dua buah informasi yaitu informasi lokal dalam point yang direperesentasikan dan juga informasi global dari keseluruhan data dalam himpunan point tersebut. Penerapan metode yang menggunakan informasi statistik tersebut menjadi dasar pembentukan algoritma pembelajaran yang disebut Kohonen Network Incorporating Explixci Statistics (KNIES).Uji coba terhadap kinerja algoritma KNIES dilakukan pada permasalahan Travelling Salesman Problem (TSP). Kumpulan kasus-kasus TSP disediakan dalam pustaka yang disebut TSPLIB. Dalam TSPLIB juga disertakan hasil optimum tour yang dilakukan oleh algoritma eksak.Dari kumpulan kota tersebut diujikan pada perangkat lunak KIES dengan radius 0.5 diperoleh hasil terburuk adalah (9.70%) didapatkan oleh Pcb442 . Sedangkan hasil rata-rata adalah 3.85%."

"ABSTRAKPeningkatan jumlah penduduk di Kota Depok diikuti dengan peningkatan jumlah timbulan sampah. Hal ini perlu diimbangi dengan penyediaan kendaraan pengumpulan sampah yang memadai agar sampah terkumpul secara keseluruhan. Kawasan perumahan Pesona Khayangan merupakan salah satu kawasan di Kota Depok yang mendapatkan pelayanan pengumpulan sampah secara door to door.Keterbatasan jumlah kendaraan pengumpul sampah dan rute pengumpulan sampah yang kurang efisien menyebabkan adanya penumpukan sampah. Penelitian ini bertujuan untuk menentukan rute pengumpulan sampah yang optimal dari segi biaya dan waktu. Penelitian ini menggunakan metode penyelesaian permasalahan arus jaringan, yaitu Travelling Salesman Problem yang akan menghasilkan rute pengumpulan sampah dengan cara meminimalkan waktu tempuh. Hasil analisis menunjukkan bahwa terdapat penghematan waktu dan jarak pada rute baru yang dihasilkan dari metode ini. Rute pada cluster pertama menghemat 67,4 menit dan 1,3 km; cluster kedua 50,2 menit dan 0,9 km; serta cluster ketiga 55,7 menit dan 1,9 km. Sementara itu, dalam hal penghematan biaya hasil analisis menunjukkan bahwa terdapat penghematan penggunaan bahan bakar sebesar Rp 1.192,- per hari untuk rute cluster 1; Rp 825,- per hari untuk rute cluster 2; dan Rp 1.742,- per hari untuk rute cluster 3.

---

ABSTRACTThe population in Depok is growing in line with the growth of garbage produced. This issue should be balanced with the availability of proper waste management facility to finally overcome the garbage problem, such as providing waste collection vehicle. Pesona Khayangan residence is one of the area in Depok which receives waste collection door-to-door service.The limited number and the covering area of waste collection vehicle makes it inefficient to reduce the mounting garbage. This research was conducted to determine the most optimal route for waste collection that is efficient in time and cost. Method used in this project is the problem solving of Travelling Salesman Problem that will result the route for waste collection by minimize the time used in the process. The result of analysis shows that there is time and distance efficiency on the new route found. The route of the first cluster has saved 67.4 minutes and 1.3 km; the second cluster has successfully saved 50.2 minutes and 0.9 km; and the third cluster has saved 55.7 minutes and 1.9 km. Meanwhile, the analysis also shows the cost efficiency in using fuel has saved IDR 1,192 per day by using the first cluster; IDR 825 per day for the second cluster; and IDR 1,742 per day for the third cluster."

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

"Sejalan dengan meningkatnya popularitas kapal pesiar dalam beberapa waktu terakhir, beberapa rute baru telah dikembangkan demi menggaet ceruk pasar yang lebih luas dan lebih masif. Walaupun dalam 3 tahun ke belakang industri tersebut terdampak pandemi, namun menurut data, di seluruh dunia, industri kapal pesiar memiliki tingkat pertumbuhan tahunan penumpang sebesar 6,6% dari 1990-2019. Menyikapi hal ini, beberapa perusahaan pelayaran kapal pesiar gencar membuat dan melakukan kajian untuk membuat rute baru. Kebijakan ini juga merupakan salah satu cara perusahaan memanfaatkan kondisi pasar yang mulai berangsur membaik pasca pandemi. Sampai saat ini sudah ada total 8 armada kapal pesiar baru dari MSC Cruises yang akan dibangun dan siap berlayar di tahun 2023-2028. Namun nyatanya beberapa rute baru hanya menggunakan diversifikasi pelabuhan singgah dan destinasi di berbagai pelabuhan sebagai variabel. Maka dari itu, pemilihan rute merupakan hal yang krusial untuk dapat mengurangi biaya operasional yang tinggi, meminimalisir jarak tempuh serta konsumsi bahan bakar demi mengurangi jejak karbon dan polusi udara. Penelitian ini mengimplementasikan metode optimasi dengan menggunakan Travelling Salesman Problem, dengan algoritma Hamiltonian cycle. Dengan algoritma tersebut, harapannya dapat ditemukan jalur antar pelabuhan dari setiap trayek round-trip dari kapal MSC Cruises yang paling pendek dalam segi jarak. Penelitian ini bertujuan untuk menguji apakah trayek yang sudah ditentukan merupakan jalur paling pendek. Pada penelitian dengan judul Optimasi Pemilihan Rute Pelayaran round-trip Kapal Pesiar MSC Cruises menggunakan Hamiltonian Cycle, ditemukan adanya perbedaan jarak yang lebih dekat sehingga menghasilkan rute pelayaran round-trip yang efisien dan lebih hemat biaya.

---

With the increasing popularity of cruise ships in recent times, several new routes have been developed to capture a wider and more massive market niche. Even though in the past 2 years the industry has been affected by a pandemic, according to data, worldwide, the cruise ship industry has had an annual passenger growth rate of 6.6% from 1990-2019. In response to this, several cruise ship shipping companies are intensively making and carrying out studies to create a new route. This policy is also one way for the company to take advantage of market conditions which are starting to improve gradually after the pandemic. Until now, there are a total of 8 new cruise ships from MSC Cruises that will be built and ready to sail in 2023-2028. However, in fact, several new routes only use the diversification of transit ports and destinations at various ports as variables. Therefore, route selection is crucial to reduce high operational costs and minimize mileage and fuel consumption to reduce carbon footprint and air pollution. This study implements the optimisation method using the Traveling Salesman Problem, with the Hamiltonian cycle algorithm. With this algorithm, the hope is to find the shortest route between ports from each round-trip route for MSC Cruises in terms of distance. This study aims to test whether the route that has been determined is the shortest path. In a study entitled Optimizing the Selection of Round-trip Cruise Routes for MSC Cruises using the Hamiltonian Cycle to find a difference in closer distances resulting in an efficient and more cost-effective round-trip shipping route."

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