Lomba VRP (Vehicle Routing Problem)
Dear rekan2 Komtek/IPOMS,
Untuk menambah keakraban para anggota dan juga melihat kreativitas rekan2 maka
akan diadakan lomba memecahkan persoalan Vehicle Routing Problem (VRP).
VRP diperkenalkan pertama kali oleh Dantziq dan Ramser pada tahun 1959 dan
semenjak itu telah banyak diteliti dan dikembangkan. VRP didefinisikan sebagai
berikut sebuah pencarian atas cara penggunaan yang efisien dari sejumlah vehicle
yang harus melakukan perjalanan untuk mengunjungi sejumlah tempat untuk
mengantar dan/atau menjemput barang. Istilah customer digunakan untuk
menunjukkan pemberhentian untuk mengantar dan/atau menjemput barang. Setiap
customer harus dilayani oleh satu vehicle saja. Penentuan pasangan
vehicle-customer ini dilakukan dengan mempertimbangkan kapasitas vehicle dalam
satu kali angkut, untuk meminimalkan biaya atau jarak yang diperlukan.
VRP adalah suatu problem untuk mencari rute optimal dari satu atau lebih
kendaraan diantara serangkaian lokasi dari suatu depot dan ditentukan bahwa
setiap lokasi hanya dikunjungi satu kali, dan kemudian kembali ke titik mula,
tanpa langkah surut. Rute optimal adalah rute yang memerlukan total jarak
tempuh, total biaya perjalanan, atau waktu tempuh yang minimum. Masalah ini
diambil dari gambaran yang dikemukakan tentang penjual keliling yang mengawali
perjalanannya dari suatu depot untuk mengunjungi (n-1) lokasi yang ditentukan
sebelum kembali kedepot. Masalah ini adalah masalah penentuan rute yang mencakup
penentuan urutan lokasi yang akan ditempuh untuk meminimumkan ongkos perjalanan.
Depot yang dimaksud dapat berupa supplier, produsen, gudang distribusi dan
lain-lain.
Problem VRP ini simpel, dan kelihatan mudah untuk dimengerti tetapi akan sulit
pemecahannya jika jumlah lokasi atau customer sudah semakin banyak. Banyak
sekali alternatif rute yang dapat dipilih. Kita dapat mecoba semua alternatif
dan memilih yang terpendek. Tetapi bagaimana, jika sangat
banyak alternatif yang harus dipilih? Jumlah alternatif rute yang harus dipilih
adalah (n-1)!/2, jika kita akan menentukan rute dari n customer. Jika jumlah
customer ada 16 maka akan ada sngat banyak rute alternatif yang berbeda.
Aplikasi VRP pada kehidupan nyata dapat ditemukan dalam perencanaan distribusi
dan logistik, seperti pada permasalahan pengantaran produk dari suplier kepada
agen, pengangkutan sampah, pengambilan surat pada kotak pos, pengantaran koran
pada para pelanggan, dan lain sebagainya.
Oleh karena itu Komtek akan mengadakan lomba untuk memecahkan permasalahan VRP
n=64, k=9.
Data yang akan disediakan adalah sebagai berikut; koordinat tiap lokasi dan
matriks jarak, data demand tiap lokasi, data jumlah kendaraan dan data
kapasitas kendaraan. Peserta lomba harus menunjukkan rute kendaraan yang
dipilih, dan berapa jarak total tempuhnya serta cara atau metoda yang
digunakan?
Persyaratan Peserta :
1. Member milis Komputer-Teknologi@ atau APICS-ID@ .
2. Peserta diperbolehkan dalam group maksimal anggotanya 3 orang/group.
Kriteria pemenang adalah peserta yang dapat mengalahkan total jarak tempuh pada
rute VRP peserta lainnya, jika ada dua atau lebih peserta yang sama total jarak
minimumnya, maka peserta yang mengirim jawaban yang lebih dahulu yang menjadi
pemenangnya.
====================================================================
Pemenang berhak mendapatkan hadiah Rp. 1.500.000,- (Satu juta lima ratus ribu
rupiah)
====================================================================
Peserta akan dikenai biaya pendaftaran lomba sebesar Rp. 50.000,- per orang.
Member IPOMS yang sudah membayar annual fee dibebaskan dari biaya pendaftaran.
Lomba akan ditutup tgl. 20-08-2011, pemenang diumumkan tgl. 22-08-2011
Bagi yang berminat dan mendapatkan info selengkapnya dari lomba ini silahkan
japri ke syarwani@yahoo.com
Contoh persoalan dan solusi VRP di bawah.
Salam Komtek,
M. Syarwani
http://www.erpweaver.com
=====
NAME : A-n32-k5
COMMENT : (Augerat et al, No of trucks: 5, Optimal value: 784)
TYPE : CVRP
DIMENSION : 32
EDGE_WEIGHT_TYPE : EUC_2D
CAPACITY : 100
NODE_COORD_SECTION
1 82 76
2 96 44
3 50 5
4 49 8
5 13 7
6 29 89
7 58 30
8 84 39
9 14 24
10 2 39
11 3 82
12 5 10
13 98 52
14 84 25
15 61 59
16 1 65
17 88 51
18 91 2
19 19 32
20 93 3
21 50 93
22 98 14
23 5 42
24 42 9
25 61 62
26 9 97
27 80 55
28 57 69
29 23 15
30 20 70
31 85 60
32 98 5
DEMAND_SECTION
1 0
2 19
3 21
4 6
5 19
6 7
7 12
8 16
9 6
10 16
11 8
12 14
13 21
14 16
15 3
16 22
17 18
18 19
19 1
20 24
21 8
22 12
23 4
24 8
25 24
26 24
27 2
28 20
29 15
30 2
31 14
32 9
DEPOT_SECTION
1
Solution:
Route #1: 21 31 19 17 13 7 26
Route #2: 12 1 16 30
Route #3: 27 24
Route #4: 29 18 8 9 22 15 10 25 5 20
Route #5: 14 28 11 4 23 3 2 6
cost 784
Mohon bantuannya untuk mengisi survei daya saing Indonesia di
http://www.ips.or.kr/site/IPS/mail/survey/20110120/26.html
*****************************************************************
Indonesian Production and Operations Management Society (IPOMS).
http://blog.ipoms.web.id/
Bergabunglah dengan IPOMS di Facebook
http://www.facebook.com/home.php?ref=home#/group.php?gid=34994473375
********************************************************************
No comments:
Post a Comment