Implementasi algoritma branch and bound pada distance constrained capacited vehicle routing problem (DCVRP)

Abstract

Distance Constarined Capacited Vehicle Routing Problem (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 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.  Oleh sebab itu, untuk mempermudah pencarian rute, Algoritma Branch and Bound tersebut diimplementasikan ke dalam program komputer menggunakan Delphi 7.