1) Mahasiswa di Fakultas Teknik Jurusan Teknik Industri Universitas Katolik Widya Mandala Surabaya
2) Staf Pengajar di Fakultas Teknik Jurusan Teknik Industri Universitas Katolik Widya Mandala Surabaya

## PENERAPAN ALGORITMA GENETIK UNTUK PENYELESAIAN MASALAH VEHICLE ROUTING DI PT.MIF
William Tanujaya 1) ,  Dian Retno Sari Dewi 2) , Dini Endah 2)
E-mail: williamtanujaya@msn.com

## ABSTRAK
Transportasi merupakan komponen yang vital dalam manajemen logistik suatu perusahaan. Pengurangan biaya  transportasi  dapat  dilakukan  dengan  menentukan  rute  pengiriman  yang  efisien.Penulisan  penelitian  ini bertujuan untuk menghasilkan suatu rute pengiriman yang memiliki total jarak tempuh terpendek Vehicle Routing Problem  with  Time  Windows  (VRPTW)  merupakan  permasalahan  membentuk  sekumpulan  rute  yang  optimal dengan  menggunakan  model  matematis  berdasarkan  pertimbangan  jarak  dan  waktu.untuk  dapat  memperoleh solusi  dari  permasalahan  ini  digunakan  algoritma  genetik  (GA),  Genetic  Algorithm  dipilih  karena  Genetic Algorithm  tidak  mempunyai  kriteria  khusus  yang  dijumpai  pada  algoritma  heuristik  lainnya,  maka  waktu komputasi juga relatif lebih singkat, serta dapat menghasilkan beberapa alternatif solusi yang mempunyai nilai obyektif  yang  sama.  Karena  GA  bersifat  iteratif  dan  jadwal  pengiriman  di  PT  MIF  berubah-ubah,  maka  perlu dibuat  suatu  program  khusus  untuk  menyelesaikan  tiap  iterasi  dan  tiap  perubahan  customer  dan  jadwal  di  PT MIF. Dari  hasil penelitian  diperoleh rute untuk kendaraan 1  adalah dari depo menuju customer 6, customer 1, customer 18, customer 7 kemudian kembali ke depo, dengan total jarak tempuh 140km,sedangkan rute kendaraan 2  dari  depo  menuju  customer  8  kemudian  kembali  lagi  ke  depo  dengan  total  jarak  17,9  km.  Persentase penghematan  yang  dapat  diperoleh  apabila  rute  hasil  perhitungan  metode  optimasi  ini  diterapkan  pada perusahaan adalah sebesar 7,88 %.
Kata kunci : transportasi, Vehicle Routing Problem with Time Windows ( VRPTW ), Genetic Algorithm .

## PENDAHULUAN
Transportasi  merupakan  komponen  yang vital dalam manajemen logistik suatu perusahaan. Salah satu faktor yang menentukan dalam  manajemen  logistik  adalah  penentuan jalur distribusi yang akan berpengaruh terhadap biaya  transportasi.  Pada  umumnya  biaya transportasi  menyerap  persentase  biaya  logistik yang  lebih  besar  daripada  aktivitas  logistik lainnya.  Oleh  karena  itu,  untuk  mengurangi biaya transportasi, diperlukan sistem transportasi  yang  efisien.  Dengan  menurunnya biaya  transportasi,  harga  produk  juga  dapat menurun dan lebih mudah bersaing dengan para kompetitor dalam hal harga.
Peningkatan efisiensi dari sistem transportasi dapat dilakukan dengan
memaksimalkan  utilitas  dari  alat  transportasi yang ada. Untuk mengurangi biaya transportasi dan juga untuk meningkatkan pelayanan kepada customer, perlu dicari rute atau jalur transportasi  terbaik  yang  dapat  meminimalkan jarak  dan  waktu.  Permasalahan  yang  bertujuan untuk  membuat  suatu  rute  yang  optimal,  untuk suatu kelompok kendaraan, agar dapat melayani sejumlah  konsumen  disebut  sebagai Vehicle Routing Problem
Dalam beberapa dekade ini, permasalahan VRP mengalami beberapa
perkembangan,  sehingga  muncul  berbagai macam  variasi  dari VRP ,  salah  satunya  adalah Vehicle  Routing  Problem  with  Time  Windows ( VRPTW ).  Untuk VRPTW ,  selain  adanya kendala kapasitas kendaraan, terdapat tambahan kendala  yang  mengharuskan  kendaraan  untuk melayani konsumen pada time frame tertentu.
Banyak  metode  yang  digunakan  dalam menyelesaikan  permasalahan VRP ini,  salah satunya  dengan  Algoritma  Genetika  / Genetic Algorithm . Algoritma Genetik merupakan suatu prosedur  penelusuran  yang  berdasarkan  pada mekanisme  dari natural  selection dan natural genetics yang dapat digunakan untuk memecahkan combinatorial optimization problems yang  sulit.  Algoritma  Genetik  ini diperkenalkan  oleh John  Holland dan  para peneliti dari University of Michigan , pada tahun 1976.  Selain  digunakan  untuk  menyelesaikan masalah mengenai vehicle routing and scheduling, Algoritma  Genetik  juga  dapat digunakan untuk menyelesaikan berbagai permasalahan  seperti  misalnya scheduling  and sequencing,reliability design, facility layout dan lain – lain
Genetic Algorithm dipilih karena Genetic  Algorithm tidak  mempunyai  kriteria khusus  yang  dijumpai  pada  algoritma  heuristik lainnya  dalam  menyaring  kualitas  solusi,  oleh
karena  itu  waktu  komputasi  juga  relatif  lebih singkat,  serta  dapat  menghasilkan  beberapa alternatif solusi yang mempunyai nilai obyektif yang sama.
Dari  skripsi  sebelumnya  dengan  judul ”Perencanaan  Rute  Transportasi  Terpendek pada PT.MIF dengan Model VRPTW ”
(Martha,2005)  yang  membahas  permasalahan
VRPTW dengan menggunakan algoritma Branch & Bound yang mencari solusi optimum dengan  membandingkan  solusi  dengan  setiap solusi  pada  semua  alternatif  kombinasi  untuk memastikan bahwa solusi yang didapat merupakan  solusi  global [1] ,  sedangkan  di penelitian  ini  permasalahan VRPTW akan diselesaikan  dengan  menggunakan Genetic Algorithm yang  mencari  solusi  terbaik  dengan mekanisme  berupa  kombinasi  dari  pencarian acak secara terstruktur.
PT. MITRA INTERTRANS
FORWARDING  (MIF)  yang  tergabung  dalam MERATUS  GROUP  merupakan  perusahaan yang  bergerak  di  bidang  jasa  pelayaran. Perusahaan ini menyediakan layanan baik untuk domestik maupun internasional. Dalam pengiriman ke tempat – tempat tujuan, PT. MIF menggunakan rute yang hanya didasarkan pada preferensi dan pengalaman kurir saja. Perusahaan belum mempunyai prosedur penentuan rute yang optimal. Dengan banyaknya jumlah customer , perusahaan membutuhkan  rute  pengiriman  yang  optimal agar  dapat  menghemat  biaya  transportasi.  Oleh karena  itu,  diperlukan  suatu  program  khusus yang  dapat  memberikan    solusi  rute  optimal untuk  tiap  kali  pengiriman.  Maka  dalam penelitian  ini  akan  dibuat  program  optimasi yang  dapat  memberikan  solusi  rute  optimal dengan perhitungan menggunakan model
VRPTW

## TINJAUAN PUSTAKA
1    Metode Clark Wright Saving Masalah  dalam  menemukan  solusi terbaik pada masalah routing dan penjadwalan  kendaraan  menjadi  semakin sulit dengan pertambahan pembatas permasalahan.  Ada  banyak  hal  yang mempengaruhi  antara  lain, time  windows , kapasitas  kendaraan  perbedaan  kecepatan, rintangan  dalam  perjalanan  dan  lain sebagainya.  Banyak  pendekatan  dianjurkan untuk  memecahkan  masalah  –  masalah kompleks  tersebut.  Akan  tetapi,  sebuah metode  pendekatan  “ saving ”  Clark-Wright telah  digunakan  selama  bertahun  –  tahun
dan  cukup  fleksibel  untuk  menangani daerah  yang  luas  dengan  pembatas  – pembatas  yang  praktis  dan  relatif  cepat komputasinya  untuk  menangani  sejumlah masalah pemberhentian dan dapat membangkitkan  solusi  yang  mendekati optimum.
Pendekatan  “ saving ”  dapat  dijabarkan sebagai berikut :
1. Awalnya, asumsikan bahwa kendaraan  dapat  digunakan  untuk tiap  pelanggan.  Persiapkan  alokasi kendaraan yang menunjukkan jumlah kendaraan dan total  muatan yang tersedia
2. Untuk membantu komputasi, persiapkan  matrik  seperti  yang terlihat  pada  gambar  2.1.  Muatan yang  dikirim  tiap  pelanggan  P i yang terdaftar dalam kolom q. Nilai disebelah  kanan  tiap  sel  adalah jarak d y,z antara P y dan P z , dimana y dan z merupakan penanda pelanggan.  Pada  sel  sebelah  kiri bawah menandakan simpanan ( saving )  S y,z dari  jarak  yang berhubungan dengan P y dan P z . S y,z dihitung dengan S y,z = d o,y + d o,z - d y,z
Load q 1200 9 1700 14 5 12 7 P2 Po P1 P3 P4 1400 23 22 17 10 1500 21
Gambar 1. Matrik Set-up “ Saving ”
3. Cari  matrik  pada  sel  y,z  yang memiliki  nilai  simpan  terbesar  dan mendapatkan  bahwa  pelanggan  z merupakan  calon  untuk  masuk dalam  rute  y,  yang  diikuti  dengan kondisi berikut :
a. f y,o dan f z,o > 0 b. Tambahan pelanggan z pada rute dengan pelanggan y tidak menyebabkan  pelanggaran batas  –  batas  lain  seperti
total waktu dan time windows 4. Pilih sebuah sel dimana 2 tour yang dapat  dikombinasikan  menjadi  1 tour.  Nilai  dari  f y,z =  1  diletakkan pada  sel  yang  terpilih,  dan  semua nilai  f y,z pada  rute  disesuaikan sehingga  jumlah  f y,z melintasi  baris ditambah  f y,z turun  ke  kolom dimana y = z sama dengan  2

## 2.   Metode Nearest Neighbor
Berikut  adalah  langkah  –  langkah  dari metode nearest neighbor :
1. Pilih  lokasi  yang  terdekat  dari depot  untuk  dikunjungi  terlebih dahulu.
2. Dari  lokasi  pertama  yang  terpilih lanjutkan  ke  lokasi  lain  yang terdekat dengan mempertimbangkan kapasitas kendaraan yang tersedia. 3. Bila belum semua lokasi tercantum pada salah satu rute, ulangi langkah 1  (Pengulangan  berhenti,  bila semua  lokasi  telah  masuk  dalam rute)

## 3. Vehicle Routing Problem
Vehicle  Routing  Problem pertama kali  diperkenalkan  oleh  Damtzig  dan Ramser  pada  tahun  1959. VRP sebenarnya merupakan  perkembangan  atau  perluasan dari Travel Salesman Problem (TSP). Versi yang  paling  dasar  dari VRP adalah Capasitated  Vehicle  Routing  Problem ( CVRP )  yang  dapat  dijelaskan  sebagai berikut :
 Suatu  depot  harus  melayani n node/customer.
 Depot  mempunyai  satu vehicle dengan  kapasitas  tertentu  Q  untuk melayani semua node.
 Tiap  node  mempunyai  demand sebesar  q  yang  harus  dipenuhi dalam sekali pelayanan.
 Karena  depot  hanya  mempunyai satu vehicle dengan  kapasitas terbatas,  maka vehicle tersebut harus  secara  periodik  kembali  ke depot  untuk  mengambil  barang untuk  memenuhi  demand  node yang lain ( reloading ).
 Tidak mungkin melayani lebih dari 1 node dalam waktu yang bersamaan ( split delivery )  Solusi dari CVRP adalah sekumpulan rute yang dilalui
vehicle, dimana  tiap  node  hanya dikunjungi sekali saja
Berbeda  dengan CVRP ,  pada VRP jumlah vehicle nya  dapat  lebih  dari  satu.  Dengan demikian split  delivery dapat  dilakukan sedangkan reloading dapat  dihindari.  Dalam perkembangan  selanjutnya, VRP mempunyai cukup banyak variasi, antara lain :
 Vehicle  Routing  Problem  with  Time Windows ( VRPTW )
 Vehicle  Routing  Problem  with  Pickup and Delivery (VRPPD)
 Period Vehicle Routing Problem (PVRP)  Fleet  Size  and  Mix  Vehicle  Routing Problem (FSMVRP)

##  Multi Depot VRP
Vehicle Routing Problem with Time Windows ( VRPTW )
VRP dapat dianalogikan sebagai multiple  TSP.  Namun  pada VRP salesmannya berupa Vehicle dengan  kapasitas  tertentu  dan tiap  node  mempunyai  demandnya  masing  – masing.  Sama  seperti  TSP,  pada VRP tiap vehicle harus berangkat dari suatu depot dengan rute  tertentu  untuk  memenuhi demand node  – node dalam rute tersebut dan kembali ke depot semula.  Setiap vehicle mempunyai  waktu operasional  maksimum  tertentu  dimana  waktu tersebut merupakan waktu maksimal bagi suatu vehicle untuk kembali ke depot.
Gambar 2. VRP sederhana dengan jumlah vehicle 2
Gambar  di  atas  merupakan  suatu  contoh sederhana  dari VRP dengan  2 vehicle. Ada  1 depot  dan  12  node  yang  setelah  di solve maka diperoleh  dua  rute  yang  total  jaraknya  paling minimum
VRPTW adalah  salah  satu  variasi  VRP dimana suatu node, kota, atau konsumen hanya dapat  dilayani  setelah  waktu  awal  yang
ditentukan  ( e i )    dan  tidak  dapat  dilayani  lagi setelah  waktu  akhir  yang  ditentukan  ( l i )  . Dengan  kata  lain  jika  suatu vehicle tiba  atau datang pada suatu node sebelum e i maka vehicle itu harus menunggu sampai e i . Dan jika vehicle itu datang setelah l i maka vehicle tersebut tidak diperbolehkan  untuk  melayani  node  tersebut. Interval  waktu  antara e i dan l i inilah  yang disebut sebagai “ Time Windows ” dibuat  di  dalam  program  komputer. Verifikasi  berguna  untuk  menjamin  bahwa model  simulasi  komputer  mempresentasikan konseptual model yang dimaksudkan. Sedangkan validasi berkaitan dengan penyusunan  model  yang  mempresentasikan sistem  nyata.  Verifikasi  merupakan  proses secara  keseluruhan  untuk  membandingkan perilaku model dengan sistem nyatanya.  Proses  validasi  model  terdiri  dari tiga langkah yaitu face validity , validasi asumsi model dan validasi input-output .
Algoritma Genetik [2]
Algoritma  Genetik  (GA)  merupakan suatu  metode  heuristic  untuk  mencari  solusi optimum  dari  suatu  permasalahan  dengan menggunakan  mekanisme  pencarian  yang meniru  proses  evolusi  biologis.  Mekanisme yang  digunakan  merupakan  kombinasi  dari pencarian  acak  dan  terstruktur.  Algoritma  ini sudah  berhasil  diterapkan  dalam  berbagai permasalahan kombinatorial, mulai dari Traveling  Salesman  Problem ( TSP ), VRP ,  dan penjadwalan produksi.
Dalam menyelesaikan penentuan kombinasi  yang  optimum,  Algoritma  Genetik berbeda  dengan  algoritma  heuristic  lainnya. Pada  umunya,  metode  heuristic  mencari  solusi optimum  dengan  menyusun  kombinasi  secara bertahap  berdasarkan  kriteria  pemilihan  dan terminasi  iterasi  yang  tertentu.  Solusi  yang didapatkan  hanya  satu  macam  solusi  saja. Sebaliknya,  Algoritma  Genetik  membuat  suatu kode  genetic  dari  kombinasi  yang  dimaksud, yang  lebih  dikenal  sebagai  istilah  gen ( genotype )  yang  selanjutnya  disempurnakan dengan  iterasi  yang  menyerupai  proses  alam dalam menurunkan sifat – sifat genetik. Karena itu,  Algoritma  Genetik  tidak  membutuhkan kriteria  khusus  yang  dijumpai  pada  algoritma heuristik  lain  dalam  menyaring  kualitas  solusi ataupun  mengurangi  waktu  komputasi  serta dapat  menghasilkan  beberapa  alternatif  solusi yang  mempunyai  nilai  fungsi  obyektif  yang sama [3] .
Istilah  –  istilah  dalam  Algoritma  Genetik (GA)
GA  menggunakan  mekanisme  genetika yang  ada  pada  proses  alami  dan  sistem  buatan. Istilah  –  istilah  yang  digunakan  adalah gabungan  dari  dua  disiplin  ilmu,  yaitu  ilmu biologi dan ilmu computer.
Semua  mahluk  hidup  terdiri  dari  sel. Tiap  sekumpulan  sel  yang  sama  dinamakan sebagai  kromosom.  Kromosom  tersusun  atas rangkaian  DNA  yang  merupakan  protein  yang membentuk  model  dari  seluruh  mahluk  hidup. Setiap  kromosom  terdiri  dari  gen,  yang merupakan sebuah blok DNA yang menentukan sifat  –  sifat  mahluk  hidup.  Ciri  –  ciri  yang mungkin  pada  sebuah  gen  disebut alleles, sedangkan  posisi  gen  pada  kromosom  disebut dengan locus . Kumpulan lengkap dari kromosom  disebut  dengan genome .  Kelompok khusus  dari  gen  dalam  genome  disebut genotype .
Selama reproduksi berlangsung, seleksi merupakan  proses  yang  pertama  kali  terjadi. Kemudian  gen  dari  parents  (orang  tua) dikombinasikan  dengan  cara  di- crossover (pindah silang) atau dengan memodifikasi suatu kromosom  dengan  menggunakan  operator mutasi.  Mutasi  berarti  bahwa  elemen  –  elemen dari  DNA  yang  ada  ditukar.  Pertukaran  ini terutama disebabkan karena adanya kemungkinan error /kesalahan yang terjadi pada saat peng- copy -an gen dari parents.
Parameter yang digunakan dalam GA [4]
Terdapat  beberapa  parameter  yang digunakan dalam GA.Parameter yang digunakan tersebut adalah :
 Jumlah Generasi
Merupakan  jumlah  perulangan  (iterasi) dilakukannya  rekombinasi  dan  seleksi. Jumlah  generasi  ini  mempengaruhi kestabilan  output  dan  lama  iterasi  ( waktu  proses  GA).  Jumlah  generasi yang  besar  dapat  mengarahkan  ke  arah solusi  yang  optimal,  namun  akan membutuhkan  waktu running yang lama. Sedangkan jika jumlah generasinya  terlalu  sedikit  maka  solusi akan terjebak dalam lokal optimal.
 Ukuran Populasi
Ukuran populasi mempengaruhi kinerja dan  efektifitas  dari  GA.  Jika  ukuran populasi  kecil  maka  populasi  tidak menyediakan  cukup materi  untuk mencakup ruang permasalahan, sehingga  pada  umumnya  kinerja  GA
menjadi buruk. Dalam hal ini dibutuhkan  ruang  yang  lebih  besar untuk  mempresentasikan  keseluruhan ruang permasalahan. Selain itu penggunaan  populasi  yang  besar  dapat mencegah  terjadinya  konvergensi  pada wilayah lokal.
 Probabilitas Crossover (P c )
Probabilitas crossover ini  digunakan untuk mengendalikan
frekuensi operator crossover .  Dalam  hal  ini, dalam  populasi  terdapat  P c *  ukuran populasi struktur yang akan melakukan crossover . Semakin besar nilai probabilitas crossover maka  semakin cepat  struktur  baru  diperkenalkan dalam populasi. Namun
jika probabilitas  crossover  terlalu  besar maka  struktur  dengan  nilai  fungsi obyektif yang baik dapat hilang dengan lebih  cepat  dari  seleksi.  Akibatnya populasi tidak dapat lagi meningkatkan nilai fungsi dari obyektifnya.
Sebaliknya  probabilitas crossover kecil akan  menghalangi  proses  pencarian dalam  proses  GA.  Adapun  mengenai probabilitas crossover yang  baik,  dari
hasil  penelitian  yang  dilakukan  oleh
Zbiniew Michalewics (1996) menyatakan bahwa probabilitas crossover yang  baik  adalah  berada dalam range 0.65 – 1.
 Probabilitas Mutasi (P m )
Mutasi  digunakan  untuk  meningkatkan variasi populasi. Probabilitas mutasi ini digunakan  untuk  menentukan  tingkat mutasi  yang  terjadi,  karena  frekuensi terjadinya  mutasi  tersebut  menjadi P m *ukuran  populasi*N,  dmn  N  adalah panjang  struktur  dalam  suatu  individu. Probabilitas  mutasi  yang  rendah  akan menyebabkan gen –  gen  yang berpotensi tidak dicoba, dan sebaliknya, tingkat  mutasi  yang  tinggi  akan menyebabkan keturunan semakin mirip dengan  induknya.  Adapun  mengenai probabilitas mutasi yang baik, dari hasil penelitian yang dilakukan oleh Zbiniew Michalewics (1996) menyatakan bahwa probabilitas  mutasi yang  baik  adalah berada dalam range 0.01 – 0.3.

## Mekanisme Dasar Algoritma Genetik (GA)
Adapun  mekanisme  GA  adalah  sangat sederhana,  yaitu  hanya  melibatkan  penyalinan
string  dan  pertukaran  bagian string .  Siklus pengembangbiakan GA diawali dengan pembuatan  himpunan  solusi  yang  dinamakan kromosom.  Selama  dalam  sebuah  generasi, kromosom  –  kromosom  tersebut  dievaluasi dengan  rumus  –  rumus  yang  ada  dalam  fungsi fitness .  Untuk  mendapatkan  suatu  kromosom baru yang dapat dilakukan dengan menggabungkan dua induk dengan menggunakan  operator crossover (pindah silang)  atau  dengan  memodifikasi  suatu kromosom  dengan  menggunakan  operator mutasi.  Dalam  kedua  operator  GA  tersebut dapat  dilakukan  evaluasi  dengan  menggunakan fungsi  obyektif  dan  batasan  –  batasan  fungsi kendala  sehingga  individu  dengan  solusi  yang lebih baiklah yang dipilih.
Sebelum  dilakukan  iterasi  selanjutnya maka  dilakukan  seleksi  sesuai  fungsi fitness sehingga  kromosom  –  kromosom  yang  fit  saja yang  diturunkan  dan  yang  tidak  fit  dapat dihilangkan. Setelah beberapa generasi, algoritma akan konvergen pada kromosom yang terbaik.  Kromosom  yang  terbaik  tersebutlah yang merupakan nilai optimum dari permasalahan.

## Langkah  –  Langkah  Dasar  Algoritma Genetik (GA)
Dalam  kehidupan  sehari  –  hari,  algoritna genetik  banyak  digunakan  untuk  memecahkan masalah  –  masalah  optimasi  seperti routing ,
penjadwalan dan masalah transportasi. Algoritma  dimulai  dari  sekumpulan solusi (ditunjukkan oleh sekumpulan kromosom)  yang  dinamakan  populasi.  Solusi dari  sebuah  populasi  diambil  dan  dgunakan untuk  membentuk  sekumpulan  populasi  baru. Motivasi  yang  digunakan  adalah  sebuah harapan  bahwa  populasi  baru  tersebut  nantinya akan lebih baik dari populasi yang lama. Solusi yang  akhirnya  dipilih  untuk  membentuk sekumpulan  solusi  baru  /  keturunan  baru (offspring)  diseleksi  berdasarkan  kemampuan  ( fitness )  mereka.  Semakin  sesuai  mereka semakin  besar  kesempatan  mereka  untuk bereproduksi.
Berikut  ini  adalah  langkah  –  langkah dasar dalam Algoritma Genetik :
a. [ Start ] Parents awal  yang  digunakan digenerate  secara  random  atau  bisa  juga dengan metode heuristik tertentu.
b. [ Fitness ] Mengevaluasi fitness f(x) dari tiap kromosom x dalam populasi.
c. [ New  population ]  Menciptakan  populasi baru  dengan  mengulang  langkah  –  langkah
di  bawah  ini  sampai  terbentuk  populasi baru.
 [ Selection ] Pilih dua parents kromosom dari populasi termasuk fitness mereka
 [ Crossover ] Dengan sebuah probabilitas crossover , penyilangan parents dilakukan  untuk  membentuk offspring (keturunan)  yang  baru.  Jika tidak  ada crossover yang  terbentuk, offspring yang  terbentuk  adalah  murni salinan dari orang tuanya.
 [ Mutation ]  Dengan  sebuah  probabilitas mutasi, offspring yang  baru  terbentuk dimutasi  pada  setiap  locus  (posisi dalam kromosom).
 [Accepting]  Tempatkan offspring yang baru pada populasi baru.
d. [ Replace ]  Gunakan  generasi  populasi  yang baru untuk replikasi algoritma berikutnya.
e. [ Test ]  Jika  kondisi  akhir  sudah  memenuhi syarat, Stop ,  kembali  ke  solusi  terbaik dalam populasi tersebut.
f. [ Loop ] Kembali ke Langkah b.

## METODE PENELITIAN Pengamatan Awal
Pada  tahap  awal  penelitian  ,  yang dilakukan  adalah  mengamati  bisnis  proses  dari perusahaan.  Hal  ini  dilakukan  dengan  tujuan untuk mengetahui kondisi perusahaan

## Identifikasi Masalah
Dari  pengamatan  awal  dapat  diketahui permasalahan yang sedang dihadapi perusahaan.  Selama  ini  perusahaan  melakukan pendistribusian  barang  berdasarkan  preferensi dan pengalaman kurir saja. Oleh karena itu rute distribusi yang digunakan dapat dikatakan tidak optimal.  Dalam  penelitian  ini  akan  dicari  rute yang terpendek.

## Studi Literatur
Studi  Literatur  ini  bertujuan  untuk mempelajari  teori  –  teori  yang  sesuai  dengan masalah yang dibahas guna membantu memecahkan masalah tersebut

## Pengumpulan Data
Pada  tahap  ini  dilakukan  pengumpulan data  yang  diperlukan  untuk  menyelesaikan permasalahan  rute  distribusi.  Data  yang dibutuhkan  adalah  data  jumlah,  jarak  node, kapasitas kendaraan yang digunakan. Selain itu
dalam  tahap  ini  juga  dikumpulkan  data  contoh pengiriman multidestination (contoh  kasus) yang pernah terjadi.

## Pengolahan Data dan Analisis Data
Data  studi  kasus  yang  diperoleh  pada tahap  pengumpulan  data  diolah  dengan  metode yang  sesuai,  tahapan  pengolahan  data  antara lain
1. Membuat  matrik  jarak  dan  waktu perjalanan  dari  depot  ke customer dan dari customer ke customer lain.
2. Menentukan metode untuk parent 1 yaitu  metode  Nearest  neighbor  dan parent  2  yaitu  metode  Clark Wright’s Saving.
3. Membuat Program GA.
4. Melakukan  input  data  terhadap program  GA  yang  telah  dibuat kemudian melakukan beberapa kali simulasi  untuk  menentukan  nilai parameter  –  parameter  GA  yang paling baik agar mendapatkan hasil yang terbaik.

## Verifikasi Hasil
Setelah diperoleh hasil, maka dilakukan verifikasi,  yaitu  dengan  cara  memeriksa  hasil tersebut  dengan  syarat  –  syarat  pengiriman, antara lain
1. Tidak  melanggar  pembatas  kapasitas kendaraan
2. Semua node telah terlewati
Apabila  persyaratan  di  atas  tidak dipenuhi  maka  akan  dilakukan  perhitungan kembali.

## Validasi Hasil
Validasi  rute  hasil  perhitungan  model VRPTW dengan  pendekatan  GA  dengan  cara membandingkan  jarak  tempuh  rute  hasil perhitungan  dengan  rute  awal  perusahaan. Apabila  jarak  tempuh  rute  hasil  perhitungan lebih  tinggi  maka  akan  dilakukan  perhitungan kembali.

## Kesimpulan dan Saran
Menarik  kesimpulan  terhadap  analisa output  dan  memberi  saran  terhadap  program penyelesaian yang dibuat.
Pengamatan Awal Identifikasi Masalah Studi Literatur Pengumpulan Data Pengolahan Data : Perancangan Model Kesimpulan dan Saran End Tidak Ya 1. Pengolahan contoh kasus dengan metode GA secara manual 2. Pembuatan Program Verifikasi hasil perhitungan manual dan Program 1. Tidak melanggar pembatas kapasitas kendaraan 2. Semua titik tujuan telah terlewati 3.Tidak melanggar pembatas waktu Apakah hasil sudah verify Validasi Hasil Membandingkan rute hasil perhitungan dengan rute awal perusahaan Apakah hasil sudah valid Ya Tidak
Gambar 3. Diagram Alir Metode Penelitian

## HASIL PENELITIAN DAN PEMBAHASAN
Pengumpulan data dilakukan dengan
wawancara  dan  observasi  secara  langsung terhadap  perusahaan.  Data  –  data  yang dibutuhkan antara lain adalah :
a) Data alamat customer
b) Data jarak antar customer
c) Data jumlah barang yang akan dikirimkan
d) Data  lama  loading  dan  unloading barang
e) Data jenis dan kapasitas kendaraan
Daerah  penelitian  hanya  dibatasi  untuk wilayah  Surabaya  dan  sekitarnya.  Depo  PT. MIF  di  Surabaya  terletak  di  Jl.  Tanjung Tembaga.
Data  jumlah  barang  dan  lama  waktu loading – unloading untuk tiap kali pengiriman selalu  berubah,  sehingga  dalam  program  yang dibuat  data  ini  selalu  diinputkan  terlebih dahulu.
Pemodelan Regresi untuk Waktu Loading/Unloading Dari  data  volume  dan  waktu loading  /
unloading dilakukan  uji  korelasi  antara volume dengan  waktu loading  /  unloading .  Hasil korelasi antara volume dengan waktu loading/unloading menghasilkan pearson correlation 0.95  dan p-value 0,00  artinya  ada korelasi antara volume dan waktu loading/unloading .  Setelah  melihat  korelasi antara  waktu loading  / unloading dengan volume  maka  selanjutnya  dilakukan  pencarian model  terbaik  dengan  menggunakan  bantuan software minitab.
Tabel 1 . Hasil pemodelan regresi tahap 1
Regresi  pada  tabel  1  diatas  merupakan model  terbaik  untuk  waktu loading / unloading setelah  mengalami  pengurangan  data  yang outlier dan influence .
Kemudian  untuk  evaluasi  kelayakan model  dilakukan  uji  terhadap standardized residual dari model yang terbentuk. standardized  residual yang  diperoleh  harus Identical  Independent  Distribution  Normal (IIDN). Untuk  mengetahui bahwa standardized residual IIDN dilakukan uji normality menggunakan  kolmogorov  smirnov  untuk melihat standardized residual berdistribusi normal.
Uji hipotesis untuk standardized residual : H o : Standardized  residual berdistribusi normal H 1 : Standardized  residual tidak  berdistribusi normal
α :5%
P-value standardized residual > 0,150 P-value > α, maka gagal tolak , H o standardized residual berdistribusi normal.
Gambar  4. Normality  Test untuk st.residual waktu loading/unloading

## Perhitungan Contoh Kasus
Berikut adalah perhitungan kasus pengiriman multidestination yang pernah dilakukan oleh perusahaan untuk pengiriman ke 5 tempat .

## Tabel 2. Data Customer Untuk Contoh Kasus
C1 Jl.Raya Pandaan 5.8 0.3 0.38 C6 Jl.Raya Sidoarjo - Krian 5.04 0.31 0.4 C7 Jl.Kalianak Barat 2 0.21 0.26 C8 Jl.Tambak Langon 2.2 0.18 0.23 C18 Jl.Sepanjang 2.06 0.21 0.25
Customer Alamat Volume barang
(m 3 ) Lama Loading (jam) Lama Unloading (jam)
Pengiriman ini dilakukan dengan menggunakan 1 colt diesel dan 1 truk engkel.

## Rute aktual perusahaan
Rute aktual perusahaan adalah :
Kendaraan 1 : Depo → C7 → C8 → Depo Kendaraan 2 : Depo → C1 → C6 → C18→ Depo
Metode Nearest Neighbor
Dengan menggunakan metode Nearest
Neighbour didapatkan rute sebagai berikut :
Tabel 3 . Metode Nearest Neighbour Kendaraan 1 8 0-1-0 111.1 5.8 Kendaraan 2 15 0-7-8-18-6-0 97.5 11.3 208.6 17.1 Total Volume (m 3 ) Kapasitas (m 3 ) Total Jarak (Km) Rute
Metode Clark Wright Saving
Dengan menggunakan metode Clark Wright Saving didapatkan rute sebagai berikut :
Tabel 4. Metode Clark Wright Saving Kendaraan 1 8 0-8-0 17.9 4.06 Kendaraan 2 15 0-6-1-18-7-0 140 13.04 157.9 17.1 Total Volume (m 3 ) Kapasitas
(m 3 ) Rute Total Jarak (Km)

## Algoritma Genetik
Sebagai parent 1  yaitu  rute  hasil  dari perhitungan  metode Nearest  Neighbour dan sebagai parent  2 yaitu  rute  hasil  perhitungan metode Clark Wright Saving .
Populasi  yang  digunakan  sejumlah 60,Jumlah  maksimum  generasi  sebesar  1000, yang  kemudian  akan  mengalami crossover ,mutasi dan seleksi, dengan nilai stopover limit 30. Iterasi dihentikan jika tidak ada peningkatan hasil  sebanyak  30  kali.  Selama  masih  ada peningkatan  hasil,  maka  iterasi  akan  terus berjalan. Probabilitas crossover yang digunakan sebesar 0.8 dan probabilitas mutasi sebesar 0.2
Flowchart program 1. Input jumlah kendaraan dan tujuan Menginputkan jumlah kendaraan  yang  akan  dipakai  dan jumlah customer yang akan dituju.
2. Input jenis kendaraan Untuk  tiap  kendaraan  inputkan jenis kendaraan.
3. Input tujuan,demand, waktu unloading Untuk  tiap  tujuan  diinputkan kode  tujuan,  jumlah  barang  yang  akan dikirim  dan  lama  unloadnya.  Jumlah demand  diinputkan  dengan  satuan volume  m 3 dan  waktu  unloading  dalam jam
4. Solve Perhitungan solve terdiri atas a. Penjumlahan total volume dicocokan  dengan  kapasitas kendaraan pertama yang
tersedia di depo
b. Penentuan  parent  1  dan  parent 2 c. Crossover operator (crossover,mutasi)
d. Pemilihan individu terbaik 5. Konversi ke waktu Membagi jarak dengan kecepatan rata – rata 6. Menjumlah  lama  perjalanan  dengan lama unloading Menjumlah  lama  perjalanan dengan waktu unloading. Waktu
unloading harus diperhatikan agar tidak melanggar pembatas waktu.
7. Hasil output Setelah semua perhitungan selesai dilakukan, maka akan ditampilkan  hasil  rute  yang    terbaik sesuai  dengan  perhitungan  algoritma genetika.
Start Input Jumlah kendaraan dan tujuan Untuk tiap kendaraan Input Jenis kendaraan Tampilkan kapasitas kendaraan For Untuk setiap tujuan Input Tujuan Input Demand Input waktu unloading For Solve Hasil Output Input Data
Gambar 5. Flowchart Program ( Input Data )
Sum demand Sum demand > kapasitas kendaraan Back to data Populasi awal Nearest Neighbor Clark Wright Saving Generasi = 0 Generasi lama = 0 Stopover limit = 0 Crossover Mutasi Seleksi Generasi = 1000 ? Pilih individu terbaik End Selisih = min[generasi lama] – min [generasi baru] Selisih > 1 ? Generasi lama = generasi Generasi = Generasi +1 SL = SL +1 Generasi lama = generasi Generasi = Generasi +1 SL = 0 Ya Tidak Ya Tidak Ya Tidak SL = 30? Ya Tidak
Gambar 6. Flowchart Program Solve Hasil Perhitungan Contoh Kasus Menggunakan Program GA Hasil  perhitungan  untuk  contoh  kasus menggunakan program algoritma genetik adalah sebagai berikut
Gambar 6. Hasil perhitungan program
Rute pengiriman kendaraan 1 : Depo → C8 → Depo Jarak tempuh = 17.9 Km Volume barang = 2.2 m 3 Rute pengiriman kendaraan 2 : Depo → C6 → C1 → C18 → C7 → Depo Jarak tempuh = 140 Km Volume barang = 14.9 m 3 Dengan total jarak tempuh 157.9 Km

## Verifikasi Hasil
Rute  hasil  perhitungan  menggunakan program  algortima  genetik  harus  diverifikasi, dengan  cara  memeriksa  kesesuaian  hasil perhitungan dengan syarat – syarat pengiriman, yaitu  tidak  melanggar  pembatas  kapasitas kendaraan  dan  semua  titik  tujuan  telah terlewati.
a. Tidak melanggar kapasitas kendaraan total volume barang  yang  diangkut  ≤ kapasitas kendaraan
Gambar 7. Verifikasi program
Kendaraan 1 kapasitas 8 m 3 → total barang yang diangkut 2.2 m 3
Kendaraan  2  kapasitas  15  m 3 →  total barang yang diangkut 14.9 m 3
Jadi  semua  barang  yang  diangkut  tidak melebihi kapasitas kendaraan.
b. Semua titik tujuan telah terlewati
Gambar 8 . Verifikasi program
Titik  tujuan  yang  harus  dilewati  adalah C1,C6,C7,C8,C18.
Kendaraan  1  melewati  C8,  Kendaraan  2 melewati C6,C1,C18,C7.
Dengan  demikian  semua  titik  tujuan  telah terlewati.
c. Tidak melanggar pembatas waktu
Gambar 9. Verifikasi Program
Semua  titik  telah  dilewati  sebelum  jam 17:00

## Validasi Hasil
Validasi  hasil  dilakukan  dengan  cara membandingkan  jarak  tempuh  pada  rute  hasil perhitungan program algoritma genetik  dengan jarak tempuh pada rute awal perusahaan.
Tabel 3. Selisih jarak tempuh rute perusahaan dan perhitungan program
13.5 7.88%
Selisih Persentase
171.4 157.9 Rute Aktual
Jarak Tempuh (Km) Rute Program
Dari  tabel  di  atas  dapat  dilihat  bahwa jarak  tempuh  rute  awal  perusahaan  lebih  besar daripada  jarak  tempuh  rute  hasil  perhitungan program  algoritma  genetik.  Dengan  demikian rute  hasil  perhitungan  program  algoritma genetik  ini  dapat  dikatakan  valid.  Selisih  jarak tempuh  antara  kedua  rute  tersebut  adalah sebesar  13.5  km.  Jadi,  persentase  penghematan yang  dapat  diperoleh  apabila  rute  hasil perhitungan  program  algoritma  genetik  ini diterapkan adalah sebesar 7.88 %.

## ANALISIS DAN PEMBAHASAN Analisa  Pengaruh  Parameter    Algoritma Genetik
Dalam  GA  terdapat  beberapa  parameter genetik, yaitu ukuran populasi, jumlah generasi, probabilitas crossover ,  probabilitas  mutasi. Dalam  hal  ini  ukuran  populasi  berarti  jumlah maksimum solusi yang bisa ditampung, jumlah generasi  adalah  jumlah  iterasi  yang  akan dilakukan dalam satu kali running , probabilitas crossover merupakan  probabilitas  terjadinya crossover ,  probabilitas  mutasi  merupakan probabilitas terjadinya mutasi
Gambar 10. Pengujian Parameter
Dalam  hal  ini  tentu  saja  dibutuhkan  parameter yang  dapat  mengurangi  waktu running untuk populasi  60  generasi  1000  outputnya  sudah cukup baik dan stabil. Sehingga bisa dikatakan
populasi  60  dan  generasi  100  memberikan solusi  yang  terbaik,  maka  untuk  selanjutnya populasi  yang  digunakan  adalah  60  dan generasi yang digunakan sebanyak 1000. Sedangkan  untuk  probabilitas  crossover  yang dipilih  adalah  sebesar  0.8  dan  probabilitas mutasi  sebesar  0.2  dan  stopover  limit  sebesar 30

## KESIMPULAN DAN SARAN Kesimpulan
Dari  hasil  penelitian  dan  pembahasan dapat  diambil  kesimpulan  bahwa  Rute  yang diperoleh  dari  hasil  perhitungan  algoritma genetik adalah  sebagai berikut : Kendaraan 1 :
Pengiriman oleh kendaraan 1 dilakukan dari  depo  menuju  ke customer 8  kemudian langsung  kembali  ke  depo  dengan  total  jarak 17.9Km  dan  volume  barang  yang  diangkut sebesar  2.2  m 3 pengiriman  dilakukan  selama 0.716 jam Kendaraan 2 :
Pengiriman oleh kendaraan 2 dilakukan dari  depo  menuju  ke  customer  6,customer 1,customer 18,customer 7 kemudian kembali ke depo  dengan  total  jarak  140  Km  dan  volume barang  yang  diangkut  sebesar 14.9 m 3 . Pengiriman dilakukan selama 5.6 jam
Persentase  penghematan  yang  dapat diperoleh apabila rute hasil perhitungan metode optimasi ini diterapkan pada perusahaan adalah sebesar 7,88 %.
Parameter yang digunakan untuk program GA ini adalah :
 Jumlah generasi = 1000
 Jumlah populasi = 60  Stopover limit = 30  Probabilitas crossover = 0.8  Probabilitas mutasi = 0.2 Saran  yang  bisa  diajukan  sebagai berikut: 1. Diharapkan dalam penelitian selanjutnya  penentuan  parameter  –  parameter dalam  GA  disimulasikan  secara  terpisah sehingga  didapat  parameter  –  parameter  yang dapat  menghasilkan  output  yang  baik  dan  juga cepat.
2. Diharapkan untuk penelitian selanjutnya  dapat  menggunakan  optimasi  GA agar hasil yang didapatkan lebih baik.

## DAFTAR PUSTAKA
[1] Martha, Perencanaan  Rute  Transportasi
Terpendek  pada  PT.  Mitra  Intertrans Forwarding (MIF) dengan Model VRPTW ,  Hlm  1-11,  Skripsi  Jurusan Teknik  Industri,  Universitas  Katolik Widya Mandala,Surabaya, 2005
[2] Gen,M and Cheng,R, Genetic Algorithms &  Engineering  Design ,  Hlm  119-251, John Willey and Sons, New York, 1993
[3] Kusiak,  A, Intelligent  Design  and Manufacturing ,  Hlm.  649-698,  John Willey and Sons,  New York, 1992 [4] Sivanandan, S.N.,dan Depa, S.N., Introduction  to  Genetic  Algorithms ,  Hlm 131-163, Springer, New York, 200.