Perbandingan Algoritma Berbasis Metaheuristik Dalam Penyelesaian Vrp Untuk Bus Sekolah Listrik Di Kota Denpasar

Firdaus, Dhafin (2022) Perbandingan Algoritma Berbasis Metaheuristik Dalam Penyelesaian Vrp Untuk Bus Sekolah Listrik Di Kota Denpasar. Other thesis, Institut Teknologi Sepuluh Nopember.

Text 05211840000103-Undergraduate_Thesis.pdf Restricted to Repository staff only Download (4MB)

Abstract

Vehicle Routing Problem (VRP) adalah salah satu jenis kelas permasalahan optimasi kombinatorial yang kerap dijumpai, salah satunya dalam perencanaan rute transportasi umum di dalam sebuah wilayah.Dalam skala tertentu, permasalahan ini tidak dapat diselesaikan hanya dengan mengandalkan algoritma optimasi, sehingga seringkali VRP masuk ke dalam kategori permasalahan NP-hard (non-deterministic polynomial problem).Hal tersebut terjadi karena permasalahan NP-hard membutuhkan daya komputasi yang tinggi serta waktu yang lama apabila diselesaikan melalui algoritma optimasi.Maka dari itu, VRP menjadi sulit jika diselesaikan dengan metode sederhana dan konvensional.Penelitian-penelitian terdahulu telah dilakukan dengan tujuan mencari algoritma yang mampu memberikan hasil terbaik untuk menyelesaikan VRP.Salah satu jenis metode yang dipilih dalam algoritma penyelesaian VRP adalah metode metaheuristik, yaitu metode yang didesain untuk mencari, menghasilkan, atau memilih heuristik yang mungkin bisa menyediakan solusi mendekati optimal untuk permasalahan optimasi, terutama dengan informasi yang terbatas atau kapasitas komputasi yang terbatas.Pada pengerjaan tugas akhir ini digunakan dua algoritma metaheuristik yaitu Simulated Annealing dan Ant Colony Optimization untuk menentukan solusi dari VRP.Hasil dari kedua algoritma metaheuristik tersebut kemudian dibandingkan untuk menentukan algoritma yang lebih baik dalam menyelesaikan permasalahan VRP.Hasil dari uji coba algoritma Simulated Annealing dan Ant Colony Optimization pada dataset terminal bus sekolah Denpasar menunjukan bahwa dengan rata-rata waktu komputasi sekitar 5 detik, Ant Colony Optimization memiliki rata-rata hasil 42,3% lebih kecil dari rata-rata hasil Simulated Annealing.Selain itu, Ant Colony Optimization juga memberikan hasil yang lebih stabil dalam setiap pengulangannya.Hasil yang serupa juga terlihat dengan rata-rata waktu komputasi sekitar 280 detik, dimana Ant Colony Optimization mendapatkan rata-rata hasil 0,8556, lebih kecil 34,3% dari rata-rata hasil Simulated Annealing sebesar 1,3022.Jika dibandingkan dengan rute eksisting, Ant Colony Optimization mampu menghasilkan hasil yang lebih kecil walau tidak signifikan sebesar 0,4 kilometer, sedangkan hasil dari Simulated Annealing lebih panjang 53,6 kilometer dari rute eksisting.
==============================================================================================================================
Vehicle Routing Problem (VRP) is one type of combinatorial optimization problem class that is often encountered, one of which is in planning public transportation routes in an area.On a certain scale, this problem cannot be solved solely by relying on optimization algorithms, so VRP often falls into the category of NP-hard problems (non-deterministic polynomial problems).This happens because NP-hard problems require high computational power and take a long time to be solved through optimization algorithms.Therefore, VRP becomes difficult if solved by simple and conventional methods.Previous studies have been carried out with the aim of finding an algorithm that is able to provide the best results for solving VRP.One type of method chosen in the VRP solution algorithm is the metaheuristic method, which is a method designed to find, generate, or select heuristics that might provide near-optimal solutions to optimization problems, especially with limited information or limited computational capacity.In this final project, two metaheuristic algorithms are used, namely Simulated Annealing and Ant Colony Optimization to determine the solution of VRP.The results of the two metaheuristic algorithms are then compared to determine which algorithm is better in solving VRP problems.The results of the trial of the Simulated Annealing and Ant Colony Optimization algorithms on the Denpasar school bus terminal dataset show that with an average computation time of about 5 seconds, Ant Colony Optimization has an average yield of 42.3% smaller than the average Simulated Annealing result.In addition, Ant Colony Optimization also provides more stable results in each iteration.Similar result is also seen with the average computation time of about 280 seconds, where Ant Colony Optimization got an average result of 0.8556, 34.3% smaller than the average Simulated Annealing result of 1.3022.

Item Type:	Thesis (Other)
Additional Information:	RSSI 005.1 Fir p-1 2022
Uncontrolled Keywords:	VRP. Metaheuristics. Simulated Annealing. Ant Colony Optimization. VRP. Metaheuristics. Simulated Annealing. Ant Colony Optimization.
Subjects:	H Social Sciences > HD Industries. Land use. Labor > HD30.213 Management information systems. Dashboards. Enterprise resource planning.
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Information System > 57201-(S1) Undergraduate Thesis
Depositing User:	Mr. Marsudiyana -
Date Deposited:	04 Jun 2026 03:00
Last Modified:	04 Jun 2026 03:00
URI:	http://repository.its.ac.id/id/eprint/133552

Actions (login required)

View Item