Tyas, Sasmi Hidayatul Yulianing (2019) Penyelesaian Permasalahan Vehicle Routing dengan Objektif Jamak yang Mempertimbangkan Keseimbangan Jarak Rute Kendaraan Menggunakan Metode Hiperheuristik. Masters thesis, Institut Teknologi Sepuluh Nopember.
Preview |
Text
05211650010021-Master_Thesis.pdf Download (16MB) | Preview |
Abstract
Vehicle Routing Problem (VRP) adalah salah satu permasalahan kombinatorik yang sulit dipecahkan. VRP bertujuan untuk menghasilkan serangkaian rute terpendek dari beberapa kendaraan berkapasitas sama untuk mengunjungi beberapa pelanggan dengan batas waktu tertentu. Sebagian besar penelitian VRP sebelumnya hanya meminimalkan jarak total sebagai objektif tunggal, tanpa mempertimbangkan keseimbangan jarak antar rute yang dihasilkan. Untuk ini diperlukan solusi terhadap permasalahan VRP yang mempertimbangkan faktor keseimbangan jarak antar rute selain batasan yang hanya melibatkan faktor minimalisasi total jarak rute.
Dalam penelitian ini dikembangkan algoritma hiperheuristik untuk menyelesaikan permasalahan VRP dengan objektif jamak, yaitu algoritma yang mengombinasikan objektif untuk meminimalkan total jarak rute dan objektif untuk menyeimbangkan jarak antar rute yang dihasilkan. Parameter keseimbangan antar jarak antar rute diukur menggunakan formulasi simpangan baku terhadap masing-masing rute yang dihasilkan. Metode pareto sorting digunakan untuk menghasilkan solusi yang efektif berdasarkan nilai kedua fungsi objektif, indikator jumlah solusi, serta nilai coverage dan nilai hypervolume dari solusi.
Algoritma hiperheuristik yang telah berhasil dikembangkan dalam penelitian ini diimplementasikan dengan menggunakan kerangka kerja HyFlex dan bahasa pemrograman Java. Uji coba hasil implementasi dilakukan menggunakan dua set data dengan kompleksitas yang berbeda, yaitu set data Solomon dan set data Gehring dan Homberger. Metode pemilihan low-level heuristic berbasis algoritma hill climbing hyperheuristic dipilih karena memberikan solusi yang lebih baik dibandingkan dengan algoritma great deluge hyperheuristic. Hasil uji coba perbandingan antara solusi VRP dengan objektif jamak dan solusi VRP dengan objektif tunggal menunjukkan bahwa rerata simpangan baku jarak antar rute untuk VRP dengan objektif jamak (sebesar 678) cukup jauh lebih rendah dibandingkan rerata simpangan baku antar rute VRP dengan objektif tunggal (sebesar 1.053), walaupun rerata total jarak minimum yang dihasilkan oleh VRP dengan objektif jamak (sebesar 99.590) relatif lebih besar dibandingkan dengan yang dihasilkan oleh VRP dengan objektif tunggal (sebesar 94.650). Hal ini menunjukkan bahwa tambahan fungsi objektif untuk menyeimbangkan jarak antar rute kendaraan dari solusi VRP yang dihasilkan sesuai dengan tujuan penelitian.
========================================================================================================================Vehicle Routing Problem (VRP) is one of the combinatoric problems hard to solve. VRP aims to generate a set of the shortest routes of vehicles with similar capacity to visit customers with certain time limit. Most previous VRP studies only minimized total distance as a single objective, regardless of the balance of route distances. Therefore, it required a solution to the VRP that considered the balance factor of distance between routes other than minimizing the total distance of the route.
In this study, hyper-heuristic algorithm was developed to solve VRP with multi-objective, an algorithm that combines objective function to minimize the total distance of the routes and objective function to balance of obtained route distances. The balance of route distances parameter was measured by standard deviation formulation of route distances. Pareto sorting method was used to generate effective solutions based on the value of the two objective functions, the number of solutions indicators, the coverage value and hypervolume value of the solutions.
The developed hyper-heuristic algorithm was implemented using HyFlex framework and Java programming. The experiments of implemented algorithm utilized two datasets with different complexity, Solomon dataset and Gehring and Homberger dataset. The low-level heuristic selection method based on the hill-climbing hyper-heuristic algorithm was chosen because it provided better solutions than the hyper-heuristic of great deluge algorithm. The comparison of multi-objective VRP solutions and single objective VRP solutions indicated that the average of standard deviation between routes of VRP with multi-objective (678) is considerably lower than the average of standard deviation between routes of VRP with single objective (1,053 ), even though the average of minimum total distance obtained by VRP with multi-objective (99,590) was relatively higher than the average of minimum total distance obtained by VRP with single objective (94,650). It showed that additional objective function for balancing vehicle route distances from obtained VRP solution corresponded to the research objectives.
| Item Type: | Thesis (Masters) |
|---|---|
| Uncontrolled Keywords: | vehicle routing problem, objektif jamak, hiperheuristik, rute terpendek, keseimbangan jarak antar rute, time windows, pareto sorting |
| Subjects: | T Technology > T Technology (General) > T57.5 Data Processing T Technology > T Technology (General) > T57.6 Operations research--Mathematics. Goal programming |
| Divisions: | Faculty of Information Technology > Information System > 59101-(S2) Master Thesis |
| Depositing User: | SASMI HIDAYATUL YULIANING TYAS |
| Date Deposited: | 14 Sep 2022 08:53 |
| Last Modified: | 14 Sep 2022 08:53 |
| URI: | http://repository.its.ac.id/id/eprint/68328 |
Actions (login required)
 |
View Item |