Hasil Pencarian  ::  Simpan CSV :: Kembali

"ABSTRAKRobust Knapsack Problem (RKP) adalah variasi dari masalah Knapsack, dimana dalam hal ini bobot dari setiap item belum diketahui secara pasti, dan hanya diketahui terletak dalam sebuah interval tentu. Pada RKP akan dicari solusi optimal yang merupakan keuntungan optimal yang akan didapatkan, dan item-item mana saja yang diletakkan ke dalam Knapsack sehingga menghasilkan solusi optimal. Terdapat dua metode alternatif yang akan dijelaskan untuk mencari solusi optimal pada RKP, yang kemudian dibandingkan efisiensi dari kedua metode tersebut dengan dilihat dari running time masing-masing metode. Sedangkan untuk mencari himpunan item-item yang menghasilkan solusi optimal pada RKP akan digunakan metode partisi rekursif, dimana ide awalnya adalah dengan mempartisi himpunan item menjadi dua subhimpunan item.

---

ABSTRACTRobust Knapsack Problem (RKP) is a variation of the Knapsack Problem, where in this case the weight of each item is not exactly known in advance, but belongs to a given interval. On RKP, it will be sought optimal solution, which is the optimal benefit to be gained, and set of items placed into the Knapsack. There are two methods that will be discussed to find optimal solution in RKP, and then the efficiency of the two alternative methods will be compared with their running time. Whereas, to search the set of items that build optimal solutions in the RKP will be used recursive partitioning method. The main idea of this method is dividing the set of items into two subsets of items."

"Knapsack Problem (KP) merupakan masalah optimisasi dalam menentukan objekdari sekumpulan objek yang memiliki nilai dan bobot yang akan ditempatkan ke dalam media penyimpanan dengan tujuan memaksimumkan nilai barang dengan syarat kapasitas bobot media penyimpanan terbatas. Dalam tugas akhir ini, akan dibahas {0-1} Knapsack Problem ({0-1} KP) yang direpresentasikan dalam bentuk graf berarah. Setelah direpresentasikan dalam bentuk graf berarah, kemudian dilakukan transformasi pada nilai busur pada graf berarah tersebut dan dicari lintasan terpendek antar dua node. Untuk mencari lintasan terpendek, digunakan Algoritma Amoeboid Organism dengan inputnya adalah matriks adjacency dari graf berarah yang telah ditransformasi nilai busurnya dan matriks konduktivitas. Output dari algoritma ini adalah menghasilkan matriks konduktivitas yang elemen-elemennya bernilai mendekati 0 atau 1. Entri yang bernilai mendekati 1 merepresentasikan lintasan terpendek pada graf. Lintasan terpendek yang diperoleh akan menjadi solusi yang optimal pada {0-1} KP.

---

Knapsack Problem (KP) is optimization problem to choose object from set of objects which have profit and weight and the object will be placed in limited storage with total of profit is maksimum. First, will be explained about representing {0-1} Knapsack Problem ({0-1} KP)to directed graph. After {0-1} KP is represented in directed graph, so transforming value of edge on directed graph and dicari lintasan terpendek antar dua node. To search shortest path, use Amoeboid Organism Algorithm with adjacency matrices from directed graph and conductivity matrices as input. Output from this algorithm is produce conductivity matrices with element which have value approach 0 and . Element which have value approach 1 represent shortest path on graph. Shortest path on graph is optimal solution in {0-1} KP."

"Knapsack Problem KP adalah masalah penempatan item barang ke dalam suatu tempat biasa disebut Knapsack yang mempunyai kapasitas tertentu dimana setiap item memiliki berat dan nilai sehingga total berat dari item item yang ditempatkan tidak melebihi kapasitas Knapsack dan nilai yang didapatkan maksimum 0 1 Knapsack Problem 0 1 KP adalah kasus khusus dari KP dimana setiap item hanya tersedia 1 unit sehingga keputusannya adalah untuk memasukkan item tersebut ke dalam Knapsack atau tidak Algoritma Soccer League Competition SLC akan digunakan untuk menyelesaikan 0 1 KP yang ide dasarnya berasal dari kompetisi yang terjadi di liga sepak bola Penyelesaian 0 1 KP menggunakan algoritma SLC ini kemudian akan disimulasikan pada 10 permasalahan 0 1 KP dengan menggunakan perangkat lunak pada komputer Lalu hasilnya akan dibandingkan dengan solusi yang diperoleh dari algoritma NGHS.

---

Knapsack Problem KP is an optimization problem to placed some item into a place called Knapsack that have certain capacity which each item has a weight and a value so that the total weight of the chosen items does not exceed the capacity of knapsack and the total value is as large as possible 0 1 Knapsack Problem 0 1 KP is a case of KP which is only one unit available for each item so that the decision is to put these items to knapsack or not Soccer League Competition algorithm will be used to solving 0 1 KP The basic idea of SLC algorithm is from the competition that happen on a soccer league Then SLC algorithm will be simulated on 10 solved 0 1 KP problem with software on computer to solve 0 1 KP and will be compared with solutions from NGHS."

"Discounted {0-1} Knapsack Problem (DKP) adalah perluasan dari {0-1} Knapsack Problem (KP). Pada DKP akan dipilih sebuah himpunan kelompok-kelompok barang, dimana setiap kelompok terdiri dari tiga barang dan paling banyak satu dari tiga barang dapat dipilih. Barang ketiga dalam setiap kelompok merupakan gabungan dari barang pertama dan barang kedua. Dengan menggunakan konsep inti alternatif, DKP dapat dipartisi ke dalam beberapa submasalah berdasarkan tipe-tipe kasusnya (tidak berkorelasi, berkorelasi lemah, dan berkorelasi kuat). DKP yang telah dipartisi ini disebut partitioned DKP. Jika kasus dari DKP diketahui berkorelasi lemah atau berkorelasi kuat, maka dapat dilakukan partisi lebih lanjut lagi untuk memperbaiki efisiensi solusinya. Baik DKP maupun partitioned DKP dapat diselesaikan dengan menggunakan pemrograman dinamik. Berdasarkan percobaan numerik, penyelesaian partitioned DKP lebih efisien daripada penyelesaian DKP untuk semua kasus DKP, dengan tingkat efisiensi sekitar 11,79% untuk kasus tidak berkorelasi, 30,28% untuk kasus berkorelasi lemah, dan 41,84% untuk kasus berkorelasi kuat.

---

The Discounted {0-1} Knapsack Problem (DKP) is an extension of the {0-1} Knapsack Problem (KP). On DKP, it will be selected a set of item groups where each group consists of three items, and at most one of the three items can be selected. The third item in each groups is a combination of first item and second item. By using concept of alternative core, DKP can be partitioned to some sub problems based on types of DKP instances (uncorrelated, weakly correlated and strongly correlated).

If DKP is known as weakly correlated or strongly correlated, so it could be more partitioned for improving the solution efficiency. DKP and partitioned DKP could be solved by dynamic programming. Based on numerical experiments, solving partitioned DKP are more efficient than solving DKP for all cases of DKP, with efficiency level about 11.79% for uncorrelated instances, 30.28% for weakly correlated instances, and 41.84% for strongly correlated instances."

"Aircraft landing problem (ALP) merupakan suatu permasalahan pesawat terbang dalam menemukan jadwal yang optimal untuk pendaratan pesawat terbang. Objektivitas dari ALP adalah meminimumkan total biaya pinalti dari pesawat pada single runway maupun multiple runway. Dalam permasalahan ini terdapat beberapa hal penting yang harus dipertimbangkan yaitu kepentingan pemisahan waktu antara pesawat terbang dan interval waktu (time window) yang harus diperhatikan demi kepentingan keselamatan penumpang. Pertama, akan diberikan pemodelan matematis dari ALP dengan fungsi objektif yang linear. Kedua, akan digunakan pendekatan solusi heuristik yaitu Algoritma Ant Colony Optimization (ACO) dalam mencari solusi ALP yang optimal.

---

Aircraft landing problem (ALP) describes the aircraft problem of finding an optimal schedule of aircrafts landing. The objective of ALP is to minimize total penalty restrictive cost of aircraft in a single runway or multiple runways. This problem considers few certain constraints, such as the necessary separation time between aircrafts and time window that should be concerned for passenger safety. In the first part, will be presented a mathematical formulation of the problem with linear objective function. The second part is heuristic solution approaches with Ant Colony Optimization Algorithm to solve ALP."

"Hazardous material (hazmat) merupakan material yang berpotensi membahayakan manusia, infrastruktur dan lingkungan (US DOT, 2004). Karena berpotensi membahayakan, maka pada pengangkutan hazmat perlu memperhatikan risiko yang mungkin timbul (baik risiko jiwa maupun harta benda) selain mempertimbangkan faktor biaya, sehingga permasalahan pengangkutan hazmat termasuk ke dalam permasalahan multi obyektif.Salah satu cara untuk menangani permasalahan multi obyektif adalah dengan menerapkan konsep optimasi Pareto, yaitu konsep yang mengatakan bahwa suatu solusi dikatakan optimal jika tidak mungkin lagi meningkatkan suatu nilai fungsi tujuan tanpa mengurangi nilai fungsi tujuan yang lain. Konsep tersebut bekerja untuk menemukan himpunan solusi non-dominated dengan menerapkan aturan dominan pareto (pareto dominance rule).Pada skripsi ini akan dibahas masalah pemilihan rute kendaraan untuk mengangkut hazmat dengan memperhatikan waktu pelayanan (time windows) yang telah ditentukan yang dimodelkan ke dalam Hazmat Vehicle Routing Problem with Time windows (HVRPTW). Rute yang terpilih merupakan jalur non dominated, yaitu jalur dengan tingkat risiko dan biaya perjalanan yang paling kecil. Untuk memilih rute tersebut digunakan metode Multi-Objective Ant Colony System yang merupakan pengembangan dari metode Ant Colony System, yaitu metode yang mengadaptasi perilaku semut dalam mencari makanan dengan bantuan pheromone (zat kimia aromatik yang dikeluarkan oleh spesies semut).

---

Hazardous materials (hazmat) is defined by any substance or material which capable of causing harm to human, property and environment (US DOT, 2004). Therefore, in every hazmat transportation needs to pay attention to possible risks (both life and property risk) in addition to considering the cost factor. So that the problem of transporting hazmat belongs to the multi-objective problems.

The best approach to deal with multi objective problem is to apply the concept of Pareto optimization. This concept declare that an optimal solution is if there is no possibility to increase the value of objective function without eliminate the value of others objective function. This concept works to determine a set of non-dominated solutions applying conditions of Pareto dominance.

This research discuss about the problem of route selection of vehicles for transporting hazmat with focusing on service time (time windows) that has been determined and known as Hazmat Vehicle Routing Problem with Time Windows (HVRPTW). A non-dominated paths as selected path is the path with the smallest amount of risk and scheduled time. The route is selected by using Multi-Objective Ant Colony System algorithm which is the development of Ant Colony System methods that belongs to Ant Colony Optimization. This method adapts the behavior of ants in looking for feed helped by a pheromone (a chemical released by the aromatic species of ants)."

"Dynamic Dial a Ride Problem with Time Windows (DDARPTW) merupakan masalah pencarian rute optimal untuk melayani sejumlah pelanggan yang ingin dijemput di suatu tempat dan diantar ke tempat lainnya dengan data permintaan penumpang yang dapat bertambah selama periode perjalanan. Solusi yang ingin didapatkan adalah suatu rute dengan tingkat ketidakpuasan pelanggan yang minimum. Tugas akhir ini membahas penggunaan algoritma 2 tahap pada DDARPTW serta implementasinya pada data sebanyak 56 pelanggan dengan menggunakan perangkat lunak. Penentuan solusi awal pada tugas akhir ini menggunakan metode insertion heuristic dan tahap pertama menggunakan metode local search yaitu 2-opt arc swap untuk memberikan perbaikan pada nilai fungsi tujuan serta tahap kedua menggunakan metode simple insertion untuk melakukan penambahan pelanggan baru dalam periode perjalanan.

---

Dynamic Dial a Ride Problem with Time Windows (DDARPTW) is a problem of finding an optimal route to serve a number of customers who want to be picked up in a certaint place and delivered to other place. Data of passenger's demand could be added during the trip period. The obtained solution is a route with minimum level of customer dissatisfaction.

This mini thesis explores the use of two phase algorithm and its implementation on the data of 56 customers using a software. The initial solution is constructed by insertion heuristic method and the first phase use 2-opt arc swap local search which provides improvements to the value of the objective function and the second phase uses a simple insertion method to add new customer in the trip period."

"Masalah jalur terpendek berkembang dengan adanya masalah baru dalam konteks Alternate Routing, yaitu pencarian jalur terpendek ke-2, ke-3, dan seterusnya. Bentuk umum dari masalah Alternate Routing tersebut adalah The K-th Shortest Path Problem, dengan salah satu algoritma yang dapat menyelesaikannya adalah Algoritma Yen. Algoritma Yen dijamin dapat menyelesaikan masalah tersebut dengan menggunakan prinsip bahwa jalur terpendek ke-K merupakan deviasi dari jalur terpendek ke-J, untuk J