PENENTUAN RUTE PENDISTRIBUSIAN MINUMAN RINGAN MENGGUNAKAN METODE HEURISTIK
RIZKY NOVALIA SARY
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2013
ABSTRAK RIZKY NOVALIA SARY. Penentuan Rute Pendistribusian Minuman Ringan Menggunakan Metode Heuristik. Dibimbing oleh FARIDA HANUM dan PRAPTO TRI SUPRIYO. Pendistribusian barang merupakan salah satu bagian penting dari kegiatan sebuah perusahaan. Pendistribusian barang harus dilakukan secara efektif dan efisien. Dalam karya ilmiah ini, masalah yang dibahas ialah pendistribusian minuman ringan dengan dua aktivitas yang meminimumkan biaya pendistribusian. Aktivitas yang dilakukan ialah pengiriman barang (delivery) dari depot ke pelanggan dan pengambilan barang (pick-up) dari pelanggan. Metode yang digunakan ialah Nearest Neighbour Heuristic, Petal Heuristic, dan beberapa metode lain sebagai metode perbaikan. Metode-metode perbaikan yang digunakan ialah metode 2-opt, metode 3-opt, metode 2-interchange terbatas, dan penggabungan rute. Hasil studi kasus menunjukkan bahwa semakin banyak metode perbaikan yang dilakukan, maka rute yang diperoleh semakin baik. Kata kunci: Heuristik, Nearest Neighbour Heuristic, Petal Heuristic, rute pendistribusian
ABSTRACT RIZKY NOVALIA SARY. Determination of Soft-drink Distribution Route Using Heuristic Methods. Supervised by FARIDA HANUM and PRAPTO TRI SUPRIYO. Distribution of goods is one important part in marketing activities. Therefore, it should be done effectively and efficiently. In this article, the study is focused on soft-drink distribution in order to minimize distribution cost, which includes two activities, i.e. delivery and pick-up. The methods used are nearest neighbour heuristic, petal heuristic and some other methods for route improvement. The methods for route improvement are 2-opt method, 3-opt method, restricted 2interchange, and route merge methods. The study case results show that the more improvements are given, the better route will be obtained. Keywords: Heuristic methods, Nearest Neighbour, Petal, distribution route
PENENTUAN RUTE PENDISTRIBUSIAN MINUMAN RINGAN MENGGUNAKAN METODE HEURISTIK
RIZKY NOVALIA SARY
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2013
Judul Skripsi Nama NIM
: Penentuan Rute Pendistribusian Minuman Ringan Menggunakan Metode Heuristik : Rizky Novalia Sary : G54060886
Menyetujui Pembimbing I,
Pembimbing II,
Dra. Farida Hanum, M.Si. NIP: 19651019 199103 2 002
Drs. Prapto Tri Supriyo, M.Kom. NIP: 19630715 199002 1 002
Mengetahui Ketua Departemen Matematika
Dr. Berlian Setiawaty, MS. NIP: 19650505 198903 2 004
Tanggal Lulus:
PRAKATA Puji syukur penulis panjatkan kepada Allah swt atas berkat, rahmat dan kasih sayang-Nya sehingga penulis mampu menyelesaikan karya ilmiah ini. Berbagai kendala dialami oleh penulis sehingga banyak sekali orang yang membantu dan berkontribusi dalam pembuatan karya ilmiah ini. Oleh karena itu, dalam kesempatan ini penulis mengucapkan terima kasih kepada: 1.
Sang pencipta, Tuhan semesta alam Allah swt, atas maha karya-Nya yaitu bumi yang sempurna ini, 2. keluarga tercinta: ayah dan ibu sebagai pemberi motivasi, untuk saudara-saudaraku Irra, Trisna, Roy, Minda, Jerry, Agri, Ulfa, dan Jihan yang selalu memberikan semangat dan doa, 3. Dra. Farida Hanum, M.Si. selaku dosen pembimbing I yang telah meluangkan waktu dan pikiran dalam membimbing, memberi motivasi, semangat dan doa, 4. Drs. Prapto Tri Supriyo, M.Kom. selaku dosen pembimbing II yang telah memberikan ilmu, kritik dan saran, motivasi serta doanya, 5. Drs. Siswandi, M.Si selaku dosen penguji yang telah memberikan ilmu, saran dan doanya, 6. semua dosen Departemen Matematika, terima kasih atas semua ilmu yang telah diberikan, 7. staf Departemen Matematika, terima kasih atas bantuan yang telah diberikan selama ini, 8. semua teman Matematika 43 yang selalu menjadi bagian dari keluarga, 9. semua teman Matematika yang selalu mendukung agar terus berkembang, 10. Gumatika yang telah mengasah pribadi ini menjadi pribadi yang tangguh, 11. semua pihak yang telah membantu dalam penyusunan karya ilmiah ini. Semoga karya ilmiah ini bermanfaat bagi dunia ilmu pengetahuan khususnya bidang matematika dan menjadi inspirasi bagi penelitian selanjutnya.
Bogor, Januari 2013
Rizky Novalia Sary
RIWAYAT HIDUP Penulis dilahirkan di Palembang pada tanggal 14 November 1987 sebagai anak kelima dari sembilan bersaudara, anak dari pasangan Syahril dan Irmawati. Pada tahun 2000 penulis lulus dari SD Polisi 4 Bogor kemudian tahun 2003 lulus dari SLTP Negeri 6 Bogor. Tahun 2006 penulis lulus dari SMA Negeri 5 Bogor dan pada tahun yang sama penulis lulus seleksi masuk IPB melalui jalur USMI (Undangan Seleksi Masuk IPB). Pada tahun 2007, penulis memilih jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama mengikuti perkuliahan, penulis menjadi asisten mata kuliah Kalkulus 2 tahun ajaran 2008/2009. Penulis juga aktif dalam mengajar Matematika bimbingan belajar privat maupun kelompok mahasiswa. Penulis pernah mengikuti seleksi olimpiade nasional Matematika dan IPA (ON-MIPA) sebagai wakil IPB pada tahun 2009. Penulis aktif dalam organisasi kemahasiswaan di kampus, seperti organisasi himpunan profesi Departemen Matematika yang dikenal dengan GUMATIKA (Gugus Mahasiswa Matematika) sebagai anggota Kesekretariatan tahun 2008/2009. Selain itu, penulis juga terlibat dalam beberapa kegiatan, antara lain Komisi Disiplin MPKMB (Masa Perkenalan Kampus Mahasiswa Baru) tahun 2007, Bendahara panitia Try-Out Pengantar Matematika mahasiswa IPB 2007, koordinator Konsumsi Matematika Ria dalam acara Pesta Sains se-Indonesia 2009.
DAFTAR ISI Halaman DAFTAR GAMBAR .................................................................................................. viii DAFTAR TABEL .......................................................................................................
ix
DAFTAR LAMPIRAN ...............................................................................................
ix
I
II
III
IV
V
PENDAHULUAN 1.1 Latar Belakang ............................................................................................. 1.2 Tujuan Penulisan ..........................................................................................
1 1
LANDASAN TEORI 2.1 Graf dan Digraf ............................................................................................ 2.2 Metode Heuristik ......................................................................................... 2.2.1 Nearest Neighbour Heuristic ............................................................. 2.2.2 Metode 2-Opt ..................................................................................... 2.2.3 Metode λ-interchange Terbatas .......................................................... 2.3 Masalah Pemartisian Himpunan ...................................................................
1 2 2 3 3 4
PEMBAHASAN 3.1 Deskripsi Masalah ........................................................................................ 3.2 Langkah-langkah Penyelesaian Secara Umum ............................................ 3.2.1 Petal Heuristic ................................................................................... 3.2.2 Tahap Perbaikan .................................................................................
5 6 6 7
APLIKASI PERMASALAHAN 4.1 Konstruksi Rute dari Setiap Metode Heuristik ............................................. 4.1.1 Konstruksi rute dengan Nearest Neighbour Heuristic (NNH) ............ 4.1.2 Konstruksi rute Petal Heurstic (PH) ................................................... 4.2 Tahap Perbaikan Rute dari Setiap Heuristik ................................................ 4.2.1 Perbaikan Rute NNH .......................................................................... 4.2.2 Tahap Perbaikan PH ............................................................................ 4.3 Hasil .............................................................................................................
8 8 10 12 12 13 14
SIMPULAN DAN SARAN 5.1 Simpulan ...................................................................................................... 5.2 Saran ............................................................................................................
16 16
DAFTAR PUSTAKA .........................................................................................
16
LAMPIRAN ........................................................................................................
17
vii
DAFTAR GAMBAR Halaman 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
Graf G = (V,E) ...................................................................................................... Graf berarah D = (V,A) ......................................................................................... Graf berbobot ........................................................................................................ Adjacent dan incident ............................................................................................ Rute yang dibentuk NNH ..................................................................................... Ilustrasi metode 2-opt ............................................................................................ Contoh metode 2-opt dengan jarak awal 11 satuan menjadi 10 satuan ................ Rute awal Contoh 2 ............................................................................................... Ilustrasi metode 2-pemindahan verteks ................................................................ Ilustrasi metode 2-penukaran verteks ................................................................... Rute Iterasi 3 Kendaraan 1 Tipe 2 pada NNH ..................................................... Rute Iterasi 3 Kendaraan 1 Tipe 2 pada NNH dengan melakukan prosedur 2-opt . Rute awal tiap iterasi pada metode NNH ................................................................ 2-pemindahan verteks antara Iterasi 1 dan Iterasi 5 .............................................. 1-pemindahan verteks antara Iterasi 2 dan Iterasi 3................................................ Rute awal yang dihasilkan pada metode PH ......................................................... 2-penukaran verteks antara Rute e2 dan Rute e6 . .................................................. Rute hasil NNH ..................................................................................................... Rute hasil NNH perbaikan .................................................................................... Rute hasil PH ........................................................................................................ Rute hasil PH perbaikan ....................................................................................... Rute awal Iterasi 1 PH kendaraan Tipe 2 dengan jarak tempuh 41.88 km ........... Pengaplikasian metode 2-opt pada Iterasi 1 PH kendaraan Tipe 2 ....................... Rute awal Iterasi 1 PH kendaraan Tipe 3 dengan jarak tempuh 41.88 km ........... Pengaplikasian metode 2-opt pada Iterasi 1 PH kendaraan Tipe 3 ....................... Rute awal Iterasi 2 PH kendaraan Tipe 3 dengan jarak tempuh 32.40 km ........... Pengaplikasian metode 2-opt pada Iterasi 2 PH kendaraan Tipe 3 ......................... Rute hasil 1-penukaran verteks antara rute Iterasi 1 dan rute Iterasi 2 pada NNH . Rute hasil 1-pemindahan verteks antara rute Iterasi 1 dan rute Iterasi 3 pada NNH .................................................................................................................... Rute hasil 1-penukaran verteks antara rute Iterasi 1 dan rute Iterasi 3 pada NNH. Rute Hasil 1-pemindahan verteks antara rute Iterasi 1 dan rute Iterasi 4 pada NNH ....................................................................................................................... Rute hasil 2-pemindahan verteks antara rute Iterasi 1 dan rute Iterasi 5 pada NNH Rute hasil 1-pemindahan verteks antara rute Iterasi 2 dan rute Iterasi 3 pada NNH ....................................................................................................................... Rute hasil 1-penukaran verteks antara rute Iterasi 2 dan rute Iterasi 3 pada NNH Rute hasil 1-pemindahan verteks antara rute Iterasi 2 dan rute Iterasi 4 pada NNH Rute hasil 3-opt pada rute e6 ................................................................................. Rute hasil 2-penukaran verteks antara rute e2 dan rute e6 ..................................... Rute hasil 2-penukaran verteks antara rute e2 dan rute e6 ......................................
1 1 2 2 3 3 3 3 4 4 9 9 12 12 13 13 13 15 15 15 15 19 19 20 20 21 21 23 23 23 24 24 25 25 25 26 26 26
viii
DAFTAR TABEL Halaman 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Jarak antarpelanggan pada Contoh 1 .................................................................... Data permintaan di setiap pelanggan .................................................................... Data tiap tipe kendaraan ....................................................................................... Data jarak antarpelanggan ................................................................................... Rute Iterasi 1 Kendaraan 1 Tipe 1 dengan NNH (kapasitas 25 krat) .................... Rute Iterasi 2 Kendaraan 2 Tipe 1 dengan NNH (kapasitas 25 krat) .................... Rute Iterasi 3 Kendaraan 1 Tipe 2 dengan NNH (kapasitas 30 krat) .................... Rute Iterasi 4 Kendaraan 2 Tipe 2 dengan NNH (kapasitas 30 krat) .................... Rute Iterasi 5 kendaraan Tipe 3 dengan NNH (kapasitas 40 krat) ........................ Rute-rute hasil pembatasan 2-interchange pada NNH .......................................... Biaya perbaikan NNH .......................................................................................... Rute-rute hasil pembatasan 2-interchange pada PH .............................................. Biaya PH perbaikan ............................................................................................... Data jarak dan biaya tiap heuristik ...................................................................... Biaya pendistribusian dengan mempertimbangkan aktivitas pick-up ..................
2 8 8 8 8 9 9 9 10 13 13 14 14 14 14
DAFTAR LAMPIRAN Halaman 1 2
Program LINGO 11.0 pada contoh masalah pemartisian himpunan .................... Program LINGO 11.0 pada contoh masalah pemartisian himpunan yang diperumum............................................................................................................... 3 Semua kemungkinan metode 2-opt pada rute (0,1,5,9,2,0) .................................. 4 Semua kemungkinan metode 2-opt pada rute (0,1,4,9,2,0) ................................. 5 Semua kemungkinan metode 2-opt pada rute (0,5,3,8,0) ..................................... 6 Program LINGO 11.0 pada aplikasi masalahan pemartisian himpunan yang diperumum ............................................................................................................. 7 Metode Pembatasan 2-interchange untuk Iterasi 1 pada NNH ............................ 8 Metode Pembatasan 2-interchange untuk Iterasi 2 pada NNH .............................. 9 Semua kemungkinan metode 3-opt pada metode PH ............................................. 10 Metode Pembatasan 2-interchange untuk e2 pada PH ........................................... 11 Biaya yang dikeluarkan dengan mempertimbangkan pick-up ...............................
18 18 19 20 21 22 23 25 26 26 27
ix
1
I PENDAHULUAN 1.1 Latar Belakang Suatu perusahaan produksi perlu melakukan pendistribusian barang yang diproduksinya agar permintaan dapat sampai ke konsumen. Pendistribusian yang dilakukan haruslah dilakukan secara efektif dan efisien. Selain itu, perusahaan juga harus memperhatikan waktu dan biaya yang dikeluarkan. Oleh karena itu, diperlukan solusi yang tepat untuk menentukan banyaknya kendaraan yang dibutuhkan serta rute yang dipilih agar biaya pendistribusian minimum. Pada karya ilmiah ini akan dibahas masalah pendistribusian minuman ringan. Pada pendistribusian minuman ringan ini terdapat dua aktivitas yaitu pengiriman barang (delivery) yang diambil dari depot dan pengambilan barang (pick-up) dari lokasi pelanggan kembali ke depot. Barang yang
dikirim merupakan minuman ringan dalam botol, dan barang yang diambil adalah botol kosong bekas minuman yang selanjutnya dapat dijual ke perusahaan pendaur ulang. Permasalahan pendistribusian minuman ringan ini akan diselesaikan menggunakan metode heuristik. Metode-metode yang digunakan antara lain Nearest Neighbour heuristic (NNH) dan Petal Heuristic (PH). Sumber utama karya ilmiah ini ialah artikel yang berjudul Solving a vehicle routing problem arising in soft drink distribution yang disusun oleh Prive dan kawan-kawan pada tahun 2006. 1.2 Tujuan Tujuan dari penulisan karya ilmiah ini ialah penentuan rute pendistribusian barang yang meminimumkan biaya dengan metode heuristik.
II LANDASAN TEORI 2.1 Graf dan Digraf Definisi 1 (Graf) Suatu graf G adalah pasangan terurut (V,E) dengan V, biasa disebut V(G), adalah himpunan berhingga dan takkososng dari elemen graf yang disebut verteks (vertex, point), sedangkan E, biasa disebut E(G), ialah himpunan pasangan yang menghubungkan dua elemen subset dari V yang disebut sisi (edge, line). Setiap sisi {u,v} pada V biasanya dinotasikan dengan uv atau vu. Banyaknya verteks dari suatu graf disebut order dan banyaknya sisi pada suatu graf disebut size. (Chartrand & Zhang 2009)
berhingga dan A himpunan pasangan terurut yang menghubungkan elemen-elemen di V. Elemen-elemen dari A disebut sisi berarah (arc). Sisi berarah (u,v) dinyatakan dengan garis berarah dari u ke v. (Chartrand & Zhang 2009)
D: u
v w
x
Gambar 2 Graf berarah D = (V, A).
G: w
Pada Gambar 2 diperlihatkan bahwa V={u,v,w,x} dan A={(v,w),(u,w),(w,x)}.
x v y u Gambar 1 Graf G = (V, E). Pada Gambar 1 diperlihatkan bahwa V = {u,v,w,x,y,z} dan E = {{u,v},{v,w},{v,x},{x,y}}. Definisi 2 (Graf Berarah/Digraf) Graf berarah (digraph) D adalah pasangan terurut (V,A) dengan V himpunan takkosong
Definisi 3 (Graf/Digraf Berbobot) Suatu graf G = (V,E) atau digraf D = (V,A) dikatakan berbobot jika terdapat sebuah fungsi w : E R atau l : A R (dengan R adalah himpunan bilangan real) yang memberikan sebuah bilangan real pada setiap sisi di E atau sisi berarah A yang disebut bobot. Bobot dari sisi berarah uv A atau {u,v} E dinotasikan dengan wuv. (Foulds 1992)
2
z u
9 23 0 0 0 72 0x 015 0 0 0 v0 0 0 0 Gambar 0 berbobot. 03 Graf 0 0 sisi0untuk Bobot tiap 0 graf pada Gambar 3 adalah w0uv=15, wvz=23, wzx=9, wvx=72.0 0 0 0 dan Incident) Definisi 4 (Adjacent Untuk suatu0 sisi e = uv, verteks u dan
verteks v disebut berhubungan (incident) dengan sisi e, dan verteks u dikatakan berdampingan (adjacent) dengan verteks v. (Foulds 1992) G: u v e1
e2
x
e3
e5
e4
w
Gambar 4 Adjacent dan incident. Ilustrasi adjacent dan incident diperlihatkan pada Gambar 4. Verteks u adjacent dengan verteks v dan x namun verteks u tidak adjacent dengan verteks w. Verteks u incident dengan sisi e1 namun tidak incident dengan e5. Definisi 5 (Jalan/Walk) Walk W pada suatu graf G adalah barisan berhingga W = viejvi+1ej+1...ekvm atau W = vivi+1-...-vm yang dimulai dari suatu verteks dan berakhir pada suatu verteks juga sehingga setiap sisi dalam barisan harus incident dengan verteks sebelum dan sesudahnya. (Chartrand & Zhang 2009) W = ue2xe5we4ve3x pada Gambar 4 adalah walk pada graf G. Definisi 6 (Walk Tertutup) Walk pada suatu graf G dikatakan tertutup (closed) jika walk tersebut dimulai dan diakhiri pada verteks yang sama. (Chartrand & Zhang 2009) 2.2 Metode Heuristik Metode heuristik merupakan metode yang dirancang untuk menyelesaikan suatu masalah dalam skala besar dan rumit dengan cara
komputasi moderat agar menghasilkan solusi yang fisibel. (Grötschel 1982) Solusi yang dihasilkan oleh metode heuristik tidak dijamin optimal namun hanya mampu mendekati solusi yang optimal saja dan waktu pencarian yang relatif lebih cepat bila dibandingkan dengan metode riset operasi pada umumnya karena membuang kemungkinan-kemungkinan yang sepertinya bukan merupakan solusi. Pada umumnya terdapat tahapan-tahapan penyelesaian VRP dengan metode heuristik, yaitu: i. penentuan rute, ii. perbaikan solusi/rute. Pada penelitian ini metode nearest neighbour heuristic akan digunakan untuk mencari solusi pada fase pertama. Selanjutnya metode 2-opt, metode 3-opt, metode pembatasan 2-interchange, dan metode penggabungan rute digunakan untuk memperbaiki solusi yang telah ada. Metodemetode tersebut akan dijelaskan pada bagian berikut ini. 2.2.1 Nearest Neighbour Heuristic (NNH) Metode nearest neighbour heuristic (NNH) adalah suatu metode penentuan rute dengan memilih suatu verteks awal kemudian memilih verteks selanjutnya dengan verteks yang belum dipilih dan terdekat dari verteks sebelumnya. (Grötschel 1982) Berikut ini akan ditampilkan contoh penerapan NNH. Contoh 1 Misalkan suatu perusahaan mempunyai 1 depot (gudang) yang dinyatakan dengan pelanggan 0, dan 3 pelanggan. Jarak antarpelanggan diberikan pada Tabel 1. Tabel 1 Jarak antarpelanggan pada contoh 1 Pelanggan 0 1 2 0 0 5 2 1 0 4 2 0 3
3 3 6 5 0
Dengan menggunakan metode NNH, rute dimulai dari depot (pelanggan 0) kemudian mengunjungi pelanggan 2 (karena jaraknya terdekat dari depot), kemudian mengunjungi pelanggan 1, selanjutnya ke pelanggan 3 setelah itu kembali ke depot, seperti yang terlihat pada Gambar 5.
3
Metode n-opt serupa dengan metode 2-opt, tetapi banyaknya sisi yang dapat dihapus dan ditambahkan sebanyak n sisi. (Nilsson 2003)
1 depot
5
0
4
2 2 3
5
3 Gambar 5 Rute yang dibentuk NNH. 2.2.2 Metode 2-Opt Pada dasarnya metode 2-opt dilakukan dengan memindahkan dua sisi pada rute yang ada, kemudian menghubungkan kembali sisi tersebut dengan pasangan konsumen yang berbeda sedemikian sehingga rute baru yang dihasilkan lebih baik daripada rute awal (Nilsson 2003). Algoritme yang digunakan adalah sebagai berikut: i. tentukan satu rute untuk satu kendaraan, ii. hapus 2 sisi yang menghubungkan 4 konsumen yang berbeda, iii. hubungkan kembali keempat konsumen dengan pasangan yang berbeda, iv. jika biaya berkurang dan tidak melanggar kendala yang ada kembali ke langkah (ii), v. selesai. (ILOG 2002)
2.2.3 Metode λ -interchange Terbatas Metode λ-interchange terdiri dari dua metode yaitu metode λ-penukaran atau metode λ-pemindahan. Metode λ-penukaran dilakukan dengan menukarkan (saling memberi) verteks yang dimiliki dengan verteks lain maksimal sebanyak λ dan berurutan, dengan tetap memperhatikan kapasitas yang dimiliki. Sedangkan Metode λ-pemindahan dilakukan dengan memberikan atau mendapatkan verteks maksimal sebanyak λ dan berurutan dari rute lain. Metode λinterchange yaitu pengombinasian antara metode λ-penukaran verteks atau metode λpemindahan verteks pada dua buah rute dengan mengupayakan semua kemungkinan yang ada guna menemukan rute terbaik. Metode 2-interchange terbatas adalah pemindahan dan penukaran verteks paling banyak dua verteks berurutan. (Prive 2006) Contoh 2 Misalkan terdapat 2 rute yaitu Rute 1 melewati verteks 1, verteks 2, verteks 3, verteks 4, dan kembali ke verteks 1. Rute 2 melewati verteks 5, verteks 6, verteks 7, verteks 8, dan kembali ke verteks 5. 5
1
4
Gambar 6 Ilustrasi metode 2-opt. 1
4 2
2
1 5
2
1
6
3
7 8
4 2
2
2
5
1
2
Gambar 7 Contoh metode 2-opt dengan jarak awal 11 satuan menjadi 10 satuan. Rute yang dihasilkan dapat disebut sebagai 2-optimal atau 2-opt, jika metode 2-opt digunakan pada setiap rute yang ada sampai tidak dimungkinkan lagi penggunaan metode tersebut.
Gambar 8 Rute awal Contoh 2. Jika rute-rute pada Gambar 8 dilakukan λpemindahan verteks maka salah satu rute akan kehilangan verteks dan lainnya akan bertambah. Seperti terlihat pada Gambar 9, Rute 1 akan kehilangan verteks 3 pada 1pemindahan verteks, sedangkan pada 2pemindahan kehilangan verteks 2 dan verteks 3. Pada 2-pemindahan verteks, verteks yang berpindah harus 2 verteks yang berurutan dan susunan urutannya dapat diubah.
4
5
1 2
6
3
7
4
8
Contoh rute dengan 1-pemindahan verteks
2.3 Masalah Pemartisian Himpunan Masalah pemartisian himpunan juga diperlukan dalam karya ilmiah ini. Definisi 7 (Partisi) Misalkan diberikan dua himpunan, yaitu I={1,2,...,m} dan P = {P1,P2,...,Pn} dengan Pj adalah suatu himpunan bagian dari I, j J = {1,2,...,n}. Himpunan Pj , j J J adalah *
5
1 2
6 7
3
jJ *
8 5 2
6 7
3 4
8
Contoh rute dengan 2-pemindahan verteks Gambar 9 Ilustrasi metode 2-pemindahan verteks. Sedangkan jika rute pada Gambar 8 dilakukan metode λ-penukaran verteks maka banyaknya verteks pada setiap rute akan tetap. Pada 1-penukaran verteks, verteks 2 pada Rute 1 menjadi bagian dari Rute 2 sebagai gantinya verteks 6 menjadi bagian dari Rute 1. Begitu pula dengan 2-penukaran verteks, yang membedakan hanyalah banyaknya verteks yang bertukar masing-masing sebanyak 2 verteks yang berurutan. Contoh λ-penukaran verteks dapat dilihat pada Gambar 10. 5
1 2 3
6 7
4
8
Contoh rute dengan 1-penukaran verteks 5
1 2
6
3
7
4
Pj I dan
*
4 1
partisi dari I jika:
untuk j , k J , j k Pj Pk . (Garfinkel & Nemhauser 1972) Ilustrasi dari suatu partisi dapat dilihat pada contoh berikut: Contoh 3 Misalkan diberikan himpunan I={1,2,3,4,5,6} dan kelas-kelas himpunan P1={1,2}, P2={3}, P3={4,6}, P4={1,4,5}, P5={2,3,6}. Partisi dari I di antaranya ialah {P4,P5}, karena untuk himpunan J*={4,5} memenuhi: Pj I dan j , k J , j k Pj Pk . *
jJ
*
Sedangkan yang bukan partisi dari I ialah {P1,P2,P3}, karena gabungannya bukan I. Masalah pemartisian himpunan (set partitioning problem/SPP) adalah masalah menentukan partisi dari himpunan I dengan biaya minimum. Untuk mendapatkan partisi tersebut, misalkan dengan menggunakan data sebelumnya, Pj={P4,P5} , 1, jika j termasuk dalam partisi xj 0, lainnya
1, jika elemen i terdapat pada Pj aij 0, lainnya dengan Pj adalah kelas himpunan cj adalah biaya dari Pj. Bentuk umum SPP: n
min c j x j j 1
8
n
terhadap kendala
aij x
j
1
i 1, 2,..., m
j 1
5
1 2 3 4
6 7 8
Contoh rute dengan 2-penukaran verteks Gambar 10 Ilustrasi metode 2-penukaran verteks.
xj = 0 atau 1 aij = 0 atau 1
(1)
Model ini memiliki beberapa sifat penting yaitu: Sifat 1 : Masalah pada model ini memiliki kendala berbentuk persamaan. Sifat 2 : Nilai sisi kanan semua kendala adalah 1. (Garfinkel & Nemhauser 1972)
5
Contoh 4 Masalah pemartisian himpunan Misalkan diberikan himpunan I beserta kelas-kelas P seperti pada Contoh 3. Misalkan diketahui biaya dari setiap kelas Pj yaitu cj, dengan c1=15, c2=10, c3=19, c4=18, c5=17. Diinginkan himpunan dari Pj yang dapat memartisi I dengan biaya minimum. Masalah tersebut dapat dimodelkan sebagai masalah pemartisian himpunan Min 15x1 + 10x2 + 19x3 + 18x4 + 17x5 terhadap kendala x1 + x4 = 1 x1 + x5 = 1 x2 + x5 = 1 x3 + x4 = 1 x4 = 1 x3 + x5 = 1 xj = 0 atau 1, untuk j {1,2,3,4,5}. Kendala-kendala masalah tersebut dapat dituliskan dalam perkalian matriks AX=1, dengan 1 0 0 1 0
A ( aij ) 6 x 5
1 0 0 0 0
0
0
0
1
0
0
0
1
1
0
0
1
0
1
0
1 0 0 1
1
objektif sebesar 35 (detail penghitungan dapat dilihat di Lampiran 1). Jadi partisi dari I={1,2,3,4,5,6} dengan biaya minimum adalah P4={1,4,5} dan P5={2,3,6}. Jika SPP (1) ditambahkan kendala
MX B , dengan M dan B adalah kendala tambahan yang diinginkan, maka masalah tersebut dikatakan Masalah Pemartisian Himpunan yang Diperumum (generalized set partitioning problem/GSPP). (Yen & Birge 2006) Contoh 5 Masalah pemartisian himpunan yang diperumum Misalkan diberikan himpunan I beserta kelas-kelas P seperti pada Contoh 3 dan n n dengan menambahkan kendala xj 2 j 1 pada contoh SPP maka GSPP dapat dimodelkan
Min 15x1 + 10x2 + 19x3 + 18x4 + 17x5 terhadap kendala x1 + x4 = 1 x1 + x5 = 1 x2 + x5 = 1 x3 + x4 = 1 x4 = 1 x3 + x5 = 1
1 x1 1 x 2 1 X x3 , 1 1 x4 1 x 5 1
x1 x2 x3 x4 x5
5
2 xj = 0 atau 1, untuk j {1,2,3,4,5}.
Dengan menggunakan LINGO 11.0 diperoleh solusi untuk masalah SPP sebagai berikut: x1=x2=x3=0, x4=x5=1, dan nilai fungsi
Dengan menggunakan LINGO 11.0 diperoleh solusi untuk masalah GSPP sebagai berikut: x1=x2=x3=0, x4=x5=1, dan nilai fungsi objektif sebesar 35 (detail penghitungan dapat dilihat di Lampiran 2).
III PEMBAHASAN Pada bab ini akan dibahas deskripsi masalah dan metode-metode yang digunakan untuk menyelesaikan masalah pada karya ilmiah ini. 3.1 Deskripsi Masalah Masalah pada pendistribusian minuman ringan ini dinyatakan sebagai sebuah graf G=(V,A), dengan V={0,1,2,3,…,n} adalah himpunan verteks dan A adalah himpunan sisi
berarah. Verteks 0 merupakan depot dan sisanya berupa verteks pelanggan. Pendistribusian dilakukan menggunakan beberapa tipe kendaraan yang dilihat dari kapasitas pengangkutannya dan setiap tipe kendaraan terdiri atas beberapa kendaraan. Biaya tetap kendaraan akan muncul bila kendaraan tersebut digunakan dalam pendistribusian dan biaya variabel dihitung berdasarkan jarak tempuhnya.
6
Pada pendistribusian ini terdapat dua aktivitas yaitu pengiriman barang (delivery) dan pengambilan barang (pick-up). Barang yang dikirim merupakan produk baru, sedangkan barang yang diambil merupakan produk daur ulang (botol kosong). Pada karya ilmiah ini, pengambilan barang (pick-up) tidak menjadi prioritas sehingga terkadang dapat diabaikan. Aktivitas ini baru menjadi perhatian saat rute optimal telah terbentuk. 3.2 Langkah-langkah Penyelesaian Secara Umum Metode yang dilakukan untuk menyelesaikan permasalahan pada karya ilmiah ini ialah: 1. Pembangkitan rute dengan metode NNH a. Pengantaran barang dimulai oleh kendaraan dengan kapasitas terkecil yang ada di depot. b. Kendaraan tersebut mengunjungi pelanggan terdekat dari depot. c. Jika kapasitas pada kendaraan masih tersedia untuk pelanggan berikutnya, maka kunjungi pelanggan terdekat dari pelanggan pertama; jika melebihi kapasitas yang tersisa, maka kendaraan dapat mengunjungi pelanggan lain yang cukup dekat dari pelanggan pertama sehingga tidak melebihi kapasitas. Lakukan hingga tidak ada lagi permintaan pelanggan yang dapat dimuat. d. Setelah seluruh permintaan didistribusikan oleh kendaraan, kemudian kendaraan tersebut kembali ke depot. e. Dengan menggunakan tipe kendaraan yang sama bangkitkan rute-rute lainnya sehingga permintaan seluruh pelanggan terpenuhi. f. Pada tipe kendaraan lainnya, lakukan hal yang sama. 2.
Perbaikan rute yang telah dibangkitkan sebelumnya dengan metode 2-0pt a. Biaya yang dihasilkan oleh rute-rute yang telah dibangkitkan kemudian dihitung. b. Rute diperbaiki dengan metode 2-opt dan biaya yang dihasilkan dihitung kembali. c. Jika biaya hasil metode 2-opt lebih kecil dari biaya sebelumnya, maka rute yang telah diperbaiki yang kemudian akan digunakan, jika tidak maka rute awal yang digunakan.
3.
4.
Penentuan rute yang akan digunakan dari rute-rute yang ada dengan metode PH (akan dijelaskan pada 3.2.1). Rute yang telah ditetapkan dari metode PH diperbaiki dengan metode 3-opt, 2interchange terbatas, dan penggabungan rute (akan dijelaskan pada 3.2.2).
3.2.1 Petal Heuristic (PH) Petal heuristic (PH) mengonstruksi satu himpunan rute berdasarkan pada metode NNH, kemudian memilih rute yang optimal dengan menyelesaikan masalah pemartisian himpunan yang diperumum. Misalkan F adalah himpunan verteks yang digunakan sebagai verteks seed yaitu verteks awal yang dikunjungi pertama kali dari depot (verteks 0) karena memiliki jarak terdekat dari depot. Misalkan U adalah himpunan konsumen yang belum dikunjungi, dan R adalah himpunan rute yang dibangkitkan. Untuk membuat rute awal PH, maka digunakanlah pencarian rute NNH beberapa kali dari sebuah verteks seed. Algoritme yang digunakan adalah sebagai berikut : 1. Inisialisasi F ={0} dan R 2. Pemilihan verteks seed (i) Jika F=V maka dilanjutkan ke Langkah 4. Jika tidak, dipilih verteks dari V\F sebagai verteks seed selanjutnya, didefinisikan sebagai i, yaitu verteks terdekat dari depot. F {i} menjadi F, U=V\{0,i}, rute (0,i,0) dimasukkan ke R . 3. Perluasan rute Rute diperluas dengan cara memilih sebuah verteks j yang memungkinkan untuk ditambahkan pada rute. Jika U \ F maka j dipilih dari U\F. Jika tidak, j dipilih dari F\{i}. Himpunan U diperbarui menjadi U\{j} kemudian prosedur 2-opt digunakan pada rute {0,i,..,j,0}, lalu hasilnya ditambahkan ke himpunan R. Lanjutkan ke Langkah 2. 4. Pengevaluasian rute Pada tahap ini dilakukan evaluasi pada rute dengan menugaskan kendaraan pada setiap rute serta menghitung biaya yang dikeluarkan tiap kendaraannya. E adalah himpunan pasangan rute dengan kendaraan yang digunakan. Biaya yang dikeluarkan setiap rute e sebesar πe yaitu penjumlahan biaya tetap dan biaya variabel pada rute e. 5. Penentuan solusi masalah pemartisian himpunan yang diperumum Misalkan didefinisikan sebagai berikut:
variabel
0-1
7
Variabel : 1, jika rute e digunakan xe 0, lainnya Parameter: 1, konsumen i dikunjungi di rute e ei 0, lainnya
1, rute e ditetapkan untuk tipe k ek 0, lainnya πe biaya rute e mk banyaknya kendaraan tiap tipe
Fungsi objektif: min e xe (3.1) eE
terhadap kendala
ei
xe 1
i I
(3.2)
ek
xe mk
k K
(3.3)
eE
Fungsi objektif pada persamaan (3.1) adalah meminimumkan biaya kendaraan dari keseluruhan rute yang ada. Kendala (3.2) menggambarkan bahwa setiap konsumen hanya dikunjungi satu kali, sedangkan kendala (3.3) menggambarkan bahwa banyaknya rute kendaraan yang akan dilewati pada setiap kendaraan maksimal sebanyak mk. 3.2.2 Tahap Perbaikan Tahap perbaikan dilakukan pada setiap solusi dari metode yang ada yaitu NNH dan PH. Pada tahap ini dilakukan tiga langkah perbaikan guna mencapai hasil yang terbaik, yaitu prosedur 3-opt, prosedur 2-interchange terbatas, dan penggabungan rute. Setelah terbentuk rute baru dari metode 2interchange terbatas, jika terdapat kendaraan yang dapat melayani dua rute sekaligus, maka digunakan NNH untuk menggabungkan kedua rute tersebut. Jika hasil yang diperoleh dapat menghemat biaya maka rute gabungan tersebut dapat menggantikan kedua rute tadi.
eE
IV APLIKASI PERMASALAHAN Misalkan suatu perusahaan minuman ringan dalam botol memiliki sebuah depot dan mempunyai 9 pelanggan. Permintaan tiap pelanggan berbeda-beda, serta memiliki lima kendaraan dengan tiga tipe kapasitas. Perusahaan depot merupakan tempat berawal dan berakhirnya suatu rute pendistribusian. Misalkan perusahaan menerima pesanan dari para pelanggan setiap waktunya dan mengantarkannya sesuai dengan pesanan yang diinginkan. Selain pengiriman barang pesanan, distributor juga dapat melakukan pengangkutan botol kosong di setiap pelanggan, namun pengangkutan ini hanya dilakukan bila tersedia ruang di kendaraan tersebut. Jika memungkinkan semua botol kosong pada pelanggan tersebut akan diangkut; jika tidak, hanya beberapa saja yang diangkut dengan tetap memperhatikan sisa kapasitas kendaraan. Pengangkutan botol kosong akan menghasilkan pendapatan bagi distributor sebesar 0.1 ribu rupiah/krat. Biaya tetap kendaraan akan muncul bila kendaraan
tersebut digunakan sedangkan biaya perjalanan adalah biaya kendaraan yang bergantung pada jarak tempuh. Asumsi pengantaran dan pengoperasian pickup diatur sebagai berikut: 1. Awal dan akhir rute kendaraan adalah depot. 2. Setiap pelanggan hanya boleh dikunjungi satu kali. 3. Semua permintaan diantarkan kepada para pelanggan. 4. Setiap satu hari sekali kendaraan yang akan digunakan diisi di depot. 5. Banyaknya pelanggan yang dikunjungi oleh sebuah kendaraan harus memenuhi kendala kapasitas kendaraan. 6. Banyaknya botol kosong hasil dari pengambilan barang (pick-up) dihitung setelah rute akhir terbentuk. Berikut ini diberikan tabel mengenai permintaan pelanggan, informasi mengenai kendaraan yang dimiliki, serta jarak antarpelanggan.
8
Tabel 2 Data permintaan di setiap pelanggan Pelanggan Permintaan Botol minuman (krat) kosong (krat) 1 17 17 2 3 2 3 7 7 4 17 18 5 8 6 6 12 15 7 19 19 8 17 17 9 2 5
Tabel 3 Data tiap tipe kandaraan Tipe kendaraan 1 2 3 Kapasitas 25 30 40 (krat) Banyak kendaraan 2 2 1 (buah) Biaya tetap 100 150 150 (ribu rupiah) Biaya perjalanan 1.5/km 1 /km 1.5/km (ribu rupiah) Kecepatan 60 60 60 (km/jam)
Tabel 4 Data jarak antarpelanggan 0 1 2 3 4 5 6 7 8 9 0 0.00 11.52 18.24 14.16 12.48 13.08 18.00 13.92 13.44 14.12 1 0.00 6.72 2.64 1.56 2.16 6.00 4.32 4.32 4.56 2 0.00 4.32 8.28 8.88 10.44 6.60 6.60 7.56 3 0.00 1.80 1.56 4.92 4.56 4.32 3.36 4 0.00 0.60 4.44 2.76 2.76 3.00 5 0.00 3.84 2.16 2.16 2.40 6 0.00 4.08 3.84 2.88 7 0.00 0.24 1.20 8 0.00 0.96 9 0.00 Keterangan: 0 menunjukkan depot sedangkan 1-9 menunjukkan pelanggan, data jarak diadaptasi dari (Raditya 2009) 4.1 Konstruksi Rute dari Setiap Metode Heuristik 4.1.1 Konstruksi rute dengan Nearest Neighbour Heuristic (NNH) Pada langkah ini, setiap kendaraan melakukan iterasi satu kali dilanjutkan oleh kendaraan lain hingga permintaan semua pelanggan terpenuhi. Iterasi 1: Kendaraan 1 Tipe 1 Berdasarkan Tabel 4, kendaraan ini mengunjungi pelanggan 1 dari depot karena jaraknya terdekat dari depot. Kapasitas yang dimiliki kendaraan sebesar 25 krat dan permintaan pelanggan 1 sebesar 17 krat, sehingga dimungkinkan untuk menambah pelanggan dalam rute kendaraan ini. Pelanggan terdekat dari pelanggan 1 ialah pelanggan 4 dengan permintaan sebesar 17 krat. Jika pelanggan 4 dimasukkan ke dalam rute kendaraan ini maka permintaan yang diangkut akan melebihi kapasitas. Maka dari
itu, dicari pelanggan lain yang cukup dekat dengan pelanggan 1 dengan permintaan maksimal 8 krat. Berdasarkan Tabel 2, pelanggan yang mungkin dikunjungi ialah pelanggan 2, pelanggan 3, pelanggan 5, dan pelanggan 9. Jika dilihat pada Tabel 4 maka pelanggan yang kunjungi selanjutnya ialah pelanggan 5, kemudian kendaraan kembali ke depot. Tabel 5 Rute Iterasi 1 Kendaraan 1 Tipe 1 dengan NNH (kapasitas 25 krat) Pelanggan Permintaan Jarak Sisa (krat) (km) kapasitas (krat) 0 25 1 17 11.52 8 5 8 2.16 0 0 13.08 0 Total 25 26.76 -
9
Sisa pelanggan = {2,3,4,6,7,8,9}. Karena masih terdapat pelanggan yang belum dikunjungi maka iterasi dilanjutkan ke Iterasi 2 menggunakan kendaraan lain. Rute yang dihasilkan pada Iterasi 1 hanya memuat tiga verteks (dua pelanggan dan satu depot) sehingga tidak perlu dilakukan metode 2-opt. Biaya yang dikeluarkan pada Iterasi 1 = 100 + 1.5 (26.76) = 140.14 ribu rupiah. Iterasi 2: Kendaraan 2 Tipe 1 Iterasi 2 dilakukan untuk menentukan rute selanjutnya bagi para pelanggan yang belum dikunjungi. kendaraan yang digunakan ialah Kendaraan 2 Tipe 1 dengan kapasitas 25 krat. Metode yang digunakan sama dengan metode pada Iterasi 1, tetapi pelanggan yang diamati hanya pelanggan yang belum dikunjungi pada iterasi sebelumnya. Tabel 6 Rute Iterasi 2 Kendaraan 2 Tipe 1 dengan NNH (kapasitas 25 krat) Pelanggan Permintaan Jarak Sisa (krat) (km) kapasitas (krat) 0 25 4 17 12.48 8 3 7 1.80 1 0 13.44 1 Total 24 28.44 Sisa pelanggan = {2,6,7,8,9}, dilanjutkan ke Iterasi 3. Pada Iterasi 2 verteks yang dihasilkan hanya tiga verteks maka tidak perlu dilakukan metode 2-opt. Biaya yang dikeluarkan pada Iterasi 2 = 100 + 1.5 (28.44) = 142.66 ribu rupiah. Iterasi 3: Kendaraan 1 Tipe 2 Iterasi 3 menggunakan metode yang sama dengan iterasi-iterasi sebelumnya. Tabel 7 Rute Iterasi 3 Kendaraan 1 Tipe 2 dengan NNH (kapasitas 30 krat) Pelanggan Permintaan Jarak Sisa (krat) (km) kapasitas (krat) 0 30 8 17 13.44 13 9 2 0.96 11 2 3 7.56 8 0 18.24 8 Total 22 40.20 Sisa pelanggan = {6,7}, dilanjutkan ke Iterasi 4.
Pada Iterasi 3, metode 2-opt dapat dilakukan karena verteks yang dihasilkan sebanyak empat verteks. Metode 2-opt mudah diaplikasikan jika rute dibentuk dalam gambar. Maka dari itu, rute yang dihasilkan dari Iterasi 3 dibentuk seperti pada Gambar 11. 0
8
13.44
18.24
0.96
2
7.56
9
Gambar 11 Rute Iterasi 3 Kendaraan 1 Tipe 2 pada NNH. Jika rute pada Gambar 11 dilakukan prosedur 2-opt maka akan didapat beberapa rute seperti pada Gambar 12. a) 0 8 14.22 18.24
0.96 6.60
2
b)
0
9 13.44
6.60
2
8 14.12
7.56
9
Gambar 12 Rute Iterasi 3 Kendaraan 1 Tipe 2 pada NNH dengan melakukan prosedur 2-opt. Rute yang dihasilkan pada Gambar 12a (0-9-8-2-0) menempuh jarak sebesar 39.92 km sedangkan pada Gambar 12b (0-8-2-9-0) menempuh jarak 41.72 km, sehingga rute yang dipilih ialah rute pada Gambar 12a dengan biaya yang dikeluarkan yaitu = 150 + 1.0 (39.92) = 189.92 ribu rupiah. Iterasi 4: Kendaraan 2 Tipe 2 Iterasi 4 dilakukan karena masih terdapat pelanggan yang belum dikunjungi. Rute Iterasi 4 dapat dilihat pada Tabel 8. Tabel 8 Rute Iterasi 4 Kendaraan 2 Tipe 2 dengan NNH (kapasitas 30 krat) Pelanggan Permintaan Jarak Sisa (krat) (km) kapasitas (krat) 0 30 7 19 13.92 11 0 13.92 11 Total 19 27.84 -
10
Sisa pelanggan = {6}, dilanjutkan ke Iterasi 5. Biaya yang dikeluarkan pada Iterasi 4 = 150 + 1.0 (27.84) = 177.84 ribu rupiah.
Pada Iterasi 1 metode 2-opt tidak perlu diterapkan. Dilanjutkan ke langkah 2.
Iterasi 5: Kendaraan Tipe 3 Iterasi 5 kendaraan hanya mengunjungi satu pelanggan yaitu Pelanggan 6 karena hanya pelanggan tersebut yang belum dikunjungi.
Iterasi 2 : 2. Pemilihan verteks seed Pelanggan i=4 merupakan verteks seed karena merupakan verteks di V\F dengan jarak terdekat dari depot. F={0,1,4}, U={2,3,6,7,8,9}, R={(0,1,0),(0,1,5,0),(0,4,0)}.
Tabel 9 Rute Iterasi 5 kendaraan Tipe 3 dengan NNH (kapasitas 40 krat) Verteks Permintaan Jarak Sisa (krat) (km) kapasitas (krat) 0 40 6 12 18.00 28 0 18.00 28 Total 12 36.00 -
3. Perluasan rute Jarak pelanggan terdekat dari pelanggan 4 adalah pelanggan 3. Pada Iterasi 2 metode 2-opt juga tidak perlu diterapkan, sehingga didapat:U=U\{3}={2,6,7,8,9} R={(0,1,0),(0,1,5,0),(0,4,0),(0,4,3,0)}. Dilanjutkan ke langkah 2.
Sisa pelanggan = {}, pada Iterasi 5 semua permintaan pelanggan telah terpenuhi, iterasi dihentikan. Biaya yang dikeluarkan pada Iterasi 5 = 150 + 1.5 (36.00) = 204.00 ribu rupiah. Setelah iterasi selesai total biaya yang didapat pada metode NNH ialah sebesar 854.56 ribu rupiah. 4.1.2 Konstruksi rute dengan Petal Heuristic (PH) Misalkan F adalah himpunan pelanggan yang telah digunakan sebagai verteks seed yaitu pelanggan pertama yang dikunjungi dari depot. U adalah himpunan pelanggan yang belum dikunjungi. R adalah himpunan rute yang dibangkitkan. Seperti halnya pada NNH, kendaraan yang digunakan dimulai dari kendaraan dengan tipe terkecil (lihat Tabel 3). Kendaraan Tipe 1 dengan kapasitas 25 krat. Iterasi 1: 1. Inisialisasi F={0}, R= 2. Pemilihan verteks seed (i) Karena jarak yang terdekat dari depot adalah pelanggan 1 maka yang menjadi verteks seed adalah pelanggan 1. Jadi F={0,1}, R={(0,1,0)}, U={2,3,4,5,6,7,8,9}. 3. Perluasan rute Karena PH mengonstruksi satu himpunan rute berdasarkan NNH maka perluasan rute yang diperoleh: R={(0,1,0),(0,1,5,0)}, U=U\{5}={2,3,4,6,7,8,9}
Iterasi 3 : 2. Pemilihan verteks seed Pelanggan i=8 merupakan verteks seed karena merupakan verteks di V\F dengan jarak terdekat dari depot. F={0,1,2,4,8}, U=U\{8}={2,6,7,9} R={(0,1,0),(0,1,5,0),(0,4,0),(0,4,3,0), (0,8,0)}. 3. Perluasan rute Jarak pelanggan terdekat dari pelanggan 8 adalah pelanggan 9 dilanjutkan ke pelanggan 2. Jika metode 2-opt dilakukan pada iterasi ini rute yang awalnya berjarak 40.20 km (lihat Gambar 11) menjadi 39.92 km (lihat Gambar 12a), sehingga didapat: R={(0,1,0),(0,1,5,0),(0,4,0),(0,4,3,0), (0,8,0),(0,9,8,2,0)}, U=U\{9,2}={6,7}. Dilanjutkan ke langkah 2. Iterasi 4 : 2. Pemilihan verteks seed Pelanggan i=7 merupakan verteks seed karena merupakan verteks di V\F dengan jarak terdekat dari depot. F={0,1,4,8,7}, U=U\{7}={6} R={(0,1,0),(0,1,5,0),(0,4,0),(0,4,3,0), (0,8,0),(0,9,8,2,0),(0,7,0)}. 3. Perluasan rute Pada Iterasi 4 tidak dapat dilakukan perluasan rute karena kapasitas yang tersisa sudah tidak dapat menampung permintaan dari pelanggan yang belum dikunjungi. Dilanjutkan ke langkah 2. Iterasi 5 : 2. Pemilihan verteks seed
11
Pelanggan i=6 merupakan verteks seed karena merupakan verteks di V\F dengan jarak terdekat dari depot. F={0,1,4,8,7}, U=U\{6}= R={(0,1,0),(0,1,5,0),(0,4,0),(0,4,3,0), (0,8,0),(0,9,8,2,0),(0,7,0),(0,6,0)}. 3. Perluasan rute Pada Iterasi 5 tidak perlu dilakukan perluasan rute karena tidak ada lagi pelanggan yang dikunjungi. Selanjutnya dilakukan metode PH menggunakan kendaraan Tipe 2 dengan kapasitas 30 krat. Iterasi 1: 1. Inisialisasi F={0}, R= 2. Pemilihan verteks seed Pelanggan i=1merupakan verteks seed sehingga F={0,1}, R={(0,1,0)}, U={2,3,4,5,6,7,8,9} 3. Perluasan rute Pelanggan terdekat dari pelanggan 1 ialah pelanggan 5, dilanjutkan ke pelanggan 9 kemudian ke pelanggan 2 dan kembali ke depot karena kendaraan sudah tidak mampu menampung permintaan lagi, sehingga didapat:R={(0,1,0),(0,1,5,9,2,0)} U=U\{5,9,2}={3,4,6,7,8}. Jika metode 2opt dilakukan pada iterasi ini maka beberapa kemungkinan rute yang dihasilkan (detail rute dapat dilihat di Lampiran 3). Rute dengan jarak terpendek ialah rute (0,1,2,9,5,0) dengan jarak 41.28 km. R = {(0,1,0),(0,1,2,9,5,0). Dilanjutkan ke langkah 2. Iterasi 2: 2. Pemilihan verteks seed Pelanggan i=4 menjadi verteks seed sehingga: F={0,1,4}, U={3,6,7,8}, R={(0,1,0),(0,1,2,9,5,0),(0,4,0)}. 3. Perluasan rute Pelanggan yang dikunjungi setelah pelanggan 4 yaitu pelanggan 3 kemudian kembali ke depot karena kendala kapasitas kendaraan, sehingga didapat U={6,7,8}, R={(0,1,0),(0,1,2,9,5,0),(0,4,0),(0,4,3,0)}. Pada Iterasi 2 tidak perlu dilakukan metode 2-opt. Dilanjutkan ke langkah 2. Iterasi 3: 2. Pemilihan verteks seed Pelanggan i=8 menjadi verteks seed sehingga: F={0,1,4,8}, U={6,7}, R={(0,1,0),(0,1,2,9,5,0),(0,4,0),(0,4,3,0), (0,8,0)}.
3. Perluasan rute Perluasan rute yang didapat dari iterasi ini dengan metode yang sama ialah U={7}, R={(0,1,0),(0,1,2,9,5,0),(0,4,0),(0,4,3,0), (0,8,0),(0,8,6,0)}. Pada iterasi ini tidak perlu melakukan metode 2-opt. Dilanjutkan ke langkah 2. Iterasi 4: 2. Pemilihan verteks seed Pelanggan i=7 menjadi verteks seed sehingga: F={0,1,4,8,7}, U={ }, R={(0,1,0),(0,1,2,9,5,0),(0,4,0),(0,4,3,0), (0,8,0),(0,8,6,0),(0,7,0)}. 3. Perluasan rute Pada Iterasi 4 tidak perlu dilakukan perluasan rute karena tidak ada lagi pelanggan yang dikunjungi. Selanjutnya dilakukan metode PH menggunakan kendaraan Tipe 3 dengan kapasitas 40 krat. Kendaraan Tipe 3 juga melakukan langkah-langkah yang sama sehingga didapat : Iterasi 1: F={0,1},R={(0,1,0),(0,1,4,9,2,0)}, U={3,5,6,7,8}, setelah dilakukan metode 2-opt (detail penghitungan dapat dilihat di Lampiran 4) maka terjadi perubahan R menjadi R={(0,1,0),(0,1,2,9,4,0)}. Iterasi 2: F={0,1,5}, R={(0,1,0),(0,1,4,9,2,0),(0,5,0),(0,5,3,8,0)}, U={6,7}, setelah dilakukan metode 2-opt R={(0,1,0),(0,1,2,9,4,0),(0,5,0),(0,8,5,3,0)}. (detail penghitungan dapat dilihat di Lampiran 5). Iterasi 3: F={0,1,5,7}, R={(0,1,0),(0,1,4,9,2,0),(0,5,0),(0,5,3,8,0),( 0,7,0),(0,7,6,0)}, U={ }, metode 2-opt tidak perlu dilakukan. 4. Evaluasi rute Rute-rute yang dihasilkan tiap iterasi pada setiap tipe kendaraan, dapat dimisalkan seperti berikut : e1= rute (0,1,5,0) kendaraan Tipe 1 e2= rute (0,4,3,0) kendaraan Tipe 1 e3= rute (0,8,9,2,0) kendaraan Tipe 1 e4= rute (0,7,0) kendaraan Tipe 1 e5= rute (0,6,0) kendaraan Tipe 1 e6= rute (0,1,5,9,2,0) kendaraan Tipe 2
12
e7= rute (0,4,3,0) kendaraan Tipe 2 e8= rute (0,8,6,0) kendaraan Tipe 2 e9= rute (0,7,0) kendaraan Tipe 2 e10= rute (0,1,2,9,4,0) kendaraan Tipe 3 e11= rute (0,8,5,3,0) kendaraan Tipe 3 e12= rute (0,7,6,0) kendaraan Tipe 3
tersebut akan lebih mudah diterapkan jika rute-rute yang ada direpresentasikan dalam bentuk sebagai berikut:
4
1
sehingga biaya tiap rute ialah:
3
5
π1 = 100 + 1.5(26.76) = 140.14 π2 = 100 + 1.5(29.57) = 142.66 π3 = 100 + 1.5(39.92) = 159.88 π4 = 100 + 1.5(27.84) = 141.76 π5 = 100 + 1.5(36.00) = 154.00 π6 = 150 + 1.0(41.88) = 191.88 π7 = 150 + 1.0(28.44) = 178.44 π8 = 150 + 1.0(35.24) = 185.24 π9 = 150 + 1.0(27.84) = 177.84 π10 = 150 + 1.5(41.88) = 211.92 π11 = 150 + 1.5(31.32) = 196.98 π12 = 150 + 1.5(36.00) = 204.00 5. Penentuan solusi masalah himpunan yang diperumum
0
0
Rute Iterasi 1
Rute iterasi 2 0 9 8 2
Rute Iterasi 3
pemartisi
Fungsi objektif Min 140.14 x1 + 142.66 x2 + 159.88 x3 + 141.76 x4 + 154.00 x5 + 191.88 x6 + 178.44 x7 + 185.24 x8 + 177.84 x9 + 211.92 x10 + 196.98 x12 + 204.00 x12 terhadap kendala x1 + x6 + x10 = 1 x3 + x6 + x10 = 1 x2 + x7 + x11 = 1 x2 + x7 + x10 = 1 x1 + x6 + x11 = 1 x5 + x8 + x12 = 1 x4 + x9 + x12 = 1 x3 + x8 + x11 = 1 x3 + x6 + x10 = 1 x 1 + x2 + x3 + x4 + x5 ≤ 2 x6 + x7 + x8 + x9 ≤ 2 x10 + x11 + x12 ≤ 1 Dengan LINGO 11.0 diperoleh solusi untuk masalah SPP sebagai berikut: x1=x3=x5=x7=x9=x10=x11=x12=0, x2=x4=x6=x8=1, dan nilai fungsi objektif sebesar 661.54 (detail penghitungan dapat dilihat di Lampiran 6). 4.2 Tahap Perbaikan dari Setiap Heuristik 4.2.1 Perbaikan rute NNH Rute-rute yang dihasilkan dari setiap iterasi kemudian diperbaiki dengan metode 3opt, metode pembatasan 2-interchange, dan pencarian rute gabungan. Metode-metode
0
0
7
6
Rute Iterasi 4 Rute Iterasi 5 Gambar 13 Rute awal tiap iterasi pada metode NNH. 1. Metode 3-opt Metode 3-opt tidak dapat dilakukan pada rute NNH karena banyaknya verteks yang dihasilkan setiap iterasi tidak dimungkinkan untuk mendapatkan rute lain. 2. Metode pembatasan 2-interchange Pencarian rute baru dengan menggunakan metode pembatasan 2-interchange ialah dengan memperhatikan perubahan total jarak sebelum dan sesudah dilakukannya metode ini. Pembatasan 2-interchange dimulai dengan mencari pasangan terbaik dari Iterasi 1 dengan tetap memperhatikan kapasitas kendaraan. a) Pembatasan 2-interchange rute Iterasi 1 Selisih jarak total terbesar pada iterasi 1 ialah dengan melakukan 2-pemindahan verteks antara Iterasi 1 dengan Iterasi 5. Total jarak awal ialah 62.76 km dan total jarak akhir 39.24 km, sehingga selisih totalnya yaitu sebesar 23.52 km (detail penghitungan dapat dilihat di Lampiran 7). 0
0 1 6
5 Gambar 14 2-pemindahan verteks antara Iterasi 1 dan Iterasi 5.
13
b) Pembatasan 2-interchange rute Iterasi 2 Pembatasan 2-interchange pada rute Iterasi 2 hanya didapat pada 1-pemindahan verteks dengan Iterasi 3. Total jarak awal ialah 68.36 km dan total jarak akhir ialah 65.12 km, sehingga selisih totalnya yaitu sebesar 3.24 km (detail penghitungan dapat dilihat di Lampiran 8). 0 0 9 4 8 3 2
4.2.2 Tahap perbaikan PH Rute-rute yang dihasilkan oleh metode PH dapat direpresentasikan sebagai berikut: 0
3. Pencarian rute gabungan Pencarian rute gabungan dapat dilakukan dengan memperhatikan tabel di bawah ini. Tabel 10 Rute-rute hasil dari pembatasan 2interchange pada NNH Sisa Total Tipe kapasitas Iterasi permintaan kendaraan kendaraan (krat) (krat) 1 1 2 1 17 8 3 2 29 1 4 2 19 11 5 3 37 3
Rute e2
Tabel 11 Biaya perbaikan NNH Iterasi Rute Jarak (km) 2 (0,4,0) 24.96 3 (0,9,8,2,3,0) 40.16 4 (0,7,0) 27.84 5 (0,6,1,5,0) 39.24 Total 132.20
Biaya (ribu rupiah) 137.44 190.16 177.84 208.86 714.30
Rute e4
0 0
1 5
8
9
6
2 Rute e6 Rute e8 Gambar 16 Rute awal yang dihasilkan pada metode PH. 1. Metode 3-opt Metode 3-opt hanya bisa diaplikasikan pada rute e6, namun dari semua kemungkinan yang ada tidak terdapat rute dengan jarak yang lebih baik, sehingga rute yang digunakan tetap rute awal. (detail penghitungan dapat dilihat di Lampiran 9). 2. Metode pembatasan 2-interchange Berdasarkan data sebelumnya, rute e2 dan rute e4 menggunakan kendaraan Tipe 1 dengan kapasitas 25 krat sedangkan rute e4 dan rute e6 menggunakan kendaraan Tipe 2 dengan kapasitas 30 krat. a)
Pada Tabel 10 terlihat bahwa tidak ada rute yang dapat digabungkan sehingga ruterute yang telah diperbaiki dapat dihitung biayanya.
7
3
Gambar 15 1-pemindahan verteks antara Iterasi 2 dan Iterasi 3. Rute yang tersisa hanya rute Iterasi 4 maka tidak perlu mencari pasangan pembatasan 2interchange.
0
4
Pembatasan 2-interchange rute e2 Selisih jarak total terbesar pada e2 hanya didapat dengan melakukan 2-penukaran verteks antara e2 dengan e6. Total jarak awal ialah 70.32 km dan total jarak akhir 70.20 km, sehingga selisih totalnya yaitu sebesar 0.12 km (detail penghitungan dapat dilihat di Lampiran 10). 0
0 1 4 3
5 9 2
Berdasarkan Tabel 11 dapat dilihat bahwa setelah perbaikan maka biaya yang dikeluarkan pada metode NNH yaitu sebesar 714.30 ribu rupiah, sehingga perusahaan dapat menghemat biaya sebesar 140.26 ribu rupiah.
Gambar 17 2-penukaran verteks antara Rute e2 dan Rute e6.
14
Rute e4 dan Rute e8 tidak dapat mengaplikasikan metode pembatasan 2interchange karena kendala kapasitas. 3. Pencarian rute gabungan Pencarian rute gabungan dapat dilakukan dengan memperhatikan tabel di bawah ini Tabel 12 Rute-rute hasil dari pembatasan 2interchange pada PH Sisa Total Tipe kapasitas Rute permintaan kendaraan kendaraan (krat) (krat) e2 1 25 0 e4 1 19 6 e6 2 29 1 e8 2 29 1 Pada Tabel 12 terlihat bahwa tidak ada rute yang dapat digabungkan sehingga ruterute yang telah diperbaiki dapat dihitung biayanya. Rute yang dihasilkan pada PH perbaikan dapat dilihat pada Tabel 13 Tabel 13 Biaya PH perbaikan Rute Jarak (km) e2 (0,1,5,0) 27.76 e4 (0,7,0) 27.84 e6 (0,4,3,9,2,0) 43.44 e8 (0,8,6,0) 35.24 Total 134.28
Biaya (ribu rupiah) 140.14 141.76 193.44 185.24 660.58
Berdasarkan Tabel 13 dapat dilihat bahwa setelah perbaikan maka biaya yang dikeluarkan pada metode PH yaitu sebesar 660.58 ribu rupiah, sehingga perusahaan dapat menghemat biaya sebesar 0.96 ribu rupiah. 4.3 Hasil Hasil yang didapat dari penerapan metodemetode yang ada dapat dilihat pada Tabel 14.
Tabel 14 Data jarak dan biaya tiap heuristik Heuristik Heuristik dengan perbaikan NNH PH NNH PH Jarak 158.96 134.53 132.20 134.28 (km) Biaya (ribu 854.56 661.54 714.30 660.58 rupiah) Berdasarkan Tabel 14 heuristik dengan perbaikan menampilkan biaya yang lebih baik bila dibandingkan dengan heuristik tanpa perbaikan. Setiap heuristik memiliki rute berbeda, rute-rute yang diambil menyebabkan perbedaan jarak yang ditempuh dan kendaraan tertentu yang digunakan, jenis kendaraan yang digunakan akan sangat memengaruhi biaya yang dikeluarkan sehingga jarak yang lebih kecil belum tentu menghasilkan biaya yang lebih kecil pula. Setelah rute tiap heuristik terbentuk, maka aktivitas pick-up berupa pengangkutan botol kosong yang ada pada tiap pelanggan mulai diperhitungkan. Aktivitas pick-up ini dapat mengurangi biaya pendistribusian. Adapun biaya yang dikeluarkan oleh pendistribusi jika memperhitungkan aktivitas pick-up dapat dilihat pada Tabel 15 (detail penghitungan dapat dilihat pada Lampiran 11). Tabel
Biaya (ribu rupiah)
15
Biaya pendistribusian dengan mempertimbangkan aktivitas pick-up Heuristik Heuristik dengan perbaikan NNH PH NNH PH 810.96
651.24
703.90
650.48
15
DEPOT
DEPOT
1
1
3
3 4
4
5
5 2
6 8
2
6 8
9
9
7
Keterangan: Tipe kendaraan
7
Jarak (km)
Biaya (ribu rupiah) 1 26.76 137.84 1 28.44 140.16 2 39.92 187.52 2 27.84 142.94 3 36.00 202.50 Gambar 18 Rute hasil NNH.
Keterangan: Tipe kendaraan
Jarak (km)
Biaya (ribu rupiah) 1 1 24.96 135.64 2 40.16 187.26 2 27.84 175.94 3 39.24 205.06 Gambar 19 Rute hasil NNH perbaikan.
DEPOT
DEPOT
1
1
3
3 4
4 5
5
2
6
2
6
8
8 9
9
7
Keterangan: Tipe kendaraan
Jarak (km)
1 26.76 1 28.44 2 39.92 2 27.84 Gambar 20 Rute hasil PH.
7
Biaya (ribu rupiah) 140.16 139.86 188.98 182.24
Keterangan: Tipe kendaraan
Jarak (km)
Biaya (ribu rupiah) 1 27.76 137.84 1 27.84 139.86 2 43.44 190.54 2 35.24 182.24 Gambar 21 Rute hasil PH perbaikan.
16
V SIMPULAN DAN SARAN 5.1 Simpulan Masalah penentuan rute distribusi barang dapat diselesaikan menggunakan metode heuristik. Penelitian ini menggunakan metode nearest neighbour heuristic dan petal heuristic serta beberapa metode perbaikan. Metode-metode perbaikan yang digunakan ialah metode 2opt, metode 3-opt, metode 2-interchange terbatas, dan penggabungan rute. Hasil studi kasus menunjukkan bahwa semakin banyak metode perbaikan yang dilakukan, maka rute yang diperoleh semakin baik.
5.2 Saran Beberapa hal yang dapat dilakukan agar penelitian ini lebih baik terkait dengan implementasinya di lapangan adalah 1. banyaknya pelanggan dapat diperbesar agar semua metode dapat digunakan, 2. dapat ditambahkan kendala waktu pada model matematikanya.
DAFTAR PUSTAKA Chartrand G, Zhang P. 2009. Chromatic Graph Theory. London: CRC Pr Foulds LR. 1992. Graph Theory Applications. New York: Springer-Verlag. Garfinkel S, Nemhauser G. 1972. Integer Programming. New York:A Wiley Interscience Publication. Grötschel M. 1982. Approaches to hard combinatorial optimization Problems. Di dalam: Bernhard K, editor. Modern Applied Mathematics Optimization and Operations Research. New York: NorthHolland Publishing Company. hlm 437515. ILOG. 2002. User’s Manual ILOG Dispatcher 2.1. France: ILOG. Prive J, Renaud J, Boctor F, Laporte G. 2006. Solving a vehicle-routing problem arising in soft-drink distribution. Journal of Operational Research Society 57: 10451052.
Nilsson C. 2003. Heuristics for the Traveling SalesmanProblem. http://www.ida.liu.se/ ~TDDB19/reports/htsp.pdf. [20 Agustus 2012]. Raditya A. 2009. Penggunaan Metode Heuristik dalam Permasalahan Vehicle Routing Problem dan Implementasinya di PT Nippon Indosari Corpindo [Skripsi]. Bogor: Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Yen J, Birge J. 2006. A Note on”A Stochastic Programming Approach to the Airline Crew Scheduling Problem”. Transportation Science 40:3-14.
17
LAMPIRAN
18
Lampiran 1 Program LINGO 11.0 pada contoh masalah pemartisian himpunan SETS: setpartisi/1..5/:x; ENDSETS !fungsi objektif; MIN=15*x(1)+10*x(2)+19*x(3)+18*x(4)+17*x(5); !kendala; x(1)+x(4)=1; x(1)+x(5)=1; x(2)+x(5)=1; x(3)+x(4)=1; x(4)=1; x(3)+x(5)=1; @FOR(setpartisi(j):@BIN(x(j))); Global optimal solution found. Objective value: 35.00000 Infeasibilities: 0.000000 Total solver iterations: 0 Variable X(1) X(2) X(3) X(4) X(5)
Value 0.000000 0.000000 0.000000 1.000000 1.000000
Reduced Cost 0.000000 0.000000 0.000000 0.000000 0.000000
Lampiran 2 Program LINGO 11.0 pada contoh masalah pemartisian himpunan yang diperumum SETS: setpartisi/1..5/:x; ENDSETS !fungsi objektif; MIN=15*x(1)+10*x(2)+19*x(3)+18*x(4)+17*x(5); !kendala; x(1)+x(4)=1; x(1)+x(5)=1; x(2)+x(5)=1; x(3)+x(4)=1; x(4)=1; x(3)+x(5)=1; x(1)+x(2)+x(3)+x(4)+x(5)<=5/2; @FOR(setpartisi(j):@BIN(x(j))); Global optimal solution found. Objective value: Infeasibilities: Total solver iterations: Variable X(1) X(2) X(3) X(4) X(5)
Value 0.000000 0.000000 0.000000 1.000000 1.000000
35.00000 0.00000 0
Reduced Cost 0.000000 0.000000 0.000000 0.000000 0.000000
19
Lampiran 3 Semua kemungkinan metode 2-opt pada rute (0,1,5,9,2,0) Semua kemungkinan rute yang dapat dibentuk oleh metode 2-opt pada perluasan rute Iterasi 1 PH kendaraan Tipe 2 ialah 0
11.52
1 2.16
5
18.24 2.40 7.56
2
9
Gambar 22 Rute awal Iterasi 1 PH kendaraan Tipe 2 dengan jarak tempuh 41.88 km. Perbaikan rute dengan metode 2-opt: a) 0
d)
0
1
11.52
1
13.08
13.08
2.16
5
6.72
5
18.24
2.40
4.56
2 2
7.56
9
7.56
9
Rute (0,1,2,9,5,0) dengan jarak 41.28 km
Rute (0,5,1,9,2,0) dengan jarak 45.6 km e) 0
b)
1
14.12
5 8.88
2.40
14.12
2
9
Rute (0,9,5,1,2,0) dengan Jarak 43.64 km c) 11.52
1 2.16
5
18.24
0
11.52
2.16
6.72
2
0
7.56
9
Rute (0,1,5,2,9,0) dengan Jarak 44.24 km
1 4.56
5
18.24 2.40
8.88
2
9
Rute (0,1,9,5,2,0) dengan Jarak 45.60 km Gambar 23 Pengaplikasian metode 2-opt pada Iterasi 1 PH kendaraan Tipe 2. Rute-rute yang dihasilkan menunjukkan bahwa rute d) memiliki jarak terkecil, maka selanjutnya rute yang akan digunakan ialah rute d).
20
Lampiran 4 Semua kemungkinan metode 2-opt pada rute (0,1,4,9,2,0) Semua kemungkinan rute yang dapat dibentuk oleh metode 2-opt dari rute Iterasi 1 kendaraan Tipe 3 pada PH. 0
11.52
1 1.56
4
18.24 3.00 7.56
2
9
Gambar 24 Rute awal Iterasi 1 PH kendaraan Tipe 2 dengan jarak tempuh 41.88 km. Perbaikan rute dengan metode 2-opt: a) 0 1 12.48
d)
0
11.52
1
1.56
12.48
4
18.24
4
6.72
4.56
3.00
2
7.56
9
2
Rute (0,4,1,9,2,0) dengan Jarak 44.40 km b)
0
9
Rute (0,1,2,9,4,0) dengan jarak 41.28 km e)
1
0
11.52
1
1.56
6.72
1.56
4
18.24
14.12
5 8.88
3.00
14.12
2
7.56
9
2
Rute (0,9,4,1,2,0) dengan jarak 43.64 km
7.56
9
Rute (0,1,5,9,2,0) dengan Jarak 43.04 km .
c)
0
11.52
1 4.56
4
18.24 3.00
8.88
2
9
Rute (0,1,9,4,2,0) dengan jarak 45.60 km Gambar 25 Pengaplikasian metode 2-opt pada Iterasi 1 PH kendaraan Tipe 3. Rute-rute yang dihasilkan menunjukkan bahwa rute d) memiliki jarat terkecil, maka selanjutnya rute yang akan digunakan ialah rute d).
21
Lampiran 5 Semua kemungkinan rute 2-opt pada rute (0,5,3,8,0) Semua kemungkinan rute yang dapat dibentuk oleh metode 2-opt dari rute Iterasi 2 PH kendaraan Tipe 3. 0
5
13.08
13.44
1.56
8
4.32
3
Gambar 26 Rute awal Iterasi 2 PH kendaraan Tipe 3 dengan jarak tempuh 32.40 km. Perbaikan rute dengan metode 2-opt: a) 0
14.16
2.16
8
5
13.08
7.56
3
Rute (0,5,8,3,0) dengan Jarak 33.72 km b) 0
5 14.12
18.24
0.96 6.60
8
3
Rute (0,3,5,8,0) dengan Jarak 31.32 km. Gambar 27 Pengaplikasian metode 2-opt pada rute Iterasi 2 PH kendaraan Tipe 3. Rute-rute yang dihasilkan menunjukkan bahwa rute d) memiliki jarat terkecil, maka selanjutnya rute yang akan digunakan ialah rute d).
22
Lampiran 6 Program LINGO 11.0 pada aplikasi masalahan pemartisian himpunan yang diperumum. SETS: partisirute/1..12/:x; ENDSETS !fungsi objektif; MIN=140.14*x(1)+142.66*x(2)+159.88*x(3)+141.76*x(4)+154*x(5)+191.88*x(6)+178.44*x(7)+ 185.24*x(8)+177.84*x(9)+211.92*x(10)+196.98*x(11)+204*x(12); !kendala; x(1)+x(6)+x(10)=1; x(3)+x(6)+x(10)=1; x(2)+x(7)+x(11)=1; x(2)+x(7)+x(10)=1; x(1)+x(6)+x(11)=1; x(5)+x(8)+x(12)=1; x(4)+x(9)+x(12)=1; x(3)+x(8)+x(11)=1; x(3)+x(6)+x(10)=1; x(1)+x(2)+x(3)+x(4)+x(5)<=2; x(6)+x(7)+x(8)+x(9)<=2; x(10)+x(11)+x(12)<=1; @FOR(partisirute(e):@BIN(x(e))); Global optimal solution found. Objective value: 661.5400 Objective bound: 661.5400 Infeasibilities: 0.0000 Extended solver steps: 0 Total solver iterations: 0 Variable X(1) X(2) X(3) X(4) X(5) X(6) X(7) X(8) X(9) X(10) X(11) X(12)
Value 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 1.000000 0.000000 0.000000 0.000000 0.000000
Reduced Cost 140.0800 142.6600 159.8800 141.7600 154.0000 191.8800 178.4400 185.2400 177.8400 211.9200 196.9800 204.0000
23
Lampiran 7 Metode Pembatasan 2-interchange untuk Iterasi 1 pada NNH Pencarian pasangan rute perbaikan NNH bagi Iterasi 1 dengan metode Pembatasan 2interchange 1. Rute Iterasi 1 dan rute Iterasi 2 Rute Iterasi 1 memiliki jarak tempuh sebesar 26.76 km sedangkan rute Iterasi 2 memiliki jarak tempuh sebesar 28.44 km, sehingga total kedua jarak tersebut yaitu sebesar 55.20 km. Jika dilakukan 1-penukaran verteks maka didapat rute seperti pada gambar berikut ini: 0
0 4
1
3
5
Gambar 28 Rute hasil 1-penukaran verteks antara Rute Iterasi 1 dan rute Iterasi 2 pada NNH. Jarak pada rute (0,1,3,0) yaitu sebesar 28. 32 km sedangkan pada rute (0,4,5,0) yaitu sebesar 26.16 km, sehingga total jarak menjadi 54.48km. Terjadi pengurangan total jarak sebesar 0.62 km. 2. Rute Iterasi 1 dan rute Iterasi 3 Rute Iterasi 1 memiliki jarak tempuh sebesar 26.76 km sedangkan rute Iterasi 3 memiliki jarak tempuh sebesar 39.92 km, sehingga total kedua jarak tersebut yaitu sebesar 66.68 km. Jika dilakukan 1-pemindahan verteks maka didapat rute seperti pada gambar berikut ini: 0 0
9 1 8
5
2
Gambar 29 Rute hasil 1-pemindahan verteks antara Rute Iterasi 1 dan rute Iterasi 3 pada NNH. Jarak pada rute (0,1,0) sebesar 23.04 km sedangkan rute (0,9,8,2,5,0) sebesar 43.56 km, sehingga total jarak menjadi 66.60 km. Terjadi pengurangan total jarak sebesar 0.08 km. Jika dilakukan 1-penukaran verteks maka didapat rute seperti pada gambar berikut ini: 0 0
9 1
5
8 2
Gambar 30 Rute hasil 1-penukaran verteks antara Rute Iterasi 1 dan rute Iterasi 3 pada NNH. Jarak pada rute (0,8,5,0) sebesar 28.68 km sedangkan rute (0,9,1,2,0) sebesar 43.64 km, sehingga total jarak menjadi 72.32 km. Terjadi penambahan total jarak sebesar 5.64 km.
24
3. Rute Iterasi 1 dan rute Iterasi 4 Rute Iterasi 1 memiliki jarak tempuh sebesar 26.76 km sedangkan rute Iterasi 4 memiliki jarak tempuh sebesar 27.84 km, sehingga total kedua jarak tersebut sebesar 54.60 km. Jika dilakukan 1-pemindahan verteks maka didapat rute seperti pada gambar berikut ini: 0 1
0 7
5
Gambar 31 Rute hasil 1-pemindahan verteks antara Rute Iterasi 1 dan rute Iterasi 4 pada NNH. Jarak pada rute (0,1,0) sebesar 23.04 km sedangkan rute (0,7,5,0) sebesar 29.16 km, sehingga total jarak menjadi 52.20 km. Terjadi pengurangan total jarak sebesar 2.40 km. 3. Rute Iterasi 1 dan rute Iterasi 5 Rute Iterasi 1 memiliki jarak tempuh sebesar 26.76 km sedangkan rute Iterasi 5 memiliki jarak tempuh sebesar 36.00 km, sehingga total kedua jarak tersebut sebesar 62.76 km. Jika dilakukan 2pemindahan verteks maka didapat rute seperti pada gambar berikut ini: 0 1 5
0 6
Gambar 32 Rute hasil 2-pemindahan verteks antara Rute Iterasi 1 dan rute Iterasi 5 pada NNH. Rute yang terbentuk pada kasus ini akan menghasilkan satu rute, karena semua pelanggan dari Iterasi 1 dapat ditampung oleh kendaraan pada Iterasi 5. Rute yang terbentuk yaitu (0,6,1,5,0) dengan jarak tempuh sebesar 39.24 km, sehingga terjadi pengurangan total jarak sebesar 23.52 km.
25
Lampiran 8 Metode Pembatasan 2-interchange untuk Iterasi 2 pada NNH Pencarian pasangan rute perbaikan NNH bagi Iterasi 2 dengan metode Pembatasan 2interchange 1.Rute Iterasi 2 dan rute Iterasi 3 Rute Iterasi 2 memiliki jarak tempuh sebesar 28.44 km sedangkan rute Iterasi 3 memiliki jarak tempuh sebesar 39.92 km, sehingga total kedua jarak tersebut sebesar 68.36 km. Jika dilakukan 1pemindahan verteks maka didapat rute seperti pada gambar berikut ini: 0 0 9 4 8
3
2 Gambar 33 Rute hasil 1-pemindahan verteks antara Rute Iterasi 2 dan rute Iterasi 3 pada NNH. Jarak pada rute (0,4,0) sebesar 24.96 km sedangkan rute (0,9,8,2,3,0) sebesar 40.16 km, sehingga total jarak menjadi 65.12 km. Terjadi pengurangan total jarak sebesar 3.24 km. Jika dilakukan 1-penukaran verteks maka didapat rute seperti pada gambar berikut ini: 0 0 9 4 8
3
2 Gambar 34 Rute hasil 1-penukaran verteks antara Rute Iterasi 2 dan rute Iterasi 3 pada NNH. Jarak pada rute (0,8,3,0) sebesar 38.28 km sedangkan rute (0,9,4,2,0) sebesar 33.08 km, sehingga total jarak menjadi 71.36 km. Terjadi penambahan total jarak sebesar 3 km. 2.Rute Iterasi 2 dan rute Iterasi 4 Rute Iterasi 2 memiliki jarak tempuh sebesar 28.44 km sedangkan rute Iterasi 4 memiliki jarak tempuh sebesar 27.84 km, sehingga total kedua jarak tersebut sebesar 56.28 km. Jika dilakukan 1pemindahan verteks maka didapat rute seperti pada gambar berikut ini: 0
0 4 7
3 Gambar 35 Rute hasil 1-pemindahan verteks antara Rute Iterasi 2 dan rute Iterasi 4 pada NNH. Jarak pada rute (0,4,0) sebesar 24.96 km sedangkan rute (0,7,3,0) sebesar 32.64 km, sehingga total jarak menjadi 57.60 km. Terjadi penambahan total jarak sebesar 1.32 km.
26
Lampiran 9 Semua kemungkinan metode 3-opt pada metode PH Semua kemungkinan rute pengaplikasian metode 3-opt rute e6 a) 0
pada
c)
0
1 13.08
2.16
1
5
13.08
6.72
14.12
5
18.24 4.56
2
2.40
6.72
9
Jarak tempuh 43.64 km
9
2
7.56
Jarak tempuh 45.00 km b) 0
1
11.52
13.08
5
4.56 8.88
2
7.56
9
Jarak tempuh 45.60 km Gambar 36 Rute hasil 3-opt pada rute e6. Rute-rute yang dihasilkan menunjukkan bahwa tidak ada rute baru yang dihasilkan oleh metode 3-opt dengan jarak lebih baik. Lampiran 10 Metode Pembatasan 2-interchange untuk e2 pada PH Pencarian pasangan rute perbaikan PH rute e2 dengan metode Pembatasan 2-interchange 1. Rute e2 dan rute e6 Rute e2 memiliki jarak tempuh sebesar 28.44 km sedangkan rute e6 memiliki jarak tempuh sebesar 41.88 km, sehingga total kedua jarak tersebut yaitu sebesar 70.32 km. Jika dilakukan 2penukaran verteks maka didapat rute seperti pada gambar berikut ini: 0 0
1 4
5 9
3
2
Gambar 37 Rute hasil 2-penukaran verteks antara Rute e2 dan rute e6. Jarak pada rute (0,1,5,0) sebesar 26.76 km sedangkan rute (0,4,3,9,2,0) sebesar 43.44 km, sehingga total jarak menjadi 70.20 km. Terjadi penambahan total jarak sebesar 0.12 km. 0 0
1 4
3
5 9 2
Gambar 38 Rute hasil 2-penukaran verteks antara Rute e2 dan rute e6. Jarak pada rute (0,1,5,0) sebesar 26.76 km sedangkan rute (0,3,4,9,2,0) sebesar 44.76 km, sehingga total jarak menjadi 70.52 km. Terjadi penambahan total jarak sebesar 0.20 km.
27
Lampiran 11 Biaya yang dikeluarkan dengan mempertimbangkan pick-up A. Biaya pada rute NNH Rute 1: Kendaraan Tipe 1 Pelanggan Permintaan Pick-up Barang yang terdapat dalam kendaraan (krat) (krat) (krat) 0 25 1 17 17 25 5 8 6 23 Biaya pendistribusian : 140.14 – 23(0.1) = 137.84 Rute 2: Kendaraan Tipe 1 Pelanggan Permintaan Pick-up Barang yang terdapat dalam kendaraan (krat) (krat) (krat) 0 24 4 17 18 25 3 7 7 25 Biaya pendistribusian : 142.66 – 25(0.1) = 140.16 Rute 3: Kendaraan Tipe 2 Pelanggan Permintaan Pick-up Barang yang terdapat dalam kendaraan (krat) (krat) (krat) 0 22 9 2 5 25 8 17 17 25 2 3 2 24 Biaya pendistribusian : 189.92 – 24(0.1) = 187.52 Rute 4: Kendaraan Tipe 2 Permintaan Pick-up Barang yang terdapat dalam kendaraan Pelanggan (krat) (krat) (krat) 0 19 7 19 19 19 Biaya pendistribusian : 177.84 – 19(0.1) = 142.94 Rute 5: Kendaraan Tipe 3 Pelanggan Permintaan Pick-up Barang yang terdapat dalam kendaraan (krat) (krat) (krat) 0 12 6 12 15 15 Biaya pendistribusian: 204.00 – 15(0.1) = 202.50 B. Biaya pada rute NNH perbaikan Rute 1: Kendaraan Tipe 1 Permintaan Pick-up Barang yang terdapat dalam kendaraan Pelanggan (krat) (krat) (krat) 0 17 4 17 18 18 Biaya pendistribusian: 137.44 – 18(0.1) = 135.64
28
Rute 2: Kendaraan Tipe 2 Pelanggan Permintaan Pick-up Barang yang terdapat dalam kendaraan (krat) (krat) (krat) 0 29 9 2 3 30 8 17 17 30 2 3 2 29 3 7 7 29 Biaya pendistribusian: 190.16 – 29(0.1) = 187.26 Rute 3: Kendaraan Tipe 2 Pelanggan Permintaan Pick-up Barang yang terdapat dalam kendaraan (krat) (krat) (krat) 0 19 7 19 19 19 Biaya pendistribusian: 177.84 – 19(0.1) = 175.94 Rute 4: Kendaraan Tipe 3 Pelanggan Permintaan Pick-up Barang yang terdapat dalam kendaraan (krat) (krat) (krat) 0 37 6 12 15 40 1 17 17 40 5 8 6 38 Biaya pendistribusian: 208.86 – 38(0.1) = 205.06 C. Biaya pada rute PH Rute 1: Kendaraan Tipe 1 Pelanggan Permintaan Pick-up Barang yang terdapat dalam kendaraan (krat) (krat) (krat) 0 24 4 17 18 25 3 7 7 25 Biaya pendistribusian: 142.66 – 25(0.1) = 140.16 Rute 2: Kendaraan Tipe 1 Pelanggan Permintaan Pick-up Barang yang terdapat dalam kendaraan (krat) (krat) (krat) 0 19 7 19 19 19 Biaya pendistribusian: 141.76 – 19(0.1) = 139.86 Rute 3: Kendaraan Tipe 2 Pelanggan Permintaan Pick-up Barang yang terdapat dalam kendaraan (krat) (krat) (krat) 0 30 1 17 17 30 5 8 6 28 9 2 4 30 2 3 2 29 Biaya pendistribusian: 191.88 – 29(0.1) = 188.98
29
Rute 4: Kendaraan Tipe 2 Pelanggan Permintaan Pick-up Barang yang terdapat dalam kendaraan (krat) (krat) (krat) 0 29 8 17 17 29 6 12 13 30 Biaya pendistribusian: 185.24 – 30(0.1) = 182.24 D. Biaya rute pada PH perbaikan Rute 1: Kendaraan Tipe 1 Pelanggan Permintaan Pick-up Barang yang terdapat dalam kendaraan (krat) (krat) (krat) 0 25 1 17 17 25 5 8 6 23 Biaya pendistribusian: 140.14 – 23(0.1) = 137.84 Rute 2: Kendaraan Tipe 1 Pelanggan Permintaan Pick-up Barang yang terdapat dalam kendaraan (krat) (krat) (krat) 0 19 7 19 19 19 Biaya pendistribusian: 141.76 – 19(0.1) = 139.86 Rute 3: Kendaraan Tipe 2 Pelanggan Permintaan Pick-up Barang yang terdapat dalam kendaraan (krat) (krat) (krat) 0 29 4 17 18 30 3 7 7 30 9 2 2 30 2 3 2 29 Biaya pendistribusian: 193.44 – 29(0.1) = 190.54 Rute 4: Kendaraan Tipe 2 Pelanggan Permintaan Pick-up Barang yang terdapat dalam kendaraan (krat) (krat) (krat) 0 29 8 17 17 29 6 12 13 30 Biaya pendistribusian: 185.24 – 30(0.1) = 182.24
