i
PENYELESAIAN VEHICLE ROUTING PROBLEM MENGGUNAKAN BEBERAPA METODE HEURISTIK KONSTRUKTIF
DEIBY TINEKE SALAKI
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2009
iii
PERNYATAAN MENGENAI TESIS DAN SUMBER INFORMASI Dengan ini saya menyatakan bahwa tesis Penyelesaian Vehicle Routing Problem Menggunakan Beberapa Metode Heuristik Konstruktif adalah karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir tesis ini.
Bogor, Juli 2009 Deiby Tineke Salaki NRP G551070031
iv
ABSTRACT
DEIBY TINEKE SALAKI. The Solution of Vehicle Routing Problem Using Some Constructive Heuristic Methods. Under supervision of AMRIL AMAN and FARIDA HANUM. The distribution of commodities or services can be viewed as a combinatorial optimization and application of graph theory named vehicle routing problem (VRP). The VRP, which is generalization of traveling salesman problem, can be described as the problem of designing least cost routes from depot to a set of costumers. The routes must be designed in such a way, that each costumer is visited only once by exactly one vehicle, started and ended at the depot. The VRP can be further complicated by associating time windows on visits, which is called VRP time windows (VRPTW). Because of the high complexity of the VRP and its wide applicability to various circumstances, heuristic method is more powerful to solve the problem than the exact one. The method is capable in performing a solution in a relatively limited running time, although it does not guarantee that the solution will be optimal. Most heuristic methods strategies involve finding an initial feasible solution by constructing a given route and then improving that solution. The aims of this research are (1) formulating model for the distribution of commodities as a VRPTW, (2) implementing the model on the delivery of “Sari Roti” bread to some stores, (3) solving the delivery problem using some heuristic methods, (4) comparing the output of each method based on running time and total of distribution distance. The distribution problem is modeled as VRPTW. The model is solved using heuristic method by means of ILOG Dispatcher software. In finding the solution, route construction method is applied by doing each saving, sweeping, nearest-to-depot, nearest addition, and insertion methods; and simultaneously performing route improvement using 2-opt, Or-opt, relocate, exchange and cross methods. Comparison of these methods, which is based on running time and distance on delivery of “Sari Roti” bread, shows that, the least route distance is given by the output of insertion method, the fastest running time is given by saving method. In contrast, the saving method yields the biggest route distance and the nearest-todepot produces the longest running time. Keywords: graph, combinatorial optimization, traveling salesman problem, vehicle routing problem, heuristic method
v
RINGKASAN
DEIBY TINEKE SALAKI. Penyelesaian Vehicle Routing Problem Menggunakan Beberapa Metode Heuristik Konstruktif. Dibimbing oleh AMRIL AMAN dan FARIDA HANUM. Pendistribusian barang atau jasa merupakan salah satu bagian penting dari kegiatan sebuah instansi pemerintah ataupun perusahaan tertentu, yang sering mengadakan pengambilan keputusan mengenai rute yang dapat mengoptimalkan biaya, waktu dan sumberdaya lain yang tersedia. Masalah ini dapat diformulasikan secara matematis sebagai sebuah Vehicle Routing Problem (VRP). VRP merupakan salah satu aplikasi dari teori graf dan optimasi kombinatorial yang mencakup penentuan sejumlah rute angkutan yang diawali dan diakhiri di suatu tempat yang disebut depot untuk mengantarkan barang kepada sekumpulan pelanggan sesuai permintaannya masing-masing. Rute yang terbentuk harus mengunjungi setiap pelanggan tepat satu kali dan menghabiskan biaya atau jarak tempuh seminimal mungkin. Salah satu variasi dari VRP adalah VRP time windows (VRPTW) yang menambahkan kendala batasan selang waktu tertentu (time windows) dalam melayani pelanggan. Selain dengan metode eksak, penyelesaian VRP, terutama yang berukuran besar dapat dilakukan dengan metode heuristik yang menentukan solusi secara cepat dari segi waktu komputasi meskipun solusi yang diperoleh belum tentu optimal. Metode heuristik dapat dibagi dalam tiga kelompok yaitu metode heuristik konstruktif (constructive heuristic), metode dua fase, dan metode perbaikan (improvement). Pada umumnya metode heuristik konstruktif dan metode perbaikan dilakukan secara bersamaan. Pada penelitian ini dilakukan formulasi masalah pendistribusian barang dalam bentuk VRPTW dan diimplementasikan pada masalah distribusi roti “Sari Roti”. Masalah tersebut selanjutnya diselesaikan dengan beberapa metode heuristik konstruktif. Rute yang diperoleh pada tahap konstruksi diperbaiki dengan metode perbaikan. Hasil masing-masing rute setelah perbaikan, selanjutnya dibandingkan berdasarkan waktu tempuh dan total jarak tempuh. Penelitian ini menggunakan software ILOG . Tahapan-tahapan metode heuristik yang digunakan adalah (1) penentuan rute fisibel awal dengan menggunakan 5 metode konstruksi yaitu saving, sweeping, nearest-to-depot, nearest addition, dan insertion, (2) memperbaiki rute yang diperoleh dari setiap metode konstruksi dengan menerapkan secara simultan 5 metode perbaikan rute yaitu metode 2-opt, metode Or-opt, metode relocate, metode exchange dan metode cross, (3) membandingkan hasil akhir perbaikan rute dari kelima metode berdasarkan total jarak tempuh dan waktu eksekusi. Hasil perbandingan lima metode heuristik konstruktif yang diterapkan pada data distribusi roti “Sari Roti” menunjukkan bahwa, jarak terkecil dari kegiatan distribusi diperoleh dari metode insertion dan jarak terbesar diperoleh dari metode saving, sebaliknya waktu eksekusi tercepat diperoleh dari metode saving dan paling lama pada metode nearest-to-depot.
vi
Total jarak tempuh distribusi dapat menjadi masukan bagi PT NIC (produsen “Sari Roti”) untuk memilih rute kendaraan guna meningkatkan efisiensi perusahaan sedangkan waktu eksekusi dapat menjadi masukan bagi pengembangan metode heuristik untuk masalah yang berukuran besar. Kata Kunci : graf, optimasi kombinatorial, traveling salesman problem, vehicle routing problem, metode heuristik
vii
@ Hak Cipta milik IPB, tahun 2009 Hak Cipta dilindungi Undang-Undang 1. Dilarang mengutip sebagian atau seluruh karya tulis ini tanpa mencantumkan atau menyebutkan sumbernya. a. Pengutipan hanya untuk kepentingan pendidikan, penelitian, penulisan karya ilmiah, penyusunan laporan, penulisan kritik, atau tinjauan suatu masalah. b. Pengutipan tidak merugikan kepentingan yang wajar IPB 2. Dilarang mengumumkan dan memperbanyak sebagian atau seluruh karya tulis dalam bentuk apa pun tanpa izin IPB.
viii
PENYELESAIAN VEHICLE ROUTING PROBLEM MENGGUNAKAN BEBERAPA METODE HEURISTIK KONSTRUKTIF
DEIBY TINEKE SALAKI
Tesis sebagai salah satu syarat untuk memperoleh gelar Magister Sains pada Departemen Matematika
SEKOLAH PASCASARJANA INSTITUT PERTANIAN BOGOR BOGOR 2009
ix
Judul Tesis Nama NRP
: Penyelesaian Vehicle Routing Problem Menggunakan Beberapa Metode Heuristik Konstruktif : Deiby Tineke Salaki : G551070031
Disetujui Komisi Pembimbing
Dra. Farida Hanum, M.Si.
Dr. Ir. Amril Aman, M.Sc. Ketua
Anggota
Diketahui Ketua Program Studi
Dekan Sekolah Pascasarjana
Matematika Terapan
Dr. Ir. Endar H. Nugrahani, M.S.
Prof. Dr. Ir. Khairil A. Notodiputro, M.S.
Tanggal Ujian: 6 Juli 2009
Tanggal Lulus:
x
Penguji Luar Komisi pada Ujian Tesis: Drs. Prapto Tri Supriyo, M.Kom.
xi
PRAKATA
Eben Haezer. Ya, (lagi dan lagi) sampai di sini, Tuhan menolong saya melewati satu tahapan penting dalam perjuangan hidup. Thanks God, for showing me Thy way and teaching me how to walk aright, more by faith and less by sight. Diawali dengan pemilihan topik pada bulan Januari 2009 sampai penyelesaian tesis ini yang diberi judul “Penyelesaian Vehicle Routing Problem Menggunakan Beberapa Metode Heuristik Konstruktif”, saya sangat didukung oleh sejumlah pihak. Bapak Amril Aman, Ph.D dan Ibu Farida Hanum, M.Si., pembimbing saya; serta Bapak Prapto Tri Supriyo, M.Kom. selaku penguji, terima kasih atas semua arahan, masukan, dan pengertiannya yang tak ternilai. Segenap civitas akademika Departemen Matematika IPB di almamater saya yang tak pernah terlupakan, terima kasih atas semua ilmu, teladan dan keramahannya. Terima kasih kepada teman-teman kuliah, kak Asmara teman seperjuangan, kepada Aji Raditya yang bersedia ‘meminjamkan’ datanya dan bersama Fariz yang memberi banyak masukan kepada saya; kepada ‘keluarga’ saya di Bogor: teman-teman kost (Deli, Yona, dan Alina) dan keluarga besar Bapak Rahmat di RM Palem Merah. Kepada GKI Pengadilan Bogor yang selalu menjadi ‘rumah’ bagi saya untuk ‘pulang’, terimakasih atas persekutuannya. Ucapan terimakasih juga disampaikan kepada pimpinan dan staf Yayasan Toyota & Astra atas kepercayaannya memberikan beasiswa. Last but not least, terima kasih kepada harta saya yang paling berharga: suami tercinta, Obrin Sualang atas pengertian, kasih sayang dan dukungannya; anakanak tersayang, Riemann, Ednayra dan my future daughter, yang selalu menyemangati saya dalam berjuang; orang tua dan keluarga besar di Pakuure dan Wioi yang selalu mendoakan saya. Terima kasih untuk semua pihak yang selama ini mendukung saya yang tidak dapat disebutkan satu per satu. Saya menerima segala kritik dan saran dari pembaca, karena saya sangat menyadari tulisan ini masih banyak kekurangan. Semoga tulisan ini bermanfaat dan menjadi inspirasi untuk penelitian selanjutnya. Bogor, Juli 2009 Deiby Tineke Salaki
xii
RIWAYAT HIDUP
Deiby Tineke Salaki, dilahirkan sebagai anak bungsu dari dua bersaudara di Amurang, Minahasa Selatan, Sulawesi Utara pada tanggal 17 Desember 1972 dari pasangan Liem Hou Ing dan Altje Fredika Wowor. Lulusan SMA Katolik Aquino Amurang tahun 1991 ini, diterima pada tahun yang sama di Program Studi Ilmu Kelautan, Fakultas Perikanan Unsrat Manado. Setahun kemudian penulis mendapat tugas belajar dari Universitas Sam Ratulangi Manado di Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam IPB dengan beasiswa EIUDP-CIDA dan TID dan lulus pada tahun 1998. Pada tahun 2007, diterima di Program Studi Matematika pada Sekolah Pascasarjana IPB. Selama menempuh jenjang S2, penulis menerima beasiswa dari Yayasan Toyota & Astra Indonesia dan bantuan penelitian dari Lembaga Penelitian Unsrat Manado. Penulis merupakan dosen pada Jurusan Matematika, FMIPA Universitas Sam Ratulangi Manado sejak tahun 2000 sampai sekarang. Pada tahun 2001, penulis menikah dengan Obrin Sualang dan dikaruniai seorang putra Riemann Janson Sualang (6 tahun), seorang putri Ednayra Marqliem Sualang (3 tahun) dan seorang calon bayi.
xiii
DAFTAR ISI
Halaman DAFTAR TABEL .....................................................................................
xv
DAFTAR GAMBAR ................................................................................
xvi
DAFTAR LAMPIRAN .............................................................................
xvii
1
2
3
4
PENDAHULUAN 1.1 Latar Belakang .............................................................................. 1.2 Tujuan Penelitian ........................................................................... 1.3 Manfaat Penelitian .........................................................................
1 3 3
TINJAUAN PUSTAKA 2.1 Graf ............................................................................................... 2.2 Optimasi Kombinatorial ................................................................ 2.3 Traveling Salesman Problem ......................................................... 2.4 Vehicle Routing Problem ............................................................... 2.5 Vehicle Routing Problem with Time Windows ................................
4 4 5 6 9
METODE HEURISTIK UNTUK VRPTW 3.1 Metode Heuristik ........................................................................... 3.2 Metode Heuristik Konstruktif ......................................................... 3.2.1 Metode Saving ................................................................... 3.2.2 Metode Sweeping ............................................................... 3.2.3 Metode Nearest-to-depot .................................................... 3.2.4 Metode Nearest Addition .................................................... 3.2.5 Metode Insertion ................................................................ 3.3 Metode Perbaikan .......................................................................... 3.3.1 Perbaikan dalam Rute ........................................................ 3.3.1.1 Metode 2-opt ................................................................ 3.3.1.2 Metode Or-opt ............................................................. 3.3.2 Perbaikan Antarrute ........................................................... 3.3.2.1 Metode Relocate ........................................................... 3.3.2.2 Metode Exchange ......................................................... 3.3.2.3 Metode Cross ...............................................................
12 12 12 14 15 16 18 19 19 19 20 21 21 22 22
PENYELESAIAN MASALAH DISTRIBUSI ROTI “SARI ROTI” 4.1 Data ............................................................................................... 4.2 Deskripsi Masalah ......................................................................... 4.3 Formulasi Masalah ........................................................................ 4.4 Hasil dan Pembahasan ................................................................... 4.4.1 Rute Kendaraan dengan Metode Saving .............................. 4.4.2 Rute Kendaraan dengan Metode Sweeping ......................... 4.4.3 Rute Kendaraan dengan Metode Nearest-to-depot ..............
24 24 26 28 29 31 32
xiv
4.4.4 Rute Kendaraan dengan Metode Nearest Addition .............. 4.4.5 Rute Kendaraan dengan Metode Insertion .......................... 4.4.6 Pembandingan Kelima Metode Heuristik Konstruktif..........
34 35 37
SIMPULAN DAN SARAN 5.1 Simpulan ....................................................................................... 5.2 Saran .............................................................................................
39 39
DAFTAR PUSTAKA ................................................................................
40
LAMPIRAN .............................................................................................
42
5
xv
DAFTAR TABEL
Halaman 1
Data pelanggan PT NIC .........................................................................
25
2
Rute kendaraan dengan metode saving ..................................................
29
3
Rute kendaraan dengan metode sweeping ..............................................
31
4
Rute kendaraan dengan metode nearest-to-depot ...................................
32
5
Rute kendaraan dengan metode nearest addition ...................................
34
6
Rute kendaraan dengan metode insertion ...............................................
35
7
Perbandingan hasil kelima metode konstruksi ........................................
37
8
Perbandingan jarak dan waktu eksekusi kelima metode konstruksi ........
37
xvi
DAFTAR GAMBAR Halaman 2.1
Contoh penyelesaian TSP ....................................................................
6
2.2
Contoh penyelesaian VRP 3 rute .........................................................
7
3.1
Contoh metode saving ..........................................................................
13
3.2
Contoh metode sweeping......................................................................
15
3.3
Contoh metode nearest-to-depot .........................................................
16
3.4
Contoh metode nearest addition ..........................................................
18
3.5
Contoh metode insertion .....................................................................
19
3.6
Contoh metode 2-opt ...........................................................................
20
3.7
Contoh metode Or-opt ........................................................................
21
3.8
Contoh metode relocate ......................................................................
22
3.9
Contoh metode exchange ....................................................................
22
3.10 Contoh metode cross ...........................................................................
23
4.1
Rute kendaraan dengan metode saving ................................................
30
4.2
Rute kendaraan dengan metode sweeping ............................................
32
4.3
Rute kendaraan dengan metode nearest-to-depot .................................
33
4.4
Rute kendaraan dengan metode nearest addition .................................
35
4.5
Rute kendaraan dengan metode insertion ............................................
36
4.6
Perbandingan waktu eksekusi dan total jarak tempuh kelima metode konstruksi ...........................................................................................
38
xvii
DAFTAR LAMPIRAN
Halaman 1
Matriks jarak antarlokasi .....................................................................
2
Program penentuan rute dengan metode saving menggunakan software
43
ILOG ..................................................................................................
44
3
Hasil penentuan rute dengan metode saving .........................................
47
4
Program penentuan rute dengan metode sweeping menggunakan software ILOG ..................................................................................................
49
5
Hasil penentuan rute dengan metode sweeping .....................................
52
6
Program penentuan rute dengan metode nearest-to-depot menggunakan software ILOG ....................................................................................
54
7
Hasil penentuan rute dengan metode nearest-to-depot ..........................
57
8
Program penentuan rute dengan metode nearest addition menggunakan software ILOG ....................................................................................
59
9
Hasil penentuan rute dengan metode nearest addition ..........................
62
10
Program penentuan rute dengan metode insertion menggunakan software
11
ILOG ..................................................................................................
64
Hasil penentuan rute dengan metode insertion......................................
67
1
1 PENDAHULUAN
1.1 Latar Belakang Pendistribusian barang atau jasa merupakan salah satu bagian penting dari kegiatan sebuah instansi pemerintah ataupun perusahaan tertentu. Masalah yang sering dihadapi terkait distribusi adalah membuat keputusan-keputusan mengenai rute yang dapat mengoptimalkan jarak tempuh atau biaya perjalanan, waktu tempuh, banyaknya kendaraan yang dioperasikan dan sumberdaya lain yang tersedia. Masalah optimasi pendistribusian barang tersebut dapat diformulasikan secara matematis sebagai sebuah Vehicle Routing Problem (VRP).
VRP yang
diperkenalkan oleh Dantzig dan Ramster pada tahun 1959, merupakan masalah optimasi kombinatorial yaitu optimasi yang melibatkan fungsi dengan banyak peubah. Terapan VRP sering dijumpai dalam kehidupan sehari-hari, antara lain pendistribusian hasil produksi oleh produsen ke pelanggan, pengiriman surat atau barang oleh perusahaan ekspedisi dan pengumpulan sampah di suatu perkotaan. Formulasi VRP ditujukan untuk membentuk sejumlah rute dengan biaya atau jarak seminimal mungkin, sedemikian sehingga (1) setiap rute berawal dan berakhir di suatu tempat yang disebut depot, (2) setiap pelanggan dikunjungi tepat satu kali oleh satu kendaraan tertentu, (3) total permintaan setiap rute tidak melebihi kapasitas kendaraan, (4) total durasi setiap rute (termasuk waktu tempuh dan waktu pelayanan) tidak melebihi batas waktu tertentu. Kondisi permasalahan yang berbeda-beda pada setiap penerapannya membuat VRP dalam prakteknya sangat bervariasi. Variasi VRP disebabkan oleh variasi kendala antara lain: kapasitas kendaraan yang digunakan heterogen atau homogen, kendaraan melakukan kegiatan pengantaran atau pengantaran dan pengumpulan barang sekaligus dalam satu rute yang sama, terdapat satu atau lebih dari satu depot, adanya selang waktu tertentu bagi pelanggan untuk menerima layanan, dan lain-lain. Pada kasus adanya batasan bahwa kapasitas muatan semua kendaraan yang digunakan adalah sama, maka VRP tersebut dinamakan capacitated VRP (CVRP). Suatu VRP dengan tambahan kendala berupa adanya selang waktu
2
pelayanan (time windows) pada setiap pelanggan, dinamakan VRP time windows (VRPTW). VRPTW terdiri atas dua tipe yaitu soft time windows dan hard time windows. Pada tipe hard time windows, pelayanan tidak dapat dilakukan apabila melewati waktu yang telah ditentukan oleh pelanggan (time windows); sedangkan pada kasus soft time windows, konsumen akan tetap dapat dilayani di luar time windows namun dengan tambahan biaya yang disebut penalti. Penelitian tentang VRP umumnya diarahkan pada pengembangan metode penentuan solusi optimal secara lebih efisien dari segi komputasi.
VRP
merupakan masalah optimasi kombinatorial yang sulit diselesaikan. Salah satu metode penyelesaian yaitu metode eksak, seperti metode branch and bound dan pemrograman dinamik, umumnya tidak mampu menyelesaikan VRP yang melibatkan banyaknya pelanggan yang berukuran besar dalam waktu yang singkat. Penelitian tentang metode ini dilakukan antara lain oleh Larsen (2001) dan Rich (1999). Metode lain yang merupakan metode pendekatan adalah metode heuristik dan metaheuristik. Metode ini lebih menekankan perolehan solusi fisibel secara cepat dari segi waktu komputasi meskipun tidak dijamin solusi tersebut optimal. Metode metaheuristik yang banyak dikembangkan pada dekade terakhir, menghasilkan kualitas solusi yang lebih baik dari metode heuristik namun biaya komputasinya relatif mahal. Beberapa penelitian tentang metode heuristik untuk penyelesaian VRPTW telah dilakukan antara lain oleh Laporte dan Semet (2002), Cordeau et al. (2002) dan Bräysy dan Gendreau (2005). Dalam penelitiannya mereka membandingkan beberapa variasi metode heuristik, antara lain berdasarkan nilai fungsi objektif, banyaknya kendaraan dan waktu eksekusi.
Pembandingan yang dimaksud,
menggunakan hasil yang dilakukan oleh peneliti lain dalam menerapkan beberapa metode heuristik pada sejumlah variasi masalah dengan banyaknya pelanggan atau simpul yang berbeda. Penelitian lain dilakukan oleh Raditya (2009) pada kasus distribusi roti yang penyelesaiannya menggunakan metode heuristik yaitu metode nearest addition pada tahap konstruksi rute fisibel awal dan pada tahap perbaikan rute
3
menggunakan metode 2-opt, metode Or-opt, metode relocate, metode exchange, dan metode cross. Pada penelitian ini akan dilakukan formulasi masalah pendistribusian barang ke dalam VRPTW dan menerapkannya pada permasalahan distribusi roti “Sari Roti”. Pada tahap awal dilakukan konstruksi rute fisibel dengan menggunakan 5 macam metode konstruksi yaitu saving, sweep, nearest-to-depot, nearest addition, dan insertion. Hasil konstruksi rute dari tiap-tiap metode tersebut selanjutnya diperbaiki dengan menggunakan 5 metode secara berturut-turut, yaitu metode 2opt, metode Or-opt, metode relocate, metode exchange, dan metode cross. Data diolah dengan menggunakan software ILOG Dispatcher dan ILOG Solver. 1.2 Tujuan Penelitian Tujuan dari penelitian ini adalah: 1.
membuat formulasi masalah distribusi dalam model VRPTW,
2.
mengimplementasikan model pada kasus distribusi roti “Sari Roti” untuk membandingkan solusi beberapa metode heuristik konstruktif dengan bantuan software ILOG Dispatcher dan ILOG Solver versi 2.1.
1.3 Manfaat Penelitian Penelitian ini diharapkan dapat memberikan informasi tentang formulasi VRPTW dan metode penyelesaiannya dengan menggunakan metode heuristik, yang dapat bermanfaat bagi penelitian lanjutan dan dapat diterapkan dalam dunia nyata.
4
2 TINJAUAN PUSTAKA
2.1 Graf Definisi 1 (Graf dan Jaringan Berarah) Suatu graf berarah (directed graph/digraf) G=(N,A) terdiri dari suatu himpunan simpul (node) N dan himpunan sisi berarah (arc) A, yang elemen-elemennya merupakan pasangan terurut dari sisi-sisi yang berbeda. Jaringan atau network berarah merupakan digraf dengan simpul dan atau sisi berarah yang berkaitan dengan nilai numerik tertentu, misalnya jarak/biaya dan kapasitas (Ahuja et al. 1993). Dalam sebagian literatur, graf dan jaringan memiliki pengertian yang sama, sedangkan menurut Foulds (1992), jaringan adalah graf yang memiliki tepat satu simpul sumber dan satu simpul tujuan. Definisi 2 (Simpul Suksesor dan Predesesor, Sisi Berarah Menjauh dan Mendekat) Misalkan diberikan suatu digraf G=(V,A) dengan (i, j) œ A. Simpul i dikatakan predesesor bagi simpul j dan simpul j disebut suksesor bagi simpul i. Sisi (i, j) dikatakan mendekati simpul j dan menjauhi simpul i (Foulds 1992). Definisi (Simpul Sumber dan Simpul Tujuan) Simpul sumber (source) adalah suatu simpul yang padanya tidak terdapat sisi yang mendekati dan sebaliknya simpul tujuan (sink) adalah simpul yang padanya tidak terdapat sisi yang menjauhi (Foulds 1992). 2.2 Optimasi Kombinatorial Suatu masalah optimasi dapat dinyatakan sebagai minimumkan f(x) terhadap
xœS
(2.1)
dengan f(x) merupakan fungsi objektif, x = (x1, x2, … ,xk) disebut peubah keputusan dan S Õ ℜk disebut ruang solusi.
5
Masalah optimasi dapat diformulasikan dalam beberapa cara yang berbeda sesuai dengan fungsi objektif, peubah keputusan dan gambaran dari ruang solusi. Masalah optimasi kombinatorial adalah masalah optimasi yang melibatkan fungsi dengan himpunan solusi terbatas namun berukuran besar sehingga hanya dapat diselesaikan dengan metode yang memerlukan waktu komputasi yang sangat lama (Larsen 2001). 2.3 Traveling Salesman Problem Menurut Garfinkel dan Nemhauser (1972), traveling salesman problem (TSP) merupakan salah satu terapan dari teori graf yang diilhami oleh permasalahan seorang pedagang yang mengunjungi sejumlah kota dengan berawal dan berakhir di tempat asalnya. Permasalahan intinya adalah menemukan rute terpendek jika harus mengunjungi semua kota tepat satu kali. Tujuannya tidak hanya terbatas pada penentuan jarak terpendek tetapi dapat dikembangkan untuk menentukan waktu tercepat yang dibutuhkan. Variasi lain dari TSP juga dapat berupa adanya selang waktu tertentu atau time windows untuk mengunjungi lokasi yang hendak dituju. Masalah ini dinamakan TSP time windows atau TSPTW. Secara formal TSP dideskripsikan sebagai berikut. Berawal dari kota asalnya, seorang salesman hendak mengunjungi sejumlah kota tepat satu kali lalu kembali ke kota asalnya. Salesman tersebut menginginkan rute yang fisibel dengan biaya atau jarak minimal. Secara matematis, TSP dapat dinyatakan sebagai suatu graf berarah G=(V,A) dengan V={1, ..., n} menyatakan himpunan simpul yang menunjukkan lokasi kota dan A={(i, j) | i, j ∈ V, i ≠ j} merupakan himpunan sisi berarah (arc) yang menyatakan jalan penghubung antarkota. Simpul 1 menyatakan kota asal/depot. Misalkan cij adalah jarak tempuh (biaya perjalanan) dari kota i ke kota j dan didefinisikan peubah:
1, xij = 0,
jika sisi berarah (i,j ) ∈ A dilalui oleh rute jika selainnya
maka formulasi matematis dari TSP adalah sebagai berikut: n
minimumkan z=
n
∑∑c x
ij ij
i =1 j =1
(2.2)
6
dengan kendala: n
∑x
ij
= 1; i = 1,.., n
(2.3)
ij
=1; j = 1,.., n
(2.4)
i =1
n
∑x j =1
∑∑x
ij
≥ 1; ∀Q ⊂ V , Q ≠ ∅
(2.5)
i∈Q j∈Q
xij œ {0, 1} ; i, j = 1, .., n
(2.6)
Persamaan (2.2) merupakan fungsi tujuannya yaitu meminimumkan total jarak tempuh (biaya perjalanan).
Kendala (2.3) dan (2.4) menggambarkan bahwa
salesman mendatangi dan meninggalkan setiap kota tepat satu kali, sedangkan kendala (2.5) memastikan bahwa tidak terdapat subrute dan kendala (2.6) menjamin bahwa xij merupakan peubah biner (Garfinkel & Nemhauser 1972). Contoh solusi dari TSP dapat dilihat pada Gambar 2.1.
Kota
Depot
Rute
Gambar 2.1 Contoh penyelesaian TSP. 2.4 Vehicle Routing Problem VRP merupakan perumuman dari TSP atau disebut juga m-TSP dengan m menunjukkan banyaknya salesman yang mengunjungi sejumlah kota. Jadi VRP berkaitan dengan penentuan rute optimal untuk permasalahan lebih dari satu kendaraan (vehicle) dengan kapasitas tertentu untuk mengunjungi sejumlah pelanggan dengan permintaannya masing-masing.
Rute yang dibentuk harus
7
dimulai dan diakhiri di suatu tempat yang disebut depot.
Setiap pelanggan
dikunjungi hanya satu kali dan total permintaan semua pelanggan dalam satu rute tidak melebihi kapasitas kendaraan yang melayani rute tersebut.
Contoh
penyelesaian VRP diberikan pada Gambar 2.2.
Pelanggan
Depot Rute
Gambar 2.2 Contoh penyelesaian VRP dengan 3 rute. Menurut Toth dan Vigo (2002), secara matematis VRP dapat dinyatakan sebagai suatu digraf G=(V, A) dengan V={0, 1, ..., n} adalah himpunan simpul yang menunjukkan lokasi pelanggan dan A={(i, j) | i, j ∈ V, i ≠ j} yaitu himpunan sisi berarah yang menyatakan jalan penghubung lokasi pelanggan.
Simpul 0
menunjukkan depot, yaitu tempat menyimpan kendaraan yang digunakan untuk distribusi dan merupakan tempat dimulai dan diakhirinya suatu rute kendaraan. Banyaknya kendaraan yang tersedia di depot adalah K dengan kapasitas kendaraan ke-k adalah Qk. Setiap pelanggan i memiliki permintaan sebanyak qi. Dengan tujuan meminimumkan biaya perjalanan atau jarak tempuh maka VRP dimodelkan dalam bentuk pemrograman linear integer sebagai berikut (Toth & Vigo 2002): K
minimumkan z = ∑ ∑ cij ∑ xijk i∈V j∈V
dengan kendala:
k =1
(2.7)
8
1. setiap pelanggan hanya dikunjungi satu kali: K
∑y
ik
= 1 ; i ∈V \ {0}
(2.8)
k =1
2. terdapat K kendaraan yang beroperasi yang berawal dari depot: K
∑y
0k
=K
(2.9)
k =1
3. kendaraan yang sama akan mengunjungi dan meninggalkan setiap pelanggan:
∑x
ijk
j∈V
= ∑ x jik = yik ; ∀i ∈ V , k = 1,2,..., K
(2.10)
j∈V
4. total angkutan setiap kendaraan tidak melebihi kapasitasnya:
∑q y i
ik
≤ Qk ; k = 1,..., K
(2.11)
i∈V
5. tidak terdapat subrute:
∑∑ x
ijk
≤ S − 1 ; ∀ S ⊆ V \ {0}, S ≥ 2, k = 1,2,..., K
(2.12)
i∈S j∈S
dengan |S| menyatakan kardinalitas S 6. peubah yik merupakan peubah biner: yik œ {0,1} ∀ i œ V, k = 1,…,K
(2.13)
7. peubah xijk merupakan peubah biner: xijk œ {0,1} ∀ i, j œ V, k = 1,…,K
dengan
jika sisi berarah (i,j ) ∈ A dilalui kendaraan k
1, xijk = 0,
jika selainnya
1, yik = 0,
jika simpul i dilalui kendaraan k jika selainnya
(2.14)
9
cij = jarak atau biaya perjalanan antara pelanggan i dan pelanggan j qi
= jumlah permintaan pelanggan i
Qk = kapasitas kendaraan ke k K
= banyaknya kendaraan yang tersedia.
2.5 Vehicle Routing Problem with Time Windows Vehicle Routing Problem with Time Windows (VRPTW) merupakan sebutan
bagi VRP dengan kendala tambahan berupa adanya time windows pada masingmasing pelanggan. Time windows pada masing-masing pelanggan dapat berbeda satu sama lain dan dinyatakan dalam selang waktu berupa batas waktu awal sampai akhir pelayanan pada pelanggan tersebut. VRPTW terdiri dari dua tipe yaitu soft time windows dan hard time windows. Pada tipe hard time windows, pelayanan tidak dapat dilakukan apabila melewati waktu yang telah ditentukan oleh pelanggan (time windows), sedangkan pada kasus soft time windows, pelanggan akan tetap dapat dilayani di luar time windows namun dengan tambahan biaya yang disebut penalti. Secara formal VRPTW dapat didefinisikan sebagai suatu digraf G=(N,A). Himpunan simpul N terdiri atas gabungan himpunan pelanggan C dan depot. Himpunan C berupa simpul 1 sampai dengan n dan simpul depot dinyatakan dengan simpul 0 dan n+1.
Jaringan jalan yang digunakan oleh kendaraan
dinyatakan sebagai himpunan sisi berarah A yaitu penghubung antarsimpul. Semua rute berawal dari simpul 0 dan berakhir di n+1. Himpunan kendaraan V merupakan kumpulan kendaraan yang homogen dengan kapasitas q.
Setiap
pelanggan atau simpul i untuk setiap i œ C memiliki pemintaan di sehingga panjang rute dibatasi oleh kapasitas kendaraan.
Setiap sisi (i, j) pada graf
memiliki jarak tempuh atau biaya perjalanan dan waktu tempuh yang masingmasing adalah cij dan tij. Waktu tempuh tij dapat diasumsikan termasuk lama pelayanan pada pelanggan i. Pelayanan pada pelanggan i harus berlangsung pada selang waktu time windows [ai, bi], dengan ai dan bi berturut-turut adalah waktu awal dan akhir pelayanan pada pelanggan i . Jika kendaraan tiba di pelanggan i sebelum time windows maka harus menunggu sampai waktu pelayanan dimulai tanpa biaya tambahan.
10
Kendaraan yang tiba di lokasi pelanggan setelah time windows, tidak dapat melayani pelanggan tersebut. Depot diasumsikan memiliki time windows yang sama yaitu [a0, b0]. Kendaraan tidak dapat meninggalkan depot sebelum a0 dan akan kembali ke depot sebelum atau pada saat bn+1. Bilangan q, di diasumsikan integer taknegatif, sedangkan ai, bi, tij, dan cij diasumsikan taknegatif. Selain itu,
diasumsikan juga bahwa ∀i, j œ N memenuhi pertaksamaan cij + cjk ≥ cik dan tij + tjk ≥ tik.
Tujuan VRPTW adalah menentukan himpunan rute dengan jarak tempuh atau biaya perjalanan minimal dengan syarat setiap pelanggan dilayani tepat satu kali, setiap rute berawal dari simpul 0 dan berakhir di simpul n+1 serta memenuhi kendala kapasitas kendaraan dan time windows. Formulasi matematis VRPTW menurut Kallehauge et al. (2002) adalah sebagai berikut: minimumkan z =
∑∑ ∑ c x
ij ijk
(2.15)
k ∈V i∈ N j ∈ N
dengan kendala: 1. setiap pelanggan dikunjungi tepat satu kali oleh suatu kendaraan:
∑∑x
= 1, ∀i ∈ C
ijk
(2.16)
k∈V j∈N
2. total permintaan semua pelanggan dalam satu rute tidak melebihi kapasitas kendaraan:
∑d ∑ x i
i∈C
ijk
≤ q , ∀k ∈ V
(2.17)
j∈ N
3. setiap rute berawal dari depot 0:
∑x
0 jk
= 1, ∀k ∈ V
(2.18)
j∈N
4. setiap kendaraan yang mengunjungi suatu pelanggan pasti akan meninggalkan pelanggan tersebut:
∑x
ihk
i∈N
− ∑ xhjk = 0 , ∀h ∈ C , ∀k ∈ V
(2.19)
j∈ N
5. setiap rute berakhir di depot n+1:
∑x
i , n +1, k
= 1, ∀k ∈V
(2.20)
i∈ N
6. suatu kendaraan k yang menuju j dari i, tidak dapat tiba di j sebelum sik + tij. Jadi jika xijk > 0 maka sik + tij ≤ sjk. Bentuk linearnya adalah:
11
sik + tij − M ij (1 − xijk ) ≤ s jk , ∀i, j ∈ N , ∀k ∈ V
(2.21)
dengan Mij adalah konstanta besar yang tidak kurang dari nilai maksimum dari bi + tij – aj ; (i, j) œ A. 7. waktu pelayanan di setiap pelanggan memenuhi time windows:
ai ≤ sik ≤ bi , ∀i ∈ N , ∀k ∈V
(2.22)
8. peubah xijk merupakan peubah biner: xijk œ {0,1}, ∀i, j œ N, ∀ k œ V
(2.23)
dengan V
= himpunan kendaraan dengan kapasitas yang sama
C
= himpunan pelanggan atau konsumen = {1,...,n}
A
= himpunan sisi berarah = {(i, j) | i, j œ N, i ≠ j}
N
= himpunan simpul = {0,1,...,n+1}
cij
= jarak/biaya dari simpul i ke simpul j
tij
= waktu tempuh dari simpul i ke simpul j
di
= jumlah permintaan pelanggan i
q
= kapasitas kendaraan
[ai, bi] = time windows dari simpul i. Untuk setiap (i, j) œ A, i ≠ n+1, j ≠ 0 dan untuk setiap kendaraan k didefinisikan peubah:
xijk
1, jika kendaraan k melalui i dan langsung ke j = 0, selainnya
sik
= waktu bagi kendaraan k mulai melayani pelanggan i
dengan q dan di adalah bilangan integer taknegatif dan ai, bi, cij, dan tij adalah bilangan taknegatif. Pada simpul depot diasumsikan a0 = b0 = an+1 = 0 dan s0k = 0 untuk setiap k.
12
3 METODE HEURISTIK UNTUK VRPTW
3.1 Metode Heuristik Metode heuristik merupakan salah satu metode penentuan solusi optimal dari permasalahan optimasi kombinatorial.
Berbeda dengan solusi eksak yang
menentukan nilai solusi secara tepat, metode ini menghampiri solusi permasalahan utama dengan cara mencari nilai optimal suatu bagian tertentu atau irisan dari masalah utamanya. Dalam hal ini, perolehan solusi fisibel secara cepat dari segi komputasi lebih ditekankan meskipun tidak dijamin solusi tersebut optimal. Menurut Laporte dan Semet (2002), metode heuristik untuk menyelesaikan VRP dapat dikategorikan dalam tiga kelompok, yaitu metode heuristik konstruktif (constructive heuristic), metode dua fase, dan metode perbaikan (improvement). Pada umumnya metode heuristik konstruktif dan metode perbaikan dilakukan secara bersamaan. Metode heuristik konstruktif, secara bertahap memilih simpul atau sisi untuk membangun suatu solusi atau rute fisibel awal dengan memperhatikan batasanbatasan seperti kapasitas atau time windows. Metode perbaikan atau local search selanjutnya melakukan perbaikan solusi sebelumnya untuk mengurangi biaya dengan melakukan serangkaian pertukaran simpul atau sisi baik di dalam rute (intra route) maupun antarrute (inter route).
3.2 Metode Heuristik Konstruktif Menurut Bräysy dan Gendreau (2005), metode heuristik konstruktif atau konstruksi rute, melakukan pemilihan simpul atau sisi secara berurutan hingga terbentuk suatu solusi fisibel awal.
3.2.1 Metode Saving Metode saving disebut juga metode Clarke-Wright karena diperkenalkan oleh Clarke dan Wright pada tahun 1964. Metode ini merupakan metode heuristik yang paling banyak digunakan untuk mengonstruksi rute. Metode ini diawali
13
dengan suatu solusi yang setiap pelanggannya dilayani secara individu oleh satu rute secara terpisah. Selanjutnya dilakukan penggabungan dua rute pelanggan i dan j sehingga menghasilkan penghematan (saving) berupa jarak tempuh sebesar sij = ci0 + c0j – cij dengan cij = jarak dari pelanggan i ke pelanggan j. Secara umum, jika dua rute (0, …, i, 0) dan (0, j,…, 0) secara fisibel dapat digabungkan menjadi rute tunggal (0, …, i, j, 0) maka akan terdapat penghematan jarak sebesar sij = (c0i + ci0 + c0j + cj0) – (c0i + cj0 + cij) = ci0 + c0j – cij (Altinel & Öncan 2005). Algoritme metode ini adalah sebagai berikut: 1. Pada awalnya, setiap pelanggan dilayani oleh satu kendaraan secara terpisah. Jadi diperoleh rute (0, i, 0) untuk setiap pelanggan i. 2. Untuk setiap pasang pelanggan i, j; i ≠ j, dihitung fungsi penghematan yang didefinisikan sebagai: sij = ci0 + c0j – cij yang diperoleh dengan cara menggabungkan dua rute pelanggan tersebut yaitu dengan membuat sisi (i,j). 3. Mengurutkan sisi (i, j) berdasarkan nilai sij secara takturun dalam sebuah daftar L. 4. Dimulai dari nilai sij terbesar, perluas setiap rute pada L dengan melakukan penggabungan dengan rute lainnya tanpa melanggar kendala. 5. Langkah (4) diulang sampai daftar L kosong. (ILOG 1999). Contoh metode ini diberikan pada Gambar 3.1.
j
i
c0j
ci0
c0i
cj0 0
i
cij
c0i
c0j 0
Depot
Depot
(1)
j
(2)
Gambar 3.1 Contoh metode saving. heuristic
14
Pada Gambar 3.1 bagian (1), pelanggan i dan pelanggan j dilayani oleh rute terpisah sedangkan pada bagian (2), kedua rute pelanggan tersebut digabungkan untuk dilayani oleh satu rute dengan cara menyelipkan pelanggan j setelah pelanggan i yaitu dengan membuat sisi berarah baru (i, j) yang fisibel sehingga memperoleh penghematan sebesar sij = ci0 + c0j – cij.
3.2.2 Metode Sweeping Metode ini diperkenalkan oleh Gillet dan Miller tahun 1974.
Misalkan
diasumsikan setiap pelanggan i ditempatkan pada suatu bidang dalam koordinat polar dengan sudut qi dari garis horizon yang berawal dari depot ke arah kanan. Berawal dari pelanggan dengan nilai qi terkecil, ditempatkan sebanyak mungkin pelanggan pada tiap-tiap kendaraan dengan urutan qi yang menaik sampai kapasitas kendaraan terpenuhi (Kyung et al. 2008). Beberapa penulis seperti Laporte dan Semet (2002), mengelompokkan metode ini ke dalam metode dua fase. Fase pertama adalah pengelompokan berdasarkan sudut qi. Pada fase kedua, tiap-tiap kelompok dipandang sebagai TSP yang akan ditentukan rute optimalnya. Pada software ILOG Dispatcher, penentuan rute dengan metode ini mengikuti algoritme sebagai berikut: 1. Misalkan O adalah posisi depot tempat kendaraan berawal dan A merupakan suatu posisi yang lain yang dianggap sebagai starting point. 2. Posisi setiap pelanggan S diurutkan berdasarkan besarnya sudut AOS secara menaik dan ditempatkan dalam daftar L. 3. Pelanggan ditempatkan pada kendaraan berdasarkan urutan tersebut tanpa melanggar kendala kapasitas kendaraan. 4. Jika kapasitas kendaraan telah dipenuhi, maka diambil kendaraan baru. 5. Proses berulang sampai semua pelanggan dalam daftar L ditempatkan pada kendaraan. (ILOG, 1999). Contoh metode ini dapat dilihat pada Gambar 3.2. Pada gambar tersebut bagian (1), dilakukan pengelompokan pelanggan ke dalam n kendaraan
15
berdasarkan sudut qi kemudian pada bagian (2), setiap kelompok ditentukan rute fisibelnya.
Kelompok ...
Kelompok n Kelompok 3
Kelompok 1
Kelompok 2 (1)
Rute …
Rute n Rute 3
Rute 1
Rute 2 (2)
Gambar 3.2 Contoh metode sweeping.
3.2.3 Metode Nearest-to-depot Metode ini membangun rute dengan cara menambahkan kunjungan yang terdekat dengan depot.
Pada setiap iterasinya, setelah diawali dari depot, dilakukan
pencarian pelanggan terdekat dengan depot untuk ditambahkan pada akhir rute tersebut. Rute baru dimulai dengan cara yang sama, jika tidak terdapat posisi
16
yang fisibel untuk menempatkan pelanggan baru karena kendala kapasitas atau time windows tidak dipenuhi. Algoritme metode ini adalah sebagai berikut: 1. Misalkan kendaraan yang tersedia dilambangkan dengan w. 2. Mulailah suatu rute yang berawal dari depot. 3. Temukan pelanggan berikutnya v yang terdekat dengan titik awal dari rute w. Jika tidak ada pelanggan yang memungkinkan, tutup rute w dan pilih kendaraan baru lainnya lalu kembali ke langkah 2. Jika tidak ada lagi kendaraan maka proses selesai. 4. Tambahkan v pada akhir dari rute tersebut. 5. Kembali ke langkah 3. (ILOG, 1999). Gambar 3.3 memberikan deskripsi tentang metode ini. Pada gambar tersebut, setelah diawali dari depot, dilakukan pencarian pelanggan yang terdekat dengan depot yaitu pelanggan i. Selanjutnya dari semua pelanggan lainnya yang tersisa, dicari yang terdekat dengan depot yaitu pelanggan j, untuk ditambahkan pada rute yang ada atau setelah pelanggan i. Pelanggan pada kasus VRPTW dipilih yang tidak melanggar kendala kapasitas dan time windows. Jika kapasitas kendaraan telah terpenuhi, mulai dengan rute baru sampai semua pelanggan terlayani.
…
i
j n
depot
Gambar 3.3 Contoh metode nearest-to-depot.
3.2.4 Metode Nearest Addition Metode nearest addition sangat mirip dengan metode nearest-to-depot. Jika pada setiap iterasinya, metode nearest-to-depot menambahkan pelanggan yang terdekat
17
dengan titik awalnya maka pada metode ini ditambahkan pelanggan yang terdekat dengan titik akhir dari rute (ILOG 1999). Metode nearest addition juga dinamakan metode nearest neighbor. Pada setiap iterasinya, dilakukan pencarian pelanggan terdekat dengan pelanggan yang terakhir untuk ditambahkan pada akhir rute tersebut. Rute baru dimulai dengan cara yang sama jika tidak terdapat posisi yang fisibel untuk menempatkan pelanggan baru karena kendala kapasitas atau time windows (Bräysy & Gendreau 2005). Metode ini 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 pelanggan sebelumnya, demikian seterusnya hingga kapasitas kendaraan terpenuhi. Jika kapasitas kendaraan telah terpenuhi maka kendaraan tersebut harus kembali ke depot. Selanjutnya kendaraan berikutnya dioperasikan dengan aturan yang sama seperti kendaraan pertama, sampai seluruh lokasi dikunjungi oleh kendaraan yang tersedia di depot. Algoritme metode ini adalah sebagai berikut: 1. Misalkan banyaknya pelanggan adalah n. Rute dimulai dari depot/simpul 0 2. Tetapkan p = 1 dan U = {0}, yaitu himpunan simpul/pelanggan yang telah dilayani. 3. Jika p < n, maka: i.
pilih pelanggan i berikutnya untuk dikunjungi sedemikian hingga c0i = min c0 j dan (0,i) fisibel. j∉U
ii.
update U = U ∪ {i}, tetapkan simpul 0 = i dan p = p + 1
4. Jika (0, i) tidak fisibel maka mulai dengan rute baru sampai |U| = n + 1 Contoh metode ini diberikan pada Gambar 3.4. Pada gambar tersebut, kunjungan berikutnya setelah depot adalah pelanggan yang terdekat dengan depot yaitu pelanggan i; dilanjutkan dengan pelanggan berikutnya yang terdekat dengan pelanggan i, yaitu pelanggan j dengan syarat sisi berarah (i, j) fisibel.
Jika
18
kapasitas kendaraan telah terpenuhi, mulai dengan rute baru. Proses berlanjut sampai semua pelanggan terlayani.
i n
j
…
depot
Gambar 3.4 Contoh metode nearest addition.
3.2.5 Metode Insertion Metode ini bekerja dengan menyisipkan setiap kunjungan pada posisi terbaik dari suatu rute berdasarkan biaya minimum. Algoritme metode ini adalah sebagai berikut: 1. Diawali dengan membuat rute T dari depot ke sembarang pelanggan i yang belum dikunjungi. 2. Selama T belum memuat semua pelanggan yang ada, maka i.
Temukan dua pelanggan yaitu l œ T dan m – T sedemikian hingga biaya clm minimum.
ii.
Temukan posisi terbaik antara pelanggan l dan n pada T, untuk menyisipkan pelanggan k sehingga diperoleh sisi (l,k) dan (k,n). Pelanggan k dipilih
3. Ulangi langkah (2) sampai semua pelanggan dikunjungi. (Gambardella 2000) Contoh metode ini diberikan pada Gambar 3.5.
Pada gambar tersebut, rute
dimulai dari 0 menuju ke m karena biaya c0m minimum. Karena ckm minimum maka dibentuk sisi baru (0,k) dan (k,m) menggantikan sisi (0,m). Pelanggan terakhir n, diselipkan menggantikan sisi (m,0) menjadi sisi (m,n) dan (n,0).
19
k
m
0
n
Gambar 3.5 Contoh metode insertion.
3.3 Metode Perbaikan (improvement) Metode ini memperbaiki solusi fisibel dengan melakukan serangkaian pertukaran sisi dan simpul dalam rute atau antarrute kendaraan dengan tujuan mengurangi biaya solusi. Metode perbaikan antarrute dapat digunakan pada perbaikan dalam rute (Laporte & Semet 2002).
3.3.1 Perbaikan Dalam Rute Perbaikan dalam rute (intra-route improvement) adalah perbaikan yang melibatkan serangkaian pertukaran simpul dan sisi dalam satu rute. Metode ini terdiri atas 2-opt dan Or-opt.
3.3.1.1 Metode 2-opt Algoritme 2-opt merupakan salah satu algoritme local search yang mengeliminasi arc/jalur yang bersilangan pada suatu rute tunggal dengan cara mengambil 2 jalur lalu menghubungkan kembali keempat vertex/lokasi pelanggan yang berdekatan. Misalkan diberikan suatu rute c0, c1, c2, … , ck, c0. Untuk setiap kombinasi pelanggan ci, cj dengan i<j; i, j œ {1,…,k−1} akan diperiksa apakah jalur dari ci−1 ke cj dan dari ci ke cj+1 lebih baik daripada jalur awal dari ci−1 ke ci dan dari cj ke cj+1.
Jika demikian, bentuk jalur baru dari ci ke cj dan dilanjutkan untuk
kombinasi lainnya yang tersisa. Setelah semua kombinasi diperiksa, maka urutan kunjungan diperbaiki sesuai urutan perbaikan yang diperoleh. Jadi, jika urutan sebelum perbaikan adalah sebagai berikut:
20
c0, c1, c2, … , ci−1, ci, ci+1, ci+2,… , cj−1, cj, cj+1, …, ck, c0 maka setelah perbaikan menjadi c0, c1, c2, … , ci−1, cj, cj−1, cj−2,… , ci+1, ci, cj+1, cj+2,…, ck, c0 (Konig 2008) Jadi pada dasarnya metode 2-opt memindahkan dua jalur pada rute yang ada, kemudian menghubungkan kembali jalur tersebut dengan pasangan konsumen yang berbeda. Algoritmenya adalah sebagai berikut: 1. Berawal dari rute awal, 2. dua jalur yang menghubungkan 4 konsumen yang berbeda, dihapus kemudian keempat pelanggan dihubungkan kembali dengan pasangan yang berbeda, 3. jika biaya berkurang dan tidak melanggar kendala yang ada maka kembali ke langkah (2), 4. selesai. (ILOG 1999). i
j
j+1
i+1
i
j+1
j
i+1
Gambar 3.6 Contoh metode 2-opt. Contoh metode 2-opt dapat dilihat pada Gambar 3.6. Pada gambar tersebut, pelanggan i+1 yang dilayani setelah pelanggan i diubah menjadi pelanggan yang dilayani setelah pelanggan j+1, sedangkan pelanggan setelah j+1 yaitu j dilayani setelah pelanggan i+1. Hal ini dilakukan dengan mengganti sisi (i, i+1) dan (j+1, j) berturut-turut dengan sisi (i, j+1) dan (i+1, j).
3.3.1.2 Metode Or-opt Metode Or-opt identik dengan metode 2-opt, tetapi banyaknya jalur yang dapat dihapus dan ditambahkan lebih dari dua. Metode ini diperkenalkan oleh Or
21
pada tahun 1976 untuk menyelesaikan TSP. Ide dasar dari metode ini adalah merelokasi beberapa simpul (pelanggan) yang berdekatan.
Contohnya dapat
dilihat pada Gambar 3.7. Pada gambar tersebut, relokasi simpul dilakukan dengan cara mengganti tiga sisi pada rute asal dengan 3 sisi yang baru tanpa mengubah arah rute. Pelanggan i dan i+1 yang sebelumnya dilayani setelah i−1 dan sebelum i+2 diubah untuk dilayani setelah pelanggan j dan sebelum j+1. Jadi sisi (i−1, i), (i+1, i+2) dan (j, j+1) diganti berturut-turut dengan (i−1, i+2), (j, i) dan (i+1, j+1) namun tetap mempertahankan arah rute (Bräysy & Gendreau 2005).
i−1
i −1
i+2
i+2
i+1 i+1
i
i
j+1
j
j+1
j
Gambar 3.7 Contoh metode Or-opt.
3.3.2 Perbaikan Antarrute Metode perbaikan antarrute (inter-route improvement), merupakan proses pertukaran himpunan pelanggan untuk dilayani oleh tiap-tiap kendaraan. Satu pelanggan atau dua pelanggan yang berdekatan dan terhubung dipilih dari suatu rute dan dipindahkan dari posisi sekarang dengan menyisipkannya pada suatu rute yang lain. Metode ini terdiri atas metode relocate, exchange dan cross (Kyung et al. 2008).
3.3.2.1 Metode Relocate Pada metode relocate, suatu pelanggan dapat dipindahkan dari satu rute dan pelanggan tersebut ditambahkan ke rute lainnya dengan syarat biaya rute berkurang dan tidak melanggar kendala. Contoh metode relocate ini dapat dilihat pada Gambar 3.8. Pada gambar tersebut, sisi (i−1, i), (i, i+1) dan (j, j+1) diganti berturut-turut dengan sisi (i−1, i+1), (j, i) dan (i, j+1) (Bräysy & Gendreau, 2005).
22
i −1
i −1
i+1
i+1
i i j
j+1
j
j+1
Gambar 3.8 Contoh metode relocate.
3.3.2.2 Metode Exchange Pada metode exchange, dua pelanggan dari dua rute yang berbeda saling dipertukarkan tanpa melanggar kendala. Contohnya dapat dilihat pada Gambar 3.9. Pada gambar tersebut, pelanggan i dan j saling dipertukarkan. Hal ini dilakukan dengan cara mengganti sisi (i−1, i), (i, i+1), (j−1, j) dan (j, j+1) berturut-turut dengan (i−1, j), (j, i+1), (j−1, i) dan (i, j+1) (Bräysy & Gendreau 2005).
i−1
i−1
i+1
i+1
j j i j−1
i j+1
j−1
j+1
Gambar 3.9 Contoh metode exchange.
3.3.2.3 Metode Cross Metode cross saling mempertukarkan pelanggan yang ada pada akhir rute dari dua rute yang berbeda. Contoh dari metode cross terlihat pada Gambar 3.10.
23
i−1
k+1 j
i j−1
i−1
k+1
j
l
l
k
i
l+1
j−1
k l+1
Gambar 3.10 Contoh metode cross. Pada Gambar 3.10, sisi (i, k) pada rute pertama diselipkan pada rute kedua dan sisi (j, l) pada rute kedua diselipkan pada rute pertama secara bersamaan. Hal ini dilakukan dengan mengganti sisi (i−1, i), (k, k+1), (j−1, j) dan (l, l+1) dengan sisi (i−1, j), (l, k+1), (j−1, i) dan (k, l+1) (Bräysy & Gendreau 2005).
24
4 PENYELESAIAN MASALAH DISTRIBUSI ROTI “SARI ROTI”
4.1 Data Data yang digunakan dalam penelitian ini adalah data kegiatan distribusi roti “Sari Roti” di daerah Bekasi dan sekitarnya yang dilakukan setiap harinya oleh PT NIC (Nippon Indosari Corpindo) sebagai produsen roti “Sari Roti”.
Data ini
merupakan hasil penelitian Aji Raditya, mahasiswa Departemen Matematika IPB (Raditya 2009) dan terdiri atas matriks jarak antarlokasi (Lampiran 1), posisi koordinat Cartesius dari 23 pelanggan dan 1 depot, jumlah permintaan dan waktu bongkar muat pada masing-masing pelanggan (Tabel 1). Penyajian dan hasil pengolahan data pada penelitian ini, menggunakan tanda titik sebagai pemisah antara satuan dan desimal.
4.2 Deskripsi Masalah Perusahaan PT NIC memproduksi sejumlah roti setiap harinya.
Kegiatan
distribusi produk roti tersebut terdiri atas lima rute saluran yang memiliki karakteristik yang berbeda satu sama lain. Lima saluran distribusi tersebut, yaitu: agen, stock point (SP), distribution center (DC), retail/outlet (RO) dan institusi. Pada tulisan ini hanya dibatasi pada kegiatan distribusi RO di daerah Bekasi dan sekitarnya. Pada kegiatan distribusi melalui saluran RO, produk dikirim dalam satuan crate (wadah roti) kepada sejumlah pelanggan yang jumlah permintaannya telah diketahui sebelumnya. Pendistribusian dilakukan setiap hari pada pukul 07.0016.00 dan menggunakan 5 kendaraan yang sama yaitu truk 4-ban.
Selain
melakukan pengiriman produk, driver dan helper juga melakukan bongkar-muat dan mengatur produk pada tempat yang telah disediakan. Setelah driver dan helper mengunjungi seluruh pelanggan, mereka akan kembali ke pabrik (depot). Masalah yang dihadapi adalah meminimumkan total jarak tempuh dengan mempertimbangkan kendala kapasitas kendaraan dan time windows untuk memenuhi setiap permintaan pelanggan.
25
Asumsi yang digunakan dalam penelitian ini adalah: 1. semua pesanan konsumen dapat dipenuhi oleh produsen, 2. jenis roti homogen dan permintaan setiap pelanggan sudah diketahui sebelumnya, 3. kendaraan yang digunakan mempunyai kapasitas yang sama yaitu 200 crate (wadah roti), 4. setiap lokasi terhubung satu sama lain dan jarak antarlokasi simetris, artinya cij = cji, 5. karena waktu pengiriman pada setiap pelanggan dapat dilakukan kapan saja pada selang waktu pukul 07.00-16.00 maka time windows dalam satuan menit untuk semua pelanggan adalah [0, 560], 6. kecepatan kendaraan konstan yaitu 60 km/jam, 7. waktu tempuh antara pelanggan i dan j, yaitu tij, sudah termasuk lama pelayanan di pelanggan i. Tabel 1 Data pelanggan PT NIC No.
Nama Pelanggan
Jumlah Permintaan (crate) 0
Waktu Bongkar Muat (menit) 0
Koordinat Cartesius xi yi −13.631
8.695
0
PT NIC
1
Hari-Hari Bekasi Trade Centre
17
38
−7.0298
2.2886
2
Mitra Wisma Asri
3
7
−6.6594
−4.2273
3
Lion Superindo Borobudur Bekasi
7
34
−6.6025
0.1463
4
PT Contimas Utama Ind. /Blue Mall
17
69
−5.1493
1.6448
5
Carrefour Bekasi Square
8
91
−4.5309
−1.3859
6
Hero Kemang Pratama
12
37
−3.5825
1.8177
7
Giant Hypermarket Bekasi
19
28
−3.0148
0.1602
8
Lion Superindo Metropolitan Mall
17
41
−3.1175
0.4612
9
Makro Bekasi 2
2
32
−2.9581
0.8333
10
Hari-Hari Bekasi Cyber Park
19
15
−1.3809
1.1434
11
CV Naga Swalayan Pondok Ungu
37
69
−3.2144
−6.9702
12
Giant Ujung Menteng
16
42
−0.7663
−9.7032
13
Carrefour Cakung
12
54
−0.1513
−11.0930
26
No.
Nama Pelanggan
Jumlah Permintaan (crate) 22
Waktu Bongkar Muat (menit) 21
−0.0748
0.4208
Koordinat Cartesius xi yi
14
Lion Superindo Kalimalang Bekasi
15
Giant Pondok Kopi SPM
15
18
3.0291
−4.1345
16
Giant Jati Bening
9
47
4.1974
1.2394
17
Star Mart Persada Golf
4
8
6.1911
0.6274
18
Tip-Top Pondok Gede
11
60
5.6338
3.9049
19
Giant Pondok Gede
18
35
9.3217
4.1036
20
CV Naga Swalayan Jatiwaringin
18
20
7.0661
1.8967
21
Tip-Top Pondok Bambu
37
81
6.8457
1.6644
22
Giant Kalimalang
18
58
6.2007
−1.1632
23
Super Indo Pondok Bambu
25
66
6.4034
−0.4744
24
Yogya Pondok Bambu Toserba
18
73
6.9748
1.314
4.3 Formulasi Masalah Formulasi masalah distribusi roti pada subbab sebelumnya dituliskan dalam model berikut :
∑∑ ∑ c x
minimumkan z =
ij ijk
(4.1)
k∈V i∈N j∈N
dengan kendala: 9. setiap pelanggan dikunjungi tepat satu kali:
∑∑x
= 1, ∀i ∈ C
ijk
(4.2)
k∈V j∈N
10. total permintaan semua pelanggan dalam satu rute tidak melebihi kapasitas kendaraan:
∑d ∑ x i
i∈C
ijk
≤ 200 , ∀k =1,...,5
(4.3)
j∈N
11. setiap rute berawal dari depot 0:
∑x
0 jk
= 1, ∀k = 1,...,5
(4.4)
j∈C
12. setiap kendaraan yang mengunjungi suatu pelanggan pasti akan meninggalkan pelanggan tersebut:
∑x
ihk
i∈N
− ∑ xhjk = 0 , ∀h ∈ C , ∀k =1,...,5 j∈N
(4.5)
27
13. setiap rute berakhir di depot 0:
∑x
i 0k
= 1, ∀k = 1,...,5
(4.6)
i∈C
14. suatu kendaraan k yang menuju j dari i, tidak dapat tiba di j sebelum sik + tij. Jadi jika xijk > 0 maka sik + tij ≤ sjk. Bentuk linearnya adalah sik + tij − M ij (1 − xijk ) ≤ s jk , ∀i, j ∈ N , ∀k = 1,...,5
(4.7)
dengan Mij adalah konstanta besar yang tidak kurang dari nilai maksimum dari bi + tij – aj ; (i, j) œ A. 15. waktu pelayanan di setiap pelanggan memenuhi time windows: ai ≤ sik ≤ bi , ∀i ∈ N , ∀k = 1,...,5
(4.8)
16. peubah xijk merupakan peubah biner: xijk œ {0,1}, ∀i, j œ N, ∀ k = 1, ..., 5
(4.9)
dengan V
= {1,..,5} = himpunan kendaraan dengan kapasitas yang sama
C
= {1,...,24} = himpunan pelanggan atau konsumen
N
= {0,1,...,24} = himpunan vertex (simpul)
A
= {(i, j) | i, j œ N, i ≠ j} = himpunan arc (sisi berarah)
cij
= jarak dari simpul i ke simpul j
tij
= waktu tempuh dari simpul i ke simpul j
di
= jumlah permintaan pelanggan i
[ai, bi]
= time windows dari simpul i
dan untuk setiap (i, j) œ A, i ≠ n+1, j ≠ 0 dan untuk setiap kendaraan k:
xijk
1, jika kendaraan k melalui i dan langsung ke j = 0, selainnya
sik
= waktu bagi kendaraan k mulai melayani pelanggan i
dengan di adalah bilangan integer taknegatif dan ai, bi, cij, dan tij adalah bilangan taknegatif. Pada simpul depot diasumsikan a0 = b0 = an+1 = 0 dan s0k = 0 untuk setiap k.
28
4.4 Hasil dan Pembahasan Salah satu software untuk menyelesaikan metode heuristik adalah ILOG Dispatcher. Software ini merupakan suatu C++ library berbasis ILOG Solver dan menawarkan fitur-fitur yang khusus diadaptasi untuk menyelesaikan masalah rute kendaraan dengan kendala-kendala standar termasuk kapasitas kendaraan dan time windows (ILOG 1999). Software ILOG Dispatcher melakukan tahapan metode heuristik konstruktif dan metode
perbaikan
secara
bersamaan
dalam
menentukan
solusi
suatu
permasalahan. Solusi fisibel awal bagi VRP dikonstruksi dengan menggunakan salah satu dari lima metode yaitu metode saving heuristic, sweeping heuristic, nearest-to-depot, nearest addition atau insertion heuristic. Selanjutnya ILOG Dispatcher
melakukan
neighborhood
search
untuk
memperbaiki
solusi
sebelumnya dengan menerapkan perbaikan dalam rute yaitu 2-opt dan Or-opt serta perbaikan antarrute yaitu relocate, exchange dan cross. Pada penelitian ini, pengolahan data distribusi roti ”Sari Roti” dilakukan melalui tahapan-tahapan berikut: penentuan rute kendaraan dengan metode saving yang pada software ILOG Dispatcher diimplementasikan dengan fungsi
IlcSavingGenerate. Selanjutnya rute awal yang diperoleh dengan metode ini diperbaiki dengan menerapkan lima metode perbaikan secara berturut-turut yaitu 2-opt yang dijalankan dengan fungsi IlcTwoOpt, Or-opt dengan fungsi
IlcOrOpt, relocate dengan fungsi IlcRelocate, exchange dengan fungsi IlcExchange dan cross dengan fungsi IlcCross.
Hasil yang diperoleh
berupa urutan kunjungan ke pelanggan yang berawal dan berakhir di depot, lengkap dengan akumulasi muatan pada setiap pelanggan, akumulasi jarak tempuh dan waktu memulai pelayanan pada masing-masing pelanggan.
Hasil ini
dideskripsikan secara numerik dalam bentuk tabel dan secara visual dalam bentuk gambar rute kendaraan. Langkah selanjutnya adalah menentukan rute kendaraan dengan metode sweeping dengan menggunakan fungsi IlcSavingGenerate dilanjutkan dengan perbaikan menggunakan lima metode perbaikan secara berturut-turut. Hal yang sama dilakukan dengan metode nearest-to-depot, nearest addition dan insertion yang hasil rute awalnya kemudian diperbaiki dengan lima metode
29
perbaikan seperti pada metode saving dan sweeping. Metode nearest-to-depot diimplementasikan dengan fungsi IlcNearestDepotGenerate, nearest addition dengan fungsi IlcNearestAdditionGenerate, dan insertion dengan fungsi IlcInsertionGenerate.
4.4.1 Rute Kendaraan dengan Metode Saving Pengolahan data dengan menerapkan metode saving pada tahap konstruksi dan lima metode perbaikan dilakukan dengan mengeksekusi program pada Lampiran 2 dan hasilnya dapat dilihat pada Lampiran 3.
Hasil pengolahan data dengan
metode tersebut, sebagaimana dirangkum pada Tabel 2, menunjukkan 3 rute kendaraan yang diperlukan untuk melayani semua pelanggan produsen roti. Rute pertama meliputi depot, pelanggan 4 dan pelanggan 1 lalu kembali ke depot pada menit ke 129.216 dengan total jarak tempuh 22.2157 km dan total muatan kendaraan 34 crate.
Rute kedua meliputi depot, pelanggan 3, pelanggan 5,
pelanggan 7, pelanggan 8, pelanggan 9, pelanggan 10, pelanggan 14, pelanggan 16, pelanggan 20, pelanggan 19, pelanggan 18 dan pelanggan 6 lalu kembali ke depot pada menit ke 516.4 dengan total jarak tempuh 55.4002 km dan total muatan 162 crate.
Rute ketiga meliputi depot, pelanggan 2, pelanggan 11,
pelanggan 12, pelanggan 13, pelanggan 15, pelanggan 22, pelanggan 23, pelanggan 17, pelanggan 24 dan pelanggan 21 lalu berakhir di depot pada menit ke 537.178 setelah menempuh jarak 61.1778 km dan membawa total muatan 185 crate. Deskripsi rutenya dapat dilihat pada Gambar 4.1. Tabel 2 Rute kendaraan dengan metode saving Kode
0 4 1 0 0 3 5 7 8 9
Nama Pelanggan
Akumulasi Jarak Tempuh (km)
Kendaraan Pertama PT NIC 0 PT Contimas Utama Ind. (Blue Mall) 11.0293 Hari-Hari Bekasi Trade Centre 13.0169 PT NIC 22.2157 Kendaraan Kedua PT NIC 0 Lion Superindo Borobudur Bekasi 11.0671 Carrefour Bekasi Square 13.6437 Giant Hypermarket Bekasi 15.8091 Lion Superindo Metropolitan Mall 16.1272 Makro Bekasi 2 16.532
Waktu Memulai Pelayanan (menit)
Akumulasi Muatan (crate)
0 11.0293 82.0169 129.216
0 17 34 34
0 11.0671 47.6437 140.809 169.127 210.532
0 7 15 34 51 53
30
10 14 16 20 19 18 6 0 0 2 11 12 13 15 22 23 17 24 21 0
Akumulasi Jarak Tempuh (km)
Nama Pelanggan
Kode
Hari-Hari Bekasi Cyber Park Lion Superindo Kalimalang Bekasi Giant Jati Bening CV Naga Swalayan (Jatiwaringin) Giant Pondok Gede Tip-Top Pondok Gede Hero Kemang Pratama PT NIC
18.1394 19.632 23.982 26.925 30.0807 33.7739 43.2236 55.4002 Kendaraan Ketiga PT NIC 0 Mitra Wisma Asri 14.683 CV Naga Swalayan (Pondok Ungu) 19.0865 Giant Ujung Menteng 22.7557 Carrefour Cakung 24.2754 Giant Pondok Kopi SPM 31.9263 Giant Kalimalang 36.2723 Super Indo Pondok Bambu 36.9903 Star Mart Persada Golf 38.1124 Yogya Pondok Bambu Toserba 39.1543 Tip-Top Pondok Bambu 39.5277 PT NIC 61.1778
Waktu Memulai Pelayanan (menit) 244.139 260.632 285.982 335.925 359.081 397.774 467.224 516.4
Akumulasi Muatan (crate) 72 94 103 121 139 150 162 162
0 14.683 26.0865 98.7557 142.275 203.926 226.272 284.99 352.112 361.154 434.528 537.178
0 3 40 56 68 83 101 126 130 148 185 185
0
19
18 1
20
6
4
9
21
10
16
8
3
17 23 22
14
7 5
2
15
11
Rute kendaraan pertama: Rute kendaraan kedua:
24
12
13
Rute kendaraan ketiga:
Gambar 4.1 Rute kendaraan dengan metode saving.
31
4.4.2 Rute Kendaraan dengan Metode Sweeping Konstruksi rute distribusi roti dengan metode sweeping dan improvement rute dengan lima metode perbaikan dilakukan dengan mengeksekusi program pada Lampiran 4 dan hasilnya dapat dilihat pada Lampiran 5. Hasil pengolahan data tersebut dirangkum pada Tabel 3 dan rutenya pada Gambar 4.2. Dari tabel dan gambar tersebut terlihat 3 rute kendaraan yang diperlukan untuk mengoptimalkan kegiatan distribusi produk roti. Tabel 3 Rute kendaraan dengan metode sweeping Kode
0 1 4 0 0 6 10 14 9 8 7 5 12 13 11 2 3 0 0 15 22 23 17 24 21 20 19 18 16 0
Akumulasi Jarak tempuh (km) Kendaraan Pertama PT NIC 0 Hari-Hari Bekasi Trade Centre 9.19879 PT Contimas Utama Ind. /Blue Mall 11.1864 PT NIC 22.2157 Kendaraan Kedua PT NIC 0 Hero Kemang Pratama 12.1766 Hari-Hari Bekasi Cyber Park 14.4791 Lion Superindo Kalimalang Bekasi 15.9718 Makro Bekasi 2 18.8845 Lion Superindo Metropolitan Mall 19.2893 Giant Hypermarket Bekasi 19.6037 Carrefour Bekasi Square 21.7727 Giant Ujung Menteng 30.9023 Carrefour Cakung 32.442 CV Naga Swalayan (Pondok Ungu) 37.5583 Mitra Wisma Asri 41.9619 Giant Pondok Gede 46.3358 PT NIC 57.4029 Kendaraan Ketiga PT NIC 0 Giant Pondok Kopi SPM 21.0275 Giant Kalimalang 25.3735 Super Indo Pondok Bambu 26.0915 Star Mart Persada Golf 27.2135 Yogya Pondok Bambu Toserba 28.2555 Tip-Top Pondok Bambu 28.6289 CV Naga Swalayan (Jatiwaringin) 28.9491 Giant Pondok Gede 32.1048 Tip-Top Pondok Gede 35.798 Giant Jati Bening 38.8259 PT NIC 58.1505 Nama Pelanggan
Waktu Memulai Pelayanan (menit)
Akumulasi Muatan (crate)
0 9.19879 49.1864 129.216
0 17 34 34
0 12.1766 51.4791 67.9718 91.8845 124.289 165.607 195.773 295.902 339.422 398.558 471.962 483.336 528.403
0 12 31 53 55 72 91 99 115 127 164 167 174 174
0 21.0275 43.3735 102.091 169.214 178.255 251.629 332.949 356.105 394.798 457.826 524.15
0 15 33 58 62 80 117 135 153 164 173 173
32
0
19
18 1
20
6
4
9
21
10
8
3
24
16 17 23 22
14
7 5
2
15
11
Rute kendaraan pertama : Rute kendaraan kedua
:
Rute kendaraan ketiga
:
12
13
Gambar 4.2 Rute kendaraan dengan metode sweeping. 4.4.3 Rute Kendaraan dengan Metode Nearest-to-depot Pengolahan data dengan menerapkan metode nearest-to-depot pada tahap konstruksi dan lima metode perbaikan dilakukan dengan mengeksekusi program pada Lampiran 6 dan hasilnya dapat dilihat pada Lampiran 7. Hasil pengolahan data tersebut dideskripsikan pada Tabel 4.
Rute kendaraan diberikan pada
Gambar 4.3. Guna memenuhi permintaan pelanggan dan mengoptimumkan biaya distribusi, diperlukan 3 rute kendaraan sebagaimana disajikan dalam tabel dan gambar tersebut. Tabel 4 Rute kendaraan dengan metode nearest-to-depot Kode
0 6 9 8 7 4 1 0
Akumulasi Jarak tempuh (km) Kendaraan Pertama PT NIC 0 Hero Kemang Pratama 12.1766 Makro Bekasi 2 13.3423 Lion Superindo Metropolitan Mall 13.7471 Giant Hypermarket Bekasi 14.0652 PTContimas Utama Ind. /Blue Mall 16.6652 Hari-Hari Bekasi Trade Centre 18.6528 PT NIC 27.8516 Nama Pelanggan
Waktu Memulai Pelayanan (menit)
Akumulasi Muatan (crate)
0 12.1766 50.3423 82.7471 124.065 154.665 18.6528 272.852
0 12 14 31 50 67 84 84
33
Kode
0 16 22 23 17 24 21 20 19 18 0 0 10 14 15 13 12 11 2 5 3 0
Akumulasi Jarak tempuh (km) Kendaraan Kedua PT NIC 0 Giant Jati Bening 19.3245 Giant Kalimalang 22.4527 Super Indo Pondok Bambu 23.1708 Star Mart Persada Golf 24.2928 Yogya Pondok Bambu Toserba 25.3347 Tip-Top Pondok Bambu 25.7082 CV Naga Swalayan (Jatiwaringin) 26.0284 Giant Pondok Gede 29.184 Tip-Top Pondok Gede 32.8773 PT NIC 52.7287 Kendaraan Ketiga PT NIC 0 Hari-Hari Bekasi Cyber Park 14.3907 Lion Superindo Kalimalang Bekasi 15.8833 Giant Pondok Kopi SPM 21.3956 Carrefour Cakung 29.0465 Giant Ujung Menteng 30.5663 CV Naga Swalayan (Pondok Ungu) 34.2354 Mitra Wisma Asri 38.639 Carrefour Bekasi Square 42.1892 Giant Pondok Gede 44.7658 PT NIC 55.8329 Nama Pelanggan
Waktu Memulai Pelayanan (menit)
Akumulasi Muatan (crate)
0 19.3245 69.4527 128.171 195.293 204.335 277.708 359.028 382.184 420.877 500.729
0 9 27 52 56 74 111 129 147 158 158
0 14.3907 30.8833 57.3956 83.0465 138.566 184.235 257.639 268.189 361.766 406.833
0 19 41 56 68 84 121 124 132 139 139
0
19
18 1
20
6
4
9
21
10
8
3
24
16 17
14
7
23
5
22
2
15
11
Rute kendaraan pertama : Rute kendaraan kedua
:
Rute kendaraan ketiga
:
12
13
Gambar 4.3 Rute kendaraan dengan metode nearest-to-depot.
34
4.4.4 Rute Kendaraan dengan Metode Nearest Addition Pada pengolahan data dengan metode nearest addition, diperoleh hasil seperti yang diberikan pada Tabel 5. Hasil ini diperoleh dengan cara mengeksekusi program pada Lampiran 8 dan hasilnya ditampilkan pada Lampiran 9. Dari hasil tersebut diperoleh tiga rute kendaraan yang harus digunakan untuk memenuhi permintaan pelanggan.
Urutan pelanggan, akumulasi jarak dan muatan serta
waktu memulai pelayanan dari setiap pelanggan dapat dilihat pada Tabel 5. Rute kendaraan diberikan pada Gambar 4.4. Tabel 5 Rute kendaraan dengan metode nearest addition Kode
0 1 4 0 0 3 5 2 11 12 13 15 22 23 6 0 0 9 8 7 10 14 16 17 24 21 20 19 18 0
Nama Pelanggan
Akumulasi Jarak Tempuh (km)
Kendaraan Pertama PT NIC 0 Hari-Hari Bekasi Trade Centre 9.19879 PTContimas Utama Ind. /Blue Mall 11.1864 PT NIC 22.2157 Kendaraan Kedua PT NIC 0 Giant Pondok Gede 11.0671 Carrefour Bekasi Square 13.6437 Mitra Wisma Asri 17.194 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 Superindo Pondok Bambu 39.5013 Hero Kemang Pratama 49.7469 PT NIC 61.9235 Kendaraan Ketiga 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.229 CV Naga Swalayan (Jatiwaringin) 25.2493 Giant Pondok Gede 28.7049 Tip-Top Pondok Gede 32.3982 PT NIC 52.2495
Waktu Memulai Pelayanan (menit)
Akumulasi muatan (create)
0 9.19879 49.1864 129.216
0 17 34 34
0 11.0671 47.6437 142.194 153.598 226.267 269.786 331.437 353.783 412.501 488.747 537.923
0 7 15 18 55 71 83 98 116 141 153 153
0 13.2558 45.6606 86.9787 116.886 133.378 158.728 207.814 216.856 290.229 371.549 394.705 433.398 513.25
0 2 19 38 57 79 88 92 110 147 165 183 194 194
35
0
19
18 1
20
6
4
9
21
10
8
3
24
16 17 23 22
14
7 5
2
15
11
Rute kendaraan pertama : Rute kendaraan kedua
:
Rute kendaraan ketiga
:
12
13
Gambar 4.4 Rute kendaraan dengan metode nearest addition. 4.4.5 Rute Kendaraan dengan Metode Insertion Hasil pengolahan data dengan metode insertion diperoleh dengan mengeksekusi program pada Lampiran 10.
Lampiran 11 menggambarkan hasil pengolahan
datanya. Secara sistematis, hasil tersebut ditampilkan pada Tabel 6. Dari tabel tersebut terlihat tiga rute kendaraan yang diperlukan untuk melayani pelanggan lengkap dengan urutan pelanggan, akumulasi jarak dan muatan serta waktu memulai pelayanan.
Gambar 4.5 mendeskripsikan rute kendaraan dalam
mendistribusikan roti ke lokasi pelanggan. Tabel 6 Rute kendaraan dengan metode insertion Kode
0 18 19 20 21 24 17 23
Nama Pelanggan
Jarak Tempuh (km)
Kendaraan Pertama PT NIC 0 Tip-Top Pondok Gede 19.8514 Giant Pondok Gede 23.5446 CV Naga Swalayan (Jatiwaringin) 26.7003 Tip-Top Pondok Bambu 27.0205 Yogya Pondok Bambu Toserba 27.3939 Star Mart Persada Golf 28.4359 Super Indo Pondok Bambu 29.5579
Waktu Memulai Pelayanan (menit)
Akumulasi Muatan (crate)
0 19.8514 83.5446 121.7 142.021 223.394 297.436 306.558
0 11 29 47 84 102 106 131
36
Kode
Jarak Tempuh (km)
Nama Pelanggan
22 16 14 10 0
Giant Kalimalang 30.2759 Giant Jati Bening 33.4041 Lion Superindo Kalimalang Bekasi 37.7541 Hari-Hari Bekasi Cyber Park 39.2467 PT NIC 53.6374 Kendaraan Kedua PT NIC 0 Giant Pondok Gede 11.0671 Carrefour Bekasi Square 13.6437 Mitra Wisma Asri 17.194 CV Naga Swalayan (Pondok Ungu) 21.5975 Giant Ujung Menteng 25.2667 Carrefour Cakung 26.7864 Giant Pondok Kopi SPM 34.4373 Giant Hypermarket Bekasi 41.5817 Lion Superindo Metropolitan Mall 42.1697 Makro Bekasi 2 42.5745 Hero Kemang Pratama 43.7403 PT NIC 55.9169 Kendaraan Ketiga PT NIC 0 Hari-Hari Bekasi Trade Centre 9.19879 PTContimas Utama Ind. /Blue Mall 11.1864 PT NIC 22.2157
0 3 5 2 11 12 13 15 7 8 9 6 0 0 1 4 0
Waktu Memulai Pelayanan (menit) 373.276 434.404 485.754 508.247 537.637
Akumulasi Muatan (crate) 149 158 180 199 199
0 11.0671 47.6437 142.194 153.598 226.267 269.786 331.437 356.852 385.17 426.575 459.74 508.917
0 7 15 18 55 71 83 98 117 134 136 148 148
0 9.19879 49.1864 129.216
0 17 34 34
0
19
18 1
20
6
4
9
21
10
8
3
24
16 17
14
7
23
5
22
2
15
11
Rute kendaraan pertama : Rute kendaraan kedua
:
Rute kendaraan ketiga
:
12
13
Gambar 4.5 Rute kendaraan dengan metode insertion.
37
4.4.6 Pembandingan Kelima Metode Heuristik Konstruktif Pembandingan kualitas solusi beberapa metode heuristik dapat dilakukan dengan membandingkan kriteria tertentu seperti waktu eksekusi program, kemudahan implementasi dan fleksibilitas dari metode tersebut. Pada penelitian ini dilakukan pembandingan hasil pengolahan data menggunakan kelima metode konstruksi berdasarkan total jarak tempuh, total muatan dan waktu tempuh. Tabel 7 Perbandingan hasil kelima metode konstruksi Metode
Saving Sweeping Nearestto-depot Nearest Addition Insertion
Jarak 22.2157 22.2157 27.8516
Kendaraan 1 Muatan Waktu 34 129.216 34 129.216 84 272.852
Jarak 55.4002 57.4029 52.7287
Kendaraan 2 Muatan Waktu 162 516.4 174 528.403 158 500.729
Jarak 61.1778 58.1505 55.8329
Kendaraan 3 Muatan Waktu 185 537.178 173 524.15 139 402.833
22.2157
34
129.216
61.9235
153
537.923
52.2495
194
513.25
53.6374
199
537.637
55.9169
148
508.917
22.2157
34
129.216
Berdasarkan Tabel 7, jarak tempuh, muatan dan waktu yang dibutuhkan kendaraan pertama untuk menyelesaikan rutenya pada metode saving, sweeping dan nearest addition sama karena rutenya tidak berbeda yaitu meliputi depot, pelanggan 1 dan 4; sedangkan hasil dari metode nearest-to-depot dan insertion relatif berbeda. Pada kendaraan kedua dan ketiga, hasil dari kelima metode relatif berbeda satu sama lainnya. Pada setiap metode, dua dari tiga kendaraan yang beroperasi mempunyai total jarak tempuh, total muatan, dan waktu tempuh yang relatif sama. Tabel 8 Perbandingan jarak dan waktu eksekusi kelima metode konstruksi Metode Konstruksi
Saving Sweeping Nearest-to-depot Nearest Addition Insertion
Total Jarak (km) 138.794 137.769 136.413 136.389 131.77
Waktu Eksekusi (detik) 0.031 0.078 0.109 0.063 0.078
Pada Tabel 8 dan Gambar 4.6 diberikan evaluasi terhadap masing-masing metode berdasarkan total jarak tempuh dan waktu eksekusi program. Berdasarkan tabel tersebut, banyaknya kendaraan yang digunakan untuk melayani semua pelanggan
38
roti adalah sama yaitu 3 unit. Total jarak tempuh relatif tidak berbeda nyata. Jarak terkecil diperoleh dari metode insertion dengan 131.77 km sedangkan jarak terbesar pada metode saving, dengan 138.794 km. Sebaliknya jika ditinjau dari waktu eksekusi program, metode saving hanya memerlukan 0.031 detik dan waktu eksekusi program metode nearest-to-depot paling lama yaitu 0.109 detik. Metode sweeping dan insertion memerlukan waktu yang sama untuk eksekusinya. Dari pembandingan hasil kelima metode heuristik ini, perbedaan total jarak tempuh semua kendaraan dapat menjadi pertimbangan bagi PT NIC untuk memilih rute kendaraan yang dapat dipakai guna meminimalkan biaya distribusi produk dari perusahaan sedangkan waktu eksekusi program dapat menjadi masukan bagi pengembangan metode heuristik untuk masalah yang berukuran besar. 0.12 Nearest-todepot
Waktu Eksekusi (detik)
0.1
0.08
Sweeping
Insertion Nearest Addition
0.06
0.04 Saving 0.02
0 131
132
133
134
135
136
137
138
139
140
Total Jarak Tempuh (Km)
Gambar 4.6 Perbandingan waktu eksekusi dan total jarak tempuh kelima metode konstruksi.
39
5 SIMPULAN DAN SARAN
5.1 Simpulan Masalah distribusi dapat dimodelkan dalam suatu vehicle routing problem time windows. Hasil pembandingan lima metode heuristik konstruktif yang diterapkan pada data distribusi roti “Sari Roti” menunjukkan bahwa, jarak tempuh terkecil dari kegiatan distribusi diberikan oleh metode insertion dan jarak tempuh terbesar pada metode saving, sebaliknya waktu eksekusi program tercepat diperoleh dari metode saving dan paling lama pada metode nearest-to-depot. Total jarak tempuh distribusi dapat menjadi pertimbangan bagi PT NIC untuk memilih rute kendaraan yang dapat digunakan untuk efisiensi perusahaan sedangkan waktu eksekusi program dapat menjadi masukan bagi pengembangan metode heuristik untuk masalah penentuan rute yang berukuran besar. 5.2 Saran Hasil pembandingan beberapa metode heuristik akan lebih akurat jika melibatkan beberapa contoh permasalahan dengan jumlah pelanggan yang berbeda dan menggunakan metode yang lebih bervariasi.
40
DAFTAR PUSTAKA
Ahuja RK, Magnanti TL, Orlin JB. 1993. Network Flow: Theory, Algorithms and Applications. New Jersey: Prentice Hall. Altinel IK, Öncan T. 2005. A new enhancement of Clarke and Wright savings heuristic for the capacitated vehicle routing problem. Journal of the Operational Research Society 56: 954−961. Bräysy O, Gendreau M. 2005. Vehicle routing problem with time windows. Part I: route construction and local search algorithms. Transportation Science 39 (1): 104−118. Cordeau J−F, Gendreau M, Laporte G, Potvin JY, Semet F. 2002. A guide to vehicle routing heuristics. Journal of the Operational Research Society 53: 512−522. Foulds LR. 1992. Graph Theory Applications. New York: Springer-Verlag. Gambardella LM. 2000. Vehicle http://www.indsia.ch/luca.html. [21 Juni 2009].
routing
problems.
Garfinkel RS, Nemhauser GL. 1972. Integer Programming. New York: John Wiley & Sons. [ILOG]. 1999. ILOG Dispatcher 2.1. User’s Manual. France: ILOG. Kallehauge B, Larsen J, Madsen OBG, Solomon MM. 2005. Vehicle routing with time windows. Di dalam Desaulniers G et al., editor. Column Generation. New York: Springer. hlm 67−98. Konig F. 2008. Scheduling in water business [Diploma Thesis]. Karlsruhe: Faculty of Informatics, Universitat Karlsruhe. Kyung HK, Byung KL, Yoon HL, Young HL. 2008. A heuristic for the vehicle routing problem with due times. Computers and Industrial Engineering 54: 421−431. Laporte G, Semet, F. 2002. Classical heuristics for the capacitated VRP. Di dalam Toth P, Vigo D, editor. The Vehicle Routing Problem. Philadelphia: Siam. hlm 109−128. Larsen J. 2001. Parallelization of the vehicle routing with time windows. [Ph. D Thesis]. Denmark: Department of Mathematical Modeling. Lyngby: University of Denmark. Raditya A. 2009. Penggunaan metode heuristik pada VRP dalam meminimumkan banyaknya dan jarak tempuh kendaraan. [Skripsi]. Bogor: Departemen Matematika, Institut Pertanian Bogor. Rich JL. 1999. A computational study of vehicle routing applications. [Ph. D Thesis]. Texas: Rice University.
41
Toth P, Vigo D. 2002. An overview of vehicle routing problems. Di dalam Toth, P, Vigo D, editor. The Vehicle Routing Problem. Philadelphia: Siam. hlm 1−26.
42
LAMPIRAN
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 0.00 9.20 14.68 11.07 11.03 11.67 12.18 13.62 13.35 13.26 14.39 18.81 22.45 23.94 15.88 1 0.00 6.53 2.18 1.99 2.66 3.48 4.54 4.32 4.32 5.76 10.01 13.53 15.05 7.20 2 0.00 4.37 6.06 6.00 6.78 5.70 5.88 6.27 7.53 4.40 8.04 9.46 8.06 3 0.00 2.09 2.41 3.45 3.59 3.50 3.71 5.32 7.88 11.45 12.96 6.53 4 0.00 0.67 1.58 2.60 2.35 2.34 3.80 8.83 12.17 13.68 5.22 5 0.00 1.04 1.95 1.69 1.67 3.16 8.46 11.71 13.23 4.56 6 0.00 1.75 1.43 1.17 2.30 8.80 11.86 13.36 3.78 7 0.00 0.32 0.68 1.91 7.13 10.12 11.61 2.95 8 0.00 0.40 1.87 7.43 10.43 11.93 3.04 9 0.00 1.61 7.81 10.76 12.25 2.91 10 0.00 8.32 10.86 12.30 1.49 11 0.00 3.67 5.14 8.03 12 0.00 1.52 10.15 13 0.00 11.51 14 0.00 15 16 17 18 19 20 21 22 23 24
Lampiran 1 Matriks jarak antarlokasi 15 21.03 11.94 9.69 10.54 10.01 9.36 8.90 7.41 7.67 7.78 6.88 6.86 6.74 7.65 5.51 0.00
16 19.33 11.28 12.16 10.86 9.36 8.73 7.80 7.29 7.36 7.17 5.58 11.06 12.02 13.08 4.35 5.50 0.00
17 21.40 13.33 13.74 12.80 11.39 10.75 9.85 9.22 9.31 9.15 7.59 12.09 12.46 13.33 6.27 5.72 2.09 0.00
18 19.28 13.86 17.28 14.50 12.48 12.09 11.06 11.62 11.50 11.14 9.76 17.32 18.75 19.88 9.43 12.34 6.84 7.32 0.00
19 23.41 16.45 18.02 16.41 14.68 14.12 13.11 12.95 12.96 12.71 11.10 16.73 17.10 17.91 10.09 10.37 5.87 4.68 5.31 0.00
20 21.79 14.10 15.03 13.78 12.22 11.61 10.65 10.23 10.28 10.08 8.48 13.58 14.00 14.86 7.29 7.26 2.94 1.54 6.19 3.16 0.00
21 21.65 13.89 14.73 13.53 12.00 11.38 10.43 9.97 10.04 9.84 8.24 13.26 13.68 14.55 7.03 6.94 2.68 1.23 6.37 3.48 0.32 0.00
22 22.15 13.67 13.22 12.87 11.69 11.03 10.23 9.31 9.46 9.37 7.92 11.06 11.02 11.79 6.47 4.35 3.13 1.79 9.10 6.12 3.18 2.90 0.00
23 22.03 13.71 13.59 13.02 11.75 11.09 10.25 9.44 9.57 9.45 7.95 11.61 11.69 12.48 6.54 4.98 2.79 1.12 8.43 5.43 2.46 2.18 0.72 0.00
24 21.89 14.04 14.72 13.63 12.13 11.51 10.57 10.06 10.13 9.94 8.36 13.13 13.47 14.31 7.11 6.73 2.78 1.04 6.74 3.65 0.59 0.37 2.60 1.88 0.00
43
44
Lampiran 2 Program penentuan rute dengan metode saving menggunakan software ILOG
// ---------------------------------------- -*- C++ -*// File: examples/src/vrp.cpp // ---------------------------------------------------#include
#if defined(ILUSESTL) #include #include #include <string> #else #include #include #include <string.h> #endif ILCSTLBEGIN void Info(IlcManager m, IlcRoutingPlan plan, char * problem) { m.printInformation(); plan.printInformation(); m.out() << "===============" << endl << "Problem name : " << problem << endl << "Cost : " << plan.getTotalCost() << endl << "Number of vehicles used : " << plan.getNbOfVehiclesUsed() << endl << "Solution : " << endl << plan << endl; } int main(int argc, char* argv[]) { IlcManager m(IlcEdit); #if defined(ILCLOGFILE) m.openLogFile("vrp.log"); #endif IlcRoutingPlan plan(m); IlcDimension2 time(plan, IlcEuclidean, "Time"); IlcDimension2 length(plan, IlcEuclidean, "Length"); IlcDimension1 weight(plan, "Weight"); ifstream infile;
45
char * problem; if (argc >=2) problem = argv[1]; else problem = (char *) "../../../examples/data/sariroti.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; IlcFloat capacity; infile >> capacity; IlcFloat depotX, depotY, openTime, closeTime; infile >> depotX >> depotY >> openTime >> closeTime; IlcNode depot(plan, depotX, depotY); for (IlcInt j = 0; j < nbOfTrucks; j++) { IlcVisit first(depot, "Depot"); m.add(first.getCumulVar(time) >= openTime); IlcVisit last(depot, "Depot"); m.add(last.getCumulVar(time) <= closeTime); char name[16]; sprintf(name, "Vehicle %d\0", j); IlcVehicle vehicle(plan, first, last, name); vehicle.setCost(length, 1.0); vehicle.setCapacity(weight, capacity); } for (IlcInt i = 0; i < nbOfVisits; i++) { IlcInt id; // visit identifier IlcFloat x, y, quantity, minTime, maxTime, dropTime; infile >> id >> x >> y >> quantity >> minTime >> maxTime >> dropTime; IlcNode customer(plan, x, y); char name[16]; sprintf(name, "%d\0", id); IlcVisit visit(customer, name); visit.setDelay(time, dropTime);
46
visit.setQuantity(weight, quantity); ILCSETWINDOW(visit.getCumulVar(time), minTime <= var && var <= maxTime); } infile.close(); IlcGoal generateGoal = IlcSavingsGenerate(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); plan.improve(5, IlcTwoOpt(plan), IlcOrOpt(plan), IlcRelocate(plan), IlcExchange(plan), IlcCross(plan)); } Info(m, plan, problem); #if defined(ILCLOGFILE) m.closeLogFile(); #endif m.end(); return 0; } /*-----------------------------------------------------
47
Lampiran 3 Hasil penentuan rute dengan metode saving
Total memory used (bytes) : 390244 Elapsed time since creation : 0.031 Number of nodes : 25 =============== Problem name : ../../../examples/data/sariroti.dat Cost : 138.794 Number of vehicles used : 3 Solution : Unperformed visits : None Vehicle 0 :
Unused
Vehicle 1 :
Unused
Vehicle 2 : -> Depot Time[0..410.784] Length[0..1.#INF) Weight[0..166] -> 4 Time[11.0293..421.814] Length[11.0293..1.#INF) Weight[0..166] -> 1 Time[82.0169..492.801] Length[13.0169..1.#INF) Weight[17..183] -> Depot Time[129.216..540] Length[22.2157..1.#INF) Weight[34..200] Vehicle 3 : -> Depot Time[0..23.5998] Length[0..1.#INF) Weight[0..38] -> 3 Time[11.0671..34.6669] Length[11.0671..1.#INF) Weight[0..38] -> 5 Time[47.6437..71.2435] Length[13.6437..1.#INF) Weight[7..45] -> 7 Time[140.809..164.409] Length[15.8091..1.#INF) Weight[15..53] -> 8Time[169.127..192.727] Length[16.1272..1.#INF) Weight[34..72] -> 9 Time[210.532..234.132] Length[16.532..1.#INF) Weight[51..89] -> 10 Time[244.139..267.739] Length[18.1394..1.#INF) Weight[53..91] -> 14 Time[260.632..284.232] Length[19.632..1.#INF) Weight[72..110] -> 16 Time[285.982..309.582] Length[23.982..1.#INF) Weight[94..132] -> 20 Time[335.925..359.525] Length[26.925..1.#INF) Weight[103..141] -> 19 Time[359.081..382.68] Length[30.0807..1.#INF) Weight[121..159] -> 18 Time[397.774..421.374] Length[33.7739..1.#INF) Weight[139..177] -> 6
48
Time[467.224..490.823] Length[43.2236..1.#INF) Weight[150..188] -> Depot Time[516.4..540] Length[55.4002..1.#INF) Weight[162..200] Vehicle 4 : -> Depot Time[0..2.82222] Length[0..1.#INF) Weight[0..15] -> 2 Time[14.683..17.5052] Length[14.683..1.#INF) Weight[0..15] -> 11 Time[26.0865..28.9088] Length[19.0865..1.#INF) Weight[3..18] -> 12 Time[98.7557..101.578] Length[22.7557..1.#INF) Weight[40..55] -> 13 Time[142.275..145.098] Length[24.2754..1.#INF) Weight[56..71] -> 15 Time[203.926..206.749] Length[31.9263..1.#INF) Weight[68..83] -> 22Time[226.272..229.095] Length[36.2723..1.#INF) Weight[83..98] -> 23 Time[284.99..287.813] Length[36.9903..1.#INF) Weight[101..116] -> 17 Time[352.112..354.935]Length[38.1124..1.#INF) Weight[126..141] -> 24 Time[361.154..363.977] Length[39.1543..1.#INF) Weight[130..145] -> 21 Time[434.528..437.35] Length[39.5277..1.#INF) Weight[148..163] -> Depot Time[537.178..540] Length[61.1778..1.#INF) Weight[185..200]
49
Lampiran 4 Program penentuan rute dengan metode sweeping menggunakan software ILOG
// ---------------------------------------- -*- C++ -*// File: examples/src/vrp.cpp // ---------------------------------------------------#include #if defined(ILUSESTL) #include #include #include <string> #else #include #include #include <string.h> #endif ILCSTLBEGIN void Info(IlcManager m, IlcRoutingPlan plan, char * problem) { m.printInformation(); plan.printInformation(); m.out() << "===============" << endl << "Problem name : " << problem << endl << "Cost : " << plan.getTotalCost() << endl << "Number of vehicles used : " << plan.getNbOfVehiclesUsed() << endl << "Solution : " << endl << plan << endl; } int main(int argc, char* argv[]) { IlcManager m(IlcEdit); #if defined(ILCLOGFILE) m.openLogFile("vrp.log"); #endif IlcRoutingPlan plan(m); IlcDimension2 time(plan, IlcEuclidean, "Time"); IlcDimension2 length(plan, IlcEuclidean, "Length"); IlcDimension1 weight(plan, "Weight"); ifstream infile;
50
char * problem; if (argc >=2) problem = argv[1]; else problem = (char *) "../../../examples/data/sariroti.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; IlcFloat capacity; infile >> capacity; IlcFloat depotX, depotY, openTime, closeTime; infile >> depotX >> depotY >> openTime >> closeTime; IlcNode depot(plan, depotX, depotY); for (IlcInt j = 0; j < nbOfTrucks; j++) { IlcVisit first(depot, "Depot"); m.add(first.getCumulVar(time) >= openTime); IlcVisit last(depot, "Depot"); m.add(last.getCumulVar(time) <= closeTime); char name[16]; sprintf(name, "Vehicle %d\0", j); IlcVehicle vehicle(plan, first, last, name); vehicle.setCost(length, 1.0); vehicle.setCapacity(weight, capacity); } for (IlcInt i = 0; i < nbOfVisits; i++) { IlcInt id; // visit identifier IlcFloat x, y, quantity, minTime, maxTime, dropTime; infile >> id >> x >> y >> quantity >> minTime >> maxTime >> dropTime; IlcNode customer(plan, x, y); char name[16]; sprintf(name, "%d\0", id); IlcVisit visit(customer, name); visit.setDelay(time, dropTime);
51
visit.setQuantity(weight, quantity); ILCSETWINDOW(visit.getCumulVar(time), minTime <= var && var <= maxTime); } infile.close(); IlcGoal generateGoal = IlcSweepGenerate(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); plan.improve(5, IlcTwoOpt(plan), IlcOrOpt(plan), IlcRelocate(plan), IlcExchange(plan), IlcCross(plan)); } Info(m, plan, problem); #if defined(ILCLOGFILE) m.closeLogFile(); #endif m.end(); return 0; } /*-----------------------------------------------------
52
Lampiran 5 Hasil penentuan rute dengan metode sweeping
Total memory used (bytes) : 380608 Elapsed time since creation : 0.078 Number of nodes : 25 =============== Problem name : ../../../examples/data/sariroti.dat Cost : 137.769 Number of vehicles used : 3 Solution : Unperformed visits : None Vehicle 0 : -> Depot Time[0..410.784] Length[0..1.#INF) Weight[0..166] -> 1 Time[9.19879..419.983] Length[9.19879..1.#INF) Weight[0..166] -> 4 Time[49.1864..459.971] Length[11.1864..1.#INF) Weight[17..183] -> Depot Time[129.216..540] Length[22.2157..1.#INF) Weight[34..200] Vehicle 1 : -> Depot Time[0..11.5971] Length[0..1.#INF) Weight[0..26] -> 6 Time[12.1766..23.7737] Length[12.1766..1.#INF) Weight[0..26] -> 10 Time[51.4791..63.0763] Length[14.4791..1.#INF) Weight[12..38] -> 14 Time[67.9718..79.5689] Length[15.9718..1.#INF) Weight[31..57] -> 9 Time[91.8845..103.482] Length[18.8845..1.#INF) Weight[53..79] -> 8 Time[124.289..135.886] Length[19.2893..1.#INF) Weight[55..81] -> 7 Time[165.607..177.204] Length[19.6073..1.#INF) Weight[72..98] -> 5 Time[195.773..207.37] Length[21.7727..1.#INF) Weight[91..117] -> 12 Time[295.902..307.499] Length[30.9023..1.#INF) Weight[99..125] -> 13 Time[339.422..351.019] Length[32.4221..1.#INF) Weight[115..141] -> 11 Time[398.558..410.155] Length[37.5583..1.#INF) Weight[127..153] -> 2 Time[471.962..483.559] Length[41.9619..1.#INF) Weight[164..190] -> 3 Time[483.336..494.933] Length[46.3358..1.#INF) Weight[167..193] -> Depot Time[528.403..540] Length[57.4029..1.#INF) Weight[174..200]
53
Vehicle 2 : -> Depot Time[0..15.8495] Length[0..1.#INF) Weight[0..27] -> 15 Time[21.0275..36.877] Length[21.0275..1.#INF) Weight[0..27] -> 22 Time[43.3735..59.223] Length[25.3735..1.#INF) Weight[15..42] -> 23 Time[102.091..117.941] Length[26.0915..1.#INF) Weight[33..60] -> 17 Time[169.214..185.063] Length[27.2135..1.#INF) Weight[58..85] -> 24 Time[178.255..194.105] Length[28.2555..1.#INF) Weight[62..89] -> 2 1 Time[251.629..267.478] Length[28.6289..1.#INF) Weight[80..107] -> 20 Time[332.949..348.799] Length[28.9491..1.#INF) Weight[117..144] -> 19 Time[356.105..371.954] Length[32.1048..1.#INF) Weight[135..162] -> 18 Time[394.798..410.648] Length[35.798..1.#INF) Weight[153..180] -> 16 Time[457.826..473.675] Length[38.8259..1.#INF) Weight[164..191] -> Depot Time[524.15..540] Length[58.1505..1.#INF) Weight[173..200] Vehicle 3 :
Unused
Vehicle 4 :
Unused
54
Lampiran 6 Program penentuan rute dengan metode nearest-to-depot menggunakan software ILOG
// ---------------------------------------- -*- C++ -*// File: examples/src/vrp.cpp // ---------------------------------------------------#include #if defined(ILUSESTL) #include #include #include <string> #else #include #include #include <string.h> #endif ILCSTLBEGIN void Info(IlcManager m, IlcRoutingPlan plan, char * problem) { m.printInformation(); plan.printInformation(); m.out() << "===============" << endl << "Problem name : " << problem << endl << "Cost : " << plan.getTotalCost() << endl << "Number of vehicles used : " << plan.getNbOfVehiclesUsed() << endl << "Solution : " << endl << plan << endl; } int main(int argc, char* argv[]) { IlcManager m(IlcEdit); #if defined(ILCLOGFILE) m.openLogFile("vrp.log"); #endif IlcRoutingPlan plan(m); IlcDimension2 time(plan, IlcEuclidean, "Time"); IlcDimension2 length(plan, IlcEuclidean, "Length"); IlcDimension1 weight(plan, "Weight"); ifstream infile;
55
char * problem; if (argc >=2) problem = argv[1]; else problem = (char *) "../../../examples/data/sariroti.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; IlcFloat capacity; infile >> capacity; IlcFloat depotX, depotY, openTime, closeTime; infile >> depotX >> depotY >> openTime >> closeTime; IlcNode depot(plan, depotX, depotY); for (IlcInt j = 0; j < nbOfTrucks; j++) { IlcVisit first(depot, "Depot"); m.add(first.getCumulVar(time) >= openTime); IlcVisit last(depot, "Depot"); m.add(last.getCumulVar(time) <= closeTime); char name[16]; sprintf(name, "Vehicle %d\0", j); IlcVehicle vehicle(plan, first, last, name); vehicle.setCost(length, 1.0); vehicle.setCapacity(weight, capacity); } for (IlcInt i = 0; i < nbOfVisits; i++) { IlcInt id; // visit identifier IlcFloat x, y, quantity, minTime, maxTime, dropTime; infile >> id >> x >> y >> quantity >> minTime >> maxTime >> dropTime; IlcNode customer(plan, x, y); char name[16]; sprintf(name, "%d\0", id); IlcVisit visit(customer, name); visit.setDelay(time, dropTime);
56
visit.setQuantity(weight, quantity); ILCSETWINDOW(visit.getCumulVar(time), minTime <= var && var <= maxTime); } infile.close(); IlcGoal generateGoal = IlcNearestDepotGenerate(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); plan.improve(5, IlcTwoOpt(plan), IlcOrOpt(plan), IlcRelocate(plan), IlcExchange(plan), IlcCross(plan)); } Info(m, plan, problem); #if defined(ILCLOGFILE) m.closeLogFile(); #endif m.end(); return 0; } /*-----------------------------------------------------
57
Lampiran 7 Hasil penentuan rute dengan metode nearest-to-depot
Total memory used (bytes) : 380608 Elapsed time since creation : 0.109 Number of nodes : 25 =============== Problem name : ../../../examples/data/sariroti.dat Cost : 136.413 Number of vehicles used : 3 Solution : Unperformed visits : None Vehicle 0 : -> Depot Time[0..267.148] Length[0..1.#INF) Weight[0..116] -> 6 Time[12.1766..279.325] Length[12.1766..1.#INF) Weight[0..116] -> 9 Time[50.3423..317.491] Length[13.3423..1.#INF) Weight[12..128] -> 8 Time[82.7471..349.895] Length[13.7471..1.#INF) Weight[14..130] -> 7 Time[124.065..391.214] Length[14.0652..1.#INF) Weight[31..147] -> 4 Time[154.665..421.814] Length[16.6652..1.#INF) Weight[50..166] -> 1 Time[225.653..492.801] Length[18.6528..1.#INF) Weight[67..183] -> Depot Time[272.852..540] Length[27.8516..1.#INF) Weight[84..200] Vehicle 1 : -> Depot Time[0..39.2713] Length[0..1.#INF) Weight[0..42] -> 16 Time[19.3245..58.5959] Length[19.3245..1.#INF) Weight[0..42] -> 22 Time[69.4527..108.724] Length[22.4527..1.#INF) Weight[9..51] -> 23 Time[128.171..167.442] Length[23.1708..1.#INF) Weight[27..69] -> 17 Time[195.293..234.564] Length[24.2928..1.#INF) Weight[52..94] -> 24 Time[204.335..243.606] Length[25.3347..1.#INF) Weight[56..98] ->21 Time[277.708..316.979] Length[25.7082..1.#INF) Weight[74..116] -> 20 Time[359.028..398.3] Length[26.0284..1.#INF) Weight[111..153] -> 19 Time[382.184..421.455] Length[29.184..1.#INF) Weight[129..171] -> 18 Time[420.877..460.149] Length[32.8773..1.#INF) Weight[147..189] -> Depot
58
Time[500.729..540] Length[52.7287..1.#INF) Weight[158..200] Vehicle 2 : -> Depot Time[0..133.167] Length[0..1.#INF) Weight[0..61] -> 10 Time[14.3907..147.558] Length[14.3907..1.#INF) Weight[0..61] -> 14 Time[30.8833..164.05] Length[15.8833..1.#INF) Weight[19..80] -> 15 Time[57.3956..190.563] Length[21.3956..1.#INF) Weight[41..102] -> 13 Time[83.0465..216.214] Length[29.0465..1.#INF) Weight[56..117] -> 12 Time[138.566..271.733] Length[30.5663..1.#INF) Weight[68..129] -> 11 Time[184.235..317.402] Length[34.2354..1.#INF) Weight[84..145] -> 2 Time[257.639..390.806] Length[38.639..1.#INF) Weight[121..182] -> 5 Time[268.189..401.356] Length[42.1892..1.#INF) Weight[124..185] -> 3 Time[361.766..494.933] Length[44.7658..1.#INF) Weight[132..193] -> Depot Time[406.833..540] Length[55.8329..1.#INF) Weight[139..200] Vehicle 3 :
Unused
Vehicle 4 :
Unused
59
Lampiran 8 Program penentuan rute dengan metode nearest addition menggunakan software ILOG
// ---------------------------------------- -*- C++ -*// File: examples/src/vrp.cpp // ---------------------------------------------------#include #if defined(ILUSESTL) #include #include #include <string> #else #include #include #include <string.h> #endif ILCSTLBEGIN void Info(IlcManager m, IlcRoutingPlan plan, char * problem) { m.printInformation(); plan.printInformation(); m.out() << "===============" << endl << "Problem name : " << problem << endl << "Cost : " << plan.getTotalCost() << endl << "Number of vehicles used : " << plan.getNbOfVehiclesUsed() << endl << "Solution : " << endl << plan << endl; } int main(int argc, char* argv[]) { IlcManager m(IlcEdit); #if defined(ILCLOGFILE) m.openLogFile("vrp.log"); #endif IlcRoutingPlan plan(m); IlcDimension2 time(plan, IlcEuclidean, "Time"); IlcDimension2 length(plan, IlcEuclidean, "Length"); IlcDimension1 weight(plan, "Weight"); ifstream infile;
60
char * problem; if (argc >=2) problem = argv[1]; else problem = (char *) "../../../examples/data/sariroti.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; IlcFloat capacity; infile >> capacity; IlcFloat depotX, depotY, openTime, closeTime; infile >> depotX >> depotY >> openTime >> closeTime; IlcNode depot(plan, depotX, depotY); for (IlcInt j = 0; j < nbOfTrucks; j++) { IlcVisit first(depot, "Depot"); m.add(first.getCumulVar(time) >= openTime); IlcVisit last(depot, "Depot"); m.add(last.getCumulVar(time) <= closeTime); char name[16]; sprintf(name, "Vehicle %d\0", j); IlcVehicle vehicle(plan, first, last, name); vehicle.setCost(length, 1.0); vehicle.setCapacity(weight, capacity); } for (IlcInt i = 0; i < nbOfVisits; i++) { IlcInt id; // visit identifier IlcFloat x, y, quantity, minTime, maxTime, dropTime; infile >> id >> x >> y >> quantity >> minTime >> maxTime >> dropTime; IlcNode customer(plan, x, y); char name[16]; sprintf(name, "%d\0", id); IlcVisit visit(customer, name); visit.setDelay(time, dropTime);
61
visit.setQuantity(weight, quantity); ILCSETWINDOW(visit.getCumulVar(time), minTime <= var && var <= maxTime); } infile.close(); 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); plan.improve(5, IlcTwoOpt(plan), IlcOrOpt(plan), IlcRelocate(plan), IlcExchange(plan), IlcCross(plan)); } Info(m, plan, problem); #if defined(ILCLOGFILE) m.closeLogFile(); #endif m.end(); return 0; } /*-----------------------------------------------------
62
Lampiran 9 Hasil penentuan rute dengan metode nearest addition
Total memory used (bytes) : 380608 Elapsed time since creation : 0.063 Number of nodes : 25 =============== Problem name : ../../../examples/data/sariroti.dat Cost : 136.389 Number of vehicles used : 3 Solution : Unperformed visits : None Vehicle 0 : -> Depot Time[0..410.784] Length[0..1.#INF) Weight[0..166] -> 1 Time[9.19879..419.983] Length[9.19879..1.#INF) Weight[0..166] -> 4 Time[49.1864..459.971] Length[11.1864..1.#INF) Weight[17..183] -> Depot Time[129.216..540] Length[22.2157..1.#INF) Weight[34..200] Vehicle 1 : -> Depot Time[0..2.07651] Length[0..1.#INF) Weight[0..47] -> 3 Time[11.0671..13.1436] Length[11.0671..1.#INF) Weight[0..47] -> 5 Time[47.6437..49.7202] Length[13.6437..1.#INF) Weight[7..54] -> 2 Time[142.194..144.27] Length[17.194..1.#INF) Weight[15..62] -> 11 Time[153.598..155.674] Length[21.5975..1.#INF) Weight[18..65] -> 12 Time[226.267..228.343] Length[25.2667..1.#INF) Weight[55..102] -> 13 Time[269.786..271.863] Length[26.7864..1.#INF) Weight[71..118] -> 15 Time[331.437..333.514] Length[34.4373..1.#INF) Weight[83..130] -> 22 Time[353.783..355.86] Length[38.7833..1.#INF) Weight[98..145] -> 23 Time[412.501..414.578] Length[39.5013..1.#INF) Weight[116..163] -> 6 Time[488.747..490.823] Length[49.7469..1.#INF) Weight[141..188] -> Depot Time[537.923..540] Length[61.9235..1.#INF) Weight[153..200] Vehicle 2 : -> Depot Time[0..26.7505] Length[0..1.#INF) Weight[0..6] -> 9 Time[13.2558..40.0063]
63
Length[13.2558..1.#INF) Weight[0..6] -> 8 Time[45.6606..72.4111] Length[13.6606..1.#INF) Weight[2..8] -> 7 Time[86.9787..113.729] Length[13.9787..1.#INF)Weight[19..25] -> 10 Time[116.886..143.636] Length[15.8856..1.#INF) Weight[38..44] -> 14 Time[133.378..160.129] Length[17.3783..1.#INF) Weight[57..63] -> 16 Time[158.728..185.479] Length[21.7282..1.#INF) Weight[79..85] -> 17 Time[207.814..234.564] Length[23.8137..1.#INF) Weight[88..94] -> 24 Time[216.856..243.606] Length[24.8556..1.#INF) Weight[92..98] -> 21 Time[290.229..316.979] Length[25.229..1.#INF) Weight[110..116] -> 20 Time[371.549..398.3] Length[25.5493..1.#INF) Weight[147..153] -> 19 Time[394.705..421.455] Length[28.7049..1.#INF) Weight[165..171] -> 18 Time[433.398..460.149] Length[32.3982..1.#INF) Weight[183..189] -> Depot Time[513.25..540] Length[52.2495..1.#INF) Weight[194..200] Vehicle 3 :
Unused
Vehicle 4 :
Unused
64
Lampiran 10 Program penentuan rute dengan metode insertion menggunakan software ILOG
// ---------------------------------------- -*- C++ -*// File: examples/src/vrp.cpp // ---------------------------------------------------#include #if defined(ILUSESTL) #include #include #include <string> #else #include #include #include <string.h> #endif ILCSTLBEGIN void Info(IlcManager m, IlcRoutingPlan plan, char * problem) { m.printInformation(); plan.printInformation(); m.out() << "===============" << endl << "Problem name : " << problem << endl << "Cost : " << plan.getTotalCost() << endl << "Number of vehicles used : " << plan.getNbOfVehiclesUsed() << endl << "Solution : " << endl << plan << endl; } int main(int argc, char* argv[]) { IlcManager m(IlcEdit); #if defined(ILCLOGFILE) m.openLogFile("vrp.log"); #endif IlcRoutingPlan plan(m); IlcDimension2 time(plan, IlcEuclidean, "Time"); IlcDimension2 length(plan, IlcEuclidean, "Length"); IlcDimension1 weight(plan, "Weight"); ifstream infile;
65
char * problem; if (argc >=2) problem = argv[1]; else problem = (char *) "../../../examples/data/sariroti.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; IlcFloat capacity; infile >> capacity; IlcFloat depotX, depotY, openTime, closeTime; infile >> depotX >> depotY >> openTime >> closeTime; IlcNode depot(plan, depotX, depotY); for (IlcInt j = 0; j < nbOfTrucks; j++) { IlcVisit first(depot, "Depot"); m.add(first.getCumulVar(time) >= openTime); IlcVisit last(depot, "Depot"); m.add(last.getCumulVar(time) <= closeTime); char name[16]; sprintf(name, "Vehicle %d\0", j); IlcVehicle vehicle(plan, first, last, name); vehicle.setCost(length, 1.0); vehicle.setCapacity(weight, capacity); } for (IlcInt i = 0; i < nbOfVisits; i++) { IlcInt id; // visit identifier IlcFloat x, y, quantity, minTime, maxTime, dropTime; infile >> id >> x >> y >> quantity >> minTime >> maxTime >> dropTime; IlcNode customer(plan, x, y); char name[16]; sprintf(name, "%d\0", id); IlcVisit visit(customer, name); visit.setDelay(time, dropTime);
66
visit.setQuantity(weight, quantity); ILCSETWINDOW(visit.getCumulVar(time), minTime <= var && var <= maxTime); } infile.close(); IlcGoal generateGoal = IlcInsertionGenerate(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); plan.improve(5, IlcTwoOpt(plan), IlcOrOpt(plan), IlcRelocate(plan), IlcExchange(plan), IlcCross(plan)); } Info(m, plan, problem); #if defined(ILCLOGFILE) m.closeLogFile(); #endif m.end(); return 0; } /*-----------------------------------------------------
67
Lampiran 11 Hasil penentuan rute dengan metode insertion
Total memory used (bytes) : 376588 Elapsed time since creation : 0.078 Number of nodes : 25 =============== Problem name : ../../../examples/data/sariroti.dat Cost : 131.77 Number of vehicles used : 3 Solution : Unperformed visits : None Vehicle 0 : -> Depot Time[0..2.3626] Length[0..1.#INF) Weight[0..1] -> 18 Time[19.8514..22.214] Length[19.8514..1.#INF) Weight[0..1] -> 19 Time[83.5446..85.9072] Length[23.5446..1.#INF) Weight[11..12] -> 20 Time[121.7..124.063] Length[26.7003..1.#INF) Weight[29..30] -> 21 Time[142.021..144.383] Length[27.0205..1.#INF) Weight[47..48] -> 24 Time[223.394..225.757] Length[27.3939..1.#INF) Weight[84..85] -> 17 Time[297.436..299.798] Length[28.4359..1.#INF) Weight[102..103] -> 23 Time[306.558..308.921] Length[29.5579..1.#INF) Weight[106..107] -> 22 Time[373.276..375.639] Length[30.2759..1.#INF) Weight[131..132] -> 16 Time[434.404..436.767] Length[33.4041..1.#INF) Weight[149..150] -> 14 Time[485.754..488.117] Length[37.7541..1.# INF) Weight[158..159] -> 10 Time[508.247..510.609] Length[39.2467..1.#INF) Weight[180..181] -> Depot Time[537.637..540] Length[53.6374..1.#INF) Weight[199..200] Vehicle 1 : -> Depot Time[0..31.0831] Length[0..1.#INF) Weight[0..52] -> 3 Time[11.0671..42.1502] Length[11.0671..1.#INF) Weight[0..52] -> 5 Time[47.6437..78.7269] Length[13.6437..1.#INF) Weight[7..59] -> 2 Time[142.194..173.277] Length[17.194..1.#INF) Weight[15..67] -> 11 Time[153.598..184.681] Length[21.5975..1.#INF) Weight[18..70] -> 12 Time[226.267..257.35]
68
Length[25.2667..1.#INF) Weight[55..107] -> 13 Time[269.786..300.87] Length[26.7864..1.#INF) Weight[71..123] -> 15 Time[331.437..362.52] Length[34.4373..1.#INF) Weight[83..135] -> 7 Time[356.852..387.935] Length[41.8517..1.#INF) Weight[98..150] -> 8 Time[385.17..416.253] Length[42.1697..1.#INF) Weight[117..169] -> 9 Time[426.575..457.658] Length[42.5745..1.#INF) Weight[134..186] -> 6 Time[459.74..490.823] Length[43.7403..1.#INF) Weight[136..188] -> Depot Time[508.917..540] Length[55.9169..1.#INF) Weight[148..200] Vehicle 2 : -> Depot Time[0..410.784] Length[0..1.#INF) Weight[0..166] -> 1 Time[9.19879..419.983] Length[9.19879..1.#INF) Weight[0..166] -> 4 Time[49.1864..459.971] Length[11.1864..1.#INF) Weight[17..183] -> Depot Time[129.216..540] Length[22.2157..1.#INF) Weight[34..200] Vehicle 3 :
Unused
Vehicle 4 :
Unused
