VRPTW

VRPTW

             Menurut Kallehauge dkk. (2001), vehicle routing problem dengan time windows (VRPTW) adalah perluasan dari VRP. Jika pada VRP ditambahkan time window pada masing–masing konsumen, maka permasalahan tersebut menjadi VRPTW. Untuk VRPTW, selain adanya kendala kapasitas kendaraan, terdapat tambahan kendala yang mengharuskan kendaraan untuk melayani tiap konsumen pada time frame tertentu.

           Kendaraan boleh datang sebelum time window “open”, tetapi konsumen tersebut tidak dapat dilayani sampai time window “open”. Kendaraan tidak diperbolehkan untuk datang setelah time window “closed”. Tangiah (1995) mendefinisikan VRPTW sebagai permasalahan untuk menjadwalkan sekumpulan kendaraan, dengan kapasitas dan travel time terbatas, dari central depot kesekumpulan konsumen yang tersebar secara geografis, dengan demand diketahui, dalam time windows tertentu. Time windows adalah two sided, yang berarti bahwa tiap konsumen harus dilayani saat atau setelah earliest time, dan sebelum latest time dari konsumen tersebut. Jika kendaraan datang ke konsumen sebelum earliest time dari konsumen tersebut, maka akan menghasilkan idle atau waktu tunggu. Kendaraan yang datang ke konsumen setelah latest time adalah tardy. Terdapat pula waktu service yang diperlukan untuk melayani tiap konsumen. Biaya rute dari suatu kendaraan adalah total dari waktu travel (proposional dengan jarak), waktu tunggu, dan waktu service, yang

diperlukan untuk mengunjungi sekumpulan konsumen.

             Homberger dkk. (1999) mendefinisikan permasalahan VRPTW sebagai berikut: n konsumen akan dilayani dari sebuah depot, dengan sejumlah kendaraan yang memiliki kapasitas, Q, yang sama. Untuk tiap konsumen i, i=1, 2, ..., n, terdapat demand qi, waktu service si, dan service time window zi=[ei, fi]. Lower bound ei merupakan waktu paling awal untuk melakukan service, dan upper bound fi, waktu paling lambat untuk melakukan service. Demand qi dari konsumen i harus dipenuhi dengan sekali service saja, dalam batas

time window zi. Sebagai tambahan, e0 merupakan waktu paling awal untuk kendaraan berangkat dari depot i, i=0, dan f0 merupakan waktu paling lambat untuk kendaraan kembali ke depot. Data mengenai lokasi dari depot, dan konsumen, jarak terpendek dij, serta waktu travel d’ij antara dua lokasi, diketahui. Tujuannya untuk menentukan jadwal rute yang feasible, yaitu pertama untuk meminimalkan jumlah kendaraan, dan kedua untuk meminimalkan total jarak travel. Konsumen tidak dapat dilayani diluar time window mereka masing–masing. Tetapi kendaraan diperbolehkan untuk datang sebelum lower bound dari time window. Apabila hal ini terjadi, maka kendaraan harus menunggu sampai batas waktu paling awal service tersebut dapat dilakukan.