Hasil Pencarian  ::  Simpan CSV :: Kembali

"Penjemputan dan Pengantaran Traveling Salesman Problem dengan aturan first-in-first-out (TSPPDF) merupakan suatu masalah pencarian rute untuk melayani sejumlah pelanggan dalam penjemputan dan sekaligus pengantaran dimana penjemputan dan pengantaran tersebut harus mengikuti aturan first-in-first-out (FIFO). Dimulai dari tempat asal (depot), mengunjungi semua tempat penjemputan dan tempat pengantaran, kemudian kembali ke tempat asal dengan total biaya atau jarak perjalanan minimal. Dalam tugas akhir ini, algoritma FIFO Nearest Neighbor (FNN) akan digunakan untuk menyelesaikan TSPPDF. Kemudian akan dibandingkan hasil penyelesaian TSPPDF yang menggunakan algoritma FNN dengan TSP solver. Setelah itu, hasil TSPPDF dari algoritma FNN akan dioptimalkan secara manual menggunakan algoritma Iterated Local Search (ILS).

---

The pickup and delivery traveling salesman problem with first-in-first-out (TSPPDF) is a routing problem to service n customers in the pickup and delivery which is the pickup and delivery operations must be executed in a first-in-first-out (FIFO). Starting from an origin vertex (depot), visiting all the pick-up and delivery, then returned to an origin vertex with minimum total cost or distance. In this undergraduate thesis, the FIFO Nearest Neighbor algorithm (FNN) will be used to solve TSPPDF. Then the results of TSPPDF which uses an FNN algorithm will be compared with TSP solver. After that, the results of the FNN algorithm will be optimized manually using the Iterated Local Search (ILS) algorithm."

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

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

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

"ABSTRACTPickup and Delivery Problem with Transfer (PDPT) dideskripsikan sebagai cara menemukan solusi optimal untuk menetapkan himpunan permintaan ke himpunan kendaraan (awalnya terletak pada beberapa depot), dengan meminimalkan fungsi objektif tertentu berdasarkan kendala yang telah ditetapkan. Transfer barang dilakukan untuk meminimalkan waktu tempuh kendaraan dengan cara memindahkan barang di titik transfer yang nantinya akan diangkut oleh kendaraan lain dengan waktu lebih singkat. Berdasarkan konsep tersebut, dibentuk formulasi PDPT dengan menambahkan secara sistematis variabel dan kendala yang direalisasikan secara dinamis selama penentuan solusi rencana. Dalam tulisan ini akan digunakan metode insertion heuristic untuk mendapatkan solusi optimal Dynamic Pickup and Delivery Problem with Transfer (D-PDPT). Solusi objektifnya adalah untuk meminimumkan waktu perjalanan kendaraan pada solusi rencana yang didapatkan di setiap perhitungan. Berdasarkan hasil eksperimen simulasi, diperoleh hasil bahwa D-PDPT dapat digunakan untuk mengoptimalkan sistem penjemputan dan pengantaran barang dengan penghematan waktu tempuh kendaraan sebesar 23%, dibandingkan dengan rute tanpa menggunakan titik transfer.

---

ABSTRACTPickup and Delivery Problem with Transfer (PDPT) is described as a way of finding the optimal solution for assigning a set of requests to a set of vehicles (initially located at several depots), by minimizing certain objective functions based on predetermined constraints. Transfer of goods is done to minimize vehicle travel time by moving goods at the point of transfer which will later be transported by other vehicles with shorter time. Based on the concept, a PDPT formulation is formed by systematically adding variables and constraints that are realized dynamically during the determination of the plan solution. n this paper we will use the Insertion Heuristic method to obtain the optimal solution of Dynamic Pickup and Delivery Problem with Transfer (D-PDPT). The objective solution is to minimize vehicle travel time in the plan solutions obtained in each calculation. Based on the results of the simulation experiments, the results show that D-PDPT can be used to optimize the pickup and delivery system with 23% vehicle travel time savings, compared to routes without using transfer points."

"Perkembangan e-commerce di Indonesia mengalami peningkatan yang sangat signifikan sehingga volume permintaan pelanggan akan pengiriman barang menjadi sangat besar. Hal tersebut menyebabkan efisiensi pengiriman barang dari pusat distribusi terdekat ke tujuan akhir (last mile delivery) menjadi tantangan bagi berbagai platform e-commerce. Salah satu solusi untuk meningkatkan efisiensi last mile delivery, yaitu Vehicle Routing Problem with Roaming Delivery Locations (VRPRDL). VRPRDL merupakan masalah optimasi penentuan rute kendaraan dalam pendistribusian barang ke sejumlah pelanggan yang memiliki lebih dari satu lokasi pengiriman. Pengiriman barang dapat dilakukan ke lokasi rumah pelanggan atau lokasi cadangan (roaming delivery). Metode Iterated Local Search (ILS) akan digunakan untuk menyelesaikan permasalah tersebut. Percobaan pada skripsi ini menggunakan 30 pelanggan dengan setiap pelanggan memiliki 2 lokasi pengiriman, yaitu lokasi rumah pelanggan dan lokasi cadangan. Hasil percobaan menunjukkan bahwa metode ILS dapat memperbaiki hasil himpunan rute pada solusi awal dengan meminimumkan total waktu perjalanan sekitar 32.28% untuk home delivery, 32.8% untuk roaming delivery, dan dapat mengurangi kendaraan yang beroperasi. Selain itu, hasil percobaan juga menunjukkan bahwa roaming delivery dapat menjadi salah satu alternatif pengiriman yang efektif dengan mengurangi biaya pengiriman sekitar 16.37% serta waktu tempuh dan jumlah kendaraan yang digunakan lebih kecil dibanding home delivery.

---

The development of e-commerce in Indonesia has experienced a very significant increase so that the volume of customer demand for shipping goods is very large. This makes the efficiency of delivering goods from the nearest distribution center to the final destination (last mile delivery) a challenge for various e-commerce platforms. One solution to improve last mile delivery efficiency is the Vehicle Routing Problem with Roaming Delivery Locations (VRPRDL). VRPRDL is an optimization problem for determining vehicle routes in the distribution of goods to customers who have more than one delivery location. Delivery of goods can be done to the customer's home location or a backup location (roaming delivery). The Iterated Local Search (ILS) method will be used to solve the problem. The experiment in this thesis uses 30 customers with each customer having 2 delivery locations, namely the customer's home location and the backup location. The experimental results show that the ILS method can improve the results of the route set in the initial solution by minimizing the total travel time of around 32.28% for home delivery, 32.8% for roaming delivery and can reduce operating vehicles. In addition, the experimental results also show that roaming delivery can be an effective delivery alternative by reducing shipping costs by around 16.37%, reduce the travel time and number of vehicles used is smaller than home delivery."

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

"Traveling salesman problem (TSP) merupakan permasalahan optimasi dimana seseorang akan melakukan perjalanan kesejumlah kota yangdimulai dari kota asal dengan mengunjungi semua kota tepat satu kali dan kembali ke kota asal dengan total biaya atau jarak perjalanannya yang minimal. Dalam tugas akhir ini, algoritma Genetic Ant Colony System (GACS) akan digunakan untuk menyelesaikan TSP. Kemudian akan dibandingkan hasil penyelesaian TSP yang menggunakan algoritma GACS dengan algoritma ACS.

---

Traveling Salesman Problem (TSP) is an optimization problem in which a person will travel to a number of cities, starting from origin city to visit every city exactly once and return to origin city with minimum total cost or distance. In this undergraduatethesis, GACS algorithm will be used to solveTSP. Then the results will be compare with ACS algorithm."

"Treveling salesman problem (TSP) adalah masalah mencari rute perjalanan melewati sejumlah berhingga tempat dengan syarat setiap tempathanya dikunjungi tepat satu kali dan perjalanan berawal dan berakhir di satu tempat. TSP berdasarkan kesimetrian terbagi menjadi TSP simetrik dan TSP asimetrik adalah TSP dimana bobot busur tidak bergantung pada arahan pembusuran ..."