Perbandingan Algoritma Ant Colony Optimization dan Large Neighborhood Search dalam Penyelesaian Cvrp dengan Rute Jalan Nyata di Kota Pontianak
Karpus, Pistu Suaha (2025) Perbandingan Algoritma Ant Colony Optimization dan Large Neighborhood Search dalam Penyelesaian Cvrp dengan Rute Jalan Nyata di Kota Pontianak. Skripsi thesis, Universitas Tanjungpura.
|
PDF (Cover-Bab1)
Cover-Bab1_D1061201028.pdf - Published Version Download (1MB) |
|
|
PDF (D1061201028_KARPUS_PISTU_SUAHA)
D1061201028_KARPUS_PISTU_SUAHA.pdf - Accepted Version Restricted to Repository staff only Download (4MB) |
Abstract
Penelitian ini bertujuan untuk mengevaluasi kinerja algoritma Ant Colony Optimization (ACO) dan Large Neighborhood Search (LNS) dalam menyelesaikan masalah Capacitated Vehicle Routing Problem (CVRP) pada rute jalan nyata di Kota Pontianak. Selain itu, juga bertujuan untuk membandingkan efektivitas dan efisiensi kedua algoritma tersebut, mengingat masih sangat terbatasnya penelitian yang secara langsung membandingkan kinerja antara kedua algoritma. Kota Pontianak, dengan jaringan jalan yang kompleks dan kondisi jalan yang beragam, menyediakan kasus uji yang ideal untuk mengevaluasi kinerja kedua algoritma. Tantangan utama yang dihadapi adalah menentukan rute pengiriman optimal, yang melibatkan pemilihan jalur paling efisien bagi kendaraan untuk mencapai berbagai lokasi dengan jarak terpendek, sambil tetap mematuhi batasan kapasitas angkut kendaraan. Permasalahan menjadi lebih kompleks ketika dihadapkan dengan peta jalan realistis. Jarak Euclidean mungkin tidak mencerminkan jarak sebenarnya yang ditempuh di jalan, karena jalan tidak selalu berupa garis lurus dan dipengaruhi oleh jaringan jalan serta hambatan fisik seperti bangunan, sungai, atau area yang tidak dapat dilalui. Penelitian ini dilakukan guna memperoleh solusi optimal dalam perencanaan rute distribusi menggunakan algoritma ACO dan LNS yang diimplementasikan dalam bahasa pemrograman JavaScript dan divisualisasikan secara interaktif melalui OpenStreetMaps dengan HTML dan CSS. Ant Colony Optimization (ACO) bekerja dengan cara meniru perilaku semut yang menggunakan jejak feromon untuk menemukan jalur terpendek. Semut buatan menjelajahi jalur secara acak dan cenderung memilih rute dengan feromon lebih tinggi. Jejak feromon pada jalur yang kurang optimal menguap, sementara jalur yang lebih efisien diperkuat, sehingga ACO secara bertahap menemukan solusi optimal. Sementara, Large Neighborhood Search (LNS) bekerja dengan cara merusak dan memperbaiki sebagian solusi, dimana solusi awal dijelajahi dalam lingkungan tertentu dengan mengeksplorasi tetangga dari solusi yang ada. Hasil analisis menunjukkan bahwa waktu komputasi LNS secara signifikan lebih cepat dengan waktu 1,198s (detik) dibandingkan ACO yang memerlukan 25,229s (detik) untuk menyelesaikan solusi, sehingga LNS terbukti sekitar 21 kali lebih cepat daripada ACO. Kedua algoritma menghasilkan jumlah rute yang sama, yaitu sebanyak 4 rute, dengan ACO total jarak tempuh mencapai 110,7 km sementara LNS total jarak tempuh hanya 102,48 km. Perbandingan ini menunjukkan bahwa LNS lebih efisien dengan pengurangan total jarak tempuh sebesar 8,22 km atau sekitar 7,42% lebih baik dibandingkan ACO. Algoritma ACO mengalami penurunan sebanyak 7 kali selama 500 iterasi, sementara LNS mencatat penurunan sebanyak 6 kali dalam rentang iterasi yang sama. ACO berhasil menurunkan total jarak tempuh sebesar 4,798 km atau 4,15% dari jarak awal 115,492 km menjadi 110,694 km. Sebaliknya, LNS menunjukkan kinerja yang lebih signifikan dengan total penurunan jarak tempuh sebesar 12,311 km atau 10,72% dari jarak awal 114,790 km menjadi 102,479 km. Hasil ini diperoleh dari penggunaan koordinat geografis dan penerapan rute jalan nyata dengan integrasi OpenStreetMaps. Kesimpulan dari penelitian ini adalah bahwa LNS lebih unggul dalam hal efisiensi waktu komputasi dan optimasi jarak tempuh. LNS juga dapat memberikan solusi yang lebih efisien dalam skenario yang memiliki rute dengan permintaan lebih besar, sehingga lebih cocok untuk kasus dengan variasi permintaan yang tinggi. Namun, ACO tetap menunjukkan kinerja yang solid dan efektif dengan kombinasi eksplorasi dan eksploitasi yang seimbang.
| Item Type: | Thesis (Skripsi) | ||||||
|---|---|---|---|---|---|---|---|
| Creators: |
|
||||||
| Subjects: | 000 - Komputer, Informasi dan Referensi Umum > 000 Ilmu komputer, ilmu pengetahuan dan sistem-sistem > 001 Ilmu pengetahuan | ||||||
| Divisions: | Fakultas Teknik > Teknik Industri S1 | ||||||
| SWORD Depositor: | Robiatul Adawiyah | ||||||
| Depositing User: | Robiatul Adawiyah | ||||||
| Date Deposited: | 22 Oct 2026 06:21 | ||||||
| Last Modified: | 22 Oct 2026 06:21 | ||||||
| URI: | https://repository.untan.ac.id/id/eprint/9433 |
Actions (login required)
![]() |
View Item |
