Vehicle Routing Problem dengan Matlab

Vehicle Routing Problem (VRP) adalah  optimasi terhadap masalah menentukan rute dengan mempertimbangkan kapasitas muat kendaraan dan permintaan (demand).  Pada contoh permasalahan ini, ada sebuah depot awal dan sejumlah n tempat untuk dikunjungi dengan permintaan (demand) dan lokasi yang berbeda-beda. Sebuah kendaraan diharapkan untuk memenuhi permintaan setiap tempat tersebut dari depot.dengan rute yang optimal dengan tabu search

============================================

Hitung Manual Nearest Neighbour

Contoh Problem Vehicle Routing Problem dengan Nearest Neighbour

Sebuah Depot berada di titik(16,21)Memiliki kendaraan dengan kapasitas max 15

memiliki 6 Pelanggan.Koordinat tiap pelanggan sbb;

X= 76 35 98 32 5 12

y= 12 89 61 55 66 31

permintaan masing-masing pelanggan :

12 8 10 2 5 13

=============================================

Detail Nearest Neighbour

Step 1   : Dimulai dari koordinat Depo (16,21).

Step 2    : Seleksi semua outlet yang belum dilayani (antara feasible dan not feasible ).

Step 3  :Jika outlet feasible pilih outlet dengan jarak terdekat dimuli dari depo ke node berikutnya,dan seterusnya sampai kapasitas tidak memenuhi(kurang dari demand/permintaan). Contoh jika outlet 6 terbaik (jarak terdekat & feasible) maka

 [1 6 1].

Step 4 : Ulangi langkah 2 dan 3 sampai tidak ada lagi outlet yang feasible.

Step 5 :Jika sudah tidak ada lagi outlet yang feasible kemudian buat rute baru dengan node/outlet yang belum dilayani (Ulangi langkah 1-4).

Step 6 : Lakukan semua langkah sampai semua outlet terlayani 

=============================================

X=[ 16 76 35 98 32 5 12 ]

Y=[ 21 12 89 61 55 66 31 ]

node	1	2	3	4	5	6	7
X	16	76	35	98	32	5	12
Y	21	12	89	61	55	66	31
demand	0	12	8	10	2	5	13

 Nb: Node 1= Depo

dengan jarak antar node sbb:

 

Contoh command Matlab untuk mengetahui jarak antar titik:

X = [0,0;2,1];

>> d = pdist(X,'euclidean')

  ==========================================================

Route 1

Jarak paling dekat = 10,7703 atau pelanggan 7 demand 13 dan Feasible (demand<muat max)

Node	Demand	muatan
1
7	13	15-13=2

Nb:Kapasitas muat maksimal =15

Node Selanjutnya yang terdekat dan feasible adalah node 5 dengan demand 2

Node	Demand	muatan
5	2	2-2=0

Karena Muatan = 0 Kembali ke depo.Jadi rute pertama [1 7 5 1].

Route 2

Jarak paling dekat selain node yg sudah dilayani = 6

Node	Demand	muatan
1
6	5	15-5=10

Node selanjutnya adalah node 3

Node	Demand	muatan
6
3	8	10-8=2

Karena tidak ada lagi yg feasible kembali ke depo mulai rute baru.

Rute 2= [1 6 3 1]

Route 3

Jarak terdekat node 2

Node	Demand	muatan
1
2	12	15-12=3

Rute 3 = [1 2 1]

Node terakhir/yang belum dilayani adalah node 4 tetapi tidak feasible sehingga harus kembali ke depo

Route 4

Node(Pelanggan) yang tersisa adalah node 4

Node	Demand	muatan
1
4	10	15-10=5

Rute 4 =[1 4 1]

Semua permintaan pelanggan sudah terpenuhi dengan rute sbb:

Rute 1 =( 1 7 5 1 )  jarak =  79.58792

Rute 2 =(1 6 3 1)   jarak =154.7316

Rute 3 = (1 2 1)     jarak =121.3425

Rute 4 =(1 4 1)      jarak =182.4719   Total 538.1339