Anggela, Ginna Alva (2023) Algoritma Sweep dan Nearest Neighbour pada Penyelesaian Capacitated Vehicle Routing Problem (CVRP). Undergraduate thesis, UNDIP.

	Text File 1 Pendahuluan - Ginna Alva Anggela.pdf Download (751kB)
	Text File 2 Isi - Ginna Alva Anggela.pdf Restricted to Repository staff only Download (1MB) | Request a copy
	Text File 3 (Daftar Pustaka) - Ginna Alva Anggela.pdf Download (317kB)

Abstract

Vehicle Routing Problem (VRP) merupakan suatu permasalahan penentuan
rute yang optimal dengan melibatkan lebih dari satu kendaraan untuk melayani
sejumlah agen dengan memperhatikan beberapa kendala sesuai dengan permintaan
dari masing-masing agen. Kapasitas kendaraan merupakan tambahan kendala dari
salah satu variasi VRP yang dapat disebut dengan Capacitated Vehicle Routing
Problem (CVRP). Pada model CVRP, semua kendaraan memiliki kapasitas yang
terbatas dan homogen. Masalah CVRP diselesaikan menggunakan metode
Algoritma Sweep dan Nearest Neighbour. Penyelesaian CVRP dilakukan dengan
dua tahapan, tahap pertama adalah tahap pengelompokkan (clustering)
menggunakan Algoritma Sweep dan tahap kedua melakukan pembentukan rute
untuk masing cluster dengan metode Algoritma Nearest Neighbour. Tujuan dari
penelitian ini adalah meminimalkan jarak tempuh dan mengoptimalkan waktu
tempuh untuk setiap rute. Data yang digunakan adalah data pendistribusian dari
perusahaan Suara Merdeka Network yang memproduksi surat kabar. Berdasarkan
perhitungan dalam menyelesaikan permasalahan CVRP dengan metode Algoritma
Sweep dan Nearest Neighbour, diperoleh total jarak tempuh kendaraan yaitu
2842.9 km dengan waktu tempuh 2132.8 menit. Perhitungan persentase
penghematan jarak tempuh yang telah dihitung yaitu didapatkan persentase sebesar
4.78%. Perolehan kapasitas kendaraan dengan metode Algoritma Sweep dan
Nearest Neighbour diperoleh kapasitas yang tidak melebihi kapasitas dari
kendaraan yaitu 400 kg. Sesuai dengan Teorema Dirac dan Teorema Ore, rute yang
dihasilkan dapat dikatakan sebuah graf Hamilton karena setiap titik kantor
perwakilan dilalui tepat satu kali oleh kendaraan kecuali titik awal yang dilalui dua
kali.

Actions (login required)

View Item