PENGGUNAAN METODE HEURISTIK DALAM PERMASALAHAN VEHICLE ROUTING PROBLEM DAN IMPLEMENTASINYA DI PT NIPPON INDOSARI CORPINDO
AJI RADITYA
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2009
ABSTRACT AJI RADITYA. The application of the heuristic method at the vehicle routing problem and its implementation at the PT Nippon Indosari Corpindo. Supervised by AMRIL AMAN and PRAPTO TRI SUPRIYO. This paper is a case study in a division of PT Nippon Indosari Corpindo company. We used the vehicle routing problem with time windows (VRPTW) to formulate the distribution problem, which is a variation of the vehicle routing problem (VRP). In the VRP, all costumers have a time windows, so the service for the costumers must be completed in a specified time interval. The objective is to minimize the number of vehicles to serve all costumers in certain area and also to minimize the route length. As the VRPTW is a difficult problem in non polynomial hard problems, then we used the heuristic approach to solve the problem. In this paper, we used the nearest addition heuristic method to find the first solution. Next we used 2-Opt, Or-Opt, relocate, exchange, and cross methods to improve the first solution. In the last chapter of this paper, the results were compared to the current condition of the company. Key word: Vehicle routing problem, heuristic method, nearest addition heuristic method.
RINGKASAN AJI RADITYA. Penggunaan Metode Heuristik Dalam Permasalahan Vehicle Routing Problem dan Implementasinya di PT Nippon Indosari Corpindo. Dibimbing oleh AMRIL AMAN dan PRAPTO TRI SUPRIYO. Penelitian ini adalah studi kasus pada bagian distribusi di PT Nippon Indosari Corpindo. Metode vehicle routing problem with time windows (VRPTW) digunakan untuk memformulasikan masalah distribusi. Metode VRPTW merupakan variasi dari metode vehicle routing problem (VRP). Dalam metode VRP, setiap kendaraan berawal dan berakhir di satu tempat (depot) untuk melayani seluruh konsumen. Pada VRPTW, setiap konsumen memiliki batasan waktu pelayanan, sehingga kegiatan pengiriman di tempat konsumen harus berada diantara batasan waktu yang ditentukan. Penelitian ini bertujuan meminimumkan banyaknya kendaraan yang digunakan untuk melayani konsumen dan meminimumkan total jarak yang ditempuh. Metode VRPTW termasuk kategori non-polynomial hard problem, karena digunakan pendekatan heuristik untuk mencari solusi masalah. Metode nearest addition heuristic digunakan untuk mencari solusi awal. Kemudian digunakan metode 2-Opt, or-Opt, relocate, exchange dan cross untuk memperbaiki solusi awal tersebut. Pada penelitian ini, solusi dengan metode di atas akan dibandingkan dengan keadaan yang terjadi pada perusahaan tersebut. Kata kunci: Vehicle routing problem, metode heuristik, metode nearest addition heuristic.
PENGGUNAAN METODE HEURISTIK DALAM PERMASALAHAN VEHICLE ROUTING PROBLEM DAN IMPLEMENTASINYA DI PT NIPPON INDOSARI CORPINDO
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika
Oleh:
AJI RADITYA G54104062
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2009
Judul Skripsi
:
Penggunaan Metode Heuristik Dalam Permasalahan Vehicle Routing Problem dan Implementasinya di PT Nippon Indosari Corpindo
Nama
:
Aji Raditya
NIM
:
G54104062
Menyetujui Pembimbing I
Pembimbing II
Dr. Ir. Amril Aman, M.Sc. NIP 19570330 198103 1 001
Drs. Prapto Tri Supriyo, M.Kom. NIP 19630715 199002 1 002
Mengetahui, Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Dr. drh. Hasim, DEA NIP 19610328 198601 1 002
Tanggal Lulus:
PRAKATA Alhamdulillah, penulis panjatkan puji dan syukur kehadirat Allah SWT atas rahmat dan karunia-Nya sehingga penulisan skripsi dengan judul “Penggunaan Metode Heuristik Dalam Permasalahan Vehicle Routing Problem dan Implementasinya di PT Nippon Indosari Corpindo” dapat diselesaikan. Pada kesempatan ini penulis menyampaikan ucapan terima kasih kepada: 1. Bapak Marsudi Harto, ibunda Sri Supami, adinda Swasti Hapsari dan sepupuku Ika Nuryuni Kartika serta seluruh keluarga besar penulis atas doa, semangat, dan kasih saying yang telah diberikan. 2. Bapak Amril Aman dan bapak Prapto Tri Supriyo selaku dosen pembimbing yang telah banyak memberikan arahan dan masukan pada penulisan skripsi ini. 3. Bapak Yusuf Hadi dan bapak Zainal Arifin sebagai General Manager dan Distribution Manager pada PT Nippon Indosari Corpindo atas bantuannya saat proses pengambilan data di perusahaan tersebut. 4. Teman seperjuanganku Fariz Saeful Romza atas kerjasamanya selama penelitian dan penulisan skripsi ini. 5. Tities Melyasih atas doa, semangat dan dukungan yang diberikan. 6. Teman-temanku di jurusam matematika (angkatan 40, 41, 42, 43) atas bantuan dan dukungannya 7. Teman-temanku di kostan “Al-Fath” yang banyak memberikan saran dan ide pada penulis. Penulis menyadari bahwa skripsi ini masih bisa untuk dikembangkan lebih jauh lagi. Korespondensi dengan penulis dapat melalui e-mail di
[email protected]. “Jangan menganggap tugas belajarmu sebagai kewajiban, melainkan pandanglah itu sebagai sebuah kesempatan untuk menikmati betapa indahnya ilmu pengetahuan yang akan diterima oleh masyarakat apabila jerih payahmu berhasil” – Albert Einstein-
Bogor, September 2009 Aji Raditya
RIWAYAT HIDUP Penulis dilahirkan di Jakarta pada tanggal 02 Desember 1986 dari ayah Marsudi Harto dan ibu Sri Supami. Penulis merupakan putra pertama dari dua bersaudara. Tahun 2004 penulis lulus dari SMA Negeri 2 Tangerang dan pada tahun yang sama lulus ujian Seleksi Penerimaan Mahasiswa Baru (SPMB) untuk masuk ke jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam IPB. Pada tahun 2008, penulis (tergabung dalam tim) memenangi Lomba Karya Tulis Mahasiswa (LKTM) bidang Ilmu Pengetahuan Sosial tingkat IPB sebagai juara II dan pada tahun yang sama penulis (tergabung dalam tim) menjadi 10 besar finalis Kompetisi Pemikiran Kritis Mahasiswa (KPKM) tingkat nasional bidang perekonomian yang diselenggarakan oleh Dikti.
Bogor, September 2009 Aji Raditya
DAFTAR ISI DAFTAR TABEL…………………………………………………………………..
Halaman viii
DAFTAR GAMBAR……………………………………………………………….
viii
DAFTAR LAMPIRAN……………………………………………………………..
viii
PENDAHULUAN Latar Belakang…………………………………………………………... Manfaat…………………………………………………………………..
1 1
LANDASAN TEORI Traveling Salesman Problem (TSP)…………………………………….. Traveling Salesman Problem with Time Windows (TSPTW)……… m-Traveling Salesman Problem (m-TSP)………………………….. Vehicle Routing Problem (VRP)………………………………………… Vehicle Routing Problem with Time Windows (VRPTW)………………. Metode Heuristik………………………………………………………… Nearest Addition Heuristic…………………………………………. 2-opt………………………………………………………………… Relocate……………………………………………………………… Exchange……………………………………………………………
1 2 3 3 4 4 5 5 5 6
METODE PENELITIAN Waktu dan Lokasi……………………………………………………….. Teknik Pengumpulan Data………………………………………………. Ruang Lingkup Penelitian……………………………………………….. Pengolahan Data…………………………………………………………
6 6 6 6
IMPLEMENTASI VEHICLE ROUTING PROBLEM PADA KEGIATAN DISTRIBUSI PRODUK DI PT NIPPON INDOSARI CORPINDO Gambaran Umum Perusahaan…………………………………………… Divisi Distribusi…………………………………………………….. Kegiatan Distribusi…………………………………………………. Kegiatan pada Saluran Distribusi RO………………………………. Perumusan Masalah……………………………………………………... Formulasi Masalah………………………………………………………. Hasil dan Pembahasan
7 7 7 8 8 9 10
SIMPULAN DAN SARAN Simpulan………………………………………………………………… Saran……………………………………………………………………..
15 15
DAFTAR PUSTAKA………………………………………………………………
15
LAMPIRAN………………………………………………………………………...
16
DAFTAR TABEL
1 2 3 4 5 6 7
Hasil simulasi untuk kendaraan pertama……………………………… Hasil simulasi untuk kendaraan kedua……………………………….. Hasil simulasi untuk kendaraan ketiga……………………………….. Rute saat ini untuk kendaraan pertama.................................................. Rute saat ini untuk kendaraan kedua...................................................... Rute saat ini untuk kendaraan ketiga..................................................... Perbandingan hasil simulasi dan data yang didapat…………………...
Halaman 10 11 12 12 13 13 14
DAFTAR GAMBAR
1 2 3 4 5 6 7 8 9
Contoh rute dalam traveling salesman problem ……………………… Contoh rute dalam vehicle routing problem………………………….. Contoh metode 2-opt…………………………………………………. Contoh metode relocate pada satu rute………………………………. Contoh metode relocate pada dua rute……………………………….. Contoh metode exchange pada satu rute……………………………… Contoh metode exchange pada dua rute……………………………… Rute hasil simulasi……………………………………………………. Rute saat ini……………………………………………………………
Halaman 2 3 5 5 6 6 6 12 14
DAFTAR LAMPIRAN
1 2 3 4 5 6 7 8 9 10
Struktur organisasi pada departemen supply chain management……... Saluran distribusi yang ada……………………………………………. Diagram alir pada saluran distribusi retail/outlet……………………... Beberapa gambar……………………………………………………… Matriks jarak …………………………………………………………. Data…………………………………………………………………… Input…………………………………………………………………… Proses………………………………………………………………….. Output…………………………………………………………………. Contoh metode multidimensional scaling……………………………..
Halaman 17 18 19 20 23 24 25 26 29 30
1
I PENDAHULUAN Pada bagian awal bab ini, akan dijelaskan latar belakang dan tujuan penelitian yang dilakukan. Sementara itu pada bagian akhir bab ini akan diperlihatkan manfaat dari penelitian ini bagi perusahaan. 1.1 Latar Belakang Masalah transportasi dan distribusi produk dalam kehidupan sehari-hari dapat dimodelkan sebagai Vehicle Routing Problem (VRP). Model VRP akan menghasilkan sejumlah rute kendaraan untuk mengunjungi setiap konsumen. Setiap rute berawal dan berakhir pada tempat yang sama yang disebut depot. Selain itu, model VRP juga memastikan agar total permintaan pada suatu rute tidak melebihi kapasitas kendaraan yang beroperasi. Penggunaan model VRP diharapkan dapat meminimumkan total jarak tempuh dan jumlah kendaraan. Kendala waktu pada model VRP merupakan masalah yang rumit. Pada masalah tersebut, konsumen hanya melayani pengiriman produk pada selang waktu tertentu setiap harinya. Sebagai contoh, sebuah gudang hanya akan melayani pengiriman produk antara pukul 08.00 WIB sampai dengan pukul 15.00 WIB. Untuk memecahkan masalah tersebut digunakanlah Vehicle Routing Problem with Time Windows (VRPTW) yaitu model VRP dengan menambahkan kendala waktu. VRPTW terbagi menjadi dua kasus yaitu kasus hard time windows dan kasus soft time windows. Pada kasus hard time windows, pengiriman akan ditolak apabila tidak sesuai dengan waktu yang telah ditentukan oleh konsumen, sedangkan pada kasus soft time konsumen akan menerima windows pengiriman walaupun tidak sesuai dengan
waktu yang telah ditentukan sekaligus memberikan penalti atau biaya tambahan atas keterlambatannya. Pada penelitian ini model VRPTW dengan kasus soft time windows dipilih karena sesuai dengan masalah yang terjadi di lapangan. VRP sulit untuk dipecahkan karena merupakan gabungan antara masalah kapasitas (packing problem) dan masalah penentuan rute (salesman routing problem). Jika masalah yang dihadapi masih tergolong kecil, maka metode branch and bound dapat memberikan solusi terbaik dari masalah VRP. Jika masalahnya kompleks dan besar, salah satu cara untuk menyelesaikannya adalah dengan menggunakan metode heuristik. Dalam penelitian ini, metode heuristik akan digunakan untuk mencari solusi dari model VRPTW yang dihadapi. Solusi tersebut dapat dicari dengan bantuan software ILOG Dispatcher versi 2.1 dan ILOG Solver versi 4.4 yang dijalankan dengan Microsoft Visual C++ versi 6.0. 1.2 Manfaat Penelitian yang dilakukan memiliki manfaat yang berbeda bagi masing-masing level management pada perusahaan tersebut. Manfaat bagi top level management dan middle level management di perusahaan tersebut adalah mempermudah proses pengambilan keputusan. Dalam hal ini keputusan untuk meminimumkan biaya distribusi yang ditanggung oleh perusahaan, langkah yang dapat dilakukan adalah meminimumkan banyaknya kendaraan dan memaksimumkan banyaknya barang yang dibawa, sedangkan manfaat bagi low level management adalah dapat menentukan rute terpendek bagi setiap kendaraan.
II LANDASAN TEORI Dalam bab ini, akan dijelaskan beberapa metode yang digunakan dalam penelitian. Pertama akan dijelaskan tentang Traveling Salesman Problem (TSP) yang merupakan dasar dari Vehicle Routing Problem (VRP), kemudian akan diperlihatkan penggunaan metode heuristik untuk mencari solusi dari kasus VRP yang dihadapi pada.
2.1 Traveling Salesman Problem Dalam TSP, seorang salesman akan berangkat dari satu kota kemudian mengunjungi seluruh kota yang ada dan pada akhir perjalanannya salesman tersebut akan kembali ke kota awal atau depot. Tujuan dari TSP adalah menentukan rute yang melalui seluruh kota dan meminimumkan jarak.
2
Model TSP dapat dituliskan sebagai berikut: Variabel keputusan
xi , j =
1, jika kota ke - j dikunjungi setelah kota ke - i 0, selainnya
Fungsi objektif: m
min Z
= j=1
m
ci, j xi, j
(2.1)
i=1
Kendala-kendala: m
xi, j 1;
i 1,2,...,m
(2.2)
j 1
m
xi, j 1;
j 1, 2,..., m
(2.3)
i 1
x j L
i L
i, j
| L | 1; L {1,2,..., m }
xi , j {0,1}; i, j 1,2,..., m
(2.4) (2.5)
Fungsi objektif dalam TSP (persamaan 2.1) adalah meminimumkan jarak yang ditempuh dan mengunjungi setiap kota yang ada, dengan ci,j adalah jarak dari kota i ke kota j dan xi,j benilai 1 jika rute dari kota ke-i menuju kota ke-j digunakan dan bernilai 0 jika selainnya. Kendala (2.2) dan (2.3) memastikan bahwa setiap kota dikunjungi tepat satu kali, sedangkan kendala (2.4) memastikan tidak terdapat subtour pada rute tersebut. Pada kendala (2.5) diperlihatkan bahwa xi,j merupakan varibel biner untuk setiap i dan j yang ada (Hoffman & Padberg 2009).
Dalam perkembangannya, TSP memiliki beberapa variasi, yaitu: Traveling Salesman Problem with Time Windows (TSPTW) yang merupakan TSP dengan tambahan waktu pelayanan di setiap kota dan m-Traveling (m-TSP) yang Salesman Problem menggunakan sejumlah salesman untuk mengunjungi seluruh kota. 2.1.1 Traveling Salesman Problem with Time windows Traveling Salesman Problem with Time (TSPTW) merupakan Windows pengembangan dari TSP. Pada TSPTW rute yang ditempuh memiliki tambahan kendala waktu pelayanan (time windows) untuk masing-masing konsumen. Time windows pada masing-masing konsumen dapat berbeda satu sama lain, tetapi memiliki karakteristik yang sama yakni berupa selang waktu. Time windows [a1, bi] menunjukkan selang waktu pelayanan pada konsumen i, dengan ai sebagai batas awal dan bi sebagai batas akhir. Model untuk TSPTW tidak berbeda dengan model TSP di atas, dengan tambahan beberapa kendala:
ai Ti bi ; i 1,..., m i , j 1, ..., m Ti ti , j T j ; i j
(2.6) (2.7)
Pada (2.6) waktu pelayanan (Ti) berada di antara batas awal (ai) dan batas akhir (bi) dari time windows, sedangkan pada persamaan (2.7) dipastikan pelayanan di kota j (Tj) merupakan waktu tempuh antara kota i dan kota j (ti,j) ditambahkan dengan waktu pelayanan di kota i (Ti) (Sutapa et al. 2003).
Konsumen
Rute
Gambar 1 Contoh rute dalam Traveling Salesman Problem (TSP) .
3
2.1.2 m-TSP m-TSP adalah salah satu variasi dari TSP, dimana terdapat sebanyak m salesman mengunjungi seluruh kota, tetapi setiap kota hanya dapat dikunjungi oleh tepat satu salesman saja. Tiap salesman berawal dari suatu depot dan pada akhir perjalannya juga harus kembali ke depot tersebut. Tujuan dari m-TSP adalah meminimumkan total jarak dari setiap rute. Masalah m-TSP dikenal juga sebagai Vehicle Routing Problem (VRP), dimana sebuah kota diasosiasikan sebagai sebuah konsumen dan tiap kendaraan memiliki kapasitas tertentu. Total jumlah permintaan dalam suatu rute tidak boleh melebihi kapasitas dari kendaraan yang beroperasi (Larsen 1999). 2.2 Vehicle Routing Problem Masalah yang berkaitan dengan pencarian rute yang optimal untuk kendaraan dari satu depot dan melayani sejumlah konsumen disebut VRP. Dalam prakteknya VRP banyak digunakan pada masalah distribusi logistik. Berikut adalah karakteristik dari model VRP. Terdapat satu depot (dilambangkan dengan O) yang memiliki sebanyak k kendaraan untuk melakukan pengiriman, dengan kapasitas setiap kendaraan sebesar C. Kendaraan tersebut mengirimkan permintaan sebesar qi untuk n konsumen, dengan i=1,2,3,…,n. Jarak yang ditempuh setiap kendaraan sebisa mungkin adalah jarak yang paling minimum dengan ci,j adalah biaya pengiriman dari konsumen i ke konsumen j, dengan i= 1,2,…,n dan j=1,2,…,n. Jarak antarkonsumen bersifat simetris atau dapat ditulis sebagai ci,j = cj,i sedangkan jarak antara tempat yang sama bernilai nol atau ci ,i 0 . Solusi yang dihasilkan merupakan anggota {R1 ,..., Rk } yang mengirimkan n dari permintaan melalui k rute yang tersedia dan permintaan yang dikirim tidak melebihi kapasitas kendaraan yang tersedia untuk setiap rute (Machado et al. 2002).
Tujuan dari VRP adalah menentukan sejumlah rute untuk melakukan pengiriman pada setiap konsumen, dengan mengikuti beberapa ketentuan, antara lain: (1) setiap rute berawal dan berakhir di depot, (2) setiap konsumen dikunjungi tepat satu kali oleh tepat satu kendaraan, (3) jumlah permintaan tiap rute tidak melebihi kapasitas kendaraan dan (4) meminimumkan biaya perjalanan (Cordeau et al. 2002). Model VRP dapat direpresentasikan sebagai berikut:
min Z
n
n
l
ci, j xik, j
(2.8)
j 1 i 1 k 1
Kendala-kendala Konsumen n
l
xik, j 1; i 1 k 1 n
(2.9)
i 2, 3, ..., n
(2.10)
l
xik, j 1; j 1 k 1
j 2, 3,..., n
Depot n
x1,k j 1; j 2 n
xik,1 1; i 2
k 1, 2,..., l
(2.11)
k 1, 2, ..., l
(2.12)
Kekontinuan rute n
n
k 1, 2,..., l
i 2
i 2
u 1, 2, ..., n
xik,u xuk, j ;
(2.13)
Kapasitas n
n
qi xik, j Ck ; i 1 j 1
xik, j {0,1};
k 1, 2,..., l
i , j 1,2,...,n k 1,...l
Konsumen
Gambar 2 Contoh rute dalam Vehicle Routing Problem (VRP).
(2.14)
(2.15)
4
Fungsi objektif dari VRP (2.8) adalah meminimumkan total biaya perjalanan, dengan ci,j adalah biaya perjalanan dari konsumen i menuju konsumen j. Variabel keputusan
xik, j bernilai 1 jika rute dari
konsumen i menuju konsumen j dilayani oleh kendaraan k dan bernilai nol jika selainnya. Pada kendala (2.9) dan (2.10) dipastikan tepat satu kendaraan yang datang dan pergi dari konsumen i, sedangkan kendala (2.11) dan (2.12) memastikan bahwa tepat satu kendaraan yang pergi dan tiba di depot untuk satu rute. Kendala (2.13) memastikan kekontinuan rute dari setiap kendaraan yang beroperasi. Kendala (2.14) memastikan agar total permintaan (qi) pada satu rute tidak melebihi kapasitas kendaraan (Ck) yang beroperasi pada rute tersebut (Kritikos & Ioannou 2004). VRP adalah masalah optimisasi kombinatorial yang sulit, karena merupakan gabungan dari masalah kapasitas (packing problem) dan masalah rute kendaraan (traveling salesman problem). Pada VRP, hanya tipe masalah kecil dan sederhana yang dapat dicari solusi optimalnya. Hingga saat ini bila masalah VRP yang dihadapi relatif besar dan kompleks maka waktu yang dibutuhkan untuk mencari solusi optimal masalah tersebut relatif lama. Berdasarkan beberapa penelitian sebelumnya, nilai optimal dari fungsi objektif sulit untuk didapat dengan menggunakan exact algorithm (contohnya: branch and dan dynamic programming). bound Pendekatan exact algorithm dinyatakan tidak cukup baik untuk masalah yang dihadapi (VRP yang besar dan kompleks), sehingga dikembangkan metode heuristik sebagai salah satu alternatif untuk menyelesaikan masalah tersebut (Cordeau et al. 2002). 2.3. Vehicle Routing Problem with Time Windows (VRPTW) VRP dengan tambahan kendala waktu pelayanan disebut sebagai Vehicle Routing Problem with Time Windows (VRPTW). Kendala waktu adalah selang waktu tertentu sehingga setiap kendaraan dapat memberikan pelayanan pada konsumen. Biasanya selang waktu tersebut berbeda pada setiap konsumen (Hideki et al, 2006 dalam Kang et al, 2007). Dalam perkembangannya VRPTW dibagi menjadi Vehicle Routing Problem with Hard Time Windows (VRPHTW) dan Vehicle Routing Problem with Soft Time Windows (VRPSTW).
Dalam VRPHTW, konsumen hanya dapat dilayani selama selang waktu yang telah ditentukan. Sedangkan pada VRPSTW konsumen dapat dilayani setiap saat, tetapi bila melewati waktu yang ditentukan akan dikenakan biaya tambahan atau penalti (Kang. et al. 2007). Seperti halnya pada VRP, fungsi objektif bagi VRPTW adalah meminimalkan biaya perjalanan untuk semua kendaraan. Kendala yang digunakan pun sama seperti model VRP (2.9) - (2.15), tetapi perlu ditambahkan beberapa kendala yang berhubungan dengan time windows. Kendala tersebut, antara lain: k
t j ti fi ti , j M (1 xi , j );
(2.16)
i , j 2, 3,..., n; k 1, ..., l ; ai ti bi ; i 1, ..., n
(2.17)
ti 0; i 1,..., n
(2.18)
Kendala (2.16) memastikan waktu kedatangan kendaraan di konsumen j (tj) selalu lebih besar dari waktu kedatangan kendaraan di konsumen i (ti), dengan fi merupakan waktu service di konsumen i dan ti,j adalah waktu tempuh dari konsumen i menuju konsumen j, sedangkan M (disebut big-M) merupakan bilangan yang relatif besar, k sehingga jika M (1 xi , j ) besar maka rute dari i ke j tidak akan ditempuh dan sebaliknya. Kendala berikutnya (2.17) memastikan kedatangan kendaraan di konsumen i berada di antara selang waktu yang telah ditentukan, dengan batas awal ai dan batas akhir bi, sedangkan kendala terakhir (2.18) memastikan agar waktu kedatangan kendaraan ke setiap konsumen selalu positif (Larsen 1999). Pada penelitian ini akan digunakan VRPSTW, karena serupa dengan masalah yang ada di lapangan. 2.4 Metode Heuristik Penggunaan metode branch and bound untuk mencari solusi VRP yang memiliki banyak kota (lebih dari 50 kota) membutuhkan waktu komputasi yang lama. Alasan tersebut menjadi sebab dikembangkannya metode heuristik. Metode heuristik dapat memberikan solusi lebih cepat daripada metode branch and bound, tetapi tidak ada jaminan solusi yang dihasilkan optimal. Solusi dari metode heuristik didapat selain dengan cara trial and error juga dengan pendekatan secara intuitif (Winston 2004).
5
Dalam metode heuristik untuk masalah VRP dikenal adanya dua fase pendekatan untuk memecahkan masalah, yaitu route constructing sebagai fase pertama dan route improvement pada fase kedua. Pada penelitian ini metode nearest addition heuristic akan digunakan untuk mencari solusi pada fase pertama. Selanjutnya metode 2-opt, metode or-opt, metode relocate, metode exchange dan metode cross digunakan untuk memperbaiki solusi yang telah ada. 2.4.1 Nearest Addition Heuristic Metode nearest addition heuristic dimulai dengan menentukan banyaknya kendaraan yang tersedia di depot. Lokasi yang terdekat dengan depot akan dikunjungi pertama kali, kemudian lokasi yang dikunjungi selanjutnya adalah lokasi yang memiliki jarak terdekat dengan lokasi konsumen pertama, demikian seterusnya hingga kapasitas kendaraan atau time windows terpenuhi. Jika kapasitas kendaraan atau time windows telah dicapai maka kendaraan tersebut harus kembali ke depot. Kemudian jalankan kendaraan berikutnya dengan aturan yang sama seperti kendaraan pertama, sampai seluruh lokasi dikunjungi oleh kendaraan yang tersedia di depot. Algoritmenya sebagai berikut: 1) pandang kendaraan sebagai w, 2) mulai sebuah rute dari depot bagi kendaraan w, 3) temukan konsumen (v) yang terdekat dari posisi terakhir w. Jika tidak dimungkinkan untuk melakukan kunjungan tanpa melanggar kendala yang ada akhiri rute kendaraan w, pilih kendaraan lain dan lakukan lagi langkah 2. Jika masih terdapat konsumen yang belum dikunjungi maka gagal, 4) tambahkan depot pada akhir rute, 5) lakukan langkah 3. (ILOG, 2002). Solusi dari metode nearest addition dapat diperbaiki dengan heuristic menggunakan beberapa metode heuristik lainnya, antara lain: metode 2-opt, metode oropt, metode relocate, metode exchange dan metode cross. 2.4.2 Metode 2-opt Pada dasarnya metode 2-opt ialah memindahkan dua jalur pada rute yang ada, kemudian menghubungkan kembali jalur tersebut dengan pasangan konsumen yang berbeda. Sebagai catatan, metode 2-opt hanya
dapat dilakukan jika rute baru yang dihasilkan lebih baik daripada rute awal (Nilsson 2003). Algoritmenya, sebagai berikut: 1) pandang satu rute untuk satu kendaraan, 2) hapus 2 jalur yang menghubungkan 4 konsumen yang berbeda, cobalah untuk menghubungkan kembali keempat konsumen dengan pasangan yang berbeda, 3) jika biaya berkurang dan tidak melanggar kendala yang ada kembali ke langkah (2), 4) selesai. (ILOG, 2002).
Gambar 3 Contoh metode 2-Opt. Rute yang dihasilkan dapat disebut sebagai 2-optimal atau 2-opt, jika metode 2-opt digunakan pada setiap rute yang ada sampai tidak dimungkinkan lagi penggunaan metode tersebut. Metode or-opt identik dengan metode 2-opt, tetapi jumlah jalur yang dapat dihapus dan ditambahkan lebih dari 2 jalur. 2.4.3 Metode Relocate Pada metode relocate, sebuah tempat dalam satu rute dapat dipindahkan urutan kunjungannya. Dengan syarat biaya rute berkurang dan tidak melanggar kendala yang ada maka hal tersebut dapat dilakukan. Metode relocate ini dapat memindahkan sebuah kunjungan pada rute yang sama ke posisi yang berbeda. Seperti terlihat pada Gambar 4 dimana jalur yang ditempuh semula adalah (a0, a1), (a1, a2), (a2, b0) dan (b0, b1) berubah menjadi (a0, a2), (a2, b0), (b0, a1) dan (a1, b1).
Gambar 4 Contoh metode relocate pada satu rute. Metode relocate juga dapat memindahkan sebuah kunjungan dari satu rute dan menambahkan kunjungan tersebut ke rute lainnya. Seperti terlihat pada Gambar 5 dimana kunjungan menuju a1 yang semula berada pada rute (a0, a1), (a1, a2) dipindahkan ke rute (b0, b1). Metode tersebut merubah rute
6
yang ditempuh menjadi rute (a0, a2) dan rute (b0, a1), (a1, b1).
Gambar 6 Contoh metode exchange pada satu rute.
Gambar 5 Contoh metode relocate pada dua rute. 2.4.4 Metode Exchange Pada metode exchange, dua tempat dapat saling dipertukarkan urutan kunjungannya. Metode ini dapat diterapkan baik pada satu rute maupun dua rute kendaraan. Selama perubahan yang terjadi tidak melanggar kendala yang ada dan dapat mengurangi biaya yang dikeluarkan. Pada satu rute kendaraan, dua kunjungan yang berbeda dapat dipertukarkan urutannya. Dari Gambar 6 terihat bahwa metode exchange mempertukarkan kunjungan menuju a1 dan b1. Sehingga rute yang semula (a0, a1), (a1, a2), (a2, b0), (b0, b1) dan (b1, b2) berubah menjadi (a0, b1), (b1, a2), (a2, b0), (b0, a1) dan (a1, b2).
Metode exchange juga dapat di pergunakan pada dua rute kendaraan, seperti terlihat pada Gambar 7 dimana a1 dari rute (a0, a1), (a1, a2) dipertukarkan dengan b1 dari rute yang berbeda, (b0, b1), (b1, b2). Metode exchange ini merubah rute semula menjadi rute (a0, b1), (b1, a2) dan rute (b0, a1), (a1, b2).
Gambar 7 Contoh metode exchange pada dua rute. Kasus pada Gambar 7 disebut inter-route exchange. Sementara itu metode exchange yang diterapkan pada satu rute disebut intraroute exchange (Caric et al. 2008).
III METODE PENELITIAN 3.1 Waktu dan Lokasi Penelitian dilakukan di PT Nippon Indosari Corpindo (PT NIC), pada departemen Supply Chain Management (SCM). Kegiatan ini memakan waktu dua minggu, dimulai pada Senin, 27 Oktober sampai dengan Jumat, 7 November 2008. 3.2 Teknik Pengumpulan Data Kombinasi antara data sekunder dan data primer digunakan untuk mendukung kesempurnaan dari penelitian ini. Selain itu pengumpulan data melalui wawancara dengan pihak yang terkait juga dilakukan untuk memahami tentang proses distribusi pada perusahaan tersebut. 3.3 Ruang Lingkup Penelitian Dalam penelitian ini, pembahasan akan dibatasi pada proses distribusi untuk saluran retail/outlet (RO) di daerah Bekasi dan sekitarnya. Saluran RO dipilih karena jumlahnya yang terbesar dibandingkan dengan
saluran lain yang ada. Selain itu, saluran RO merupakan saluran yang memliki rantai distribusi paling pendek dibandingkan dengan saluran lain yang ada. 3.4. Pengolahan Data Setelah mendapatkan informasi yang dibutuhkan, penelitian dilanjutkan dengan memformulasikan masalah distribusi yang ada sebagai sebuah model VRP. Selanjutnya, digunakan program ILOG Dispatcher versi 2.1 dan ILOG Solver versi 4.4, yang dijalankan dalam Microsoft Visual C++ versi 6.0, sebagai alat untuk mencari solusi dari model VRP yang dihadapi. Data yang diperoleh dari kegiatan tersebut, antara lain: letak konsumen, permintaan konsumen dan waktu bongkar - muat di tempat konsumen. Sedangkan diasumsikan kecepatan kendaraan konstan, waktu buka tutup gudang konsumen adalah seragam yakni pada pukul 06.00 sampai dengan pukul 16.00,
7
dimana pukul 06.00 dimisalkan sebagai 0 dan pukul 16.00 sebagai 540 dan kendaraan mampu memuat hingga 200 crate (wadah roti). Langkah pertama adalah menentukan letak setiap konsumen dan mengetahui jarak dari setiap konsumen, seperti terlihat pada Lampiran 4. Nilai jarak setiap tempat didapat dengan melakukan estimasi, menggunakan bantuan peta dan benang kemudian akan diambil jarak terdekat setiap tempat. Langkah berikutnya, matriks jarak yang didapat dikonversi menjadi koordinat
Cartesius dengan menggunakan metode multidimensional scaling (MDS). Setelah didapat letak dari setiap titik, data tersebut menjadi input untuk program ILOG bersama dengan data permintaan dan waktu bongkarmuat di setiap tempat. Penggunaan metode nearest addition heuristic sebagai fase pertama dan metode 2-opt, or-opt, relocate dan exchange sebagai fase kedua dengan alat bantu ILOG akan digunakan sebagai langkah terakhir dalam penelitian ini.
IV IMPLEMENTASI VEHICLE ROUTING PROBLEM (VRP) PADA KEGIATAN DISTRIBUSI PRODUK DI PT NIPPON INDOSARI CORPINDO (PT NIC) Bab ini diawali dengan gambaran umum perusahaan tempat penelitian ini berlangsung, selain itu juga terdapat rumusan masalah yang dihadapi serta formulasinya secara matematis. Hasil dan pembahasan dari penelitian yang dilakukan terdapat pada bagian akhir bab ini. 4.1 Gambaran Umum Perusahaan PT Nippon Indosari Corpindo (PT NIC) adalah perusahaan yang bergerak dalam bidang pangan, khususnya industri pembuatan roti. Perusahaan ini didirikan pada tanggal 8 Maret 1995 dan mulai beroperasi pada Oktober 1996. PT NIC terletak dalam wilayah perindustrian Jababeka I Real Estate Cikarang, Bekasi, tepatnya berlokasi di Jl. Jababeka XII A Blok W 40-41 Cikarang, Bekasi 17530. Pada mulanya perusahaan tersebut hanya menjual empat jenis roti antara lain roti tawar dan tiga jenis roti manis, isi coklat, isi keju, dan isi strawberry dengan merek dagang “Sari Roti”. Produk Sari Roti yang dipasarkan hanya untuk memenuhi permintaan konsumen di daerah Cikarang, Bekasi dan sekitarnya. Dengan berjalannya waktu, PT NIC dapat mengembangkan pemasarannya hingga daerah Jabotabek. Selanjutnya, pada tahun 2003, PT NIC sudah mampu memperluas pemasarannya ke daerah Jawa Barat dan Semarang. Puncaknya, yaitu pembukaan depot di daerah Bandung yang berfungsi sebagai peyalur untuk daerah Jawa Barat. Saat ini PT NIC memproduksi tujuh jenis produk roti, antara lain: roti tawar, roti manis, roti krim, roti sobek, roti burger, roti hot dog, dan remah roti. PT NIC mendistribusikan produk rotinya melalui 56% jaringan distribusi modern
seperti hypermarket, supermarket dan minimarket, sementara itu 44% sisanya didistribusikan melalui jaringan tradisional seperti agen dan stock point. 4.1.1 Divisi Distribusi PT NIC menggunakan jasa pihak ketiga, dalam hal ini perusahaan ekspedisi, yang transporter, untuk disebut sebagai mendistribusikan produk ke konsumen. Masing–masing transporter menyewakan kendaraan, driver dan helper pada PT NIC untuk mendistribusikan produk ke konsumen. Setiap transporter dikepalai oleh koordinator, karyawan dari perusahaan ekspedisi, yang bertanggung jawab untuk memastikan ketersediaan kendaraan, driver, dan helper pada setiap pengiriman. Koordinator sendiri bertanggung jawab pada distribution officer, yang merupakan karyawan PT NIC. Pembagian tugas pada level distribution officer didasarkan pada daerah pengiriman, yakni daerah pusat-Bogor, daerah selatan, daerah barat, dan daerah timur - utara. Setiap distribution officer bertanggung jawab untuk seluruh saluran pada daerah pengiriman yang telah ditentukan. Lebih jelas tentang struktur departemen SCM, dapat dilihat pada Lampiran 1. 4.1.2 Kegiatan Distribusi Kegiatan distribusi pada PT NIC dibagi dalam lima rute saluran yang memiliki karakteristik yang berbeda satu sama lain. Lima saluran distribusi, yaitu: agen, stock point (SP), distribution center (DC), retail/outlet (RO) dan institusi. Pada saluran agen dan SP, pengiriman produk dilakukan pada sore hari, antara pukul
8
16.00-17.00. Transporter mengirim produk langsung ke agen yang ada, kemudian agen akan membagi produk yang dikirim tadi ke sejumlah tricycle yang ada. Selanjutnya tricycle tersebut akan dibawa oleh hawker sesuai rute masing-masing untuk langsung menemui konsumen. Proses di SP berbeda dengan agen, setelah produk sampai di SP kemudian SP akan membagikan produk ke sejumlah sepeda motor yang ada. Kemudian sepeda motor tersebut akan meletakkan produk di warung warung yang memesan sebelum sampai ke tangan konsumen. Agen dan SP biasanya terletak di sekitar perumahan padat penduduk. Proses pada saluran DC berbeda dengan agen dan SP. Pada saluran DC pengiriman dilakukan dua kali sehari yakni pada pukul 05.00 - 06.00 dan 10.00-11.00. Transporter hanya mengirim ke DC yang telah ditunjuk, kemudian produk akan dikirimkan sendiri oleh pihak pengelola DC ke tempat yang telah ditentukan. Saluran DC terdiri dari: Alfamart, Indomart dan Alfamidi. Saluran untuk Carrefour, Giant, Makro dan beberapa pasar swalayan lainnya masuk dalam saluran RO. Pada saluran ini, produk dikirim langsung dari produsen ke RO yang ada. Berbeda dengan saluran DC, pada saluran RO transporter bahkan mengatur produk pada tempat yang telah tersedia. Pengiriman dilakukan pada pukul 06.00 - 07.00 setiap harinya. Pada saluran institusi, pemesanan dilakukan oleh perusahaan lain untuk keperluan perusahaan tersebut, misalnya sarapan karyawan. Waktu pengirimannya dilakukan bersamaan dengan waktu pengiriman saluran RO. Bagan pada Lampiran 2 memberikan gambaran tentang alur kegiatan distribusi secara lebih jelas. 4.1.3 Kegiatan pada saluran distribusi RO Penelitian ini akan dibatasi pada saluran RO di daerah Bekasi dan sekitarnya. Pada diagram alir yang terdapat di Lampiran 3, konsumen memberikan pesanan atau purchase order (PO) kepada bagian penjualan, sales Selanjutnya sales administrator. administrator akan membuat surat jalan atau delivery note (DN) yang berisi jumlah produk dan daftar konsumen yang memesan produk tersebut. Selain membuat DN, sales administrator juga membuat faktur penjualan (FP) yang berisi total harga yang harus dibayar oleh konsumen untuk produk yang dipesan. Kemudian kedua dokumen tersebut yaitu DN dan FP akan diserahkan kepada
pegawai pada bagian pergudangan, disebut sebagai warehouse operator. Kemudian warehouse operator akan menyiapkan produk sesuai dengan DN yang telah diberikan oleh sales administrator. Setelah memastikan produk sesuai dengan DN, driver dan helper dengan bantuan karyawan bagian pergudangan akan memeriksa kembali banyaknya produk yang akan dikirim dan jumlah crate (wadah roti) yang akan dibawa pada pengiriman kali ini, kegiatan tersebut dinamakan proses loading. Sesampai di tempat tujuan, driver dan helper memindahkan produk menuju gudang konsumen dan kembali memeriksa jumlah barang yang dikirim, disaksikan oleh perwakilan dari pihak konsumen. Setelah melewati tahap pemeriksaan tersebut helper menata produk di tempat yang telah disediakan, sedangkan driver mengurus penandatanganan DN dan FB oleh pihak konsumen. Selain itu driver juga menerima bukti terima barang dari pihak konsumen serta nota penarikan barang (NPB), sekaligus dengan produk yang mengalami pengembalian bila ada. Setelah driver dan helper mengunjungi seluruh konsumen yang ada pada DN, selanjutnya kembali ke pabrik untuk melakukan proses unloading. Pada proses ini, dilakukan pemeriksaan terhadap kelengkapan dokumen (seperti DN, FP dan NPB), kesesuaian banyaknya crate dan juga kesesuaian produk yang mengalami pengembalian dengan dokumen yang ada. 4.2. Perumusan Masalah Perusahaan memproduksi sejumlah roti setiap harinya, kemudian produk tersebut akan didistribusikan ke sejumlah konsumen (retail/outlet) yang ada – dalam karya ilmiah ini jumlah konsumennya sebanyak 24. Konsumen dinyatakan sebagai n dengan n= 1 menyatakan depot. Banyaknya permintaan setiap RO telah diketahui sebelumnya, baik jenis maupun jumlahnya. Pendistribusian akan dilakukan dengan menggunakan tiga kendaraan sejenis, sehingga kapasitas untuk setiap kendaraan seragam. Setiap kendaraan akan memulai kegiatan distribusinya dari depot. Selain melakukan pengiriman produk, driver dan helper juga melakukan bongkar muat dan mengatur produk pada tempat yang telah disediakan, disebut delay. Biaya tetap kendaraan akan muncul bila kendaraan tersebut dipakai dalam kegiatan distribusi. Masalah yang dihadapi adalah meminimumkan banyaknya kendaraan yang
9
digunakan dengan mempertimbangkan kendala kapasitas pada kendaraan dan untuk memenuhi setiap permintaan RO. Beberapa asumsi yang digunakan, antara lain: semua pesanan konsumen dapat dipenuhi oleh pabrik, kecepatan kendaraan konstan sehingga tidak ada satu pun yang dapat mempercepat atau memperlambat kecepatan kendaraan. Kendaraan yang digunakan seragam, sehingga setiap kendaraan mempunyai kapasitas yang sama. Biaya bila kendaraan digunakan (fixed cost) dan biaya setiap kilometer telah diketahui. 4.3 Formulasi Masalah Variabel Keputusan
25
3
j 1
k 1
x
x
1; k 1, 2, 3
(4.4)
1; k 1, 2, 3
(4.5)
Kekontinuan rute 25 k 1, 2,3 xik,u xuk, j ; u 1, 2,..., 25 i 2 i2 Kapasitas
(4.6)
k 1, j
j 2 25
x
k i ,1
i 2
25
25
q x i
i 1
k i, j
C ; k 1, 2, 3 i , j 1, 2,..., 25
xik, j z k ;
k 1, 2,3 i , j 1, 2,..., 25
vk tik, j d i , j ;
Konstanta qi banyaknya permintaan konsumen i C kapasitas maksimum kendaraan yang dibutuhkan dari konsumen k ti , j waktu i ke konsumen j dengan kendaraan k
Eliminasi sub-tour
d i , j d j ,i ;
x
k i, j
iF
k 1, 2,3
i , j 1, 2,..., 25
25
F L : 2 F i 1
25
x
k i, j
;
ci , j
biaya perjalanan dari konsumen i ke konsumen j
Time windows ai ti bi ; i 1, 2,..., 25
vk
kecepatan rata-rata kendaraan k
wk
biaya tetap (fixed cost) bila kendaraan k digunakan waktu buka gudang pada konsumen i
ti fi tik, j M (1 xik, j ) t j ;
fi
Fungsi Objektif 3
minZ wk z k k 1
25
25
x i 1 j 1
k i, j i, j
c
(4.1)
Kendala-kendala
Konsumen 25
3
i 1
k 1
x
k i, j
1; j 2,3,..., 25
(4.2)
(4.10)
z k {0,1};
xik, j {0,1};
(4.11)
j 1
k 1, 2,3
L
(4.9)
| F | 1;
jarak dari konsumen i ke konsumen j
waktu kedatangan pada konsumen i himpunan semua konsumen termasuk depot Lama waktu servis di konsumen i
(4.8)
jF
di , j
waktu tutup gudang pada konsumen j
(4.7)
j 1
1, jika kendaraan k dioperasikan zk 0, jika selainnya
ai bi ti
(4.3)
Depot 25
25
1, jika konsumen j dikunjungi k xi , j setelah konsumen i oleh kendaraan k 0, jika selainnya
1; i 2,3,..., 25
k i, j
i, j 1,2,...,25 k 1,2,3
k 1, 2, 3
k 1, 2,3 i, j 1, 2,..., 25
(4.12) (4.13) (4.14) (4.15)
Fungsi objektif (4.1) pada model di atas adalah meminimumkan banyaknya kendaraan yang digunakan dan meminimumkan jarak tempuh kendaraan. Kendala (4.2) dan (4.3) memberikan kepastian bahwa setiap konsumen yang ada akan dilayani oleh tepat satu kendaraan. Kendala (4.4) dan (4.5) akan memastikan tersedianya kendaraan untuk melayani rute yang ada dan untuk memastikan kendaraan berangkat dan kembali dari depot. Pada kendala (4.6) akan dipastikan kontinuitas rute kendaraan artinya memastikan bahwa kendaraan yang masuk ke suatu kota harus
10
meninggalkan kota tersebut, sedangkan kendala (4.7) menggambarkan bahwa jumlah permintaan untuk satu rute tidak melebihi kapasitas kendaraan yang beroperasi. Selanjutnya, pada kendala (4.8) dipastikan bahwa tidak akan ada konsumen yang dilayani oleh kendaraan yang tidak aktif. Kendala (4.9) memperlihatkan hubungan antara jarak, yaitu kecepatan dan waktu tempuh kendaraan, jarak dan waktu tempuh berbanding lurus. Kendala (4.10) menunjukkan bahwa jarak dari i ke j sama dengan jarak dari j ke i, sedangkan kendala (4.11) memastikan tidak ada sub-tour pada model yang ada. Berikutnya, kendala (4.12) dan (4.13) berkaitan dengan waktu pelayanan. Pada kendala (4.12) dipastikan waktu kedatangan kendaraan di tempat konsumen berada di antara waktu buka dan tutup gudang. Kendala (4.13) memastikan kendaraan akan berada di j pada saat kendaraan berangkat dari i ditambah dengan waktu servis pada i dan waktu tempuh dari i ke j, sedangkan M (big-m) merupakan bilangan yang relatif besar jika M (1 xi , j ) k
bernilai besar maka rute konsumen i ke konsumen j tidak akan ditempuh dan sebaliknya. Kendala (4.14) dan (4.15) menunjukkan bahwa zk dan
xik, j merupakan
variabel keputusan yang bernilai 0 dan 1. 4.4 Hasil dan Pembahasan Pada subbab ini akan diperlihatkan hasil dari masalah yang dihadapi, kemudian hasil tersebut akan dibandingkan dengan keadaan yang terjadi di lapangan saat ini. Masalah VRP yang dihadapi dapat dicari solusinya dengan menggunakan exact method dan metode heuristik. Penggunaan exact method untuk masalah VRP yang dihadapi tidak cukup baik karena dibutuhkan waktu yang relatif lama untuk mendapatkan solusi
Kode 0 1 4 0
optimalnya. Oleh karena itu, dikembangkan metode heuristik sebagai salah satu alternatif untuk menyelesaikan masalah VRP yang dihadapi secara lebih cepat. Metode heuristik yang digunakan dalam penelitian ini dibagi menjadi dua fase. Fase pertama adalah route construction yang menggunakan nearest addition heuristic untuk mencari solusi fisibel awal dari masalah VRP yang dihadapi. Fase berikutnya adalah route improvement dimana solusi awal yang telah ada diperbaiki menggunakan beberapa metode heuristik lainnya, yakni metode 2-Opt, or-Opt, relocate, exchange, dan cross. Input dari masalah yang akan diselesaikan menggunakan kedua fase heuristik terdapat pada Lampiran 8. Lampiran tersebut merupakan input bagi program yang akan digunakan. Isi dari input tersebut berupa banyaknya konsumen yang akan dikunjungi, banyaknya kendaraan yang tersedia dan kapasitas maksimum dari kendaraan yang digunakan, selain itu terdapat juga kode, jumlah permintaan, waktu buka-tutup gudang dan letak setiap konsumen. Dibutuhkan waktu 0,32 detik untuk memberikan solusi dari masalah VRP dengan menggunakan software ILOG Dispatcher versi 2.1 dan ILOG Solver versi 4.4 yang dijalankan menggunakan Microsoft Visual C++ versi 6.0 yang dioperasikan pada komputer dengan prosessor Intel Celeron 2.53 GHz (Giga Hertz) dan memori sebesar 512 MB (Megabyte). Output dari masalah VRP yang diselesaikan menggunakan software tersebut dapat dilihat pada Lampiran 10. Tabel 1, Tabel 2 dan Tabel 3 merupakan rangkaian rute yang dihasilkan dengan menggunakan metode heuristik dua fase yang telah dijelaskan sebelumnya dan masingmasing tabel merepresentasikan satu kendaraan.
Tabel 1 Hasil simulasi untuk kendaraan pertama Jarak Nama tempuh (kilometer) PT NIC 0 HARI-HARI BEKASI TRADE CENTRE 9,1988 PT CONTIMAS UTAMA IND. (BLUE MALL) 11,1864 PT NIC 22,2157
Permintaan (crate) 0 17 17 0
11
Kode 0 3 5 2 11 12 13 15 22 23 6 0
Kode 0 9 8 7 10 14 16 17 24 21 20 19 18 0
Tabel 2 Hasil simulasi untuk kendaraan kedua Jarak Nama tempuh (kilometer) PT NIC 0 LION SUPERINDO BOROBUDUR BEKAS 11,0671 CARREFOUR BEKASI SQUARE 13,6437 MITRA WISMA ASRI 17,1940 CV NAGA SWALAYAN (Pondok Ungu) 21,5975 GIANT UJUNG MENTENG 25,2667 CARREFOUR CAKUNG 26,7864 GIANT PONDOK KOPI SPM 34,4373 GIANT KALIMALANG 38,7833 SUPER INDO PONDOK BAMBU 39,5013 HERO KEMANG PRATAMA 49,7469 PT NIC 61,9235
Tabel 3 Hasil simulasi untuk kendaraan ketiga Jarak Nama tempuh (kilometer) PT NIC 0 MAKRO BEKASI 2 13,2558 LION SUPERINDO METROPOLITAN MALL 13,6606 GIANT HYPERMARKET BEKASI 13,9787 HARI-HARI BEKASI CYBER PARK 15,8856 LION SUPERINDO KALIMALANG BEKASI 17,3783 GIANT JATI BENING 21,7282 STAR MART PERSADA GOLF 23,8137 YOGYA PONDOK BAMBU TOSERBA 24,8556 TIP-TOP PONDOK BAMBU 25,2290 CV NAGA SWALAYAN (Jatiwaringin) 25,5493 GIANT PONDOK GEDE 28,7049 TIP-TOP PONDOK GEDE 32,3982 PT NIC 52,2495
Dari ketiga tabel di atas, terlihat bahwa dibutuhkan tiga kendaraan untuk melayani seluruh konsumen. Pada kendaraan pertama rute yang dilalui meliputi depot, konsumen ke-1, konsumen ke-4 dan kembali ke depot, dengan total jarak yang ditempuh sepanjang 22,2157 kilometer dan banyaknya produk yang dibawa sebanyak 25 crate. Sedangkan pada kendaraan kedua, rute yang ditempuh meliputi depot, konsumen ke3, konsumen ke-5, konsumen ke-2, konsumen ke-11, konsumen ke-12, konsumen ke-13, konsumen ke-15, konsumen ke-22, konsumen ke-23 dan konsumen ke-6 sebelum kembali ke depot. Kendaraan kedua menempuh 61,9235 kilometer dan memuat sebanyak 153 crate pada pengirimannya.
Permintaan (crate) 0 7 8 3 37 16 12 15 18 25 12 0
Permintaan (crate) 0 2 17 19 19 22 9 4 18 37 18 18 11 0
Lain halnya dengan kendaraan ketiga, kendaraan ini menempuh perjalanan sepanjang 52,2495 kilometer untuk menyelesaikan satu rute yang dijadwalkan. Rute tersebut meliputi depot, konsumen ke-9, konsumen ke-8, konsumen ke-7, konsumen ke-10, konsumen ke-14, konsumen ke-16, konsumen ke-17, konsumen ke-24, konsumen ke-21, konsumen ke-20, konsumen ke-19 dan konsumen ke-18 sebelum kembali ke depot, dengan membawa 194 crate dari maksimum 200 crate yang dapat dibawa dalam satu kali pengiriman. Total perjalanan yang ditempuh oleh ketiga kendaraan tersebut adalah 136,388 kilometer.
12
The Simulation Route 10 0 18
5 19 1 3
0 Miles kilometer
4 5
6 9 87
16
10
17
14
20 21 24
23 22
15
2 -5 11
Kendaraan pertama -10
Kendaraan kedua
12 13
Kendaraan ketiga
-15 -15
-10
-5
0
5
10
Miles
kilometer
Gambar 8 Rute hasil simulasi. Hasil simulasi di atas kemudian dibandingkan dengan data lapangan yang diamati penulis.
Kode 0 16 20 23 22 21 24 19 11 18 0
Tabel 4, Tabel 5 dan Tabel 6 merupakan rute kendaraan saat ini yang melayani 24 konsumen.
Tabel 4 Rute saat ini untuk kendaraan pertama Jarak Nama tempuh (kilometer) PT NIC 0 GIANT JATI BENING 19,3245 CV NAGA SWALAYAN (Jatiwaringin) 22,2676 SUPER INDO PONDOK BAMBU 24,7295 GIANT KALIMALANG 25,4476 TIP-TOP PONDOK BAMBU 28,3478 YOGYA PONDOK BAMBU TOSERBA 28,7212 GIANT PONDOK GEDE 32,3667 CV. NAGA SWALAYAN (Pondok Ungu) 49,0934 TIP-TOP PONDOK GEDE 63,1134 PT NIC 82,9648
Permintaan (crate) 0 9 18 25 18 37 18 18 37 11 0
13
Kode 0 15 13 12 2 3 14 10 0
Kode 0 4 1 7 6 5 8 9 17 0
Tabel 5 Rute saat ini untuk kendaraan kedua Jarak Nama tempuh (kilometer) PT NIC 0 GIANT PONDOK KOPI SPM 21,0275 CARREFOUR CAKUNG 28,6783 GIANT UJUNG MENTENG 30,1981 MITRA WISMA ASRI 38,2426 LION SUPERINDO BOROBUDUR BEKAS 42,6166 LION SUPERINDO KALIMALANG BEKASI 49,1501 HARI-HARI BEKASI CYBER PARK 50,6427 PT NIC 65,0334
Tabel 6 Rute saat ini untuk kendaraan kedua Jarak Nama tempuh (kilometer) PT NIC 0 PT CONTIMAS UTAMA IND. (BLUE MALL) 11,0293 HARI-HARI BEKASI TRADE CENTRE 13,0169 GIANT HYPERMARKET BEKASI 17,5612 HERO KEMANG PRATAMA 19,3132 CARREFOUR BEKASI SQUARE 22,6542 LION SUPERINDO METROPOLITAN MALL 24,9801 MAKRO BEKASI 2 25,3849 STAR MART PERSADA GOLF 34,5364 PT NIC 55,9374
Data di atas memperlihatkan bahwa dibutuhkan sebanyak tiga kendaraan untuk melayani seluruh konsumen. Kendaraan pertama akan menempuh jarak sepanjang 82,9648 kilometer dan membawa 191 crate dari 200 crate yang dapat dibawa. Kendaraan pertama melayani rute depot, konsumen ke16, konsumen ke-20, konsumen ke-23, konsumen ke-22, konsumen ke-21, konsumen ke-24, konsumen ke-19, konsumen ke-11, konsumen ke-18 dan kembali ke depot. Rute untuk kendaraan kedua meliputi depot, konsumen ke-15, konsumen ke-13, konsumen ke-12, konsumen ke-2, konsumen
Permintaan (crate) 0 15 12 16 3 7 22 19 0
Permintaan (crate) 0 17 17 19 12 8 17 2 4 0
ke-3, konsumen ke-14 dan konsumen ke-10 sebelum kembali ke depot. Dengan membawa 94 crate dan menempuh jarak sepanjang 65,0334 kilometer untuk rute tersebut. Rute berikutnya, untuk kendaraan ketiga, dijadwalkan akan membawa sebanyak 96 crate dan menempuh perjalanan sepanjang 55,9374 kilometer. Rute tersebut meliputi depot, konsumen ke-4, konsumen ke-1, konsumen ke-7, konsumen ke-6, konsumen ke-5, konsumen ke-8, konsumen ke-9 dan konsumen ke-17 sebelum kembali ke depot. Total jarak tempuh tiga kendaraan adalah 203,935 kilometer.
14
Current Route 10 0 18
5 19 1
4 5 3
Miles kilometer
0
6 9 87
16
10
17
14
20 21 24
23 22
15
2 -5 11
Kendaraan pertama -10
Kendaraan kedua
12 13
Kendaraan ketiga
-15 -15
-10
-5
0
5
Miles kilometer
Gambar 9 Rute saat ini. Tabel 7 memberikan perbandingan antara hasil simulasi (pada Tabel 1, Tabel 2 dan Tabel 3) dengan kondisi rute yang saat ini (pada Tabel 4, Tabel 5 dan Tabel 6).
Perbandingan tersebut meliputi muatan yang dibawa oleh masing-masing kendaraan dan total jarak yang ditempuh oleh setiap kendaraan.
Tabel 7 Perbandingan muatan kendaraan hasil simulasi dan kendaraan yang beroperasi saat ini Kapasitas Muatan Jarak Tempuh max (crate) (kilometer) (crate) Keadaan saat ini Kendaraan ke-1 191 (95,5%) 200 82,9648 Kendaraan ke-2 94 (47,0%) 200 65,0334 Kendaraan ke-3 96 (48,0%) 200 55,9374 Hasil Simulasi Kendaraan ke-1 34 (17,0%) 200 22,2157 Kendaraan ke-2 153 (76,5%) 200 61,9235 Kendaraan ke-3 194 (97,0%) 200 52,2495 Dari Tabel 7 dapat disimpulkan bahwa masing-masing rute pada hasil simulasi memiliki jarak tempuh yang lebih pendek dibandingkan dengan rute yang ditempuh oleh kendaraan pada saat ini. Pada hasil simulasi
total jarak yang ditempuh ketiga kendaraan adalah 136,388 kilometer, sedangkan total jarak pada ketiga kendaraan saat ini adalah 203,935 kilometer. Dengan kata lain, total jarak yang ditempuh pada hasil simulasi
10
15
mencapai 66,88% dari total jarak yang ditempuh kendaraan saat ini. Sementara itu banyaknya produk yang dibawa oleh kendaraan kedua dan ketiga pada hasil simulasi lebih besar dibandingkan dengan banyaknya barang yang dibawa oleh
kendaraan kedua dan ketiga saat ini. Persentase kedua kendaraan tersebut mencapai 76,5% dan 97%, sedangkan pada kendaraan yang beroperasi saat ini persentase muatan pada kendaraan kedua dan ketiga sebesar 47% dan 48%.
V SIMPULAN DAN SARAN 5.1 Kesimpulan 1. Masalah penentuan rute untuk distribusi barang (VRP) dapat diformulasikan sebagai masalah Integer Linear Programming. 2. Masalah penentuan rute untuk distribusi barang (VRP) dapat diselesaikan dengan menggunakan metode heuristik, pada penelitian ini menggunakan metode nearest addition heuristic. 3. Hasil simulasi menggunakan metode heuristik memperoleh hasil yang lebih baik daripada kondisi yang ada sekarang, karena total jarak tempuh menjadi lebih pendek.
5.2 Saran Beberapa hal yang dapat dilakukan agar penelitian ini lebih baik terkait dengan implementasinya di lapangan, antara lain: 1. Jarak antar tempat dapat dibuat serealistis mungkin, karena jarak antar tempat yang terdapat pada matriks jarak merupakan hasil estimasi. 2. Waktu bongkar-muat di konsumen dapat diestimasi dengan cara yang lebih baik. Misalnya dengan melakukan beberapa kali pengamatan terhadap waktu bongkar-muat di setiap konsumen, kemudian gunakan rata-rata waktu tersebut sebagai input.
DAFTAR PUSTAKA Caric T, Galic A, Fosin J, Gold H, Reinholz. 2008. A Modelling and Optimization Framework for Real-World Vehicle Routing Problem. Vehicle Routing Problem: 142, I-Tech, Vienna, Austria. Cordeau J-F, Gendreau M, Laporte G, Potvin JY, Semet F. 2002. A Guide to Vehicle Routing Heuristics. Journal of Operation Research Society 53: 512-522. Hoffman K, Padberg M. 2009. Traveling Salesman Problem. http://iris.gmu.edu/ ~khoffman/papers/trav_salesman.html. [8 Feb 2009]. Kritikos MN, Ioannou G. 2004. A synthesis of assignment and heuristic solutions for vehicle routing with time windows. Journal of the Operational Research Society 55: 2–11. Kang HK, Byung KL, Yoon HL, Young HL. 2007. A Heuristic for the vehicle routing problem with due times. Computers and Industrial Engineering 54: 421-431.
Laporte G, Boctor F, Renaud J, Prive J. 2006. Solving a vehicle-routing problem arising in soft-drink distribution. Journal of Operation Research Society 57: 10451052. Larsen J. 1999. Vehicle Routing with Time Windows- Finding optimal solution efficiently. Machado P, Tavares J, Pereira BF, Costa E. 2002. Vehicle Routing Problem: Doing it The Evolution Way. Nilsson C. 2003. Heuristics for the Traveling Salesman Problem. Sutapa NI, Widyadana AGI, Christine. 2003. Studi tentang Traveling Salesman Problem dan Vehicle Routing Problem dengan Time windows. Jurusan Teknik Industri, Universitas Petra, Surabaya. ILOG. 1999. User’s Manual ILOG Dispatcher 2.1. France: ILOG Winston WL. 2004. Operation Research Applications and Algorithms. Ed ke-4. Belmont, California: Brooks/ColeThompson Learning.
16
LAMPIRAN
17
Lampiran 1 Struktur organisasi pada departemen supply chain managment
18
Lampiran 2 Saluran distribusi yang ada
P R O
K Agen
hawker
Stock Point (SP)
Motor
D U
Retail/outlet (RO)
N
warung
N S U M
S E
O
Distribution Center (DC) Institusi
E N
19
Lampiran 3 Diagram alir pada saluran distribusi retail/outlet Purcahased Order (PO)
Konsumen
Sales admin
-
-
Delivery note (DN) Faktur penjualan PO
F P (stempel, ttd) D N (stempel, ttd) Check product Display -
Warehouse Operator -
DN Faktur penjualan (FP) PO Product/ roti & crate
loading Divisi Distribusi Driver & helper
-
DN Sisa stock/ titipan (bila ada) Nota penarikan barang Product/ roti BS & crate
unloading
Bukti Terima Barang Sisa Stock/ titipan (bila ada) Nota Penarikan Barang Product/ Roti BS & Crate
20
Lampiran 4 Beberapa gambar:
Pemisahan permintaan
Kendaraan saat loading
21
Memasukkan pesanan ke mobil-box
Penghitungan roti
22
Sisa roti
Crate kosong saat unloading
23
Lampiran 5 Matriks Jarak
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 0.00 11.52 18.24 14.16 12.48 13.08 18.00 13.92 13.44 15.12 15.12 20.76 22.68 24.24 16.32 1 0.00 6.72 2.64 1.56 2.16 6.00 4.32 4.32 4.56 5.88 11.40 13.32 14.88 7.08 2 0.00 4.32 8.28 8.88 10.44 6.60 6.60 7.56 7.92 7.56 9.48 11.04 9.12 3 0.00 1.80 1.56 4.92 4.56 4.32 3.36 6.00 8.88 10.80 12.36 7.20 4 0.00 0.60 4.44 2.76 2.76 3.00 4.32 9.84 11.76 13.08 5.40 5 0.00 3.84 2.16 2.16 2.40 3.72 9.24 11.16 12.48 4.92 6 0.00 4.08 3.84 2.88 5.52 10.92 12.84 14.40 6.72 7 0.00 0.24 1.20 1.68 6.84 8.76 10.32 2.88 8 0.00 0.96 1.68 7.08 9.00 10.56 2.88 9 0.00 2.64 8.04 9.96 11.52 3.84 10 0.00 8.52 10.44 12.00 1.20 11 0.00 1.92 3.48 7.32 12 0.00 1.56 9.24 13 0.00 10.80 14 0.00 15 16 17 18 19 20 21 22 23 24
15 22.08 12.84 11.64 9.96 10.08 9.48 11.40 7.32 7.56 8.52 6.96 8.16 5.16 6.48 5.76 0.00
16 19.01 12.48 13.56 15.12 10.92 10.32 10.80 6.96 6.96 7.92 5.28 10.08 11.04 12.60 4.08 5.88 0.00
17 20.76 13.92 16.44 15.84 12.00 11.64 14.64 9.60 9.60 10.56 8.40 13.56 12.00 11.52 6.72 6.36 3.84 0.00
18 23.33 13.32 17.28 9.72 11.76 11.16 8.88 9.96 9.72 8.76 9.60 14.40 20.78 21.67 8.40 10.20 4.32 8.16 0.00
19 23.40 17.47 17.35 17.59 15.91 15.31 12.36 13.27 13.27 12.24 11.59 17.83 16.03 17.11 10.39 11.71 5.83 6.36 3.48 0.00
20 21.72 14.35 16.39 14.47 12.79 12.19 13.99 10.15 10.15 11.11 8.47 14.71 12.91 13.99 7.27 7.75 6.55 5.28 6.60 3.12 0.00
21 22.80 14.47 16.51 12.48 10.80 10.20 14.11 10.27 10.27 11.23 8.59 14.95 13.03 14.04 7.39 9.43 6.67 6.36 7.68 4.20 1.08 0.00
22 24.19 11.88 13.92 12.00 10.32 9.72 11.52 7.68 7.68 8.64 6.00 12.36 10.44 11.52 4.80 5.28 4.08 1.92 9.07 5.59 2.47 2.59 0.00
23 23.64 12.43 14.47 12.55 10.87 10.27 12.07 8.23 8.23 9.19 6.55 12.91 10.99 12.07 5.35 5.83 4.63 2.47 8.52 5.04 1.92 2.04 0.55 0.00
24 22.32 13.99 16.03 14.11 12.43 11.83 13.63 9.79 9.79 10.75 8.11 14.47 12.55 13.56 6.91 7.39 6.19 5.88 7.20 3.72 0.60 0.48 2.11 1.56 0.00
24
Lampiran 6 Data No
Nama Tempat
Permintaan (crate)
Waktu bongkar-muat (menit)
0
PT. NIC
1
HARI-HARI BEKASI TRADE CENTRE
17
38
2
MITRA WISMA ASRI
3
7
3
LION SUPERINDO BOROBUDUR BEKAS
7
34
4
PT.CONTIMAS UTAMA IND. (BLUE MALL)
17
69
5
CARREFOUR BEKASI SQUARE
8
91
6
HERO KEMANG PRATAMA
12
37
7
GIANT HYPERMARKET BEKASI
19
28
8
LION SUPERINDO METROPOLITAN MALL
17
41
9
MAKRO BEKASI 2
2
32
10
HARI-HARI BEKASI CYBER PARK
19
15
11
CV. NAGA SWALAYAN (Pondok Ungu)
37
69
12
GIANT UJUNG MENTENG
16
42
13
CARREFOUR CAKUNG
12
54
14
LION SUPERINDO KALIMALANG BEKASI
22
21
15
GIANT PONDOK KOPI SPM
15
18
16
GIANT JATI BENING
9
47
17
STAR MART PERSADA GOLF
4
8
18
TIP-TOP PONDOK GEDE
11
60
19
GIANT PONDOK GEDE
18
35
20
CV. NAGA SWALAYAN (Jatiwaringin)
18
20
21
TIP-TOP PONDOK BAMBU
37
81
22
GIANT KALIMALANG
18
58
23
SUPER INDO PONDOK BAMBU
25
66
24
YOGYA PONDOK BAMBU TOSERBA
18
73
25
Lampiran 7 Input Berupa file .dat yang berisi sebagai berikut: 24 5 200 1 0
540
-13.6310
8.6950
1
17
0
540
38
-7.0298
2.2886
2
3
0
540
7
-6.6594
-4.2273
3
7
0
540
34
-6.6025
0.1463
4
17
0
540
69
-5.1493
1.6448
5
8
0
540
91
-4.5309
-1.3859
6
12
0
540
37
-3.5825
1.8177
7
19
0
540
28
-3.0148
0.1602
8
17
0
540
41
-3.1175
0.4612
9
2
0
540
32
-2.9581
0.8333
10
19
0
540
15
-1.3809
1.1434
11
37
0
540
69
-3.2144
-6.9702
12
16
0
540
42
-0.7663
-9.7032
13
12
0
540
54
-0.1513
-11.0930
14
22
0
540
21
-0.0748
0.4208
15
15
0
540
18
3.0291
-4.1345
16
9
0
540
47
4.1974
1.2394
17
4
0
540
8
6.1911
0.6274
18
11
0
540
60
5.6338
3.9049
19
18
0
540
35
9.3217
4.1036
20
18
0
540
20
7.0661
1.8967
21
37
0
540
81
6.8457
1.6644
22
18
0
540
58
6.2007
-1.1632
23
25
0
540
66
6.4034
-0.4744
24
18
0
540
73
6.9748
1.314
26
Lampiran 8 Proses Source code yang digunakan sebagai berikut: #include
#include #if defined(ILUSESTL) #include #include #include <string> #else #include #include #include <string.h> #endif ILCSTLBEGIN void Info(IlcManager m, IlcRoutingPlan plan, char * problem) { //////////////////////////////////////////////////////// // informasi aja //////////////////////////////////////////////////////// m.printInformation(); plan.printInformation(); m.out() << "===============" << endl << "Problem name : " << problem << endl // nama permasalahan << "Cost : " <=2) problem = argv[1]; else problem = (char *) "E:/ta/prognya/code/coba/vrp/cost on vehicle/vrp20_1_1_1.dat"; infile.open(problem); if (!infile) { m.out() << "File not found or not specified: " << problem << endl; #if defined(ILCLOGFILE) m.closeLogFile(); #endif m.end(); return 0; } IlcInt nbOfVisits, nbOfTrucks; infile >> nbOfVisits >> nbOfTrucks;
27
IlcFloat capacity; infile >> capacity; IlcFloat openTime, closeTime; infile >> openTime >> closeTime; IlcFloat depotX, depotY ; infile >> depotX >> depotY; IlcNode depot(plan, depotX, depotY); for (IlcInt j = 0; j < nbOfTrucks; j++) { IlcVisit first(depot, "Depot"); // dimulai dari depot m.add(first.getCumulVar(time) >= openTime); // definisikan waktu buka IlcVisit last(depot, "Depot"); // diakhiri di depot m.add(last.getCumulVar(time) <= closeTime); // definisikan waktu tutup char name[16]; sprintf(name, "Vehicle %d\0", j); // kendaraan yang melakukan pengiriman IlcVehicle vehicle(plan, first, last, name); vehicle.setCapacity(weight, capacity); // kendala kapasitas kendaraan vehicle.setSpeed(length, 1); } for (IlcInt i = 0; i < nbOfVisits; i++) { IlcInt id; // visit identifier?? IlcFloat x, y, quantity, minTime, maxTime, dropTime; infile >> id >> quantity >> minTime >> maxTime >> dropTime >> x >> y; IlcNode customer(plan, x, y); char name[16]; sprintf(name, "%d\0", id); IlcVisit visit(customer, name); visit.setDelay(time, dropTime); //kendala waktu bongkar-muat visit.setQuantity(weight, quantity);// kendala yang dibawa kendaraan /////////////////////////////////////////////// // kendala waktu pelayanan (time window) /////////////////////////////////////////////// ILCSETWINDOW(visit.getCumulVar(time), minTime <= var && var <= maxTime); } infile.close(); ///////////////////////////////////////////////////////////////////////// // mencari solusi dengan menggunakan metode nearest addition heuristic ///////////////////////////////////////////////////////////////////////// IlcGoal generateGoal = IlcNearestAdditionGenerate(m, plan); m.add(generateGoal); if (!m.nextSolution()) { m.out() << "Not enough vehicles to generate first solution" << endl; #if defined(ILCLOGFILE) m.closeLogFile(); #endif m.end(); return 0; } else { m.restart(); m.remove(generateGoal); ////////////////////////////////////////////////////////////////////////////////// //memperbaiki solusi yang didapat dengan twoOP,orOpt,Relocate,Exchange,dan Cross ////////////////////////////////////////////////////////////////////////////////// plan.improve(5, IlcTwoOpt(plan), IlcOrOpt(plan), IlcRelocate(plan), IlcExchange(plan),
28
IlcCross(plan)); } Info(m, plan, problem); #if defined(ILCLOGFILE) m.closeLogFile(); #endif m.end(); return 0; }
29
Lampiran 9 Output Problem name: cost: 3136.39 Number of vehicles used: 3 Solution: Unperform visits: None Vehicle 0: Depot Weight [0..166] Time [0..401.784] Length [0..1.#INF] 1 Weight [0..166] Time [9.19879..419.983] Length [9.19879..1.#INF] 4 Weight [17..183] Time [49.1864..459.971] Length [11.1864..1.#INF] Depot Weight [34..200] Time [129.216..540] Length [22.2157..1.#INF] Vehicle 1: Depot Weight [0..47] Time [0..2.07651] Length [0..1.#INF] 3 Weight [0..47] Time [11.0671..13.1436] Length [11.0671..1.#INF] 5 Weight [7..54] Time [47.6437..49.7202] Length [13.6437..1.#INF] 2 Weight [15..62] Time [142.194..144.27] Length [17.194..1.#INF] 11 Weight [18..65] Time [153.598..155.674] Length [21.5975..1.#INF] 12 Weight [55..102] Time [226.267..228.343] Length [25.2667..1.#INF] 13 Weight [71..118] Time [269.786..271.863] Length [26.7864..1.#INF] 15 Weight [83..130] Time [331.437..333.514] Length [34.4373..1.#INF] 22 Weight [98..145] Time [353.783..355.860] Length [38.7833..1.#INF] 23 Weight [116..163] Time [412.501..414.578] Length [39.5013..1.#INF] 6 Weight [141..188] Time [488.747..490.823] Length [49.7469..1.#INF] Depot Weight[153..200] Time [537.923..540] Length [61.9235..1.#INF] Vehicle 2: Depot Weight [0..6] Time [0..26.7505] Length [0..1.#INF] 09 Weight [0..6] Time [13.2558..40.0063] Length [13.2558..1.#INF] 08 Weight [2..8] Time [45.6606..72.4111] Length [13.6606..1.#INF] 07 Weight [19..25] Time [86.9787..113.729] Length [13.9787..1.#INF] 10 Weight [38..44] Time [116.886..143.636] Length [15.8856..1.#INF] 14 Weight [57.. 63] Time[133.378..160.129] Length [17.3783..1.#INF] 16 Weight [79..85] Time [158.728..185.479] Length [21.7282..1.#INF] 17 Weight [88..94] Time [207.814..234.564] Length [23.8137..1.#INF] 24 Weight [92..98] Time [216.856..243.606] Length [24.8556..1.#INF] 21 Weight [110..116] Time [290.229..316.979] Length [25.229..1.#INF] 20 Weight [147..153] Time [371.549..398.300] Length [25.5493..1.#INF] 19 Weight [165..171] Time [394.705..421.455] Length [28.7049..1.#INF] 18 Weight [183..189] Time [433.398..460.149] Length [32.3982..1.#INF] Depot Weight[194..200] Time [513.250..540] Length [52.2495..1.#INF]
30
Lampiran 10 Contoh dari metode multidimensional scaling (MDS): Input: D= X Atl Chi Den Hou LA Mia
NYC
SF
Sea
WDC
Atl
0
587
1212
701
1936
604
748
2139
2182
543
Chi
587
0
920
940
1745
1188
713
1858
1737
597
Den
1212
920
0
879
831
1726
1631
949
1021
1494
Hou
701
940
879
0
1374
968
1420
1645
1891
1220
LA
1936
1745
831
1374
0
2339
2451
347
959
2300
Mia
604
1188
1726
968
2339
0
1092
2594
2734
923
NYC
748
713
1631
1420
2451
1092
0
2571
2408
205
SF
2139
1858
949
1645
347
2594
2571
0
678
2442
Sea
2182
1737
1021
1891
959
2734
2408
678
0
2329
WDC
543
597
1494
1220
2300
923
205
2442
2329
0
Matriks jarak antara 10 kota di Amerika Serikat Ouput yang dihasilkan:
Output Multidimensional Scaling (MATLAB, 2004)
