Text

Penyelesaian Capacitated Vehicle Routing Problem (CVRP) Menggunakan Metode Savings Heuristic 511.8 SOF p

---

ABSTRAK

Masalah rute kendaraan atau dikenal dengan Vehicle Routing Problem (VRP)
merupakan masalah penentuan rute minimum yang melibatkan lebih dari satu
kendaraan untuk melayani sejumlah pelanggan sesuai dengan permintaannya
masing-masing. Masalah ini sangat sering terjadi dalam sistem pendistribusian
barang. Penentuan rute harus menghasilkan jarak yang minimal agar distibutor
tidak mengalami kerugian. Capacitated Vehicle Routing Problem (CVRP)
merupakan salah satu varian dari VRP. Pada model CVRP, semua kendaraan
memiliki kapasitas yang terbatas dan homogen. CVRP termasuk dalam kategori
NP-Hard Problem (Nondeterministik Polynomial-Hard), sehingga sulit untuk
diselesaikan menggunakan algoritma eksak. Untuk menyelesaikan masalah
tersebut, digunakan metode pendekatan yang salah satunya adalah dengan metode
Savings Heuristic (algoritma Clarke and Wright). Solusi didapat dengan cara
melakukan perhitungan penghematan antar titik kemudian mengaitkan titik-titik
menjadi sebuah rute berdasarkan nilai penghematan yang terbesar. Simulasi telah
dilakukan dengan mencari solusi dari beberapa kasus VRP. Selanjutnya salah satu
hasil perhitungan tersebut dibandingkan dengan hasil pehitungan menggunakan
algoritma Sweep. Dari perbandingan kedua metode tersebut, terlihat bahwa untuk
pada kasus CVRP, metode Savings Heuristic lebih unggul dalam hal mendapatkan
solusi yang lebih optimal dalam artian meminimalkan total jarak tempuh
kendaraan daripada menggunakan algoritma Sweep.
Kata kunci : Capacitated Vehicle Routing Problem (CVRP), metode Savings
Heuristic (algoritma Clarke and Wright), algoritma Sweep.

ABSTRACT

Vehicle Routing Problem (VRP) is the problem of determining the minimum
route involving more than one vehicle to serve a number of customers according
to their demand. This problem is very common in the system of distribution of
goods. Determination of route should have result in the proximate distance so that
distributors not losses. Capacitated Vehicle Routing Problem (CVRP) is one of
the variants of the VRP. In the model CVRP, all vehilcles have a limited capacity
and homogeneous. CVRP included in the category of NP-Hard Problem
(Nondeterministik Polynomial-Hard), so it is difficult to be solved using the exact
algorithm. To resolve the problem, use the approach method that one of them is
the Savings Heuristic method (Clarke and Wright algorithm). The solution is
obtained by calculating the savings between nodes then associate the nodes into a
route based on the value of the largest savings. Simulations have been conducted
to find solutions in some cases VRP. Furthemore, one of the calculation result
were compered with results using Sweep algorithm. From the comparison of the
two methods, it appears that for the case CVRP, Savings Heuristic method have
an optimal solution witch mean of minimum route than using Sweep algorithm.
Keywords : Capacitated Vehicle Routing Problem (CVRP), Savings Heuristic
method (Clarke and Wright algorithm), Sweep algorithm.

---

Ketersediaan

1936A17I

1936 A 17

Perpustakaan FSM Undip (Referensi)

Tersedia

Informasi Detail

Judul Seri

MATEMATIKA

No. Panggil

1936 A 17

Penerbit

: ., 2016

Deskripsi Fisik

-

Bahasa

Indonesia

ISBN/ISSN

-

Klasifikasi

1436

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

-

Info Detail Spesifik

-

Pernyataan Tanggungjawab

Gina Sofia

Versi lain/terkait

Lampiran Berkas

Komentar

---

Anda harus masuk sebelum memberikan komentar