Skripsi

Implementasi algoritma branch and bound pada distance constrained capacitated vehicle routing problem (DCVRP) / Reny Magfiroh

Abstrak
ABSTRAK Maghfiroh Reny. 2015. Implementasi Algoritma Branch and Bound pada Distance Constarined Capacited Vehicle Routing Problem (DCVRP). Skripsi Jurusan Matematika FMIPA Universitas Negeri Malang. Pembimbing Dra. Susy Kuspambudi Andaini M.Kom. Kata Kunci Constarined Capacited Vehicle Routing Problem (DCVRP) Algoritma Branch and Bound Borland Delphi 7.0. Dalam graph terdapat berbagai teori yang dapat diterapkan pada permasalahan yang terjadi di kehidupan sehari-hari beberapa diantaranya adalahShortest Path Travelling Salesman Problem (TSP)dan Vehicle Routing Problem (VRP). Suatu shortest path yang melalui semua titik dalam suatu graph dan kembali ke titik awal disebut TSP. Suatu TSP menghasilkan cycle tunggal. TSP yang menghasilkan cycle lebih dari satu disebut VRP. Salah satu perluasan dari VRP adalah Distance Constarined Capacited Vehicle Routing Problem (DCVRP). DCVRP merupakan permasalahan penentuan rute optimal kendaraan dalam melayani customer dengan batasan kapasitas kendaraan dan ditambah satu batasan lagi yaitu jarak tempuh kendaraan.Kendaraan tersebut berangkat dan kembali pada depot yang sama.Algoritma Branch and Bound dari TSPdimodifikasisedemikian sehingga dapat diterapkan pada DCVRP. Dalam penyelesaian DCVRP dengan menggunakan algoritma Branch and Bound terdapat 3 tahap. Tahap pertama uji jarak customer tahap kedua uji kapasitas customer. Customer yang lolos pada tahap uji pertama dan kedua akan masuk pada tahap terakhir yaitu pembentukan rute. Ketentuan pada tahap uji jarak customer adalah dua kali jarak setiap customer terhadap depot kurang dari jarak maksimal. Sedangkan untuk uji kapasitas permintaan setiap customer disyaratkan kurang dari kapasitas maksimal. Selanjutnya untuk proses di tahap pembentukan rute yaitu depot selalu dipilih sebagai titik awal rute. Kemudian memilih dua customer dengan jarak terdekat ke depot secara berurutan customer terpilih diuji kapasitas. Customer yang memenuhi uji kapasitas dan memiliki jarak terpendek adalah yang dipilih untuk masuk pada rute. Proses ini berlanjut sampai salah satu batasan dilanggar. Ketika batasan dilanggar maka dibentuk rute baru dengan proses yang sama. Proses berhenti saat semua customer yang masuk pada tahap pembentukan rute telah masuk pada rute. Implementasi algoritma Branch and Bound terhadap bahasa pemrograman Borland Delphi 07 dirancang secara terstruktur dalam artian program disusun dalam bentuk procedure-procedure. Program diuji coba menggunakan 6 10 20 52 sampai 100 titik.Eksekusi program tanpa ada kendala. Jumlah titik tidak berpengaruh terhadap waktu proses pencarian solusi. Waktu untuk menampilkan solusi relatif cepat. Program ini juga difasilitasi penyimpanan data inputan pada file dan juga fasilitas untuk membuka kembali file

Informasi Detail

DDC

Rs 511.8 MAG i

Prodi

Universitas Negeri Malang. Program Studi Matematika, 2015.

Deskripsi Fisik

viii, 105 lembar: il., tab. ; 30 cm

Bahasa

Indonesia

No Reg

04113/KI/15

Edisi

Skripsi (Sarjana)-- Universitas Negeri Malang, 2015

Subjek

1. ALGORITMA
2. ALGORITHM

Pembimbing

1. Susy K. Andaini

Lampiran Berkas