PENENTUAN SOLUSI LASO DARI TRAVELING SALESMAN PROBLEM WITH PICK-UP AND DELIVERY DENGAN METODE HEURISTIK ATIKAH NURBAITI

PENENTUAN SOLUSI LASO DARI TRAVELING SALESMAN PROBLEM WITH PICK-UP AND DELIVERY DENGAN METODE HEURISTIK

ATIKAH NURBAITI

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2015

PERNYATAAN MENGENAI SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Penentuan Solusi Laso dari Traveling Salesman Problem with Pick-up and Delivery dengan Metode Heuristik adalah benar 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 skripsi ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor. Bogor, Mei 2015 Atikah Nurbaiti NIM G54110001

ABSTRAK ATIKAH NURBAITI. Penentuan Solusi Laso dari Traveling Salesman Problem with Pick-up and Delivery dengan Metode Heuristik. Dibimbing oleh FARIDA HANUM dan TONI BAKHTIAR. Pendistribusian barang atau jasa merupakan salah satu bagian penting dalam sebuah perusahaan atau instansi. Masalah optimasi pendistribusian barang dapat diselesaikan secara matematis menggunakan formulasi Traveling Salesman Problem (TSP). Pembahasan karya ilmiah ini difokuskan pada salah satu variasi TSP yaitu Traveling Salesman Problem with Pick-up and Delivery (TSPPD) dengan permintaan pengambilan (pick-up) dan permintaan pengiriman (delivery) sebagai bagian masalah terpenting. Jika TSP murni memiliki aturan bahwa kendaraan hanya dapat mengunjungi setiap tempat satu kali, maka dalam TSPPD ini kendaraan dimungkinkan mengunjungi beberapa tempat lebih dari satu kali agar semua kendala terpenuhi. Penyelesaian TSPPD iniberbentuk laso yang terdiri dari loop yang cukup besar, spoke, junction, dan depot berada di ujungnya. Tujuan karya ilmiah ini yaitu menentukan solusi laso dari traveling salesman problem with pick-up and delivery dengan metode heuristik dan mengimplementasikan model untuk masalah permintaan pengambilan dan pengiriman dalam botol isi ulang. Kata kunci: metode heuristik, solusi laso, pick-up and delivery, TSP, TSPPD.

ABSTRACT ATIKAH NURBAITI. Determining Lasso Solution of Traveling Salesman Problems with Pick-up and Delivery on Heuristic Method. Supervised by FARIDA HANUM and TONI BAKHTIAR. Goods and service distributions are essential in a company or institution. The optimization of goods distribution problems can be solved mathematically by using TSP formulation. This paper discusses one of TSP variations. It is a TSPPD with pick-up and delivery demand considering as the most important problem. Pure TSP has property that a vehicle can not visit each post more than once. Meanwhile the TSPPD can visit each post more than once, therefore all constraints can be fulfilled. The TSPPD solution forms a lasso consisting a loop which is large enough, spoke, junction, and depot at the end. This solution is named as lasso solution. The aim of this work is to determine lasso solution from traveling salesman problem with pick-up and delivery on heuristic method and then to implement the model for the problem of shipping and picking up refilling bottles. Key word: heuristic method, lasso solution, pick-up and delivery, TSP, TSPPD.

PENENTUAN SOLUSI LASO DARI TRAVELING SALESMAN PROBLEM WITH PICK-UP AND DELIVERY DENGAN METODE HEURISTIK

ATIKAH NURBAITI

Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2015

PRAKATA Puji dan syukur penulis panjatkan kepada Allah subhanahu wa ta’ala atas segala karunia-Nya sehingga karya ilmiah ini berhasil diselesaikan. Tema yang dipilih dalam karya ilmiah ini adalah Riset Operasi dengan judul Penentuan Solusi Laso dari Traveling Salesman Problem with Pick-up and Delivery dengan Metode Heuristik. Penyusunan karya ilmiah ini juga tidak lepas dari bantuan berbagai pihak. Oleh karena itu, penulis mengucapkan terima kasih kepada: 1 Keluarga tercinta Abi Sunardi, Umi Sri Sumari, Bila, Yusuf, Ghina dan keluarga besar yang selalu memberikan doa, motivasi, dan kasih sayang. 2 Ibu Dra Farida Hanum, MSi dan Bapak Dr Toni Bakhtiar, MSc selaku pembimbing yang telah banyak memberikan ilmu, motivasi, dan saran. 3 Bapak Drs Prapto Tri Supriyo, MKom selaku dosen penguji yang telah memberikan ilmu, motivasi, dan saran. 4 Andini, Resty, Intan, Kiki, Riefdah, Sifa, Febi, Aini, Lidya, Hanna, Putri selaku sahabat yang menemani penulis selama masa kuliah dan memberikan motivasi serta doa. 5 Farah, Wardah, Zakiyya, Hera, Nida, Devis, Azmah, Fafa, Afiefah, Faza, Dewi, selaku sahabat yang telah mendengarkan curahan hati selama penulisan skripsi ini, dan memberikan motivasi serta doa. 6 Teman-teman seperjuangan Matematika angkatan 48, kakak-kakak Matematika angkatan 47, serta adik-adik Matematika angkatan 49 yang selalu memberikan keceriaan, motivasi dan doa. 7 Keluarga Birena Al-Hurriyyah IPB, keluarga OMDAKEMALA IPB, penghuni Asrama lorong 6 TPB IPB 2011/2012 yang selalu memberikan motivasi dan doa kepada penulis. Semoga karya ilmiah ini bermanfaat.

Bogor, Mei 2015 Atikah Nurbaiti

DAFTAR ISI DAFTAR TABEL

vi

DAFTAR GAMBAR

vi

DAFTAR LAMPIRAN

vi

PENDAHULUAN

1

Latar Belakang

1

Tujuan

1

TINJAUAN PUSTAKA

2

Traveling Salesman Problem

2

Traveling Salesman Problem with Pick-up and Delivery

2

Solusi Laso

4

Metode Heuristik

5

Metode Heuristik untuk TSPPD dengan Satu Kendaraan

6

Metode Heuristik untuk TSPPD dengan Beberapa Kendaraan

7

PEMBAHASAN Deskripsi Masalah

9 9

Kasus 1: TSPPD dengan Satu Kendaraan

10

Kasus 2: TSPPD dengan Beberapa Kendaraan Berkapasitas Sama

14

Kasus 3: TSPPD dengan Beberapa Kendaraan Berkapasitas Berbeda

18

SIMPULAN DAN SARAN

22

Simpulan

22

Saran

22

DAFTAR PUSTAKA

23

LAMPIRAN

24

RIWAYAT HIDUP

37

DAFTAR TABEL 1 2 3 4 5 6 7 8 9 10 11

Data jarak antar pelanggan Data permintaan pengambilan dan permintaan pengiriman barang Hasil metode heuristik untuk TSPPD dengan satu kendaraan Hasil metode heuristik solusi laso dari solusi TSP untuk TSPPD dengan satu kendaraan Nilai fi,v setiap pelanggan terhadap seed customer Hasil metode heuristik untuk TSPPD Kelompok 1 pada Kasus 2 Hasil metode heuristik untuk TSPPD Kelompok 2 pada Kasus 2 Hasil metode heuristik untuk TSPPD Kelompok 3 pada Kasus 2 Hasil metode heuristik untuk TSPPD Kelompok 1 pada Kasus 3 Hasil metode heuristik untuk TSPPD Kelompok 2 pada Kasus 3 Hasil metode heuristik untuk TSPPD Kelompok 3 pada Kasus 3

9 10 11 13 15 16 17 18 20 21 21

DAFTAR GAMBAR 1 2 3 4 5 6 7 8 9 10 11 12

Bentuk solusi laso Ilustrasi bentuk solusi laso Ilustrasi metode nearest neighbour heuristic Ilustrasi penentuan bobot fiv Rute solusi laso TSPPD dengan satu kendaraan Rute solusi TSP dengan satu kendaraan Rute solusi laso dari solusi TSP untuk TSPPD dengan satu kendaraan Seed customer setiap kelompok kendaraan Anggota pelanggan setiap kelompok kendaraan pada Kasus 2 Rute solusi laso TSPPD setiap kelompok kendaraan pada Kasus 2 Anggota pelanggan setiap kelompok kendaraan pada Kasus 3 Rute solusi laso TSPPD setiap kelompok kendaraan pada Kasus 3

4 5 5 8 11 12 14 14 15 18 19 22

DAFTAR LAMPIRAN 1 Tahapan metode heuristik menentukan solusi laso untuk TSPPD dengan satu kendaraan 2 Sintaks dan hasil komputasi program LINGO 11.0 dalam menyelesaikan TSP dengan satu kendaraan 3 Sintaks dan hasil komputasi program LINGO 11.0 dalam menyelesaikan pengelompokan pelanggan dari setiap kendaraan pada Kasus 2 4 Sintaks dan hasil komputasi program LINGO 11.0 dalam menyelesaikan pengelompokan pelanggan dari setiap kendaraan pada Kasus 3

24 27

31

34

PENDAHULUAN Latar Belakang Pendistribusian barang atau jasa merupakan salah satu bagian penting dalam sebuah perusahaan atau instansi. Masalah yang sering dihadapi terkait dengan distribusi antara lain menentukan rute perjalanan yang mampu meminimumkan jarak tempuh, waktu tempuh, atau biaya operasional.Masalah optimasi pendistribusian barang tersebut dapat diselesaikan secara matematis menggunakan formulasi Traveling Salesman Problem (TSP). TSP merupakan masalah optimasi kombinatorial dengan banyak aplikasi praktis. TSP secara umum sulit dipecahkan ketika permasalahan cukup besar. TSP dapat diselesaikan dengan metode klasik heuristik atau diformulasikan ke dalam pemrograman tertentu seperti Integer Programming, Dynamic Programming, dan sebagainya. Dalam perkembangannya, TSP mengalami berbagai variasi, yaitu Traveling Salesman Problem with Time Windows (TSPTW), m-Traveling Salesman Problem (m-TSP), Traveling Salesman Problem with Pick-Up and Delivery(TSPPD), Backhauls Traveling Salesman Problem (TSPB), dan Distance Constrained Traveling Salesman Problem (DCTSP) (Ahmadvand et al. 2012). Dalam karya ilmiah ini dibahas salah satu variasi TSP yaitu TSPPD dengan permintaan pengambilan (pick-up)dan permintaan pengiriman (delivery) sebagai bagian masalah terpenting dan penyelesaiannya menggunakan metode heuristik. Masalah permintaan pengambilan dan permintaan pengiriman pada kasus ini harus terpenuhi secara keseluruhan dalam suatu rute perjalanan. Jika TSP murni memiliki aturan bahwa kendaraan hanya dapat mengunjungi setiap tempat satu kali, maka dalam masalah TSPPD kendaraan dimungkinkan untuk mengunjungi beberapa tempat lebih dari satu kali agar semua kendala terpenuhi. Kunjungan pertama ke tempat pertama hanya melayani permintaan pengiriman saja. Selanjutnya beberapa tempat lain dikunjungi secara berurutan dalam suatu rute tertentu dan melakukan pelayanan permintaan pengambilan dan permintaan pengiriman. Setelah semua tempat dikunjungi, kendaraan kembali ke tempat pertama untuk melayani permintaan pengambilan lalu kembali ke depot. Uraian singkat tersebut merupakan cara untuk menentukan rute perjalanan dari masalah TSPPD yang terdiri dari loop yang cukup besar,spokedan depot berada di ujungnya sehingga membentuk laso. Penyelesaian TSPPD berbentuk laso selanjutnya akan menjadi pokok bahasan dalam karya ilmiah ini.

Tujuan Penulisan karya ilmiah ini bertujuan: 1 menentukan solusi laso dari traveling salesman problem with pick-up and delivery dengan metode heuristik, 2 mengimplementasikan model untuk masalah permintaan pengambilan dan pengiriman minuman dalam botol isi ulang.

TINJAUAN PUSTAKA Traveling Salesman Problem Traveling Salesman Problem (TSP)adalah suatu permasalahan ketika seorang salesman akan mengunjungi seluruh tempat yang ada untuk memulai suatu tur diawali dari tempat pertama dan mengunjungi setiap tempat lain tepat satu kali, kemudian kembali ke tempat pertama sehingga total jarak perjalanan menjadi minimum (Nemhauser dan Wolsey 1999). Masalah rute perjalanan seorang salesman dalam pendistribusian barang dengan model TSP menggunakan formulasi sebagai berikut: Misalkan: n : banyaknya tempat yang akan dikunjungi, cij : jarak tempat i ke tempat j, 𝑢𝑖 : variabel tambahan saat mengunjungi tempat i. Variabel keputusan: 1, jika ada perjalanan dari tempat 𝑖 ke tempat 𝑗 𝑥𝑖𝑗 = 0, selainnya. Fungsi objektif: Fungsi objektif TSP ialah meminimumkan total jarak tempuh kendaraan 𝑛

𝑛

min 𝑍 =

𝑐𝑖𝑗 𝑥𝑖𝑗 . 𝑖=1 𝑗 =1

Kendala-kendala: 1 Setiap tempatharus dikunjungi tepat satu kali 𝑛

𝑥𝑖𝑗 = 1,

∀𝑗 = 1, 2, … , 𝑛.

𝑥𝑖𝑗 = 1,

∀𝑖 = 1, 2, … , 𝑛.

𝑖=1 𝑛

𝑗 =1

2 Tidak ada subtur yang terbentuk pada rute perjalanan, sehingga hanya ada satu tur rute perjalanan berupa cycle 𝑢𝑖 − 𝑢𝑗 + 𝑛𝑥𝑖𝑗 ≤ 𝑛 − 1, 𝑖 ≠ 𝑗, ∀𝑖 = 2, 3, … , 𝑛; ∀𝑗 = 2, 3, … , 𝑛 𝑢𝑗 ≥ 0. (Winston 2004).

Traveling Salesman Problem with Pick-up and Delivery Traveling Salesman Problem with Pick-up and Delivery (TSPPD) adalah bentuk variasi dari TSP dengan permintaan pengambilan (pick-up)dan permintaan pengiriman (delivery).Misalkan dalam TSPPD beberapa kendaraan dengan

3 kapasitas angkut tertentu untuk melayani permintaan pengambilan dan permintaan pengiriman dalam suatu rute perjalanan pada pelanggan yang dimulai dari depot. Masalah TSPPD tersebut dapat diformulasikan sebagai berikut: Indeks: i,j : indeks untuk menyatakan depot dan pelanggan, i,j = 1 menyatakan depot dan i,j = 2, 3, ..., n menyatakan pelanggan, v : indeks untuk menyatakan kendaraan, v = 1, 2, ..., m, ik : indeks untuk menyatakan pelangganiyang dikunjungi ke-k, k = 1, 2, ..., n−1 dan ikϵ {2, 3, ..., n}. Parameter: cij : jarak dari pelanggan i ke pelanggan j, di : banyaknya permintaan pengiriman (delivery)pada pelanggan i, pi : banyaknya permintaan pengambilan (pick-up) pada pelanggan i, L(ik) : besarnya beban kendaraan setelah meninggalkan pelanggan i yang dikunjungi ke-k, CD(ik) : jumlah permintaan pengiriman (delivery)setelah meninggalkan pelanggani yang dikunjungi ke-k, CP(ik) : jumlah permintaan pengambilan (pick-up) setelah meninggalkan pelanggan i yang dikunjungi ke-k, Kv : kapasitas angkut kendaraanv. Variabel keputusan: 1, jika ada perjalanan dari pelanggan 𝑖 ke pelanggan 𝑗 𝑥𝑖𝑗 = 0, selainnya. Fungsi objektif: Fungsi objektif TSPPD ialah meminimumkan total jarak tempuh kendaraan 𝑛

𝑛

min 𝑍 =

𝑐𝑖𝑗 𝑥𝑖𝑗 ,

𝑖 ≠ 𝑗.

𝑖=1 𝑗 =1

Kendala-kendala: 1 Setiap pelanggan harus dikunjungi tepat satu kali 𝑛

𝑥𝑖𝑗 = 1,

∀𝑗 = 1, 2, … , 𝑛.

𝑥𝑖𝑗 = 1,

∀𝑖 = 1, 2, … , 𝑛.

𝑖=1 𝑛

𝑗 =1

2 Beban kendaraan pada pelanggani yang dikunjungi ke-kadalah fungsi dari pengiriman kumulatif, pengambilan kumulatif, dan jumlah beban awal 𝐿 𝑖𝑘 = 𝐿 1 − 𝐶𝐷 𝑖𝑘 + 𝐶𝑃(𝑖𝑘 ) 𝑖𝑘

dengan

𝐶𝑃 𝑖𝑘 =

𝑖𝑘

𝑝𝑛 dan𝐶𝐷 𝑖𝑘 = 𝑛 =1

𝑑𝑛 . 𝑛 =1

4 3 Beban kendaraan setelah meninggalkan pelanggan ke-ktidak boleh melebihi kapasitas angkut kendaraan ke-v 𝐿 𝑖𝑘 ≤ 𝐾𝑣 . 4 Variabel keputusan merupakan kendala biner 𝑥𝑖𝑗 ∈ 0,1 , ∀𝑖, 𝑗 = 1, 2, … , 𝑛; 𝑖 ≠ 𝑗. (Gribkovskaia et al. 2001).

Solusi Laso Solusi laso terbentuk saat kapasitas angkut kendaraan tidak mampu melayani permintaan pengambilan dan permintaan pengiriman secara bersamaan. Hal tersebut terjadi jika beberapa pelanggan mempunyai permintaan pengambilan lebih besar daripada permintaan pengiriman. Rute perjalanan kendaraan dari solusi laso dimulai dari tempat pertama yang hanya melayani permintaan pengiriman saja agar kapasitas angkut kendaraan tidak berlebih. Selanjutnya beberapa tempat lain dikunjungi secara berurutan dalam suatu rute tertentu dan melakukan pelayanan permintaan. Setelah semua tempat dikunjungi, kendaraan kembali ke tempat pertama untuk melayani permintaan pengambilan lalu kembali ke depot (Gribkovskaia et al. 2001). Solusi laso merupakan salah satu bentuk penentuan solusi dari traveling salesman problem with pick-up and delivery. Solusi laso terdiri dari loop yang cukup besar dan dihubungkan dengan junction (permulaan loop)pada spokedan depot berada di ujungnya. Spoke merupakan simpul-simpul yang berada diantaradepot danloop yang dikunjungi lebih dari satu kali. Spoke dapat terdiri atas satu simpul atau lebih. Bentuk solusi laso ditunjukkan seperti pada Gambar 1.

depot

spoke

junction

loop

Gambar 1 Bentuk solusi laso Misalkan terdapat 6 simpuldan 1 kendaraan dengan kapasitas angkut sebesar 150 unit. Diberikan di yaitu banyaknya permintaan pengiriman (delivery)pada pelanggan i, pi yaitu banyaknya permintaan pengambilan (pick-up) pada pelanggan i, dan L(ik) besarnya beban kendaraan setelah meninggalkan pelanggan i yang dikunjungi ke-k. Ilustrasi sederhana tersebut akan ditunjukkan pada Gambar 2.

5 L(3)= 130 d2=10 L(2)= 140 d3=10

L(1) =150

depot

p2=20

p3=30

2

3

p2=20

P3=30

d4=30 p4=20

L(4)= 120

4 5

d5=25 p5=15

6 L(2)= 145

L(3)= 125 L(6)= 95

d6=35 p6=20

L(5)= 110

Gambar 2 Ilustrasi bentuk solusi laso Metode Heuristik Kata heuristik berasal dari bahasa Yunani ‘eureka” yang artinya menemukan. Dalam masalah optimasi, metode heuristik merupakan teknik penyelesaian yang dapat mengarahkan pemecahan masalah untuk menemukan penyelesaian yang efisien tetapi tidak menjamin tercapainya solusi yang optimal. Metode heuristik yang tepat dapat mengurangi waktu komputasi yang diperlukan dalam penyelesaian masalah dengan menghapuskan beberapa pertimbangan kemungkinan atau kendala yang tidak relevan (Idaman 2013). Metode nearest neighbour heuristic (NNH) adalah suatu metode heuristik penentuan rute dengan memilih suatu simpul awal kemudian memilih simpul selanjutnya dengan simpul yang belum dipilih dan terdekat dari simpul sebelumnya (Winston 2004). Ilustrasi sederhana dari metode NNH ditunjukkan pada Gambar 3.

Rute pada tahap 1

Rute pada tahap 2

Rute yang diperoleh

Gambar 3 Ilustrasi metode nearest neighbour heuristic

6 Metode Heuristik untuk TSPPD dengan Satu Kendaraan Semua prosedur metode heuristik untuk TSP murni menghasilkan solusi rute delivery/pick-up dalam bentuk cycle Hamilton, yaitu rute yang melewati semua simpul tepat satu kali dan kembali ke simpul awal. Tahapan metode heuristik dalam menentukan solusi laso dilakukan dengan dua pendekatan yang berbeda yaitu penenentuan solusi laso secara langsung dan penentuan solusi laso menggunakan solusi TSP yang telah terbentuk. Misalkan terdapat 1 depot dan n−1 simpul yang harus dikunjungi. Misalkan i0 = 1 sebagai depot danik menyatakan simpul yang dikunjungi ke-kdan ik+1 sebagai simpul yang dikunjungi ke-(k+1).L(ik)menyatakan besarnya beban setelah meninggalkan simpulyang dikunjungi ke-k,serta Kvmenyatakan kapasitas angkut kendaraan v.Berikut merupakan tahapan metode heuristik untuk menentukan solusi laso: Prosedur Penentuan Solusi Laso Langkah 1: Jalur (path)dibuat dengan metodenearest neighbour heuristic sehingga ikdan ik+1 memenuhi pertaksamaan 𝐿 𝑖𝑘 ≤ 𝐾𝑣 , 𝐿 𝑖𝑘+1 > 𝐾𝑣 , dan 𝐿 𝑖𝑗 ≤ 𝐾𝑣 ; ∀𝑗 < 𝑘. Jika tidak ditemukan ikdan ik+1, maka kembali ke depot dari simpul terakhir pada jalur dan berhenti. Jika ditemukan ikdan ik+1, maka simpul pertama i1pada jalur diganti menjadi spoke, pengambilan pesanan diabaikan dan beban kendaraansimpul tersebut dikurangi dengan permintaan pengambilan pesanan 𝑝𝑖1 . Tahapan dilanjutkan ke Langkah 2. Langkah 2: Nearest neighbour heuristicdigunakan kembali untuk menambah jalur sampai ditemukan kembali pasangan ikdan ik+1 yang memenuhi pertaksamaan 𝐿 𝑖𝑘 ≤ 𝐾𝑣 , 𝐿 𝑖𝑘+1 > 𝐾𝑣 , dan 𝐿 𝑖𝑗 ≤ 𝐾𝑣 ; ∀𝑗 < 𝑘. Simpul pertama pada jalur digantimenjadi spoke danpengambilan pesanan diabaikan. Beban kendaraan pada jalur dikurangi dengan permintaan pengambilan pesanan dari spoke yang baru. Langkah 3: Langkah 2 diulangi sampai jalurmemuat semua simpul. Simpul terakhir pada jalur dihubungkan dengan spoke terakhir yang terbentuk. Spoke tersebut diganti menjadi junction sehingga terbentuk solusi laso(Gribkovskaia et al. 2001). Langkah 1 sampai Langkah 3 dilakukan saat permasalahan TSPPD belum diberikan rute awal. Jika rute awal optimal dari TSP dengan mengabaikan permintaan pengambilan, permintaan pengiriman, dan kapasitas kendaraan telah diberikan, maka prosedur penentuan solusi laso dapat diadaptasi untuk menyelesaikan permasalahan TSPPD. Dalam menentukan solusi laso dengan kondisi tersebut, kendaraanmelayani permintaan pengiriman pesanan ke pelanggan dalam urutan yang sama seperti pada rute awal. Namun, pelayanan permintaan pengambilan pesanan tidak akan dilakukan secara bersamaan untuk semua pelanggan. Kendaraan akan mengunjungi pelanggan ini kedua kalinya dan melayani permintaan pengambilan dalam urutan terbalik setelah semua permintaan pengiriman dilakukan.

7 Prosedur PenentuanSolusi Laso dari Solusi TSP: Langkah 1:Cycle Hamilton ditentukan menggunakan algoritme penyelesaian TSP dengan mengabaikan permintaan pelanggan untuk menghasilkan rute perjalanan yang memuat semua simpul. Rute yang diperoleh diperiksa kefisibelannya dengan memperhatikan semua kendala pada TSPPD. Suatu rute dikatakan fisibel apabila rute tersebut memenuhi semua kendala pada TSPPD. Jika rute sudahfisibel, maka proses berhenti. Jika tidak, maka dilanjutkan ke Langkah 2. Langkah 2: Mulai dari depot, semua pelayanan dilakukan sesuai dengan rute cycle Hamilton sampai beberapa simpul membuat beban kendaraan melebihi kapasitas kendaraan. Simpul pertamasetelah depotpada rute, yaitu simpul i1, diganti menjadi spoke dan permintaan pengambilan pesanan pada simpul tersebut diabaikan. Beban kendaraan pada simpul yang dikunjungidikurangi dengan permintaan pengambilan pesanan dari spoke. Tahapan dilanjutkan ke Langkah 3. Langkah 3: Pelayanan sepanjang rute dilanjutkan sampai beberapa simpul membuat beban kendaraan melebihi kapasitas kendaraan lagi. Simpul pertama setelah spokeyaitu simpul i2pada rute kembali diganti menjadi spoke dan permintaan pengambilan pesanan pada rute tersebut diabaikan. Beban kendaraan pada simpul yang dikunjungidikurangi dengan permintaan pengambilan pesanan dari spoke yang baru. Tahapan dilanjutkan ke Langkah 3. Langkah 4: Langkah 3 diulangi sampai semua simpul dikunjungi. Simpul terakhir yang dikunjungi dihubungkan dengan spoke terakhir yang terbentuk. Simpul ini diganti menjadi junction sehingga terbentuk laso. Pelayanan permintaan pengambilan dilakukan saat perjalanan dari junction ke depot (Gribkovskaia et al. 2001). Metode Heuristik untuk TSPPD dengan Beberapa Kendaraan Pada kasus lain, perlu adanya pertimbangan untuk menggunakan lebih dari satu kendaraan, seperti bentuk Vehicle Routing Problem (VRP). Diasumsikan bahwa semua kendaraan memiliki kapasitas tertentu. Pemanfaatan kapasitas kendaraan yang buruk untuk satu kelompok rute dapat menyebabkan kurangnya kapasitas untuk kelompok yang tersisa. Prosedur penyelesaian TSPPD dengan beberapa kendaraan adalah sebagai berikut: Langkah 1: Pengelompokan pelanggan ke dalam beberapa rute menggunakan Integer Programming dengan formulasi sebagai berikut: Indeks: i,j : indeks untuk menyatakan depot dan pelanggan, i,j = 1 menyatakan depot dan i,j = 2, 3, ..., n menyatakan pelanggan, v : indeks untuk menyatakan kendaraan, v = 1, 2, ..., m. Parameter: 𝑠𝑣 : seed customer, pelanggan yang ditempatkan terlebih dahulu pada setiap kendaraan ke-v yang akan dibentuk, 𝑑𝑖 : permintaan pengiriman (delivery) pada pelanggan i,

8 𝑝𝑖 cij Kv 𝑓𝑖𝑣

: permintaan pengambilan (pick-up) pada pelanggan i, : jarak dari pelanggan i ke pelanggan j, : kapasitas angkut kendaraan ke-v, : bobotselisih jarak yang harus ditempuh kendaraanv dari depot ke seed customer svdan kembali ke depot jika melalui pelanggan i, 𝑓𝑖𝑣 = min {𝑐1𝑖 + 𝑐𝑖𝑠𝑣 − 𝑐1𝑠𝑣 , 𝑐𝑠𝑣 𝑖 + 𝑐𝑖1 − 𝑐𝑠𝑣 1 } 𝑐1𝑖 + 𝑐𝑖𝑠𝑣 − 𝑐1𝑠𝑣 akan bernilai sama dengan 𝑐𝑠𝑣 𝑖 + 𝑐𝑖1 − 𝑐𝑠𝑣 1 jika matriks jarak antarpelanggan simetrik. Ilustrasi penentuan bobot 𝑓𝑖𝑣 disajikan pada Gambar 4. 𝑐1𝑠𝑣 depot sv 𝑐1𝑖 i

i ≠ 1(depot) i ≠sv

𝑐𝑖𝑠𝑣

Gambar 4 Ilustrasi penentuan bobot 𝑓𝑖𝑣 Variabel keputusan: 1, jika kendaraan 𝑣 mengunjungi pelanggan 𝑖 𝑊𝑖𝑣 = 0, selainnya. Fungsi objektif: Fungsi objektif pengelompokan ialah meminimumkan total bobot jarak tempuh kendaraan 𝑛

𝑚

min 𝑍 =

𝑓𝑖𝑣 𝑊𝑖𝑣 . 𝑖=2 𝑣=1

Kendala-kendala: 1 Total barang angkutan yang dikirim tidak melebihi kapasitas kendaraan 𝑛

𝑑𝑖 𝑊𝑖𝑣 ≤ 𝐾𝑣 ; ∀𝑣 . 𝑖=2

2 Total barang angkutan yang diambil tidak melebihi kapasitas kendaraan 𝑛

𝑝𝑖 𝑊𝑖𝑣 ≤ 𝐾𝑣 ; ∀𝑣 . 𝑖=2

3 Setiap pelanggan dikunjungi oleh tepat satu kendaraan 𝑚

𝑊𝑖𝑣 = 1

; ∀𝑖; 𝑖 ≠ 1.

𝑣=1

Langkah 2: Penentuan solusi laso menggunakan prosedur penyelesaian metode heuristik. Metode yang digunakan seperti pada TSPPD untuk satu kendaraan dan diterapkan pada setiap kelompok yang terbentuk (Gribkovskaia et al. 2001).

PEMBAHASAN Deskripsi Masalah Salah satu masalah yang dapat diselesaikan dengan Traveling Salesman Problem (TSP) adalah permasalahan pendistribusian produk dengan menentukan rute yang optimal sehingga jarak yang ditempuh kendaraan merupakan jarak minimum. Dalam karya ilmiah ini, akan dibahas TSP dengan kasus tambahan yaitu pengambilan produk dari setiap pelanggan yang dimodelkan dalam Traveling Salesman Problem with Pick-up and Delivery (TSPPD). Misalkan sebuah perusahaan mempunyai produk minuman kemasan botol isi ulang yang dapat digunakan kembali. Perusahaan tersebut tentunya akan mengambil kembali produk kemasan dari pelanggan agar dapat diisi ulang dan mendistribusikan kembali produk yang telah diisi ulang ke pelanggan. Misalkan perusahaan mempunyai beberapa kendaraan, sejumlah pelanggan, dan satu depot. Perusahaan tersebut mempunyai aturan-aturan dalam mendistribusikan produk yang dibuat. Aturan-aturan tersebut antara lain: 1 rute perjalanan dalam pengambilan dan pengiriman selalu diawali dan diakhiri di depot, 2 jarak antarpelanggan adalah simetrik, artinya jarak dari pelanggan i ke pelanggan j sama dengan jarak dari pelanggan j ke pelanggan i, 3 setiap pelanggan dalam suatu kelompok hanya boleh dikunjungi tepat satu kendaraan; setelah pelanggan dikunjungi, kendaraan harus meninggalkan pelanggan tersebut, 4 kendaraan yang digunakan memiliki kapasitas angkut yang terbatas, 5 total barang yang telah diambil dari pelanggan dan total barang yang akan dikirim ke pelanggan tidak boleh melebihi kapasitas kendaraan, 6 ada pelanggan dengan permintaan jumlah barang yang diambil lebih besar daripada jumlah barang yang diantar. Dalam karya ilmiah ini, data yang digunakan berasal dari beberapa sumber dan data hipotetik. Data yang digunakan yaitu data jarak antar pelanggan, data banyaknya pengambilan (pick-up)dan pengiriman (delivery) barang ke setiap pelanggan, dan data kapasitas kendaraan yang digunakan. Jarak antar pelanggan diperoleh dari (Gribkovskaiaet al. 2001). Data jarak antar pelanggan diberikan untuk 13 pelanggan dan 1 depot dan data disajikan pada Tabel 1. Tabel 1 Data jarak antarpelanggan (dalam km) Pelanggan 1 2 3 4 5 6 7

1 2

3

4

5

6

7

8

9

10

11

12

13

14

0 55

75

115

170

148

145

159

98

101

95

50

58

20

0

43 0

115 80 0

165 125 56 0

155 120 41 41 0

170 142 72 85 45 0

198 181 124 145 105 60

142 135 102 145 105 75

138 123 80 120 80 53

115 91 40 88 55 53

75 64 66 121 96 98

105 106 100 151 120 103

75 95 124 178 153 145

10 Tabel 1 Data jarak antarpelanggan (dalam km) Pelanggan 8 9 10 11 12 13 14

1

2

3

4

5

6

7

8

9 0

10

11

12

13

14

60 25 0

91 60 40 0

123 72 65 45 0

104 40 50 64 46 0

150 88 95 98 58 47 0

63 0

Setiap pelanggan memiliki jumlah permintaan pengambilan dan permintaan pengiriman barang yang berbeda-beda. Banyaknya permintaan pengambilan dan permintaan pengiriman barang ke setiap pelanggan diperoleh dari (Gribkovskaiaet al. 2001) dan disajikan pada Tabel 2. Tabel 2 Data permintaan pengambilan dan permintaan pengiriman barang (unit) Pelanggan Pengiriman Pengambilan

1

2

3

4

5

6

7

8

9

10

11

12

13

14

Total

0 0

20 30

25 30

15 15

40 30

20 15

10 15

30 20

30 35

25 10

20 15

15 15

20 30

20 35

290 295

Kasus 1: TSPPD dengan Satu Kendaraan Penentuan Solusi Laso Kasus pertama dalam masalah ini adalah menggunakan satu kendaraan saja dengan kapasitas angkut kendaraan sebesar 300 unit. Penyelesaian pada kasus pertama ini adalah menentukan rute solusi laso dari TSPPD tersebut dengan metode nearest neighbour heuristic untuk menentukan jalur terpendek. Misalkan kendaraan berangkat dari depot membawa 290 unit barang yaitu total permintaan pengiriman barang untuk semua pelanggan. Langkah 1: Metode nearest neighbour heuristic akan menghasilkan jalur terpendek pertama yaitu 1 – 14. Pada pelanggan 14 ini, salesman akan mengirim 20 unit barang dan mengambil 35 unit barang, sehingga beban kendaraan yang harus diangkut pada pelanggan 14 mencapai 305 unit dan melebihi kapasitas angkut kendaraan. Oleh karena itu, pelanggan 14 diganti dari simpul menjadi spoke dan mengurangi kelebihan beban sejumlah 35 unit yaitu permintaan pengambilan pada pelanggan 14. Langkah 2: Dari pelanggan 14 diteruskan sesuai hasil urutan rute yaitu 13– 9–10–11–4–6–5–7–8–12–3 sampai pada simpul terakhir yaitu pelanggan 2 dengan melakukan permintaan pengambilan dan permintaan pengiriman barang pada setiap pelanggan. Langkah 3: Dari pelanggan 2 kembali ke pelanggan 14 untuk melakukan pengambilan barang sehingga pelanggan 14 diganti dari spoke menjadi junction. Tahapan dan perhitungan lengkap metode heuristik TSPPD untuk satu kendaraan ini disajikan pada Lampiran 1.

11 Hasil metode heuristik untuk TSPPD dengan satu kendaraan memperoleh bentuk rute solusi laso yaitu 1–14–13–9–10–11–4–6–5–7–8–12–3–2–14-1 dengan total jarak 764 dan disajikan pada Gambar 5. `

10

9

11

13

4

depot

14

1

6

Z = 764

2

5 3

7 12

8

Gambar 5 Rute solusi laso TSPPD dengan satu kendaraan Hasil metode heuristik penentuan solusi laso untuk TSPPD satu kendaraan tersebut disajikan pada Tabel 3. Tabel 3 Hasil metode heuristik untuk TSPPD dengan satu kendaraan Pelanggan 1

Pengiriman -

Pengambilan -

L(i) 290

14

20

35

overload

13 9 10 11 4 6 5 7 8 12 3 2

20 20 30 25 20 15 20 40 10 30 15 25 20

30 35 10 15 15 15 30 15 20 15 30 30

270 280 285 270 265 265 260 250 255 245 245 250 260

20 47 40 25 40 40 41 41 85 60 123 64 43

14

-

35

295

75

1

-

295

20 764

Total jarak

Jarak 0

Keterangan Pelanggan 14 diganti menjadi spoke

Pelanggan 14 diganti menjadi junction

12 Penentuan Solusi Laso dari Solusi TSP Selanjutnya akan dilakukan penentuansolusi laso dari solusi TSP yang telah depot terbentuk menggunakan metode heuristik. Langkah 1: Solusi optimal dari TSP merupakancycle Hamilton optimal dengan total jarak 641. Solusi ini diperoleh dengan bantuan peranti lunak LINGO 11.0 . Sintaks program dan hasil komputasi disajikan pada Lampiran 2. Solusi yang diperoleh dari LINGO 11.0 memberikan rute 1 – 2 – 3 – 12 – 11 – 4 – 5 – 6 – 7 – 8 – 10 – 9 – 13 – 14 – 1 dengan nilai fungsi objektif 641 dan disajikan pada Gambar 6. 14

1

2

13

3

9

12 Z = 641

10

11 8

4 7

6

5

Gambar 6 Rute solusi TSP dengan satu kendaraan Solusi cylce TSP tersebut tidak fisibel untuk TSPPD karena beban kendaraan yang harus diangkut setelah meinggalkan pelanggan 3 sebesar 305 unit melebihi kapasitas kendaraan 300 unit, sehingga perlu dilanjutkan ke tahap berikutnya sesuai prosedur perbaikan solusi laso. Langkah 2: Dimulai dari depot, kendaraan membawa 290 unit barang menuju pelanggan 2 untuk melakukan permintaan pengambilan dan permintaan pengiriman. Pada pelanggan 2 ini, salesman akan mengirim 20 unit barang dan mengambil 30 unit barang, sehingga beban kendaraan yang harus diangkut pada pelanggan 2 mencapai 300 unit dan masih mencukupi kapasitas angkut kendaraan. Perjalanan dilanjutkan menuju pelanggan 3 untuk melakukan permintaan pengambilan dan permintaan pengiriman. Pada pelanggan 3 ini, salesman akan mengirim 25 unit barang dan mengambil 30 unit barang, sehingga beban kendaraan yang harus diangkut pada pelanggan 3 mencapai 305 unit dan melebihi kapasitas angkut kendaraan. Oleh karena itu, perlu peninjauan kembali sistem pengangkutan pada pelanggan 2 yaitu pelanggan 2 diganti dari simpul menjadi spoke dan mengurangi kelebihan beban sejumlah 30 unit yaitu permintaan pengambilan pada pelanggan 2. Peninjauan kembali pada pelanggan 2 dilakukan untuk mengefisienkan rute solusi laso yang terbentuk. Jika pelanggan 3 yang diganti menjadi spoke, maka setelah kendaraan mengunjungi semua pelanggan dan kembali ke pelanggan

13 3untuk melakukan permintaan pengambilan, kendaraan akan kembali lagi melewati pelanggan 2 tanpa melakukan pelayanan apapun. Langkah 3: Selanjutnya diteruskan dari pelanggan 2 sesuai hasil urutan rute yaitu 3 – 12 – 11 – 4 – 5 – 6 – 7 – 8 – 10 – 9 – 13 sampai pada simpul terakhir yaitu pelanggan 14 dengan melakukan permintaan pengambilan dan permintaan pengiriman barang pada setiap pelanggan. Langkah 4: Selanjutnya dari pelanggan 14 kembali ke pelanggan 2 untuk melakukan pengambilan barang sehingga pelanggan 2 diganti dari spoke menjadi junction. Penerapan metode heuristik perbaikan solusi laso untuk TSPPD dengan satu kendaraan ini memperoleh rute 1 – 2 – 3 – 12 – 11 – 4 – 5 – 6 – 7 – 8 – 10 – 9 – 13 – 14 – 2 – 1 dengan total jarak 751. Nilai objektif total jarak ini lebih kecil jika dibandingkan dengan solusi laso yang diperoleh sebelumnya yaitu 764. Hasil metode heuristik penentuan solusi laso dari solusi TSP untuk TSPPD dengan satu kendaraan disajikan pada Tabel 4. Tabel 4 Hasil metode heuristik solusi laso dari solusi TSP untuk TSPPD dengan satu kendaraan Pelanggan 1 2 3

Pengiriman 20 25

1

-

Pengambilan L(i) 290 30 300 30 overload Peninjauan kembali 290

Jarak 0 55

0

2

20

-

270

55

3 12 11 4 5 6 7 8 10 9 13 14

25 15 20 15 40 20 10 30 25 30 20 20

30 15 15 15 30 15 15 20 10 35 30 35

275 275 270 270 260 255 260 250 235 240 250 265

43 64 45 40 56 41 45 60 60 25 40 47

2

-

30

295

75

1

-

295

55 751

Total jarak

Keterangan

Pelanggan 2 diganti menjadi spoke

Pelanggan 2 diganti menjadi junction

14 Dengan hasil metode heuristik penentuan solusi laso dari solusi TSP untuk TSPPD satu kendaraan tersebut, maka diperoleh bentuk solusi laso seperti pada Gambar 7. 11

12

4

3

depot

5

2

1

6

Z = 751

14

7 13

8 9

10

Gambar 7 Rute solusi laso dari solusi TSP untuk TSPPD dengan satu kendaraan Kasus 2: TSPPD dengan Beberapa Kendaraan Berkapasitas Sama Kasus kedua dalam masalah ini adalah menggunakan beberapa kendaraan. Misalkan terdapat tiga kendaraan dengan kapasitas angkut setiap kendaraan sama yaitu sebesar 100 unit. Langkah 1: Pengelompokan rute pendistribusian untuk setiap kendaraan dilakukan dengan menerapkan metodepengelompokan Integer Programming menggunakan peranti lunak LINGO 11.0. Pada langkah awal ini perlu ditentukan tiga seed customer terlebih dahulu, dengan setiap seed customer yang dipilih mewakili satu kelompok rute pendistribusian. Pada umumnya, seed customer dapat dipilih secara acak seperti pada masalah knapsack problem. Namun dalam kasus ini,seed-customer dipilih pada pelanggan yang memiliki jumlah permintaan pengambilan lebih besar dibandingkan permintaan pengirimanagar di setiap kendaraan terbentuk rute solusi laso. Pelanggan yang akan dijadikan seedcustomer yaitu pelanggan 2, pelanggan 13, dan pelanggan 14.

2

13

14

Kelompok 1

Kelompok 2

Kelompok 3

d2= 20, p2= 30 d13 = 20, p13 = 30

d14= 20, p14= 35

Gambar 8Seed customer setiap kelompok kendaraan

15 Tahap selanjutnya yaitu mencari nilai bobot jarak tempuh kendaraan 𝑓𝑖,𝑣 untuk semua pelanggan terhadap setiap seed customer. Nilai 𝑓𝑖 ,𝑣 dicari berdasarkan rumus min 𝑐1,𝑖 + 𝑐𝑖,𝑠𝑣 − 𝑐1,𝑠𝑣 , 𝑐𝑆𝑣 ,𝑖 + 𝑐𝑖,1 − 𝑐𝑠𝑣 ,1 ; 𝑖 ≠ 𝑠𝑣 dan akan disajikan pada Tabel 5. Tabel 5 Nilai 𝑓𝑖,𝑣 setiap pelanggan terhadap seed customer Pelanggan 2

1 2 3 4 5 6 7 8 9 10 11 12 13 14

Pelanggan 13

Pelanggan 14

𝑐1,𝑖

𝑐𝑖,2

𝑐1,2

𝑓𝑖,2

𝑐1,𝑖

𝑐𝑖,13

𝑐1,13

𝑓𝑖,13

𝑐1,𝑖

𝑐𝑖,14

𝑐1,14

𝑓𝑖,14

0 55 75 115 170 148 145 159 98 101 95 50 0 0

55 0 43 115 165 155 170 198 142 138 115 75 0 0

55 55 55 55 55 55 55 55 55 55 55 55 0 0

0 0 63 175 280 248 260 302 185 184 155 70 0 0

0 0 75 115 170 148 145 159 98 101 95 50 58 0

58 0 106 100 151 120 103 104 40 50 64 46 0 0

58 0 58 58 58 58 58 58 58 58 58 58 58 0

0 0 123 157 263 210 190 205 80 93 101 38 0 0

0 0 75 115 170 148 145 159 98 101 95 50 0 20

20 0 95 124 178 153 145 150 88 95 98 58 0 0

20 0 20 20 20 20 20 20 20 20 20 20 0 20

0 0 150 219 328 281 270 289 166 176 173 88 0 0

Selanjutnya denganInteger Programmingpada halaman 7 dan dengan program LINGO 11.0 ditentukan anggota kelompok pelanggan dari setiap kendaraan. Sintaks program dan hasil komputasi disajikan pada Lampiran 3. Hasil dari iterasi program LINGO 11.0 adalah sebagai berikut Kelompok 1 terdiri dari pelanggan 2, 3, 4, 10, dan 12; Kelompok 2 terdiri dari pelanggan 6, 7, 8, 11, dan 13; serta Kelompok 3 terdiri dari pelanggan 5, 9, dan 14 seperti pada Gambar 9. 2

12

3 4

10

Kelompok 1

13

6

7 11

5

14

8

Kelompok 2

9

Kelompok 3

Gambar 9 Anggota pelanggan setiap kelompok kendaraan pada Kasus 2 Langkah 2: Penentuan penyelesaian solusi laso menggunakan prosedur metode heuristik TSPPD untuk satu kendaraan pada setiap kelompok yang terbentuk.

16 Penentuan Solusi Laso Kelompok 1 pada Kasus 2 Langkah 1: Dimulai dari depot, kendaraan membawa 100 unit barang. Dengan metode nearest neighbour heuristicakan dihasilkan jalur terpendek pertama yaitu 1 – 2. Pada pelanggan 2 ini, salesman akan mengirim 20 unit barang dan mengambil 30 unit barang, sehingga beban kendaraan yang harus diangkut pada pelanggan 2 mencapai 110 unit dan melebihi kapasitas angkut kendaraan. Oleh karena itu, pelanggan 2 diganti dari simpul menjadi spoke dan mengurangi kelebihan beban sejumlah 30 unit yaitu permintaan pengambilan pada pelanggan 2. Langkah 2: Dari pelanggan 2 diteruskan sesuai hasil urutan rute yaitu 3 – 12 –10 sampai pada simpul terakhir yaitu pelanggan 4 dengan melakukan permintaan pengambilan dan permintaan pengiriman barang pada setiap pelanggan. Langkah 3: Dari pelanggan 4 kembali ke pelanggan 2 untuk melakukan pengambilan barang sehingga pelanggan 2 diganti dari spoke menjadi junction. Metode heuristik TSPPD dengan satu kendaraan pada Kelompok 1 ini memperoleh rute 1 – 2 – 3 – 12 – 10 – 4 – 2 – 1 dengan jarak 477 dan disajikan pada Tabel 6. Tabel 6 Hasil metode heuristik untuk TSPPD Kelompok 1 pada Kasus 2 Pelanggan 1

Pengiriman -

Pengambilan -

L(i) 100

2

20

30

overload

20

-

80

55

3 12 10 4

25 15 25 15

30 15 10 15

85 85 70 70

43 64 65 80

2

-

30

100

115

1

-

-

100

55

Total jarak

Jarak 0

Keterangan

Pelanggan 2 diganti menjadi spoke

Pelanggan 2 diganti menjadi junction

477

Penentuan Solusi Laso Kelompok 2 pada Kasus 2 Langkah 1: Dimulai dari depot, kendaraan membawa 100 unit barang. Dengan metode nearest neighbour heuristic akan dihasilkan jalur terpendek pertama yaitu 1 – 13. Pada pelanggan 13 ini, salesman akan mengirim 20 unit barang dan mengambil 30 unit barang, sehingga beban kendaraan yang harus diangkut pada pelanggan 13 mencapai 110 unit dan melebihi kapasitas angkut kendaraan. Oleh karena itu, pelanggan 13 diganti dari simpul menjadi spoke dan mengurangi kelebihan beban sejumlah 30 unit yaitu permintaan pengambilan pada pelanggan 13. Langkah 2: Dari pelanggan 13 diteruskan sesuai hasil urutan rute yaitu 11 – 7 – 6 sampai pada simpul terakhir yaitu pelanggan 8 dengan melakukan

17 permintaan pengambilan dan permintaan pengiriman barang pada setiap pelanggan. Langkah 3: Dari pelanggan 8 kembali ke pelanggan 13 untuk melakukan pengambilan barang sehingga pelanggan 13 diganti dari spoke menjadi junction. Metode heuristik TSPPD dengan satu kendaraan pada Kelompok 2 ini memperoleh rute 1 – 13 – 11 – 7 – 6 – 8 – 13 – 1 dengan jarak 487 dan disajikan pada Tabel 7. Tabel 7 Hasil metode heuristik untuk TSPPD Kelompok 2 pada Kasus 2 Pelanggan

Pengiriman

Pengambilan

1

-

-

L(i)

100

13

20

30

overload

11 7 6 8

20 20 10 20 30

15 15 15 20

80 75 80 75 65

Jarak

Pelanggan 13 diganti menjadi spoke 58 64 53 45 105

13

-

30

95

104

1

-

-

95

58

Total jarak

Keterangan

Pelanggan 13 diganti menjadi junction

487

Penentuan Solusi Laso Kelompok 3 pada Kasus 2 Langkah 1: Dimulai dari depot, kendaraan membawa 90 unit barang. Dengan metode nearest neighbour heuristic akan dihasilkan jalur terpendek pertama yaitu 1 – 14. Pada pelanggan 14 ini, salesman akan mengirim 20 unit barang dan mengambil 35 unit barang, sehingga beban kendaraan yang harus diangkut pada pelanggan 14 mencapai 105 unit dan melebihi kapasitas angkut kendaraan. Oleh karena itu, pelanggan 14 diganti dari simpul menjadi spoke dan mengurangi kelebihan beban sejumlah 35 unit yaitu permintaan pengambilan pada pelanggan 14. Langkah 2: Dari pelanggan 14 diteruskan sesuai hasil urutan rute ke pelanggan 9 sampai pada simpul terakhir yaitu pelanggan 5 dengan melakukan permintaan pengambilan dan permintaan pengiriman barang pada setiap pelanggan. Langkah 3: Dari pelanggan 5 kembali ke pelanggan 14 untuk melakukan pengambilan barang sehingga pelanggan 14 akan diganti dari spoke menjadi junction. Metode heuristik TSPPD dengan satu kendaraan pada Kelompok 3 ini memperoleh rute 1 – 14 – 9 – 5 – 14 – 1 dengan jarak 451 dan disajikan pada Tabel 8.

18 Tabel 8 Hasil metode heuristik untuk TSPPD Kelompok 3 pada Kasus 2 Pelanggan

Pengiriman

Pengambilan

L(i)

Jarak

1

-

-

90

-

14

20

35

overload

9 5

20 30 40

35 30

70 75 65

Keterangan

Pelanggan 14 diganti menjadi spoke 20 88 145

14

-

35

100

178

1

-

-

100

20

Total jarak

Pelanggan 14 diganti menjadi junction

451

Rute yang dihasilkan pada setiap kelompok pendistribusian memenuhi penyelesaian solusi laso dan fisibel dengan total jarak 1415 untuk ketiga kendaraan seperti pada Gambar 10.

depot

Z= 451 Z= 477

Z= 487

Gambar 10 Rute solusi laso TSPPD setiap kendaraan pada Kasus 2 Kasus 3: TSPPD dengan Beberapa Kendaraan Berkapasitas Berbeda Pada kasus ketiga ini misalkan terdapat tiga kendaraan dengan kapasitas angkut setiap kendaraan berturut-turut sebesar 130 unit, 100 unit, dan 70 unit. Perbedaan kasus kapasitas angkut kendaraan yang berbeda dengan kapasitas angkut kendaraan yang sama terletak pada penentuan anggota kelompok pelanggan pada setiap kendaraan. Penentuan seed customer dan pencarian nilai 𝑓𝑖,𝑣 sama seperti pada Kasus 2. Langkah 1: Pengelompokan rute pendistribusian anggota kelompok pelanggan dari setiap kendaraan akan dilakukan dengan Integer

19 Programmingmenggunakan program LINGO 11.0 Sintaks program dan hasil komputasi disajikan pada Lampiran 4. Hasil dari LINGO 11.0 adalah sebagai berikut Kelompok 1 terdiri dari pelanggan 2, 3, 4, 6, 7, 10, dan 12; Kelompok 2 terdiri dari pelanggan 8, 9, 11, dan 13; serta Kelompok 3 terdiri dari pelanggan 5 dan 14 seperti pada Gambar 11. 2

12

3

4

10 6

7

Kelompok 1

13

9 11

8

Kelompok 2

5

14

Kelompok 3

Gambar 11 Anggota pelanggan setiap kelompok kendaraan pada Kasus 3 Langkah 2: Penentuan penyelesaian solusi laso menggunakan prosedur metode heuristik TSPPD untuk satu kendaraan pada setiap kelompok yang terbentuk. Penentuan Solusi Laso Kelompok 1 pada Kasus 3 Langkah 1: Dimulai dari depot, kendaraan membawa 130 unit barang. Dengan metode nearest neighbour heuristic akan dihasilkan jalur terpendek pertama yaitu 1 – 2. Pada pelanggan 2 ini, salesman akan mengirim 20 unit barang dan mengambil 30 unit barang, sehingga beban kendaraan yang harus diangkut pada pelanggan 2 mencapai 140 unit dan melebihi kapasitas angkut kendaraan. Oleh karena itu, pelanggan 2 diganti dari simpul menjadi spoke dan mengurangi kelebihan beban sejumlah 30 unit yaitu permintaan pengambilan pada pelanggan 2. Langkah 2: Dari pelanggan 2 diteruskan sesuai hasil urutan rute yaitu 3 – 12 –10 – 7 – 6 sampai pada simpul terakhir yaitu pelanggan 4 dengan melakukan permintaan pengambilan dan permintaan pengiriman barang pada setiap pelanggan. Langkah 3: Dari pelanggan 4 kembali ke pelanggan 2 untuk melakukan pengambilan barang sehingga pelanggan 2 diganti dari spoke menjadi junction. Metode heuristik TSPPD dengan satu kendaraan pada Kelompok 1 ini memperoleh rute 1 – 2 – 3 – 12 – 10 – 7 – 6 – 4 – 2 – 1 dengan jarak 536 dan disajikan pada Tabel 9.

20 Tabel 9 Hasil metode heuristik untuk TSPPD Kelompok 1 pada Kasus 3 Pelanggan 1

Pengiriman -

Pengambilan -

L(i) 130

2

20

30

Overload

3 12 10 7 6 4

20 25 15 25 10 20 15

30 15 10 15 15 15

110 115 115 100 105 100 100

2

-

1

-

30 Total jarak

130 130

Jarak 0

Keterangan Pelanggan 2 diganti menjadi spoke

55 43 64 65 53 45 41 Pelanggan 2 115 diganti menjadi junction 55 536

Penentuan Solusi Laso Kelompok 2 pada Kasus 3 Langkah 1: Dimulai dari depot, kendaraan membawa 100 unit barang. Dengan metode nearest neighbour heuristic akan dihasilkan jalur terpendek pertama yaitu 1 – 13. Pada pelanggan 13 ini, salesman akan mengirim 20 unit barang dan mengambil 30 unit barang, sehingga beban kendaraan yang harus diangkut pada pelanggan 13 mencapai 110 unit dan melebihi kapasitas angkut kendaraan. Oleh karena itu, pelanggan 13 diganti dari simpul menjadi spoke dan mengurangi kelebihan beban sejumlah 30 unit yaitu permintaan pengambilan pada pelanggan 13. Langkah 2: Dari pelanggan 13 diteruskan sesuai hasil urutan rute yaitu 9– 11 sampai pada simpul terakhir yaitu pelanggan 8 dengan melakukan permintaan pengambilan dan permintaan pengiriman barang pada setiap pelanggan. Langkah 3: Dari pelanggan 8 kembali ke pelanggan 13 untuk melakukan pengambilan barang sehingga pelanggan 13 diganti dari spoke menjadi junction. Metode heuristik TSPPD dengan satu kendaraan pada Kelompok 2 ini memperoleh rute 1 – 13 – 9 – 11 – 8 – 13 – 1 dengan jarak 411 dan disajikan pada Tabel 10.

21 Tabel 10 Hasil metode heuristik untuk TSPPD Kelompok 2 pada Kasus 3 Pelanggan 1

Pengiriman -

Pengambilan -

L(i) 100

13

20

30

Overload

9 11 8

20 30 20 30

35 15 20

80 85 80 70

58 40 60 91

13

-

30

100

104

1

-

100

58 411

Total jarak

Jarak -

Keterangan Pelanggan 13 diganti menjadi spoke

Pelanggan 13 diganti menjadi junction

Penentuan Solusi Laso Kelompok 3 pada Kasus 3 Langkah 1: Dimulai dari depot, kendaraan membawa 60 unit barang. Dengan metode nearest neighbour heuristic akan dihasilkan jalur terpendek pertama yaitu 1 – 14. Pada pelanggan 14 ini, salesman akan mengirim 20 unit barang dan mengambil 35 unit barang, sehingga beban kendaraan yang harus diangkut pada pelanggan 14 mencapai 75 unit dan melebihi kapasitas angkut kendaraan. Oleh karena itu, pelanggan 14 diganti dari simpul menjadi spoke dan mengurangi kelebihan beban sejumlah 35 unit yaitu permintaan pengambilan pada pelanggan 14. Langkah 2: Dari pelanggan 14 diteruskan sampai pada simpul terakhir yaitu pelanggan 5 dengan melakukan permintaan pengambilan dan permintaan pengiriman barang pada setiap pelanggan. Langkah 3: Dari pelanggan 5 kembali ke pelanggan 14 untuk melakukan pengambilan barang sehingga pelanggan 14 adiganti dari spoke menjadi junction. Metode heuristik TSPPD satu kendaraan pada Kelompok 3 ini memperoleh rute 1 – 14 – 5 – 14 – 1 dengan jarak 396 dan disajikan pada Tabel 11. Tabel 11 Hasil metode heuristik untuk TSPPD Kelompok 3 pada Kasus 3 Pelanggan 1

Pengiriman -

Pengambilan -

L(i) 60

14

20

35

Overload

5

20 40

30

40 30

Jarak -

Keterangan Pelanggan 14 diganti menjadi spoke

20 178

14

-

35

65

178

1

-

Total jarak

65

20 396

Pelanggan 14 diganti menjadi unction

22 Rute yang dihasilkan pada setiap kelompok pendistribusian memenuhi penyelesaian solusi laso dan fisibel dengan total jarak 1343 untuk ketiga kendaraan. Nilai objektif total jarak ini lebih kecil jika dibandingkan dengan total jarak untuk kapasitas kendaraan yang sama pada Kasus 2 yaitu 1415. Hasil metode heuristik untuk setiap rute kendaraan disajikan pada Gambar 12.

depot

Z= 411

Z = 396

Z= 536

Gambar 12 Rute solusi laso TSPPD setiap kelompok kendaraan pada Kasus 3

SIMPULAN DAN SARAN Simpulan Model traveling salesman problem with pick-up and delivery (TSPPD) dapat diselesaikan dengan metode heuristik solusi laso. Model ini bertujuan meminimumkan total jarak yang ditempuh salesman dari depot ke beberapa tempat pelanggan dan kembali ke depot mengikuti suatu rute yang berbentuk laso. Implementasi model pada suatu kasus pendistribusian sebuah perusahaan yang mempunyai produk minuman kemasan botol isi ulang yang dapat digunakan kembali dengan data dari (Gribkovskaia et al. 2001) dan data hipotetik. Solusi laso yang diperoleh dari solusi TSP menggunakan metode heuristik TSPPD dengan satu kendaraan menghasilkan total jarak yang lebih minimum yaitu 751 kilometer. Solusi laso yang diperoleh dari TSPPD dengan tiga kendaraan berkapasitas angkut berbeda-beda menghasilkan total jarak yang lebih minimum yaitu 1343 kilometer jika dibandingkan dengan total jarak untuk TSPPD dengan tiga kendaraan berkapasitas angkut kendaraan yang sama yaitu 1415 kilometer.

Saran Pada karya ilmiah ini, data yang digunakan merupakan data dari jurnal penelitian dan data hipotetik. Penelitian ini dapat dikembangkan dengan

23 memperhatikan total biaya yang harus dikeluarkan perusahaan selama distribusi dan waktu pelanggan dapat dilayani.

DAFTAR PUSTAKA Ahmadvand M, Yousefikhoshbakht M, Darani NM. 2012. Solving the traveling salesman problem by an efficient hybrid metaheuristic algorithm. Journal of Advances in Computer Research; 2012 Agustus; Sari, Iran. Sari (IR): Islamic Azad University. hlm 75-84. Gribkovskaia I, Halskau Ǿ, Myklebost KB. 2001. Models for pick-up and deliveries from depots with lasso solutions.Proceedings of the 13th Annual Conference on Logistics Research - NOFOMA 2001 Collaboration in logistics: Connecting Islands using Information Technology; 2001 Juni 14-15; Reykjavik, Islandia. Gӧteborg (SE): Chalmers University of Technology. hlm 279-293. Idaman S. 2013. Penyelesaian Vehicle Routing Problem with Simultaneous Pickup and Delivery Service Menggunakan Algoritme Tabu Search [skripsi]. Bogor (ID): Institut Pertanian Bogor. Nemhauser G, Wolsey L. 1999. Integer and Combinatorial Optimization. New York (US): A Wiley-Interscience. Winston WL. 2004. Operations Research: Applications and Algorithms 4thed. California (US): Duxbury.

24

LAMPIRAN Lampiran 1 Tahapan metode heuristik menentukan solusi laso untuk TSPPD dengan satu kendaraan Langkah 1 i0 = 1 L(1) = 290 ≤ Kv = 300 Metode nearest neighbour: 1 14 i1= 14 L(14) = 290 – 20 + 35 = 305 >Kv = 300 Akibatnya i1= 14 diganti menjadi spoke, abaikan p(14) L(14) = 290 – 20 + 0 = 270 ≤Kv = 300 Langkah 2 i1 = 14 Metode nearest neighbour: 1 14  13 i2 = 13 L(13) = 290 – 40 + 30 = 280 ≤Kv = 300 Langkah 3 Ulangi langkah 2 sampai jalur memuat semua simpul i2= 13 Metode nearest neighbour: 1 14  13  9 i3 = 9 L(9) = 290 – 70 + 65 = 285 ≤Kv = 300 i3 = 9 Metode nearest neighbour: 1 14  13  9  10 i4= 10 L(10) = 290 – 95 + 75 = 270 ≤Kv = 300 i4= 10 Metode nearest neighbour: 1 14  13  9  10  11 i5= 11 L(11) = 290 – 115 + 90 = 265 ≤Kv = 300 i5= 11 Metode nearest neighbour: 1 14  13  9  10  11  4 i6 = 4

25 L(4)

= 290 – 130 + 105 = 265 ≤Kv = 300

i6 = 4 Metode nearest neighbour: 1 14  13  9  10  11  4  6 i7 = 6 L(6) = 290 – 150 + 120 = 260 ≤Kv = 300 i7 = 6 Metode nearest neighbour: 1 14  13  9  10  11  4  6  5 i8 = 5 L(5) = 290 – 190 + 150 = 250 ≤Kv = 300 i8 = 5 Metode nearest neighbour: 1 14  13  9  10  11  4  6  5 7 i9 = 7 L(7) = 290 – 200 + 165 = 255 ≤Kv = 300 i9 = 7 Metode nearest neighbour: 1 14  13  9  10  11  4  6  5 7  8 i10= 8 L(8) = 290 – 230 + 185 = 245 ≤Kv = 300 i10= 8 Metode nearest neighbour: 1 14  13  9  10  11  4  6  5 7  8  12 i11= 12 L(12) = 290 – 245 + 200 = 245 ≤Kv = 300 i11= 12 Metode nearest neighbour: 1 14  13  9  10  11  4  6  5 7  8  12  3 i12= 3 L(3) = 290 – 270 + 230 = 250 ≤Kv = 300 i12= 3 Metode nearest neighbour: 1 14  13  9  10  11  4  6  5 7  8  12  3  2 i13= 2 L(2) = 290 – 290 + 260 = 260 ≤Kv = 300

26 Jalur telah memuat semua simpul, simpul terakhir yaitu simpul ke-2 dihubungkan dengan spoke terakhir yang terbentuk yaitu simpul ke-14 i13= 2 Metode nearest neighbour: 1 14  13  9  10  11  4  6  5 7  8  12  3  2  14 i1= 14 L(14) = 290 – 290 + 295 = 295 ≤Kv = 300 Akibatnya i1 = 14 diganti dari spoke menjadi junction i1= 14 Metode nearest neighbour: 1 14  13  9  10  11  4  6  5 7  8  12  3  2  14  1 i0 = 1 L(1) = 290 – 290 + 295 = 295 ≤Kv = 300 Terbentuk solusi laso untuk TSPPD dengan satu kendaraan dengan rute 1  14  13  9  10  11  4  6  5 7  8  12  3  2  14  1

27 Lampiran 2Sintaks dan hasil komputasi program LINGO 11.0 dalammenyelesaikan Traveling Salesman Problem (TSP) dengan satu kendaraan Model: ! Traveling Salesman Problem; Sets: CITY / 1.. 14/: U; ! U( i ) = urutan untuk setiap tempat; LINK( CITY, CITY ): DIST, ! matriks jarak; X; ! X( i,j ) = 1, jika ada perjalanan dari tempat i ke tempat j; Endsets Data: ! matriks jarak berbentuk simetrik; DIST = 0 55 75 115 170 148 145 159 98 101 95 50 58 20

55 0 43 115 165 155 170 198 142 138 115 75 105 75

75 43 0 80 125 120 142 181 135 123 91 64 106 95

115 115 80 0 56 41 72 124 102 80 40 66 100 124

170 165 125 56 0 41 85 145 145 120 88 121 151 178

148 155 120 41 41 0 45 105 105 80 55 96 120 153

145 170 142 72 85 45 0 60 75 53 53 98 103 145

159 198 181 124 145 105 60 0 63 60 91 123 104 150

98 142 135 102 145 105 75 63 0 25 60 72 40 88

101 138 123 80 120 80 53 60 25 0 40 65 50 95

95 115 91 40 88 55 53 91 60 40 0 45 64 98

50 75 64 66 121 96 98 123 72 65 45 0 46 58

; Enddata N = @size( CITY ); min = @sum( LINK: DIST * X ); @for( CITY( K ): ! kendaraan yang masuk ke suatu kota; @sum( CITY( I )| I #NE# K: X( I, K )) = 1; ! kendaraan yang keluar dari suatu kota; @sum( CITY( J )| J #NE# K: X( K, J )) = 1; ! tidak ada subtur yang takfisibel dan terbentuk tur yang fisibel; @for( CITY( J )| J #GT# 1 #AND# J #NE# K:

58 105 106 100 151 120 103 104 40 50 64 46 0 47

20 75 95 124 178 153 145 150 88 95 98 58 47 0

28 U( K ) - U( J ) + X ( K,J )*N <= ( N - 1 ) ); ); ! X variabel biner; @for( LINK: @bin( X )); end

Hasil yang diperoleh:

Global optimal solution found. Objective value: Objective bound: Infeasibilities: Extended solver steps: Total solver iterations: Variable N U( 2) U( 3) U( 4) U( 5) U( 6)

641.0000 641.0000 0.1776357E-14 0 1115

Value 14.00000 1.000000 2.000000 5.000000 7.000000 8.000000

U( 7) U( 8) U( 9) U( 10) U( 11) U( 12)

9.000000 10.00000 12.00000 11.00000 4.000000 3.000000

29 U( 13) U( 14) DIST( 1, 2) DIST( 1, 3) DIST( 1, 4) DIST( 1, 5) DIST( 1, 6) DIST( 1, 7) DIST( 1, 8) DIST( 1, 9) DIST( 1, 10) DIST( 1, 11) DIST( 1, 12) DIST( 1, 13) DIST( 1, 14) DIST( 2, 1) DIST( 2, 3) DIST( 2, 4) DIST( 2, 5) DIST( 2, 6) DIST( 2, 7) DIST( 2, 8) DIST( 2, 9) DIST( 2, 10) DIST( 2, 11) DIST( 2, 12) DIST( 2, 13) DIST( 2, 14) DIST( 3, 1) DIST( 3, 2) DIST( 3, 4) DIST( 3, 5) DIST( 3, 6) DIST( 3, 7) DIST( 3, 8) DIST( 3, 9) DIST( 3, 10) DIST( 3, 11) DIST( 3, 12) DIST( 3, 13) DIST( 3, 14) DIST( 4, 1) DIST( 4, 2) DIST( 4, 3) DIST( 4, 5) DIST( 4, 6) DIST( 4, 7) DIST( 4, 8) DIST( 4, 9) DIST( 4, 10) DIST( 4, 11) DIST( 4, 12) DIST( 4, 13)

13.00000 14.00000 55.00000 75.00000 115.0000 170.0000 148.0000 145.0000 159.0000 98.00000 101.0000 95.00000 50.00000 58.00000 20.00000 55.00000 43.00000 115.0000 165.0000 155.0000 170.0000 198.0000 142.0000 138.0000 115.0000 75.00000 105.0000 75.00000 75.00000 43.00000 80.00000 125.0000 120.0000 142.0000 181.0000 135.0000 123.0000 91.00000 64.00000 106.0000 95.00000 115.0000 115.0000 80.00000 56.00000 41.00000 72.00000 124.0000 102.0000 80.00000 40.00000 66.00000 100.0000

DIST( 4, 14) DIST( 5, 1) DIST( 5, 2) DIST( 5, 3) DIST( 5, 4) DIST( 5, 6) DIST( 5, 7) DIST( 5, 8) DIST( 5, 9) DIST( 5, 10) DIST( 5, 11) DIST( 5, 12) DIST( 5, 13) DIST( 5, 14) DIST( 6, 1) DIST( 6, 2) DIST( 6, 3) DIST( 6, 4) DIST( 6, 5) DIST( 6, 7) DIST( 6, 8) DIST( 6, 9) DIST( 6, 10) DIST( 6, 11) DIST( 6, 12) DIST( 6, 13) DIST( 6, 14) DIST( 7, 1) DIST( 7, 2) DIST( 7, 3) DIST( 7, 4) DIST( 7, 5) DIST( 7, 6) DIST( 7, 8) DIST( 7, 9) DIST( 7, 10) DIST( 7, 11) DIST( 7, 12) DIST( 7, 13) DIST( 7, 14) DIST( 8, 1) DIST( 8, 2) DIST( 8, 3) DIST( 8, 4) DIST( 8, 5) DIST( 8, 6) DIST( 8, 7) DIST( 8, 9) DIST( 8, 10) DIST( 8, 11) DIST( 8, 12) DIST( 8, 13) DIST( 8, 14)

124.0000 170.0000 165.0000 125.0000 56.00000 41.00000 85.00000 145.0000 145.0000 120.0000 88.00000 121.0000 151.0000 178.0000 148.0000 155.0000 120.0000 41.00000 41.00000 45.00000 105.0000 105.0000 80.00000 55.00000 96.00000 120.0000 153.0000 145.0000 170.0000 142.0000 72.00000 85.00000 45.00000 60.00000 75.00000 53.00000 53.00000 98.00000 103.0000 145.0000 159.0000 198.0000 181.0000 124.0000 145.0000 105.0000 60.00000 63.00000 60.00000 91.00000 123.0000 104.0000 150.0000

30 DIST( 9, 1) DIST( 9, 2) DIST( 9, 3) DIST( 9, 4) DIST( 9, 5) DIST( 9, 6) DIST( 9, 7) DIST( 9, 8) DIST( 9, 10) DIST( 9, 11) DIST( 9, 12) DIST( 9, 13) DIST( 9, 14) DIST( 10, 1) DIST( 10, 2) DIST( 10, 3) DIST( 10, 4) DIST( 10, 5) DIST( 10, 6) DIST( 10, 7) DIST( 10, 8) DIST( 10, 9) DIST( 10, 11) DIST( 10, 12) DIST( 10, 13) DIST( 10, 14) DIST( 11, 1) DIST( 11, 2) DIST( 11, 3) DIST( 11, 4) DIST( 11, 5) DIST( 11, 6) DIST( 11, 7) DIST( 11, 8) DIST( 11, 9) DIST( 11, 10) DIST( 11, 12) DIST( 11, 13) DIST( 11, 14) DIST( 12, 1) DIST( 12, 2) DIST( 12, 3) DIST( 12, 4) DIST( 12, 5) DIST( 12, 6) DIST( 12, 7) DIST( 12, 8) DIST( 12, 9) DIST( 12, 10) DIST( 12, 11) DIST( 12, 13) DIST( 12, 14) DIST( 13, 1)

98.00000 142.0000 135.0000 102.0000 145.0000 105.0000 75.00000 63.00000 25.00000 60.00000 72.00000 40.00000 88.00000 101.0000 138.0000 123.0000 80.00000 120.0000 80.00000 53.00000 60.00000 25.00000 40.00000 65.00000 50.00000 95.00000 95.00000 115.0000 91.00000 40.00000 88.00000 55.00000 53.00000 91.00000 60.00000 40.00000 45.00000 64.00000 98.00000 50.00000 75.00000 64.00000 66.00000 121.0000 96.00000 98.00000 123.0000 72.00000 65.00000 45.00000 46.00000 58.00000 58.00000

DIST( 13, 2) DIST( 13, 3) DIST( 13, 4) DIST( 13, 5) DIST( 13, 6) DIST( 13, 7) DIST( 13, 8) DIST( 13, 9) DIST( 13, 10) DIST( 13, 11) DIST( 13, 12) DIST( 13, 14) DIST( 14, 1) DIST( 14, 2) DIST( 14, 3) DIST( 14, 4) DIST( 14, 5) DIST( 14, 6) DIST( 14, 7) DIST( 14, 8) DIST( 14, 9) DIST( 14, 10) DIST( 14, 11) DIST( 14, 12) DIST( 14, 13) X( 1, 2) X( 2, 3) X( 3, 12) X( 4, 5) X( 5, 6) X( 6, 7) X( 7, 8) X( 8, 10) X( 9, 13) X( 10, 9) X( 11, 4) X( 12, 11) X( 13, 14) X( 14, 1)

105.0000 106.0000 100.0000 151.0000 120.0000 103.0000 104.0000 40.00000 50.00000 64.00000 46.00000 47.00000 20.00000 75.00000 95.00000 124.0000 178.0000 153.0000 145.0000 150.0000 88.00000 95.00000 98.00000 58.00000 47.00000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000

31 Lampiran 3Sintaks dan hasil komputasi program LINGO 11.0 dalam menyelesaikan pengelompokan pelanggan dari setiap kendaraan pada Kasus 2 Model: !Pengelompokan pelanggan (clustering1); SETS: nodes/1..14/:demand,pickup; vehicles/1..3/:; rute(nodes, vehicles):x, cost1; ENDSETS DATA: cost1= 0 0 0 0 600 600 63 123 150 175 157 219 280 263 328 248 210 281 260 190 270 302 205 289 185 80 166 184 93 176 155 101 173 70 38 88 600 0 600 600 600 0 ; demand = 0 20 25 15 40 20 10 30 30 25 20 15 20 20; pickup = 0 30 30 15 30 15 15 20 35 10 15 15 30 35; ENDDATA min = @sum(rute(i,j):cost1(i,j)*x(i,j)); !setiap kendaraan j mengunjungi pelanggan i; @for(nodes(i)|i#NE#1:@sum(vehicles(j):x(i,j)) = 1); !setiap pengiriman pada cluster tidak melebihi kapasitas kendaraan; @for(vehicles(j):@sum(nodes(i)|i#NE#1: demand(i)*x(i,j)) <= 100); !setiap pengambilan pada cluster tidak melebihi kapasitas kendaraan; @for(vehicles(j):@sum(nodes(i)|i#NE#1: pickup(i)*x(i,j)) <= 100); @for(rute(i,j):@bin(x(i,j)));

32 END

Hasil yang diperoleh:

Global optimal solution found. Objective value: Objective bound: Infeasibilities: Extended solver steps: Total solver iterations: Variable DEMAND( 2) DEMAND( 3) DEMAND( 4) DEMAND( 5) DEMAND( 6) DEMAND( 7) DEMAND( 8) DEMAND( 9) DEMAND( 10) DEMAND( 11) DEMAND( 12)

Value 20.00000 25.00000 15.00000 40.00000 20.00000 10.00000 30.00000 30.00000 25.00000 20.00000 15.00000

1692.000 1692.000 0.000000 0 295

33 DEMAND( 13) DEMAND( 14) PICKUP( 2) PICKUP( 3) PICKUP( 4) PICKUP( 5) PICKUP( 6) PICKUP( 7) PICKUP( 8) PICKUP( 9) PICKUP( 10) PICKUP( 11) PICKUP( 12) PICKUP( 13) PICKUP( 14) X( 2, 1) X( 3, 1) X( 4, 1) X( 5, 3) X( 6, 2) X( 7, 2) X( 8, 2) X( 9, 3) X( 10, 1) X( 11, 2) X( 12, 1) X( 13, 2) X( 14, 3) COST1( 2, 2) COST1( 2, 3) COST1( 3, 1) COST1( 3, 2) COST1( 3, 3) COST1( 4, 1) COST1( 4, 2) COST1( 4, 3) COST1( 5, 1) COST1( 5, 2) COST1( 5, 3) COST1( 6, 1) COST1( 6, 2) COST1( 6, 3) COST1( 7, 1) COST1( 7, 2) COST1( 7, 3) COST1( 8, 1) COST1( 8, 2) COST1( 8, 3) COST1( 9, 1) COST1( 9, 2) COST1( 9, 3) COST1( 10, 1) COST1( 10, 2)

20.00000 20.00000 30.00000 30.00000 15.00000 30.00000 15.00000 15.00000 20.00000 35.00000 10.00000 15.00000 15.00000 30.00000 35.00000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 600.0000 600.0000 63.00000 123.0000 150.0000 175.0000 157.0000 219.0000 280.0000 263.0000 328.0000 248.0000 210.0000 281.0000 260.0000 190.0000 270.0000 302.0000 205.0000 289.0000 185.0000 80.00000 166.0000 184.0000 93.00000

COST1( 10, 3) COST1( 11, 1) COST1( 11, 2) COST1( 11, 3) COST1( 12, 1) COST1( 12, 2) COST1( 12, 3) COST1( 13, 1) COST1( 13, 3) COST1( 14, 1) COST1( 14, 2)

176.0000 155.0000 101.0000 173.0000 70.00000 38.00000 88.00000 600.0000 600.0000 600.0000 600.0000

34 Lampiran 4Sintaks dan hasil komputasi program LINGO 11.0 dalam menyelesaikan pengelompokan pelanggan dari setiap kendaraan pada Kasus 3 Model: !Pengelompokan pelanggan (clustering2); SETS: nodes/1..14/:demand,pickup; vehicles/1..3/:; rute(nodes,vehicles):x, cost; ENDSETS DATA: cost= 0 0 0 0 600 600 63 123 150 175 157 219 280 263 328 248 210 281 260 190 270 302 205 289 185 80 166 184 93 176 155 101 173 70 38 88 600 0 600 600 600 0 ; demand = 0 20 25 15 40 20 10 30 30 25 20 15 20 20; pickup = 0 30 30 15 30 15 15 20 35 10 15 15 30 35; ENDDATA min = @sum(rute(i,j):cost(i,j)*x(i,j)); !setiap kendaraan j mengunjungi pelanggan i; @for(nodes(i)|i#NE#1:@sum(vehicles(j):x(i,j)) = 1); !setiap pengiriman pada cluster tidak melebihi kapasitas kendaraan; @sum(nodes(i)|i#NE#1: demand(i)*x(i,1)) <= 130; @sum(nodes(i)|i#NE#1: demand(i)*x(i,2)) <= 100; @sum(nodes(i)|i#NE#1: demand(i)*x(i,3)) <= 70; !setiap pengambilan pada cluster tidak melebihi kapasitas kendaraan; @sum(nodes(i)|i#NE#1: pickup(i)*x(i,1)) <= 130;

35 @sum(nodes(i)|i#NE#1: pickup(i)*x(i,2)) <= 100; @sum(nodes(i)|i#NE#1: pickup(i)*x(i,3)) <= 70; @for(rute(i,j):@bin(x(i,j))); END

Hasil yang diperoleh

Global optimal solution found. Objective value: Objective bound: Infeasibilities: Extended solver steps: Total solver iterations: Variable DEMAND( 2) DEMAND( 3) DEMAND( 4) DEMAND( 5) DEMAND( 6)

Value 20.00000 25.00000 15.00000 40.00000 20.00000

1714.000 1714.000 0.000000 2 329

36 DEMAND( 7) DEMAND( 8) DEMAND( 9) DEMAND( 10) DEMAND( 11) DEMAND( 12) DEMAND( 13) DEMAND( 14) PICKUP( 2) PICKUP( 3) PICKUP( 4) PICKUP( 5) PICKUP( 6) PICKUP( 7) PICKUP( 8) PICKUP( 9) PICKUP( 10) PICKUP( 11) PICKUP( 12) PICKUP( 13) PICKUP( 14) X( 2, 1) X( 3, 1) X( 4, 1) X( 5, 3) X( 6, 1) X( 7, 1) X( 8, 2) X( 9, 2) X( 10, 1) X( 11, 2) X( 12, 1) X( 13, 2) X( 14, 3) COST( 2, 2)

10.00000 30.00000 30.00000 25.00000 20.00000 15.00000 20.00000 20.00000 30.00000 30.00000 15.00000 30.00000 15.00000 15.00000 20.00000 35.00000 10.00000 15.00000 15.00000 30.00000 35.00000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 600.0000

COST( 2, 3) COST( 3, 1) COST( 3, 2) COST( 3, 3) COST( 4, 1) COST( 4, 2) COST( 4, 3) COST( 5, 1) COST( 5, 2) COST( 5, 3) COST( 6, 1) COST( 6, 2) COST( 6, 3) COST( 7, 1) COST( 7, 2) COST( 7, 3) COST( 8, 1) COST( 8, 2) COST( 8, 3) COST( 9, 1) COST( 9, 2) COST( 9, 3) COST( 10, 1) COST( 10, 2) COST( 10, 3) COST( 11, 1) COST( 11, 2) COST( 11, 3) COST( 12, 1) COST( 12, 2) COST( 12, 3) COST( 13, 1) COST( 13, 3) COST( 14, 1) COST( 14, 2)

600.0000 63.00000 123.0000 150.0000 175.0000 157.0000 219.0000 280.0000 263.0000 328.0000 248.0000 210.0000 281.0000 260.0000 190.0000 270.0000 302.0000 205.0000 289.0000 185.0000 80.00000 166.0000 184.0000 93.00000 176.0000 155.0000 101.0000 173.0000 70.00000 38.00000 88.00000 600.0000 600.0000 600.0000 600.0000

37

RIWAYAT HIDUP Penulis dilahirkan di Kota Bandar Lampung pada tanggal 1 Mei 1993 sebagai anak pertama dari pasangan bapak Sunardi dan ibu Sri Sumari. Tahun 2011 penulis lulus dari SMA Al-Kautsar Lampung dan pada tahun yang sama penulis lulus Seleksi Nasional Masuk Perguruan Tinggi Negeri (SNMPTN) melalui jalur Undangan dan diterima di Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Selama mengikuti perkuliahan, penulis menjadi asisten mata kuliah Kalkulus II dan Pendidikan Agama Islam pada semester genap tahun ajaran 2012/2013 dan semester ganjil tahun ajaran 2013/2014, asisten mata kuliah Pemrograman Tak Linier pada semester ganjil tahun ajaran 2014/2015, asisten mata kuliah Matematika Ekonomi pada semester genap tahun ajaran 2014/2015, dan menjadi pengajar SMPN 1 Ciampea Kabupaten Bogor mata pelajaran Matematika pada tahun 2015. Selain itu, penulis mendapat beasiswa Tanoto Foundation pada tahun 2012-2015. Penulis juga aktif pada kegiatan kemahasiswaan, antara lain sekretaris club Tutor Sebaya Asrama TPB IPB pada tahun 2011/2012, staf Kurikulum dan Kesiswaan Birena Al-Hurriyyah IPB pada tahun 2012/2013, staf Badan Pengawas (BP) Gumatika pada tahun 2012/2013, sekretaris Kurikulum dan Kesiswaan Birena Al-Hurriyyah IPB pada tahun 2013/2014, dan Bendahara Umum Birena Al-Hurriyyah IPB pada tahun 2014/2015.