Penerapan metode upper bound pada multi depot vehicle routing problem (MDVRP)

Abstract

Multi Depot Vehicle Routing Problem(MDVRP) merupakan permasalahan yang meliputi beberapa depot yang melayani beberapa customer dengan total jarak minimum dan kembali ke depot yang sama tanpa melanggar kendala kapasitas kendaraan. Terdapat tiga tahap dalam permasalahan MDVRP, diantaranya adalah pengelompokan, pembentukan rute, dan pengurutan rute. Pada tahap pengelompokan, beberapa customer dikelompokkan berdasarkan depot terdekat. Pada tahap pembentukan rute, pencarian rute menggunakan metode Upper Bound. Terdapat dua langkah pada metode tersebut yakni pemilihan depot sebagai titik awal pencarian rute dan dilanjutkan dengan pencarian jarak terpendek antar titik yang terpilih, apabila melanggar kapasitas maka pencarian rute langkah diulangi sampai semua titik termuat dalam suatu rute. Pada Tahap terakhir, urutan pengiriman dipilih sehingga urutan pengiriman dimulai dari depot ke customer terdekat, kemudian ke customer berikutnya yang terdekat dari customer sebelumnya, dan seterusnya. Untuk mengimplementasikan proses penyelesaian permasalahan MDVRP dengan metode Upper Bound maka dibuat program menggunakan software Borland Delphi 07.