## JURNAL ILMIAH TEKNIK INDUSTRI
Journal homepage: http://journals.ums.ac.id/index.php/jiti/index doi: 10.23917/jiti.v17i2.6703

## Penyelesaian Vehicle Routing Problem with Simultaneous Pick Up and Delivery dengan Algoritma Tabu Search
Annisa Kesy Garside 1* , Dian Nur Cahyanti 1
Abstract. Vehicle routing problem with simultaneous pickup and delivery (VRPSPD) is a problem of vehicle routes where the delivery and pickup of products to each consumer is conducted simultaneously.  Pangkalan Agisindo Alam Mandiri is engaged in the distribution of 3 kg LPG.  At present, pangkalan already has a schedule of visits to retail stores,  but  the  visit  route  is  still  subjectively  set  which  causes  long  mileage  and  high  transportation  costs.    The problem of determining the route at this pangkalanis calledVRPSPD because pangkalandelivered filled   LPG tubes to retail stores and at the same time picked up empty LPG tubes to be brought back.  To determine the route, one must consider the vehicle capacity and the ratio of the number of LPG tubes delivered and picked up.  This research used a tabu search algorithm to get the proposed route.  The steps in the tabu search algorithm includes   determination of the  initial  solution,  the  neighborhood  search,  intensification  phase,  diversification  phase,  standard  phase,  and interactive phase.  By using the tabu search algorithm, the proposed route provided a savings of transportation costs of 13.  72% rather than the initial route of the company.
Keywords: vehicle routing, pick up, delivery, tabu search algorithm, distribution of LPG.
Abstrak. Vehicle routing problem with simultaneous pickup and delivery (VRPSPD) merupakan permasalahan rute kendaraan dimana pengiriman dan pengambilan produk ke tiap konsumen dilakukan sekaligus.  Pangkalan Agisindo Alam Mandiri bergerak dalam pendistribusian LPG 3 kg.  Saat ini, pangkalan sudah memiliki jadwal kunjungan ke toko ritel, namun rute kunjungan masih ditetapkan secara subyektif sehingga menyebabkan jarak tempuh yang lama dan  biaya  transportasi  yang  tinggi.    Permasalahan  penentuan  rute  pada  pangkalan  ini  termasuk  VRPSPD  karena pangkalan  mengirimkan  tabung  LPG  yang  terisidan  sekaligus  mengambil  tabung  LPG  yang  kosong  untuk  dibawa kembali  ke  pangkalan.    Dalam  penentuan  rute  harus  mempertimbangkan  kapasitas  kendaraan  serta  rasio  jumlah tabung LPG yang dikirim dan diambil.  Penelitian ini menggunakan algoritma tabu search untuk mendapatkan rute usulan.  Langkah-langkah dalam algoritma tabu search meliputi penentuan solusi awal, pencarian neighborhood, fase intensifikasi, fase diversifikasi, fase standar, dan fase interaktif.  Dengan menggunakan algoritma tabu search, rute usulan memberikan penghematan biaya transportasi sebesar 13,72 % daripada rute awal perusahaan.
Kata Kunci: rute kendaraan, pick up, delivery, algoritma tabu search, distribusi LPG .

## I. P ENDAHULUAN
1
Vehicle  routing  problem  with  simultaneous pickup  and  delivery (VRPSPD)  adalah  salah  satu varian  dari vehicle  routing  problem yang mempertimbangkan  2  tipe  layanan  yaitu pengiriman  dan  pengambilan  produk  yang dilakukan  sekaligus  saat  mengunjungi  seorang konsumen.  Min (1989) memperkenalkan VRPSPD pertama  kali  dan  mengusulkan  algoritma
1
1 Jurusan Teknik Industri, Fakultas Teknik, Universitas Muhammadiyah Malang, Jalan Raya Tlogomas Nomor 246, Malang, 65144
* email: annisa_garside@yahoo.com
Diajukan: 25-08-2018
Diperbaiki: 10-11-2018 Disetujui: 04-12-2018
berdasarkan pendekatan cluster first-route second . Selanjutnya,  Salhi  dan  Nagy  (1999)  mengusulkan cluster  insertion  heuristic untuk  menyelesaikan VRPSPD.    Dethloff  (2001)  mengusulkan  formulasi matematis  dan  mengembangkan cheapest insertion  heuristic untuk  VRPSPD.      Pada  tahun 2005, Nagy dan Salhi mengembangkan 3 metode heuristik  baru  berdasarkan  penelitian  yang sebelumnya dilakukan.  Wassan dkk.  (2008), masih melanjutkan  penelitian  VRPSPD  yang  dilakukan oleh  Nagy,  namun  mengusulkan  metaheuristik yang disebut dengan reactive tabu search . Saat  ini, tabu  search adalah  salah  satu algoritma  metaheuristik  yang  paling  luas digunakan.    Beberapa  peneliti  telah  mengusulkan algoritma tabu  search untuk  menyelesaikan VRPSDP.    Crispim  dan  Brandao  (2005) menyelesaikan  VRPSDP  dengan  algoritma hybrid
Garside & Cahyanti / Penyelesaian Vehicle Routing Problem with .... JITI, Vol. 17 (5), Des 2018, 125 – 134
yang  terdiri  dari tabu  search dan variable neighborhood  descent .    Chen  dan  Wu  (2006) mengusulkan  solusi  awal  dengan cheapest insertion  algorithm dan  selanjutnya  diperbaiki dengan  algoritma hybrid yang  terdiri  dari tabu search dan record-to-record  travel .    Pada  tahun yang  sama,  Montane  dan  Galvao  (2006) mengembangkan  algoritma tabu  search untuk menyelesaikan  VRPSPD.    Prosedur tabu  search yang  diusulkan  menunjukkan  rata-rata  perbaikan solusi biaya sebesar 8,82% untuk set data problem Dethloff serta 13,43% untuk set data problem Salhi dan  Nagy.    Bianchessi  dan  Righini  (2007) mengusulkan  algoritma local  search dan tabu search untuk  menyelesaikan  VRPSPD.    Dari  hasil perbandingan  dengan  algoritma  Dethloff, tabu search yang  diusulkan  mereka  menunjukkan perbaikan  solusi  biaya  yang  lebih  besar. Selanjutnya Zachariadis dkk.  (2009) mengusulkan pendekatan  hibrid  metaheuristik  berdasarkan pada tabu  search dan guided  local  search untuk memperbaiki  solusi  awal  yang  diperoleh  dengan menggunakan cost  saving  method .      Selanjutnya Phannikul  dan  Sindhuchao  (2010)  serta  Fard  dan Akbari (2013) mengusulkan algoritma tabu search untuk menyelesaikan VRPSDP.
Pangkalan  Agisindo  Alam  Mandiri  (AAM) bergerak  dalam  pendistribusian  LPG  ( Liquified Petroleum Gas ) 3 kg.  Pangkalan ini mengirimkan LPG ke 55 toko ritel yang tersebar di Kecamataan Singosari  dan  Karang  Ploso.    Saat  ini,  pangkalan sudah  memiliki  jadwal  kunjungan  setiap  hari, tetapi  tidak  memiliki  rute  yang  pasti  dalam melakukan  pengiriman.    Sopir  mengunjungi  toko ritel  mulai  dari  yang  terdekat  dari  pangkalan kemudian  dilanjutkan  ke  toko  ritel  lain  yang berada  di  sekitarnya,  sehingga  berakibat  pada lamanya  waktu  tempuh  dan  tingginya  biaya transportasi  yang  dikeluarkan  oleh  pangkalan tersebut.  Problem penentuan rute yang dihadapi oleh pangkalan AAM termasuk  ke dalam VRPSPD karena  ada  2  tipe  layanan  yang  harus  dilakukan sekaligus pada tiap toko ritel yaitu jumlah jumlah tabung  LPG  penuh  yang  akan  dikirim  dan  jumlah tabung LPG kosong yang akan diambil.
Algoritma tabu  search adalah  sebuah  metode optimasi  dengan  prinsip  dasar  mengikuti kemampuan local  search dengan  tambahan
kemampuan  untuk  menghindari  optimum  lokal dengan  cara  membiarkan nonimproving  value bergerak  kembali  ke  solusi  sebelumnya  dengan menggunakan memori yang disebut dengan tabu list (Glover,  1989).    Penggunaan  memori  yang menyimpan informasi yang terkait dengan proses pencarian merupakan fitur dari tabu search (Hedar &  Bakr,  2014).      Berdasarkan  hasil  penelitian terdahulu,  algoritma tabu  search telah  banyak digunakan  dalam  menyelesaikan  VRPSPD  dan mampu  menghasilkan  biaya  yang  lebih  kecil dibanding  beberapa  algoritma  lain.    Oleh  karena itu, penyelesaian permasalahan rute yang dihadapi pangkalan  AAM  menggunakan  algoritma tabu search .

## II. M ETODE P ENELITIAN
Langkah penyelesaian VRPSPD dalam penelitian dibagi dalam 3 tahap: (1) pengumpulan data,  (2)  penentuan  rute  dengan  algoritma tabu search, (3)  perhitungan  total  jarak  tempuh,  waktu tempuh  dan  biaya  transportasi  antara  rute perusahaan dengan rute usulan.
Pada  tahap  pertama,  data-data  yang dikumpulkan  meliputi:  1)  nama  dan  alamat  toko ritel,  2)  jumlah  tabung  LPG  penuh  yang  dikirim dan  jumlah  tabung  LPG  kosong  yang  diambil,  3) jaraktempuh dari pangkalan ke toko ritel dan dari satu toko ritel ke toko ritel yang lainnya, 4) waktu tempuh dari pangkalan ke toko ritel dan dari satu toko  ritel  ke  toko  ritel  yang  lainnya,  5)  waktu pelayanan  yang  dibutuhkan  untuk loading dan unloading LPG  di  tiap  toko.    Data  jarak  tempuh diperoleh dengan mengikuti perjalanan kendaraan secara  langsung.    Sedangkan  waktu  tempuh kendaraan  dihitung  dengan  membagi  jarak tempuh dengan kecepatan kendaraan.  Kecepatan kendaraan  pada  saat  penelitian  rata-rata  sebesar 20 km/jam.
Pada  tahap  kedua,  penentuan  rute  usulan menggunakan  sprosedur  algoritma tabu  search yang  diusulkan  oleh  Montane  dan  Galvao  (2006). Hal  ini  didasarkan  pertimbangan  performansi prosedur  algoritma  ini  lebih  bagus  dibanding beberapa  prosedur  algoritma tabu  search yang lain.    Penelitian  terdahulu  yang  menggunakan struktur  algoritma  yang  sama  dilakukan  Idaman
(2013)  untuk  menyelesaikan  permasalahan distribusi air minum Fresh.
Langkah 0.  Penentuan solusi rute awal dengan menggunakan prosedur heuristik yaitu Independent  Grouping  and  Routing 1  (IGR1). Dalam  prosedur  ini  pengelompokan  toko  ritel dibuat  berdasarkan smallest  maximum  load , kemudian  metode  heuristik  2-opt  digunakan untuk  memperbaiki  rute  awal  yang  diperoleh dengan  mengurutkan  kunjungan  toko  ritel. Smallest  maximum  load terjadi  ketika  kendaraan mengunjungi  semua  toko  ritel  yang  mempunyai nd(i)  ≤  0  terlebih  dahulu  kemudian  mengunjungi toko ritel yang mempunyai nd(i) > 0 dengan syarat tidak  melanggar  kapasitas  kendaraan.    Dimana nd(i) menyatakan net demand dari toko ritel i yang merupakan  selisih  banyaknya  LPG  yang  diminta untuk  diambil/ pickup (pi)  dan  banyaknya  LPG yang dikirim (di).
Langkah 1 (fase awal).  Pada fase ini dilakukan pencarian  solusi neighborhood dari  solusi sebelumnya dengan menggunakan tiga tipe inter- movement  route ( relocation , interchange ,  dan crossover ) dan satu tipe intra-movement route ( 2- opt ).    Setiap  tipe inter-movement  route dapat membuat neighborhood ,  dalam  penelitian  ini pencarian neighborhood menggunakan best admissible solution , artinya seluruh neighborhood dicari  dan  selanjutnya  solusi feasible  movement terbaik  yang  akan  dipilih.    Kemudian  dilakukan pengecekan status move apakah bersifat tabu aktif atau  tidak  (jika  tabu  aktif  dilakukan  pengecekan kriteria  aspirasi), update  tabu  list ,  dan update solusi sekarang jika solusi yang ditemukan setelah melakukan move memiliki  nilai  fungsi  objektif lebih  baik  dari  solusi  sekarang.    Dalam  fase  awal ini, jumlah iterasi ditetapkan sebanyak 5 kali, nilai tabu  tenure untuk  sisi  yang  dihilangkan  adalah  3 dan  sisi  yang  ditambahkan  adalah  2.    Banyaknya sisi  yang  boleh  berada  pada tabu  list adalah  20 sisi.
Langkah  2  (fase  intensifikasi).    Fase  ini  dimulai dari solusi terbaik yang diperoleh pada fase awal. Pada  fase  intensifikasi,  langkah  pencarian  solusi neighborhood pada  langkah  1  diganti  dengan pencarian  solusi neighborhood menggunakan prosedur  intensifikasi.    Nilai tabu  tenure dipecah
menjadi  dua  pada  saat  fase  ini.    Dalam  fase  ini, jumlah iterasi ditetapkan sebanyak 1 kali.
Langkah 3 (fase diversifikasi).   Fase ini dimulai dari  solusi  yang  diperoleh  pada  fase  intensifikasi. Pada  fase  ini,  langkah  pencarian  solusi neighborhood pada  langkah  2  diganti  dengan pencarian  solusi neighborhood menggunakan prosedur  diversifikasi.    Pada  fase  ini  nilai tabu tenure pada  fase  sebelumnya  diperbaiki.    Dalam fase ini, jumlah iterasi ditetapkan sebanyak 1 kali.
Langkah 4 (fase standar).  Fase ini dimulai dari solusi  yang  didapat  dari  fase  3.    Pencarian  solusi neighborhood algoritma tabu  search dilakukan seperti  pada  fase  1.    Nilai tabu  tenure dari penghilangan  dan  penambahan  sisi  ditetapkan kembali.    Jumlah  iterasi  pada  fase  ini  ditetapkan sebanyak 3 kali.
Langkah  5  (fase  interaktif).    Ulangi  fase  2-4 hingga  salah  satu  dari  kriteria  penghentian dicapai.    Kriteria  penghentian  yang  digunakan adalah:  (1)  tidak  ada  lagi movement yang  layak dan (2) maksimum jumlah iterasi pada langkah 1-4 telah  tercapai.    Jumlah  iterasi  pada  fase  ini ditetapkan 3 kali.
Pada tahap ketiga, perhitungan total jarak dan waktu tempuh diperoleh dengan   menjumlahkan jarak  dan  waktu  tempuh  berdasarkan  rute  yang terbentuk.  Selanjutnya biaya transportasi dihitung dengan  menjumlahkan  biaya  tenaga  kerja  dan biaya  bahan  bakar.    Biaya  tenaga  kerja mempertimbangkan  durasi  waktu  pelayanan  dan waktu  tempuh  kendaraan.    Sedangkan  biaya bahan  bakar  mempertimbangkan  jarak  tempuh rute.  Jika biaya transportasi rute usulan lebih kecil dari  rute  perusahaan  maka  penyelesaian  masalah rute  pangkalan  telah  tercapai.    Sebaliknya,  akan dilakukan  pencarian  rute  kembali  dengan menambah  jumlah  iterasi  pada  langkah  1-4  pada prosedur algoritma tabu search diatas.

## III. H ASIL DAN P EMBAHASAN
Pangkalan  AAM  menggunakan  1  unit  mobil pick-up untuk  melakukan  pengiriman  LPG  3  kg dengan  kapasitas  angkut  150  tabung.    Pangkalan mendapat pengiriman dari agen LPG sebesar 200 tabung/hari sehingga maksimal mampu mengirim 200  tabung  ke  toko-toko  ritel.    Karena  hanya
memiliki  satu  kendaraan,  setiap  toko  ritel  telah memiliki  jadwal  kunjungan  tertentu.    Tabel  1 sampai  dengan  Tabel  3  menunjukkan  toko  ritel yang  dikunjungi  pada  tanggal  7-9  Mei  2018 beserta kuantitas LPG yang harus dikirim ( delivery ) dan diambil ( pickup ).  Pada tanggal 7-9 Mei 2018 terdapat  12,  8,  dan  11  toko  ritel  yang  harus
dikunjungi.

## Penentuan Rute Tanggal 7 Mei 2018
Berdasarkan  data  pada  Tabel  1,  penentuan solusi  awal  dimulai  dengan  menghitung  nd(i). Selanjutnya pengelompokan dimulai dengan toko ritel  yang  mempunyai  nd(i)  ≤  0  terlebih  dahulu
Tabel 1. Kuantitas delivery dan pickup tiap toko ritel pada 7 Mei 2018 Toko ritel Lokasi Delivery  Pickup T1 Jl.  Raya Tumapel, No.  21, Singosari 17 16 T2 Jl.  Raya Tumapel, No.  47, Singosari 21 21 T5 Jl. Tumapel Barat, No.  151, Singosari 35 35 T6 Jl.  Ronggowuni, No.  35, Singosari 14 14 T9 Jl.  Masjid No.  84, Singosari 10 8 T11 Jl.  Kembang No.  29, Singosari 25 25 T12 Jl.  Kembang No.  34, Singosari 15 15 T13 Jl.  Raya Singosari No.120, Singosari 7 7 T14 Jl.  Rogonoto No.  12 A, Singosari 10 10 T25 Jl.  Brawijaya No.  6 A, Singosari 15 15 T28 Jl.  Rogonoto Timur No.  228, Singosari 9 9 T29 Jl.  Kebon Agung No.  112, Singosari 20 20 Total 198 195 Tabel 2. Kuantitas delivery dan pickup tiap toko ritel pada 8 Mei 2018 Toko ritel Lokasi Delivery Pickup T5 Jl.Tumapel Barat No.  151, Singosari 35 35 T7 Jl.  Mondoroko Raya, B2 No.  25, Singosari 20 19 T8 Jl.  Mondoroko Raya, B2 No.  29, Singosari 25 25 T11 Jl.  Kembang No.  29, Singosari 25 25 T15 Jl.  Rogonoto No.  65, Singosari 10 9 T16 Jl.  Rogonoto No.  109, Singosari 20 20 T17 Jl.  Suropati No.  6, Singosari 30 28 T27 Jl.  Rogonoto Timur No.  192,  Singosari 20 20 Total 185 181
Tabel 3. Kuantitas delivery dan pickup tiap toko ritel pada 9 Mei 2018
Toko ritel Lokasi Delivery Pickup T3 Jl.  Raya Tumapel, No.  97, Singosari 20 20 T4 Jl.  Raya Tumapel, No.  112, Singosari 15 15 T10 Jl.  Tohjoyo Gg I No.  129, Singosari 10 10 T18 Jl.  Kadipaten No.  151, Singosari 30 30 T19 Jl.  Wisnuwardana No.  7, Singosari 13 13 T20 Jl.  Kertanegara No.  49, Singosari 20 20 T21 Jl.  Kertanegara No.  6, Singosari 18 17 T22 Jl.  Empu Purwo No.  291, Singosari 10 10 T23 Jl.  Tunggul Ametung No.  175, Singosari 19 19 T24 Jl.  Jendral Ahmad Yani No.  125, Singosari 20 20 T26 Jl.  Rogonoto Timur No.  208, Singosari 25 25 Total 200 199
kemudian  baru  mengunjungi  toko  ritel  yang mempunyai  nd(i)  >  0  dengan  syarat  tidak melanggar  kapasitas  kendaraan.    Selanjutnya menggunakan move neighbourhood dengan 2- Opt untuk  mendapat  rute  yang  meminimumkan jarak tempuh.   Solusi awal terbentuk 2 grup rute seperti ditunjukkan pada Tabel 4.
Tabel 4. Solusi rute awal pada 7 Mei 2018
Grup Rute Pick up Deli- very Jarak (Km) 1 0,29,28,14,25,0 54 54 9,94 2 0,12,11,5,6,2,1,9, 13,0 141 144 6,27 Total jarak 16,21 Berdasarkan  solusi  awal  yang  diperoleh, langkah satu
adalah
pencarian
solusi neighborhood dari  solusi  sebelumnya  dengan menggunakan inter-movement  route ( relocation , interchange ,  dan cross-over )  dan intra-movement route ( 2-opt ).    Pencarian neighborhood memakai best  admissible  solution berdasarkan move  value terbesar.    Pada  langkah  ini  dilakukan  5  iterasi sesuai  dengan  jumlah  iterasi  yang  ditetapkan sebelumnya.    Pada  langkah  1  iterasi  1, move terbaik  yang  dipilih  yaitu  relokasi  dengan move value sebesar  0,84.    Rute  baru  terbentuk  dengan menghilangkan  sisi  (12,11),  (11,5),  (25,0),  dan menambahkan  sisi  (12,5),  (25,11),  (11,0).    Solusi pada langkah 1 iterasi 1 terlihat pada Tabel 5.
Tabel 5. Solusi langkah 1 iterasi 1 pada 7 Mei 2018
Grup Rute Pick up Deli- very Jarak (Km) 1 0,12,5,6,2,1,9,13,0 116 119 6,27 2 0,29,28,14,25,11,0 79 79 9,12 Total jarak 15,39
Update  tabu  list ,  sisi  yang  dihilangkan  (12,11), (11,5),  (25,0)  dengan  nilai tabu  tenure 3. Sedangkan  sisi  yang  ditambahkan  adalah  (12,5), (25,11),  (11,0)  dengan  nilai tabu  tenure 2.    Solusi pada langkah 1 iterasi 1 lebih baik daripada solusi awal pada langkah 0, sehingga solusi awal diganti dengan  solusi  yang  terdapat  pada  langkah  1 iterasi 1.
Pada  langkah  1  iterasi  2, move terbaik  yang dipilih  yaitu  relokasi move  value sebesar  1.    Rute
baru terbentuk dengan  menghilangkan  sisi  (0,12), (12,5),  (11,0),  dan  menambahkan  sisi  (0,5)  (11,12), (12,0).    Cek  status tabu ,  (12,5)  dan  sisi  (12,11) bersifat tabu aktif  karena  terdapat  pada tabu  list . Selanjutnya  cek  kriteria  aspirasi,  karena  solusi iterasi  2  lebih  baik  daripada  solusi  pada  iterasi  1 maka  kriteria  aspirasi  terpenuhi,  sehingga  status tabu dapat  dilanggar.    Solusi  pada  langkah  1 iterasi 2 dapat dilihat pada Tabel 6.
Tabel 6. Solusi langkah 1 iterasi 2 pada 7 Mei 2018
Grup Rute Pick up Deli- very Jarak (Km) 1 0,5,6,2,1,9,13,0 101 104 4,82 2 0,29,28,14,25,12,11,0 94 94 9,32 Total jarak 14,14
Update  tabu  list ,  sisi  yang  dihilangkan  (12,11), (11,5), (25,0) dengan nilai tabu tenure 2 dan (0,12),
(12,5),  (11,0)  dengan  nilai tabu  tenure 3. Sedangkan  sisi  yang  ditambahkan  (12,5),  (25,11), (11,0) dengan nilai tabu tenure 1 dan (0,5), (11,12), (12,0)  dengan  nilai tabu  tenure 2.    Solusi  pada langkah 1 iterasi 2 lebih baik daripada solusi pada iterasi  1,  sehingga  solusi  iterasi  1  diganti  dengan solusi yang terdapat pada iterasi 2.
Pada  langkah  1  iterasi  3, move terbaik  yang dipilih  yaitu  relokasi  dengan move  value sebesar 0,65.  Rute baru terbentuk dengan menghilangkan sisi  (9,13),  (13,0),  (0,29),  dan  menambahkan  sisi (9,0),  (0,13),  (13,29).    Cek  status tabu ,  semua  sisi diatas tidak bersifat tabu aktif sehingga sisi dapat digunakan  pada  iterasi  saat  ini.    Status  muatan kendaraan juga tidak dilanggar sehingga sisi dapat digunakan.    Tabel  7  menunjukkan  solusi  pada langkah 1 iterasi 3.
Tabel 7. Solusi langkah 1 iterasi 3 pada 7 Mei 2018
Grup Rute Pick up Deli- Very Jarak (Km) 1 0,5,6,2,1,9,0 94 97 3,71 2 0,13,29,28,14,25,12,11,0 101 101 9,78 Total jarak 13,49
Update  tabu  list ,  sisi  yang  dihilangkan  (12,11), (11,5),  (25,0)  dengan  nilai tabu  tenure 1;  (0,12),
(12,5), (11,0) dengan nilai tabu tenure 2; dan (9,13), (13,0), (0,29) dengan nilai tabu tenure 3.  Sisi yang
Garside & Cahyanti / Penyelesaian Vehicle Routing Problem with .... JITI, Vol. 17 (5), Des 2018, 125 – 134
ditambahkan (0,5), (11,12), (12,0) dengan nilai tabu tenure 1 dan (9,0), (0,13), (13,29) dengan nilai tabu tenure 2.  Solusi pada iterasi 3 lebih baik daripada solusi  pada  iterasi  2,  sehingga  solusi  iterasi  2 diganti dengan solusi yang terdapat pada iterasi 3.
Pada  langkah  1  iterasi  4, move terbaik  yang dipilih  yaitu  menggunakan  2- Opt dengan  nilai move  value sebesar  0,47.    Rute  terbentuk  baru dengan  menghilangkan  sisi  (0,5),  (1,9)  dan menambahkan  sisi  (0,1),  (5,9).    Cek  status tabu , semua sisi diatas tidak bersifat tabu aktif sehingga sisi  dapat  digunakan  pada  iterasi  saat  ini.    Status muatan  kendaraan  juga  tidak  dilanggar  sehingga sisi  dapat  digunakan.    Solusi  pada  iterasi  4 ditunjukkan pada Tabel 8.
Tabel 8. Solusi langkah 1 iterasi 4 pada 7 Mei 2018
Grup Rute Pick up Deli- very Jarak (Km) 1  0,1,2,6,5,9,0 94 97 3,24 2  0,13,29,28,14,25,12,11,0 101  101  9,78 Total jarak 13,02
Update  tabu  list ,  sisi  yang  dihilangkan  (0,12), (12,5), (11,0)  dengan  nilai tabu  tenure 1;  (9,13),
(13,0), (0,29) dengan nilai tabu tenure 2; (0,5), (1,9) dengan  nilai tabu  tenure 3.    Sedangkan  sisi  yang ditambahkan (9,0), (0,13), (13,29) dengan nilai tabu tenure 1 dan (0,1), (5,9) dengan nilai tabu tenure 2. Solusi pada langkah 1 iterasi 4 lebih baik daripada solusi  pada  iterasi  3,  sehingga  solusi  iterasi  3 diganti dengan solusi yang terdapat pada iterasi 4.
Pada  langkah  1  iterasi  5, move terbaik  yang dipilih yaitu crossover dengan move value sebesar -1.    Rute  baru  terbentuk  dengan  menghilangkan sisi  (2,6),  (14,25)  dan  menambahkan  sisi  (2,25), (14,6).    Selanjutnya  status tabu diperiksa,  semua sisi  diatas  tidak  bersifat tabu aktif  sehingga  sisi dapat  digunakan  pada  iterasi  saat  ini.    Status muatan  juga  tidak  dilanggar  sehingga  sisi  dapat digunakan.    Tabel  9  menunjukkan  solusi  pada langkah 1 iterasi 5.
Update  tabu  list ,  sisi  yang  dihilangkan  (9,13), (13,0), (0,29)  dengan  nilai tabu  tenure 1;  (0,5), (1,9)  dengan nilai tabu tenure 2; dan (2,6), (14,25) dengan  nilai tabu  tenure 3.    Sedangkan  sisi  yang ditambahkan (0,1), (5,9)  dengan  nilai tabu  tenure 1 dan (2,25), (14,6)  dengan  nilai tabu  tenure 2.
Solusi  pada  iterasi  5  tidak  lebih  baik  daripada solusi pada iterasi 4, sehingga solusi tidak diganti. Solusi  terbaik  masih  menggunakan  solusi  dari iterasi 4.
Tabel 9. Solusi langkah 1 iterasi 5 pada 7 Mei 2018
Grup Rute Pick up Deli- very Jarak (Km) 1 0,1,2, 25,12,11,0 92 93 6,66 2 0,13,29,28,14, 6,5,9,0 103 105 7,83 Total jarak 14,49
Langkah  1  atau  fase  awal  mulai  dari  iterasi  1 sampai  5  telah  selesai  sehingga  pencarian  solusi dilanjutkan pada langkah 2 atau fase intensifikasi. Input yang digunakan pada fase ini diperoleh dari solusi terbaik pada langkah sebelumnya.  Prosedur pencarian  menggunakan  prosedur  intensifikasi, move yang  akan  dipilih  adalah move yang mempunyai  nilai eco  move i terbesar  (Idaman, 2013). Move terbaik  yang  dipilih  yaitu  relokasi dengan  nilai eco  move i sebesar  -1,79.    Rute  baru terbentuk  dengan  menghilangkan  sisi  (5,9),  (9,0), (13,29), dan menambahkan sisi (5,0), (13,9), (9,29). Selanjutnya  memeriksa  status tabu ,  semua  sisi diatas tidak bersifat tabu aktif sehingga sisi dapat digunakan  pada  iterasi  saat  ini.    Solusi  fase intensifikasi  (langkah  2)  dapat  dilihat  pada  Tabel 10.
Tabel 10. Solusi fase intensifikasi pada 7 Mei 2018
Grup Rute Pick up Deli- Very Jarak (Km) 1 0,1,2,6,5,0 86 87 2,58 2 0,13,9,29,28,14,25,12,11,0  109  111  12,23 Total jarak 14,81
Update  tabu  list ,  sisi  yang  dihilangkan  (2,6), (14,25) dengan nilai tabu tenure 1 dan (5,9), (9,0), (13,29)  dengan  nilai tabu  tenure 2.      Sisi  yang ditambahkan (5,0),  (13,9)  (9,29)  dengan  nilai tabu tenure 2.    Solusi  pada  fase  intensifikasi  akan menjadi input pada fase diversifikasi.
Pada  fase  diversifikasi,  prosedur  pencarian menggunakan  prosedur  diversifikasi, move yang akan  dipilih  adalah move yang  mempunyai  nilai eco  move d terbesar  (Montane  dan  Galvao,  2006). Move terbaik  yang  dipilih  yaitu interchange
dengan nilai eco move d sebesar 38,29.  Rute baru terbentuk  dengan  menghilangkan  sisi  (0,1),  (1,2), (29,28),  (28,14)  dan  menambahkan  (0,28),  (28,2), (29,1),  (1,4).    Selanjutnya  status tabu diperiksa, semua sisi diatas tidak bersifat tabu aktif sehingga sisi dapat digunakan pada iterasi saat ini.  Tabel 11 menunjukkan solusi diversifikasi.
Tabel 11. Solusi fase diversifikasi pada 7 Mei 2018
Grup Rute Pick up Deli- very Jarak (Km) 1 0,28,2,6,5,0 79 79 7,23 2 0,13,9,29,1,14,25,12,11,0  116  119  12,54 Total jarak 19,77
Update  tabu  list ,  sisi  yang  dihilangkan  (5,9), (9,0), (13,29)  dengan nilai tabu tenure 2 dan (0,1),
(1,2), (29,28), 28,14)  dengan  nilai tabu  tenure 3. Sisi yang ditambahkan (5,0), (13,9) (9,29)   dengan nilai tabu tenure 1 dan (0,28), (28,2), (29,1), (1,14) dengan  nilai tabu  tenure 2.      Solusi  pada  fase diversifikasi akan digunakan pada fase standar.
Pada  fase  standar  ulangi  prosedur  pencarian rute  dengan tabu  search seperti  pada  fase  awal. Pada  fase  ini  akan  dilakukan  sebanyak  3  iterasi, dengan input solusi dari fase diversifikasi.   Fase ini dilakukan  hingga  3  iterasi.    Pada  fase  standar iterasi  1, move terbaik  yang  dipilih  yaitu  2- Opt dengan  nilai move  value sebesar  2,15.    Tentukan rute baru dengan menghilangkan sisi (9,29), (1,14) dan  menambahkan  sisi  (9,1),  (29,  14).    Cek  status tabu ,  sisi  (9,29),  dan  sisi  (1,14)  bersifat tabu aktif, cek  apakah  solusi  lebih  baik  dari  solusi diversifikasi.    Solusi  yang  didapat  lebih  baik daripada  solusi  yang  diperoleh  pada  fase diversifikasi,  kriteria  aspirasi  terpenuhi  sehingga sisi  dapat  digunakan  pada  iterasi  saat  ini.    Status muatan  juga  tidak  dilanggar  sehingga  sisi  dapat digunakan.    Solusi  pada  fase  standar  iterasi  1 ditunjukkan pada Tabel 12.
Update  tabu  list ,  sisi  yang  dihilangkan  (5,9), (9,0), (13,29)  dengan nilai tabu tenure 1;(0,1), (1,2),
(29,28),  28,14)  dengan  nilai tabu  tenure 2;  dan (9,29), (1,14) dengan nilai tabu tenure 3.  Sisi yang ditambahkan  (0,28),  (28,2),  (29,1),  (1,14)  dengan nilai tabu  tenure 1  dan  (9,1),  (29,14)  dengan  nilai
tabu tenure 2.   Solusi pada iterasi 1 fase standar lebih baik dari fase diversifikasi.  Lakukan prosedur yang sama hingga iterasi ke-3.
Tabel 12. Solusi fase standar iterasi 1 pada 7 Mei 2018
Grup Rute Pick up Deli- very Jarak (Km) 1 0,28,2,6,5,0 79 79 7,23 2 0,13,9,1,29,14,25,12,11,0  116 119  10,39 Total jarak 17,62
Fase  terakhir  adalah  fase  interaktif,  pada  fase ini iterasi diulangi dari fase awal, fase intensifikasi, fase  diversifikasi  dan  fase  standar.    Fase-fase tersebut dapat dilakukan hingga salah satu kriteria pemberhentian  telah  tercapai.      Dengan menggunakan  kriteria  penghentian  yang  tercapai adalah maksimum iterasi pada tiap fase, diperoleh solusi  pada  seluruh  fase  untuk  menyelesaikan penentuan  rute  pada  tanggal  7  Mei  2018 ditunjukkan  pada  Tabel  13.      Dari  tabel  13  dapat dilihat  rute  terbaik  dengan  total  jarak  sebesar 13,02 Km diperoleh pada fase awal iterasi 4.

## Penentuan Rute Pada 8 Mei 2018
Penentuan  rute  dilakukan  dengan  prosedur yang  sama  dengan  tanggal  7  Mei  2018.    Dengan menggunakan  kriteria  penghentian  yang  tercapai adalah maksimum iterasi pada tiap fase, diperoleh solusi  pada  seluruh  fase  untuk  menyelesaikan penentuan  rute  pada  tanggal  8  Mei  2018 ditunjukkan  pada  Tabel  14.    Dari  tabel  14  dapat dilihat  rute  terbaik  dengan  total  jarak  sebesar 11,58 Km diperoleh pada fase interaktif iterasi 3.

## Penentuan Rute pada 9 Mei 2018
Penentuan  rute  dilakukan  dengan  prosedur yang  sama  dengan  tanggal  7  Mei  2018.    Dengan menggunakan  kriteria  penghentian  yang  tercapai adalah maksimum iterasi pada tiap fase, diperoleh solusi  pada  seluruh  fase  untuk  menyelesaikan penentuan rute pada 9 Mei 2018 ditunjukkan pada Tabel 15.  Dari Tabel 15 dapat dilihat rute terbaik dengan  total  jarak  sebesar  13,08  km  diperoleh pada fase intensifikasi iterasi 1.
Garside & Cahyanti / Penyelesaian Vehicle Routing Problem with .... JITI, Vol. 17 (5), Des 2018, 125 – 134
Tabel 13. Solusi rute per langkah dengan tabu search pada 7 Mei 2018 Langkah dan Fase Iterasi ke Rute Jarak (Km) Total Jarak (Km) Langkah 0 (solusi awal) 1 0-29-28-14- 25- 0 9,94 16,21 0- 12- 11- 5- 6- 2- 1- 9- 13- 0 6,27 Langkah 1 (fase awal) 1 0- 12- 5- 6- 2- 1- 9- 13- 0 6,27 15,39 0- 29- 28- 14- 25- 11- 0 9,12 2 0- 5- 6- 2- 1- 9- 13- 0 4,82 14,14 0- 29- 28- 14- 25- 12- 11- 0 9,32 3 0- 5- 6- 2- 1- 9- 0 3,71 13,49 0- 13- 29- 28- 14- 25- 12- 11- 0 9,78 4 0- 1- 2- 6- 5- 9- 0 3,24 13,02 0- 13- 29- 28- 14- 25- 12- 11- 0 9,78 5 0- 1- 2- 25- 12- 11- 0 6,66 14,49 0- 13- 29- 28- 14- 6- 5- 9- 0 7,83 Langkah 2 (fase intensifikasi) 1 0- 1- 2- 6- 5- 0 2,58 14,81 0-13-9- 29- 28- 14-25- 12-11- 0 12,23 Langkah 3 (fase diversifikasi) 1 0- 28- 2- 6- 5- 0 7,23 19,77 0-13- 9- 29-1- 14- 25- 12- 11- 0 12,54 Langkah 4 (fase standar) 1 0- 28- 2- 6- 5- 0 7,23 17,62 0-13- 9-1- 29- 14- 25- 12- 11- 0 10,39 2 0- 28- 29- 14- 25- 12- 11- 0 9,29 14,11 0- 13- 9- 1- 2- 6- 5- 0 4,8 3 0- 28- 29- 14- 25- 12- 1- 0 8,91 15,51 0- 13- 9- 11- 2- 6- 5- 0 6,6 Langkah 5 (fase interaktif) 1 0-29-28-14-25-12-1-0 9,4 16 0-13-9-11-2-6-5-0 6,6 2 0-29-28-14-6-12-1-0 8,33 19,35 0-13-9-11-2-25-5-0 11,02 3 0-29-28-14-6-1-0 6,39 19,08 0-13-9-11-2-25-5-0 12,69 Tabel 14. Solusi per langkah dengan tabu search pada 8 Mei 2018 Langkah dan Fase Iterasi ke Rute Jarak (Km) Total Jarak (Km) Langkah 0 (solusi awal) 1 0-27-16-15-17-5-11-0 9,17 11,66 0-7-8-0 2,49 Langkah 1 (fase awal) 1 0-15-16-27-17-5-11-0 9,09 11,58 0-7-8-0 2,49 2 0-15-16-27-17-11-5-0 9,11 11,6 0-7-8-0 2,49 3 0-15-5-17-27-16-11-0 13,53 16,02 0-7-8-0 2,49 4 0-16-15-27-17-5-11-0 12,05 13,58 0-7-8-0 2,49 5 0-15-5-17-27-16-11-0 13,53 16,02 0-7-8-0 2,49 Langkah 2 (fase intensifikasi) 1 0-15-17-27-16-5-0 10,55 13,04 0-7-8-0 2,49 Langkah 3 (fase diversifikasi) 1 0-15-17-27-8-0 9,86 19,44 0-7-16-5-11-0 9,58 Langkah 4 (fase standar) 1 0-15-17-7-8-0 7,63 15,48 0-27-16-5-11-0 7,85 2 0-15-17-7-8-0 7,63 15,4 0-16-27-5-11-0 7,77 3 0-17-7-8-0 6,33 14,1 0-15-16-27-5-11-0 7,77 Langkah 5 1 0-7-8-0 2,49 11,58 (fase interaktif) 0-15-16-27-17-5-11-0 9,09 2 0-7-5-0 4,41 17,25 0-15-16-27-17-8-11-0 12,84 3 0-7-8-0 2,49 11,58 0-15-16-27-17-5-11-0 9,09
Perbandingan  Rute  Awal  Perusahaan  dengan Rute Usulan
Perbandingan  jarak  tempuh  dan  biaya transportasi  pada  rute  awal  perusahaan  dengan rute usulan dapat dilihat pada Tabel 16.  Dari hasil perbandingan  pada  Tabel  16,  diperoleh  selisih jarak  tempuh  antara  rute  perusahaan  dengan usulan sebesar 17,38 Km atau 46,87%.  Total biaya transportasi rute perusahaan sebesar Rp 373.  059, sedangkan total biaya transportasi usulan sebesar Rp  328.039.    Diperoleh  selisih  biaya  transportasi sebesar    Rp  45.020  dengan  kata  lain  biaya
transportasi rute usulan lebih hemat 13,72   %.

## IV. S IMPULAN
Penelitian  ini  telah  mengusulkan  algoritma tabu  search untuk  menyelesaikan  permasalahan penentuan  rute  pada  pangkalan  Agisindo  yang termasuk dalam VRPSPD.  Dari hasil perbandingan dengan rute awal perusahaan, rute usulan mampu memberikan  penghematan  jarak  tempuh  sebesar 46,87%  dan  penghematan  biaya  transportasi sebesar 13,72%.   Rute  usulan lebih baik sehingga
Tabel 15. Solusi per langkah dengan tabu search pada 9 Mei 2018 Langkah dan Fase Iterasi ke Rute Jarak (Km) Total Jarak (Km) Langkah 0 (solusi awal) 1 0-10-3-4-18-20-19-21-23-0 6,74 16,55 0-26-22-24-0 6,81 Langkah 1 (fase awal) 1 0-10-3-4-18-19-21-23-0 5,86 15,59 0-26-22-24-20-0 9,73 2 0-10-3-4-18-19-21-20-0 4,75 15,59 0-26-22-24-23-0 10,3 3 0-10-3-4-18-19-21-0 4,41 14,88 0-20-26-22-24-23-0 10,57 4 0-10-3-4-18-19-21-0 4,41 13,92 0-20-26-24-22-23-0 9,51 5 0-10-3-4-18-24-22-23-0 6,92 13,34 0-20-26-19-21-0 6,42 Langkah 2 (fase intensifikasi) 1 0-10-3-4-18-24-22-23-0 6,92 13,08 0-26-20-19-21-0 6,16 Langkah 3 (fase diversifikasi) 1 0-10-21-4-18-24-22-23-0 8,17 14,42 0-26-20-19-3-0 6,25 Langkah 4 (fase standar) 1 0-10-21-4-3-0 3,43 13,1 0-26-20-19-18-24-22-23-0 9,67 2 0-10-21-4-3-0 3,43 13,8 0-26-20-18-19-24-22-23-0 10,37 3 0-10-21-22-23-0 4,01 13,16 0-26-20-19-18-24-4-3-0 9,15 Langkah 5 1 0-10-21-4-3-0 3,41 13,1 (fase interaktif) 0-26-20-19-18-24-22-23-0 9,67 2 0-10-21-26-3-0 7,17 15,07 0-4-20-19-18-24-22-23-0 7,9 3 0-10-21-4-3-0 3,43 13,1 0-26-20-19-18-24-22-23-0 9,67 Tabel 16. Perbandingan rute perusahaan dengan rute usulan Tanggal Rute Jarak (km) Biaya transportasi (Rp) Awal Usulan Awal Usulan Awal Usulan 7 Mei 0-1-2-9-5-6-11-12-13-0 0-1-2-6-5-9-0 7,36 3,24 81.203 52.989 0-14-28-25-29-0 0-13-29-28-14-25-12-11-0 13,85 9,78 50.107 65.394 8 Mei 0-7-8-5-11-17-15-0 0-7-8-0 10,22 2,49 86.586 25.633 0-16-27-0 0-15-16-27-17- 5- 11-0 4,84 9,09 27.722 65.604 9 Mei 0-3-4-21-20-19-18-23-22-0 0-10-3-4-18-24- 22-23-0 8,73 6,92 84.548 71.511 0-10-24-26-0 0-26-2019-21-0 9,46 6,16 42.893 46.908 Total 54,46 37,08 373.059 328.039
Garside & Cahyanti / Penyelesaian Vehicle Routing Problem with .... JITI, Vol. 17 (5), Des 2018, 125 – 134
pangkalan  dapat  mempertimbangkan  algoritma tabu  search sebagai  metode  penentuan  rute. Saran  yang  bisa  diusulkan  adalah  membuat software untuk  mempercepat  proses  perhitungan sehingga  algoritma  ini  bisa  diaplikasikan  dalam penentuan rute di pangkalan.

## U CAPAN T ERIMA K ASIH
Kami  mengucapkan  terima  kasih  kepada Universitas  Muhammadiyah  Malang  yang  telah mensponsori  penelitian  ini  melalui Block  Grant Penelitian  dan  Pengabdian  Masyarakat  No: 01/P2M-HDL/FT-UMM/ VI /2018.

## D AFTAR P USTAKA
Bianchessi,  N.;  Righini,  G.  (2007).  “Heuristic  algorithms for  the  vehicle  routing  problem  with  simultaneous pick-up  and  delivery”. Computers  and  Operations Research , Vol. 34 (2), 578 – 594.
Chen,  J;  Wu,  T.  (2006).  “Vehicle  routing  problem  with simultaneous  delivery  and  pickup”. Journal  of Operational Research Society , Vol. 57 (5), 579 – 587. Crispim, J.; Brandao, J. (2005).  “Metaheursitics apllied to mixed  and  simultaneous  extensions  of  vehicle routing  problems  with  backhauls”. Journal  of Operational  Research  Society ,  Vol. 56 (11),  1296  – 1302. Dethloff, J. (2001). “Vehicle routing and reverse logistics: the  vehicle  routing  problem  with  simultaneous delivery  and  pick-up”. OR  Spektrum ,  Vol. 23 ,  79  –
96.
Fard,  M.;  Akbari,  M.  (2013).  “A  hybrid  tabu  search algorithm  for  the  vehicle  routing  problem  with simultaneous  pickup  and  delivery  and  maximum tour  time  length”. African  Journal  of  Business Management , Vol. 7 (11), 801 – 810. Glover, F. (1989). “Tabu search part I”, ORSA Journal on Computing , Vol. 1 (3), 190 – 206.
Hedar, A.; Bakr, M. (2014). “Three strategies tabu search for  vehicle  routing  problem  with  time  windows”, Computer Science and Information Technology , Vol.
2 (2), 108 – 119. Idaman,  S.  (2013). Penyelesaian  Vehicle  Routing Problem  with  Simultaneous  Pick-up  and  Delivery Service  Menggunakan  Algoritma  Tabu  Search . Skripsi.  Bogor:  Departemen  Matematika,  Institut Pertanian Bogor.
Min  H.  (1989).  “The  multiple  vehicle  routing  problem with  simultaneous  delivery  and  pickup  points”. Transportation Research Part A , Vol. 5 , 377 – 386.
Montane, F.; Galvao, R. (2006). “A tabu search algorithm for  the  vehicle  routing  problem  with  simultaneous pick-up  and  delivery  service”. Computers  and Operations Research , Vol. 33 (3), 595 – 619.
Nagy, G.; Salhi, S. (2005). “Heuristics algorithm for single and  multiple  depot  vehicle  routing  problems  with pickup  and  deliveries”. European  Journal  of Operational Research , Vol. 33 (3), 595 – 619.
Phannikul, T.; Sindhuchao, S. (2010). “A customized tabu search  for  the  vehicle  routing  problem  with simultaneous  pickup  and  delivery”. Thammasat International Journal of Science and Technology , Vol.
15 (2), Salhi, S.; Nagy, G. (1999). “A cluster insertion heuristic for single  and  multiple  depot  vehicle  routing  problems with  backhauling”. Journal  of  the  Operational Research Society , Vol. 50 , 1034 – 1042. Wassan, N.; Wassan, A.; Nagy, G. (2008). “A reactive tabu serach  algorithm  for  the  vehicle  routing  problem with  simultaneous  pickups  and  deliveries”. Journal of Combinatorial Optimization , Vol. 15 , 368 – 386. Zachariadis,  E.;  Tarantilis,  C.;  Kiranoudis,  C.  (2009).  “A hybrid  metaheuristic  algorithm  for  vehicle  routing problem  with  simultaneous  delivery  and  pick-up service”. Expert  System  with  Applications ,  Vol. 36 , 1070 – 1081.