## Aplikasi Algoritma Tabu Search dan Safety Stock Pada Penentuan Rute Distribusi Air Mineral di Daerah Istimewa Yogyakarta

## Anita Nurul Firdaus dan Pipit Pratiwi Rahayu
Program Studi Matematika Fakultas Sains dan Teknologi, UIN Sunan Kalijaga, Jl. Marsda Adisucipto No. 1 Yogyakarta, Indonesia
Korespondensi; Pipit Pratiwi Rahayu, Email: pipitprahayu@yahoo.com

## Abstrak
Pendistribusian produk berperan penting dalam dunia industri. Salah satu usaha yang dapat dilakukan perusahaan untuk  mengoptimalkan  pendistribusian  produk  adalah  meminimalkan  biaya  tranportasi  melalui  penentuan  rute optimal kendaraan yang disebut dengan VRP (Vehicle Routing Problem). Tujuan dari VRP adalah menentukan rute optimal yaitu rute dengan jarak minimum untuk mendistribusikan produk kepada konsumen. Salah satu variasi VRP adalah Capacitated Vehicle Routing Problem (CVRP), yaitu VRP dengan kendala kapasitas kendaraan. Kasus CVRP tersebut dapat diselesaikan dengan menggunakan Algoritma Tabu Search. Cara kerja Algoritma Tabu Search dimulai dengan penentuan initial solution menggunakan Nearest Neighbor, evaluasi move menggunakan  Exchange, 2-Opt, Relocated, dan Cross Exchange, update Tabu List, kemudian apabila kriteria pemberhentian terpenuhi  maka proses Algoritma Tabu Search berhenti jika tidak, maka kembali pada evaluasi move. Proses perhitungan Algoritma Tabu Search  dilakukan  secara  manual  pada  PT  IAP.  Setiap  perusahaan  distributor  atau  pun  jasa  selalu  mengadakan persediaan, salah satunya adalah Safety Stock. Perhitungan sederhana Safety Stock dapat membantu menyelesaikan persediaan pengaman yang harus dipersiapkan perusahaan untuk mengurangi tingkat kerugian. Berdasarkan proses perhitungan manual diperoleh solusi pendekatan optimal yaitu rute dengan total jarak terpendek sebesar 138,834 km dan nilai untuk Safety Stock adalah ± 9 karton.
Kata Kunci Algoritma Tabu Search; Capacitated Vehicle Routing Problem (CVRP); Nearest Neighbor ; Safety Stock

## Abstract
Distribution  of  the  product  play  an  important  role  in  the  industry  field.  The  effort  done  by  the  companies  to optimize the distribution is minimize transportation fee by deciding the shortest route of the vehicle, known as Vehicle Routing Problem (VRP). The purpose of VRP is to determine the optimal route of the route with a minimum distance to distribute product to the consumer. One of the varieties of VRP is Capacitated Vehicle Routing Problem (CVRP ), which is VRP with vehicle capacity problems. CVRP case can be solved by using Tabu Search Algorithm . How  it  works  Tabu  Search  Algorithm  starts  with  the  determination  of  the  initial  solution  using  the  Nearest Neighbor,  evaluating the move using Exchange, 2-Opt, Relocated,  and Cross  Exchange, updates Tabu List, then when the criteria for termination are met then the Tabu Search algorithm stop if not, then go back to the evaluation of the move. Tabu  Search  Algorithm  calculation process is  done  manually PT IAP.   Every distributor or service company always hold inventory, one of them is Safety Stock. The simple calculation of Safety Stock can help solve the safety availability that should be prepared by the companies and reduce the level of losses. Based on the manual calculation process obtained optimal solution approach that is route with the shortest route to the optimal total distance of 138,834 km and the value of safety stock is ± 9 cartons.
Keywords Capacitated Vehicle Routing Problem (CVRP); Nearest Neighbor ; Safety Stock ; Tabu Search Algorithm

## Pendahuluan
Pada dunia industri, logistik memiliki peranan penting dalam meningkatkan kinerja suatu perusahaan. Kemampuan perusahaan untuk mengelola logistik secara efektif dan efisien dapat mempengaruhi biaya dan tingkat pelayanan terhadap konsumen sehingga dapat bersaing dengan perusahaan sejenis lainnya.
Salah  satu  usaha  yang  dapat  dilakukan  perusahaan  untuk  mengoptimalkan  pendistribusian  produk adalah meminimalkan biaya tranportasi melalui penentuan rute optimal kendaraan yang disebut Vehicle Routing Problem (VRP). Kasus VRP merupakan bagian TSP dengan menyertakan kendala satu kendaraan dengan kapasitas sehingga digolongkan ke dalam NP-Hard Problem. Secara teori ataupun praktik pada dunia nyata memiliki permasalahan yang sangat banyak dan kompleks sehingga sulit untuk dipecahkan. Kasus NP-Hard dapat diselesaikan menggunakan pendekatan solusi optimal dengan metode heuristik. Dibandingkan dengan metode heuristik klasik, metaheuristik menunjukkan pencarian solusi yang lebih teliti. Salah satu metode metaheuristik yang dapat diaplikasikan untuk menuntun prosedur pencarian local heuristik untuk menjelajahi daerah solusi di luar titik optimal lokal [9].
Algoritma Tabu Search dapat digunakan untuk mencari solusi optimal VRP yaitu rute yang memiliki total jarak tempuh minimum dengan mempertimbangkan kapasitas kendaraan. Langkah Algoritma Tabu Search  dimulai  dengan  penentuan initial  solution  menggunakan  Nearest  Neighbor,  evaluasi  move menggunakan metode Exchange, 2-Opt, Relocated, dan Cross Exchange, update Tabu List , kemudian apabila kriteria pemberhentian terpenuhi maka proses Algoritma Tabu Search berhenti jika tidak, maka kembali pada evaluasi move. Perhitungan sederhana Safety Stock bertujuan untuk menyeimbangkan jumlah  persediaan  dengan  jumlah  permintaan  konsumen.  Keseimbangan  tersebut  tentunya  akan mendatangkan  keuntungan  bagi  perusahaan  karena  kemungkinan  akan  adanya  modal  macet  yang berbentuk  persediaan  akan  semakin  kecil  sehingga  proses  perputaran  modal  dari  perusahaan  akan lebih  lancar.  Algoritma  Tabu  Search  dapat  memudahkan  pencarian  solusi  optimal  VRP  yang  lebih efektif dan efisien pada PT IAP Yogyakarta.

## Landasan Teori
Teori Graf Graf adalah kumpulan simpul ( nodes) yang dihubungkan satu sama lain melalui sisi (edge). Suatu graf 𝐺 merupakan pasangan himpunan (𝑉, 𝐸) ditulis dengan notasi 𝐺 = (𝑉, 𝐸) , dimana 𝑉 adalah himpunan berhingga  dan  tak  kosong  dari  simpul  ( node)  sedangkan 𝐸 adalah  himpunan  sisi  ( edge)  yang menghubungkan sepasang  elemen tidak berurutan dari 𝑉 .  Elemen dari 𝑉 dinamakan simpul ( node), 𝑉 = {𝑣 1 , 𝑣 2 , 𝑣 3 , . . . , 𝑣 𝑛 } dan elemen dari 𝐸 dinamakan sisi ( edge), 𝐸 = {𝑒 1 , 𝑒 2 , 𝑒 3 , . . . , 𝑒 𝑛 } [10].
Graf Berarah Berbobot Graf berarah berbobot ( weighted directed graph) adalah graf yang setiap node diberikan orientasi arah dan memiliki bobot [22]. Graf berarah berbobot sering digunakan untuk menggambarkan aliran proses, peta lintas Kota dan lain-lain. Lebih lanjut, pada graf berarah berbobot tidak memperbolehkan adanya sisi ganda atau multiple edges.

## Graf Hamilton
Sebuah lintasan pada graf 𝐺 yang melalui tiap node di dalam graf tersebut tepat satu kali disebut lintasan Hamilton, sedangkan sebuah sirkuit pada graf 𝐺 yang melalui tiap node tepat satu kali disebut sebagai sirkuit Hamilton [22].

## Travelling Salesman Problem (TSP)
Travelling salesman problem (TSP) merupakan suatu permasalahan untuk menemukan rute perjalanan terpendek dari kota asal atau depot kemudian mengunjungi seluruh kota konsumen yang harus dilalui satu kali dan kembali lagi ke depot. TSP dapat direpresentasikan pada sebuah graf 𝐺 = (𝑉, 𝐸) , dimana 𝑉 adalah simpul (node) yang merepresentasikan kota, dan 𝐸 adalah sisi yang merepresentasikan jalan yang menghubungkan kota tersebut. Secara umum model matematika untuk TSP adalah sebagai berikut [28]:
Diberikan 𝑣 𝑖𝑗 adalah jarak dari Kota 𝑖 ke Kota 𝑗 ( 𝑣 𝑖𝑗 nonnegative) dan 𝑛 adalah jumlah Kota yang akan dilewati.  Fungsi  tujuan untuk  meminimumkan  total  jarak  tempuh perjalanan  salesman.  Jika 𝑍 adalah fungsi tujuan maka;
𝑀𝑖𝑛 𝑍 = ∑ ∑ 𝑣 𝑖𝑗 𝑥 𝑖𝑗 𝑛 𝑗=1 𝑛 𝑖=1 (1)
Didefinisikan variabel keputusan:
𝑥 𝑖𝑗 = { 1, 𝐽𝑖𝑘𝑎 𝑠𝑎𝑙𝑒𝑠𝑚𝑎𝑛 𝑚𝑒𝑙𝑎𝑘𝑢𝑘𝑎𝑛 𝑝𝑒𝑟𝑗𝑎𝑙𝑎𝑛𝑎𝑛 𝑑𝑎𝑟𝑖 𝑘𝑜𝑡𝑎 𝑖 𝑘𝑒 𝑘𝑜𝑡𝑎 𝑗
0, 𝑠𝑒𝑙𝑎𝑖𝑛𝑛𝑦𝑎
1. Setiap kota dikunjungi 1 kali
∑ 𝑥 𝑖𝑗 𝑛 𝑖=1 = 1 , untuk 𝑗 = 1,2, . . . , 𝑛 (2)
∑ 𝑥 𝑗𝑖 𝑛 𝑗=1 = 1 , untuk 𝑖 = 1,2, . . . , 𝑛 (3)
𝑥 𝑖𝑗 = 0 , untuk 𝑖 = 𝑗 (4)
2. Variabel keputusan 𝑥 𝑖𝑗 𝑘 merupakan bilangan biner
𝑥 𝑖𝑗 ∈ {0,1}, ∀𝑖, 𝑗 = 1,2, … , 𝑛 (5)

## Capacitated Vehicle Routing Problem (CVRP)
Vehicle  Routing  Problem  (VRP)  merupakan  bagian  dari  TSP,  artinya  VRP  merupakan  TSP  dengan menyertakan  kendala  satu  kendaraan  dengan  kapasitas  [25].  Beberapa  komponen  beserta karakteristiknya yang terdapat dalam masalah VRP yaitu; depot, jaringan jalan, konsumen, kendaraan, pengemudi [32].
Capacitated Vehicle Routing Problem (CVRP) merupakan salah satu variasi dari masalah VRP dengan penambahan kendala kapasitas kendaraan yang terbatas. CVRP dapat direpresentasikan sebagai suatu graf  berarah  berbobot  ( weighted  directed  graph)  dilambangkan  dengan 𝐷 = (𝑉, 𝐴) dimana 𝑉  = {𝑣 𝑖 |𝑖 = 1,2, … , 𝑛} dapat pula ditulis dengan 𝑉 = {𝑣 1 , 𝑣 2 , 𝑣 3 , . . . , 𝑣 𝑛 } adalah himpunan nodes dan 𝐴 = {(𝑣 𝑖 , 𝑣 𝑗 )|𝑣 𝑖 , 𝑣 𝑗 ∈ 𝑉 𝑖≠𝑗 } adalah himpunan sisi ( edges) yang menghubungkan himpunan nodes. Node 𝑣 𝑖 dinyatakan sebagai depot dan yang lainnya adalah konsumen. Setiap elemen dari edges menyatakan jarak.  Setiap nodes  memiliki  permintaan  (demand)  yang  dinotasikan  sebagai 𝑞 𝑖 dengan 𝑖 = {1, 2, 3, … , 𝑛} .  Himpunan 𝐾 = {𝑘 1 , 𝑘 2 , 𝑘 3 , … , 𝑘 𝑚 } merupakan  kumpulan  kendaraan  yang  homogen. Kapasitas kendaraan yang digunakan dinotasikan dengan 𝑄 [31].
Diberikan 𝑣 𝑖𝑗 adalah  jarak  dari node  i  ke  node  j  (v ij merupakan  bilangan nonnegative).  Jarak diasumsikan simetrik (𝑣 𝑖𝑗 = 𝑣 𝑗𝑖 ) dan (𝑣 𝑖𝑖 = 𝑣 𝑗𝑗 = 0) . Permasalahan tersebut kemudian dapat dibuat menjadi model matematika dengan tujuan meminimumkan total jarak tempuh perjalanan kendaraan. Didefinisikan variabel keputusan:
𝑥 𝑖𝑗 𝑘 = { 1, 𝐽𝑖𝑘𝑎 𝑘𝑒𝑛𝑑𝑎𝑟𝑎𝑎𝑛 𝑘 𝑚𝑒𝑛𝑔𝑢𝑛𝑗𝑢𝑛𝑔𝑖 𝑛𝑜𝑑𝑒 𝑣 𝑗 𝑠𝑒𝑡𝑒𝑙𝑎ℎ 𝑛𝑜𝑑𝑒  𝑣 𝑖 0, 𝑠𝑒𝑙𝑎𝑖𝑛𝑛𝑦𝑎
𝑦 𝑖 𝑘 = { 1, 𝐽𝑖𝑘𝑎 𝑛𝑜𝑑𝑒 𝑣 𝑖 𝑑𝑖𝑙𝑎𝑦𝑎𝑛𝑖 𝑜𝑙𝑒ℎ 𝑘𝑒𝑛𝑑𝑎𝑟𝑎𝑎𝑛 𝑘 0, 𝑠𝑒𝑙𝑎𝑖𝑛𝑛𝑦𝑎
Keterangan variabel:
𝐷 = (𝑉, 𝐴) 𝑉 = Himpunan nodes {𝑣 1 , 𝑣 2 , 𝑣 3 , . . . , 𝑣 3 } , dimana 𝑣 1 adalah depot dan {𝑣 2 , 𝑣 3 , . . . , 𝑣 3 } adalah konsumen.
𝐴 = Himpunan sisi berarah (arcs) {(𝑣 𝑖 , 𝑣 𝑗 )|𝑣 𝑖 , 𝑣 𝑗 ∈   𝑉 𝑖≠𝑗 } . 𝑣 𝑖𝑗 = Jarak antara nodes 𝑖 ke nodes 𝑗 . 𝑞 𝑖 = Permintaan konsumen ke 𝑖, 𝑖 ∈ 𝑉 . 𝑄 = Kapasitas masing-masing kendaraan 𝑘 𝑖 ∈ 𝐾, 𝑖 = {1,2,3, … , 𝑛} . 𝐾 = {𝑘 1 , 𝑘 2 , 𝑘 3 , … , 𝑘 𝑚 } kendaraan seragam yang digunakan.
Fungsi tujuan untuk meminimumkan total jarak tempuh kendaraan. Jika 𝑍 adalah fungsi tujuan, maka:
𝑀𝑖𝑛 𝑍 = ∑ ∑ ∑ 𝑣 𝑖𝑗 𝑥 𝑖𝑗 𝑘 𝑚 𝑘=1 𝑛 𝑗=1 𝑛 𝑖=1 (6)
Kendala: 1. Setiap node hanya boleh dikunjungi tepat satu kali oleh 1 kendaraan.
∑ ∑ 𝑥 𝑖𝑗 𝑘 𝑛 𝑗=1 𝑚 𝑘=1 = 1, ∀𝑖 ∈ 𝑉 (7)
2. Kendaraan yang telah mengunjungi node 𝑖 , kendaraan 𝑘 harus meninggalkan node tersebut menuju node lain.
∑ 𝑥 𝑖𝑗 𝑘 𝑛 𝑗=1 − ∑ 𝑥 𝑗𝑖 𝑘 𝑛 𝑗=1 = 0, ∀𝑖 ∈ 𝑉, ∀𝑘 ∈ 𝐾 (8)
3. Total jumlah permintaan konsumen dalam satu rute tidak melebihi kapasitas kendaraan.
∑ 𝑞 𝑖 𝑛 𝑖=1 ∑ 𝑥 𝑖𝑗 𝑘 𝑛 𝑗=1 ≤ 𝑄, ∀𝑘 ∈ 𝐾 (9)
4. Setiap rute perjalanan kendaraan berakhir dan didepot.
∑ 𝑥 1𝑗 𝑘 𝑛 𝑗=1 = 1, ∀𝑘 ∈ 𝐾 (10)
5. Setiap rute perjalanan kendaraan berakhir dan didepot.
∑ 𝑥 𝑖1 𝑘 𝑛 𝑗=1 = 1, ∀𝑘 ∈ 𝐾 (11)
6. Variabel keputusan 𝑥 𝑖𝑗 𝑘 merupakan bilangan biner.
𝑥 𝑖𝑗 𝑘 {0,1}, ∀𝑖, 𝑗 ∈ 𝑉, ∀𝑘 ∈ 𝐾 (12)
Variabel  keputusan  hanya  akan  terdefinisi  jika  jumlah  permintaan node 𝑣 𝑖 dan node 𝑣 𝑗 tidak melebihi kapasitas kendaraan. Apabila kapasitas kendaraan tidak memadahi untuk konsumen berikutnya maka kendaraan harus mengisi muatan di depot sehingga akan terbentuk rute baru.

## Algoritma Tabu Search
Konsep dasar dari Algoritma Tabu Search yaitu menuntun setiap tahapannya agar dapat menghasilkan solusi yang paling optimum tanpa terjebak ke dalam solusi awal yang ditemukan selama tahapan ini berlangsung.  Tujuan  dari  Algoritma  Tabu  Search  yaitu  mencegah  terjadinya  perulangan  dan ditemukannya solusi yang sama pada suatu iterasi yang akan digunakan lagi pada iterasi selanjutnya. Algoritma Tabu Search memiliki Lima langkah utama yang digunakan untuk menyelesaikan VRP, yaitu: 1. Representasi Solusi
Representasi solusi yang digunakan Algoritma Tabu Search untuk menyelesaian VRP adalah solusi feasible yang ditulis sebagai suatu urutan titik-titik (nodes), dimana tiap titik (node) hanya terlihat sekali dalam urutan. Titik ( node) tersebut merepresentasikan depot dan konsumen.
2. Pembentukan Solusi Awal ( Initial Solution)
Solusi Awal  merupakan langkah pertama yang dilakukan dalam proses Algoritma  Tabu Search. Solusi  awal  dapat  dibentuk  menggunakan  metode  random  atau  metode  heuristik  yang  akan diperbaiki  pada  iterasi  berikutnya.  Langkah  berikutnya  mencari  solusi Neighborhood.  Solusi Neighborhood merupakan solusi alternatif yang diperoleh dengan melakukan perpindahan  node ( move). Setiap perpindahan node (move) akan menghasilkan satu solusi Neighborhood. Perpindahan
node  (move)  dapat  dilakukan  menggunakan  metode  heuristik  yaitu  Exchange,  2-Opt,  Cross Exchange dan Relocated.
3. Tabu List
Tabu list berisi atribut move yang telah ditemukan sebelumnya. Ukuran Tabu List akan bertambah seiring meningkatnya ukuran masalah agar dapat menghasilkan kualitas solusi yang baik. Ukuran Tabu List yang terlalu panjang tidak akan menghasilkan kualitas solusi yang baik karena dapat menyebabkan terlalu banyak perpindahan node (move) yang di larang [13].
4. Kriteria Aspirasi ( Aspiration Criteria)
Kriteria aspirasi adalah suatu metode untuk membatalkan status tabu [13].
5. Kriteria Pemberhentian ( Termination criteria)
Kriteria pemberhentian yang digunakan yaitu setelah semua iterasi yang telah ditentukan terpenuhi.

## Safety Stock
Safety  Stock  adalah  rata-rata  produk  yang  dijadikan  sebagai  pengendalian  dari  risiko.  Produk pengendalian ini juga dipengaruhi oleh service level yang mengikuti distribusi normal karena service level berkaitan erat dengan toleransi yang diberikan perusahaan atas tidak terpenuhinnya permintaan produk yang ada. Lead time adalah lamanya waktu antara mulai dilakukannya pemesanan bahan baku sampai dengan kedatangan bahan baku yang dipesan tersebut dan diterima di depot persediaan [16]. Rumusan dari total persediaan yang harus dipenuhi adalah Safety Stock, Perhitungan untuk mencari jumlah Safety Stock adalah sebagai berikut: [11].
𝑆𝑆 = 𝑍𝛼 × 𝑆𝑑𝑙 (13)
dan,
𝑆𝑑𝑙 = √(𝑑 2 × 𝑆𝑙 2 ) + (𝑙 × 𝑆𝑑 2 ) (14)
𝑆𝑆 = 𝑍𝛼 × √(𝑑 2 × 𝑆𝑙 2 ) + (𝑙 × 𝑆𝑑 2 ) (15)
Selanjutnya untuk mencari nilai 𝑆𝑑 dan 𝑆𝑙 menggunakan persamaan berikut ini;
𝑆𝑑 = √ ∑ (𝑑 𝑖 −𝑑) 2 𝑛 𝑖=1 𝑟−1 (16)
dan,
𝑆𝑙 = √ ∑ (𝑙 𝑖 −𝑙) 2 𝑛 𝑖=1 𝑟−1 (17)
Keterangan:
𝑆𝑆 = Persediaan pengaman ( Safety Stock)
𝑍𝛼 = Safety factor untuk resiko out stock
𝑆𝑑 = Standar deviasi permintaan perpriode
𝑆𝑙 = Standar deviasi lead Time 𝑑 𝑖 = Jumlah permintaan priode ke- 𝑖 𝑙 𝑖 = Jumlah lead time priode ke- 𝑖
𝑑 = Rata-rata permintaan
𝑙 = Rata-rata lead time
𝑟 = Ukuran sampel

## Metode Penelitian
Data yang digunakan dalam penelitian ini adalah data permintaan konsumen, jarak antar konsumen, jarak depot ke konsumen, kapasitas kendaraan PT IAP sebagai salah satu distributor air mineral untuk wilayah Daerah Istimewa Yogyakarta dan lama lead time. Diperoleh data dengan jumlah konsumen sebanyak  19,  depot  sebanyak  satu,  kapasitas  maksimal  kendaraan  yaitu  60  karton,  data lead  time selama satu sampai tiga hari, serta jarak antar konsumen. Kemudian dapat dilakukan proses perhitungan dengan langkah-langkah sebagai berikut:
1. Pembentukan Solusi awal ( initial solution)
Solusi awal pada pendistribusian produk air mineral ini dibentuk menggunakan metode heuristik Nearest Neighbor pada TSP.
2. Menentukan solusi Neighborhood dengan evaluasi move
Pada  Algoritma  Tabu  Search,  solusi Neighborhood  merupakan  solusi  alternatif  yang  diperoleh dengan melakukan pertukaran node (move). Setiap perpindahan node (move) akan menghasilkan satu  solusi Neighborhood.  Perpindahan  node  (move)  dilakukan  menggunakan  metode  heuristik yaitu Exchange, Relocate, 2-Opt dan Cross Exchange.
3. Analisa solusi optimal VRP menggunakan Algoritma Tabu Search. Solusi optimal diperoleh menggunakan Algoritma Tabu Search setelah semua iterasi dipenuhi.

## Hasil dan Pembahasan
Penerapan Algoritma Tabu Search pada kasus pendistribusian produk air mineral menggunakan data permintan (Tabel 1) dan jarak (Tabel 2) sebagai berikut:
Tabel 1. Data permintaan konsumen produk air mineral.
No. Konsumen Permintaan No. Konsumen Permintaan 1 A01 - 11 A11 1 karton 2 A02 25 karton 12 A12 2 karton 3 A03 6 karton 13 A13 3 karton 4 A04 2 karton 14 A14 2 karton 5 A05 10 karton 15 A15 1 karton 6 A06 11 karton 16 A16 2 karton 7 A07 1 karton 17 A17 2 karton 8 A08 1 karton 18 A18 2 karton 9 A09 1 karton 19 A19 2 karton 10 A10 1 karton 20 A20 2 karton
Tabel 2. Jarak depot ke konsumen dan antar konsumen dalam satuan kilometer.
Kemudian  proses  perhitungan  Algoritma  Tabu  Search  secara  manual  dilakukan  dengan  langkah- langkah sebagai berikut:
1. Langkah pertama yang dilakukan adalah menentukan solusi awal  sebagai  solusi optimum pada iterasi ke-0 dengan metode Nearest Neighboor, diperoleh solusi TSP awal A01-A02-A17-A15-A09- A10-A08-A06-A03-A11-A16-A14-A19-A05-A18-A20-A12-A13-A07-A04-A01.  Solusi  awal  yang diperoleh  kemudian  dibatasi  berdasarkan  kapasitas  kendaraan  dan  permintaan  konsumen.  Jika kapasitas  kendaraan  sudah  tidak  dapat  memenuhi  permintaan  konsumen  berikutnya  maka kendaraan kembali lagi ke depot untuk mengisi muatan dan melanjutkan perjalanan dengan rute yang baru sampai semua node dikunjungi. Total permintaan tiap rute merupakan total permintaan tiap konsumen yang sudah dilewati oleh kendaraan pada tiap rute. Total jarak tiap rute merupakan jumlah  jarak  yang  dilalui  kendaraan  saat  mengantarkan  pesanan  kepada  konsumen  dalam  tiap rute. Diperoleh rute VRP awal pada Tabel 3:

## Tabel 3. Solusi awal VRP

## .
Rute Solusi Awal VRP Kapasitas Jarak 1 A01-A02-A17-A15-A09-A10-A08-A06-A03-A11-A16-A14-A19-A01 0+25+2+1+1+1+1+11+6+1+2+2+2+0 55 3,3+3+6,1+3,9+9,75+1,7+1,6+1,4+1,5+3,1+4+3,6+23,2 57,15 2 A01-A05-A18-A20-A12-A13-–A07-A04-A01 0+10+2+2+2+3+1+2+0 22 24,7+0,034+1,2+8,4+4,2+25,4+13,6+14,7 92,234 Total 77 149,384
2. Langkah ke-2 yaitu menentukan iterasi selanjutnya dan mencari solusi Neighborhood TSP. Solusi Neighborhood TSP diperoleh dari node yang ditukar dan dihasilkan menggunakan empat metode Exchange, Relocate, 2-Opt atau Cross Exchange yang dipilih secara random sedemikian sehingga diperoleh  solusi Neighborhood  terbaik.  Berikut  merupakan  salah  satu  solusi  Neighborhood  TSP yang diperoleh menggunakan metode Relocated pada solusi Neighborhood TSP ke sebelas.
Tabel 4. Salah satu solusi Neighborhood TSP menggunakan metode Relocated .
No.  Metode Solusi Neighborhood TSP Jarak 11 Relocated A01-A02-A17-A15-A09-A10-A08-A11-A06-A03-A16-A14-A19-A05- A18-A20-A12-A13-A07-A04-A01 A08  A11  3,3+3+6,1+3,9+0,75+1,7+1,8+0,55+1,4+1,6+4+3,6+1,5+0,034+ 1,2+8,4+4,2+25,4+13,6+14,7 100,734
3. Langkah selanjutnya yaitu memilih solusi terbaik diantara solusi Neighborhood yang telah diperoleh pada langkah sebelumnya. Solusi terbaik adalah solusi denga total jarak terpendek.
4. Setelah  diperoleh  solusi  terbaik  pada  langkah  sebelumnya  maka node  yang  telah  digunakann dimasukan kedalam tabu list sehingga tidak akan digunakan pada iterasi selanjutnya.
5. Proses  Algoritma  Tabu  search  diulang  kembali mulai  dari  langkah  2  dan  akan berhenti  ketika kriteria pemberhentian terpenuhi. Diperoleh solusi optimal menggunakan Algoritma Tabu Search kemudian direpresentasikan pada peta Yogyakarta dan sekitarnya.

## Tabel 5. Solusi Optimal VRP.
Rute Solusi terbaik Kapasitas Jarak 1 A01-A02-A04-A15-A06-A11-A08-A10-A09-A03-A16-A14-A19-A01 55 karton 60,4 km 2 A01-A05-A18-A20-A12-A13-A07-A17-A01 22 karton 78,834 km Total 77 karton  138,834 km
Rute terpendek yang diperoleh berdasarkan perhitungan manual yaitu sebesar 138,834 km.
Gambar 1. Rute terpendek yang diperoleh.
Perhitungan  sederhana Safety  Stock  dapat  membantu  menyelesaikan  persediaan  pengaman  yang harus  dipersiapkan  oleh  perusahaan  dan  mengurangi  tingkat  kerugian. Safety  Stock  dan  CVRP merupakan dua permasalahan yang berbeda, tetapi saling terkait dalam proses pelayanan perusahaan terhadap konsumen.
Proses perhitungan sederhana persediaan pengaman ( Safety Stock) untuk pendistribusian air mineral Daerah Istimewa Yogyakarta. Asumsi yang digunakan adalah sebagai berikut:
1). Menggunakan data laporan pemesanan konsumen sebelumnya.
2). Lead Time selama 1 sampai 3 hari.
3). Tingkat kepercayaan (𝑍𝛼) 95 %
Tabel 6. Data laporan pemesanan.
No Tanggal Total Keterangan 1 07 Agustus 2017 71 karton Senin pertama 2 14 Agustus 2017 55 karton Senin kedua 3 21 Agustus 2017 95 karton Senin ketiga 4 28 Agustus 2017 45 karton Senin keempat 1. Akan dicari nilai Safety Stock dengan lead time 3 hari 𝑙 = 3: 3: 3: 3 ℎ𝑎𝑟𝑖
𝑑 = 71+55+95+45
4
𝑙 = 3+3+3+3
4
𝑑 = 66,5
𝑙 = 3
𝑑 2 = 4.422,25
2. Akan ditentukan standar deviasi lead time (𝑆𝑙)
𝑆𝑙 = √ ∑ (𝑙 𝑖 − 𝑙) 2 4 𝑖=1 𝑟 − 1 = √ (3 − 3) 2 + (3 − 3) 2 + (3 − 3) 2 + (3 − 3) 2 4 − 1 = √ 0 3 = 0
3. Akan ditentukan standar deviasi permintaan perpriode (𝑆𝑑)
𝑆𝑑 = √ ∑ (𝑑 𝑖 − 𝑑) 2 4 𝑖=1 𝑟 − 1 = √ (71 − 66,5) 2 + (55 − 66,5) 2 + (95 − 66,5) 2 + (45 − 66,5) 2 4 − 1

## = 21,809783737274
4. Akan ditentukan standar deviasi permintaan dan lead time
𝑆𝑑𝑙 = √(𝑑 2 × 𝑆𝑙 2 ) + (𝑙 × 𝑆𝑑 2 )
= √(4.422,25 × 0) + (3 × 475,66666666667)
= √478,66666666667
= 21,878452108563
𝑆𝑆 = 𝑍𝛼 × 𝑆𝑑𝑙
= 𝑍𝛼 × √(𝑑 2 × 𝑆𝑙 2 ) + (𝑙 × 𝑆𝑑 2 )
= 1,645 × 21,8784521085
= 35,990053718586
Jadi,  diperoleh nilai safety  stock  untuk  lead  time  berbeda hari adalah 35,9900537185,  sehingga dapat disimpulkan untuk total persediaan dengan lead time 3 harinya selama satu bulan ±35 karton. Berdasarkan data informasi yang diperoleh dari perusahaan dapat ditarik kesimpulan bahwa lead time
cenderung konstan maka perhitungan sederhana Safety Stock akan menghasilkan nilai yang cenderung konstan juga. Berikut merupakan conter example untuk perhitungan Safety Stock.
1. Akan dicari nilai Safety Stock dengan lead time berbeda
𝑙 = 1: 2: 3: 2 ℎ𝑎𝑟𝑖 𝑑 = 71+55+95+45 4
𝑙 = 1+2+3+2
4
𝑑 = 66,5 𝑙 = 2 𝑑 2 = 4.422,25
2. Akan ditentukan standar deviasi lead time (𝑆𝑙)
𝑆𝑙 = √ ∑ (𝑙 𝑖 − 𝑙) 2 4 𝑖=1 𝑟 − 1 = √ (1 − 2) 2 + (2 − 2) 2 + (3 − 2) 2 + (2 − 2) 2 4 − 1
= √0,66666666667 = 0,81649696580928
3. Akan ditentukan standar deviasi permintaan perpriode (𝑆𝑑)
𝑆𝑑 = √ ∑ (𝑑 𝑖 − 𝑑) 2 4 𝑖=1 𝑟 − 1 = √ (71 − 66,5) 2 + (55 − 66,5) 2 + (95 − 66,5) 2 + (45 − 66,5) 2 4 − 1
= √475,66666666667 = 21,809783737274
4. Akan ditentukan standar deviasi permintaan dan lead time
𝑆𝑑𝑙 = √(𝑑 2 × 𝑆𝑙 2 ) + (𝑙 × 𝑆𝑑 2 )
= √(4.422,25 × 0,81649696580928) + (2 × 475,66666666667)
= √(3.610,75200500885) + (2 × 475,66666666667)
= √4.088,41867167552 = 63,940743440122

## 𝑆𝑆 = 𝑍𝛼 × 𝑆𝑑𝑙
= 𝑍𝛼 × √(𝑑 2 × 𝑆𝑙 2 ) + (𝑙 × 𝑆𝑑 2 )
= 1,645 × 63,940743440122
= 105,182522959001
Jadi, diperoleh nilai safety stock untuk lead time berbeda hari adalah 105,182522959001, sehingga dapat disimpulkan untuk total persediaan dengan lead time yang harinya berbeda selama satu bulan ± 105 karton.

## Kesimpulan
Berdasarkan hasil pembahasan tentang aplikasi Algoritma Tabu Search dan Safety Stock pada penentuan rute  distribusi  air  mineral  wilayah  Daerah  Istimewa  Yogyakarta  dapat  ditarik  kesimpulan  sebagai berikut:
1. Proses  perhitungan  Algoritma  Tabu  Search  terdiri  dari  Lima  langkah.  Langkah  pertama  yaitu menentukan solusi awal sebagai iterasi 0 dan menetapkan nilai solusi awal sebagai nilai solusi optimum  sementara.  Langkah  kedua  yaitu  mencari  solusi Neighborhood  (solusi  alternatif)  yang tidak melanggar tabu atau memenuhi kriteria aspirasi. Langkah ketiga yaitu memilih solusi terbaik diantara  solusi Neighborhood  pada  tiap  iterasi  yang  akan  disimpan  sebagai  solusi  optimum. Langkah keempat yaitu memperbarui Tabu List dengan memasukkan node yang telah digunakan pada pertukaran node di langkah ketiga. Langkah terakhir yaitu apabila kriteria pemberhentian dipenuhi maka proses perhitungan Algoritma Tabu Search berhenti dan diperoleh solusi terbaik (optimum), jika tidak dipenuhi maka proses kembali berulang dimulai pada langkah kedua.
2. Pada  kasus  perusahaan  air  mineral  diperoleh  solusi  terbaik  (optimum)  dengan  menggunakan Algoritma Tabu Search. Jarak terpendek yang diperoleh menggunakan perhitungan manual adalah 138,834 km. Berdasarkan hasil perhitungan dihasilkan solusi rute:
Tabel 6. Solusi rute terbaik (optimum).
Rute  Solusi terbaik Kapasitas Jarak 1 A01-A02-A04-A15-A06-A11-A08-A10-A09-A03-A16-A14-A19-A01 55 karton 60,4 km 2 A01-A05-A18-A20-A12-A13-A07-A17-A01 22 karton 78,834 km Total 77 karton  138,834 km 3. Nilai Safety Stock yang diperoleh dengan kasus perusahaan air mineral yang mengalami lead time satu sampai tiga hari adalah penambahan ± 35 karton di gudang sebagai Safety Stock selama satu bulan.

## Referensi
[1] Alkallak, Isra Natheer, & Shaban, Ruqaya Z. 2008. Tabu Search Method For Solving The Traveling Salesman Problem. Raf. J. of Comp. & Math’s. 5:141-153
[2] Al-Mahally,  Imam  Jalaluddin  &  Imam  Jalaluddin  As-suyutti.  1990. Tafsir  Jalalain  Berikut  Asbab  Annujulnya,  Jilid  I.  Bandung: Penerbit Sinar Baru.
[3] Ballou, Ronald H. 2006. Bussiness Logistic Management. United State: Prenticehall.
[4] Christopher, Martin. 2011. Logistics & Supply Chain Management Fourt Edition. United Stated of America: Prentice Hall, Inc.
[5] Cordeau, J.F., Laporte, G., Savelsbergh, M.W., et al. 2002. Vehicle Routing. Handbook on OR & MS.
[6] Gendreau, M. Hertz, A. G. Laporte. 1994. A Tabu Search Heuristic for the Vehicle Routing Problem. Management Science.
[7] Glover, F & Kochenberger, G.A. (Eds). 2003. Handbook of Metaheuristics. Dordrecht: Kluwer Academic Publisher.
[8] Glover, F & Laguna, M. 1997. Tabu Search. Massachusetts: Kluwer Academic Publisher.
[9] Glover, F & Marti, R. 2006. Metaheuristic Produres for Training Neural Networks. Alba and Marti (Eds.).Springer.
[10] Gooddairrie, Edgar G. & Parmenter, Michael M. 2002. Discrete Mathematics with Graph Theory Second Edition. United States of America: Prentice-Hall, Inc.
[11] Heyzer, Jay & Barry, Render. 2005. Operation management, 7 Th edition. Jakarta: Penerbit salemba empat.
[12] Kallehauge, B., J. Larsen, dan O.B.G. Marsen. 2001. Lagrangean duality applied on vehicle routing problem with time windows. Technical Report. IMM. Technical University of Denmark.
[13] Kismono, Gugup. 2001. Pengantar bisnis, Edisi pertama. Yogyakarta: BPFE. Indonesia.
[14] Kusumadewi, S., & Purnomo, H. 2005. Penyelesaian Masalah Optimasi dengan Teknik-Teknik Heuristik. Yogyakarta: Graha Ilmu. Indonesia.
[15] Manongga, Danny dan Nataliani, Yessica. 2013. Matematika Diskrit. Jakarta: Prenadamedia Group. Indonesia.
[16] Nasution, Arman & Prasetyawan, Yudha. 2008. Perencanaan Dan Pengendalian Produksi. Yogyakarta: Graha Ilmu Indonesia.
[17] Nurmatias. 2010. Penentuan Stock Material Chemical dengan Simulasi Monte Carlo. Jurnal Universitas Islam Indonesia. Yogyakarta.
[18] Pakpahan, Efendi. 2009. Manajemen Pemasaran. Yogyakarta: BPFE. Indonesia.
[19] Parwadi, Moengin. 2011. Metode Optimasi. Bandung: Muara Indah. Indonesia.
[20] Raditya, Aji. 2009. Penggunaan Metode Heuristik dalam Permasalahan Vehicle Routing Problem dan Implementasinya di PT Nippon Indosari Corpindo.Skripsi, tidak diterbitkan, Institut Pertanian Bogor.
[21] Rahmat, Basuki. 2011. Perbandingan Genetic Algorithm, Multiple Ant Colony System, dan Tabu Search untuk Penyelesaian Vehicle Routing Problem With Time Windows (VRPTW).Jawa Timur.
[22] Rosen, Kenneth H. 2012. Discrete Mathematics and Its Application Seventh Edition. NewYork: Mc-Graw-Hill.
[23] Salaki, D.T. 2009. Penyelesaian vehicle routing problem menggunakan beberapa metode heuristic konstruktif. Tesis. Bogor. Sekolah pasca sarjana institute pertanian.
[24] Siregar, W.D. 2012. Analisis kualitas Fisik, Biologi, dan Kimia pada Air Minum dalam Kemasan barbagai merk yang dijual di Kota Medan. Fakultas kesehatan masyarakat. Universitas Sumatera utara. Medan.
[25] Solomon, M & Desrosiers, J. 1988. Time window constrained routing and scheduling Problems.Transportation science.
[26] Sulistiono. 2015. Rancang Bangun Vehicle Routing Problem Menggunakan Algoritma Tabu Search. Skripsi, tidak diterbitkan. UIN Sunan Kalijaga: Yogyakarta.
[27] Suyanto. 2010. Algoritma Optimasi Deterministik atau Probabilitik. Yogyakarta: Graha Ilmu.
[28] Taha, H. A. 2003. Operations Research: An Introduction seventh Edition. Prentice Hall, Inc.
[29] Tarantilis, C. D., Ioannou, G., Kiranoudis, C. T., dan Prasdacos, G. P. 2005. Solving the open vehicle routing problem via single parameter meta-heuristic algorithm. Journal of the Operational research Society.
[30] Tjiptono, Fandy. 2008. Strategi Pemasaran. Yogyakarta: Penerbit Andi. Indonesia.
[31] Tonci Caric, Hrvoje Gold. 2008. Vehicle Routing Problem. University of Zagreb: In-teh Croatia.
[32] Toth, P., & Vigo. D. 2002. Vehicle Routing Problem, Methods, and Applications Second Edition. Philadelphia: Society for Industrial and Applied Mathematics.