## INFOMATEK
Volume 19 Nomor 1 Juni 2017
PENGARUH NILAI PARAMETER TERHADAP SOLUSI HEURISTIK PADA MODEL VTPTW
Tjutju T. Dimyati
Program Studi Teknik Industri Fakultas Teknik – Universitas Pasundan
Abstrak: Penentuan  rute  kendaraan  (Vehicle  Routing  Problem,  VRP)  merupakan  sub  persoalan  yang  sangat penting  dari  suatu  sistem  distribusi,  sehingga  telah  mengundang  banyak  perhatian  peneliti  untuk  menggali berbagai aspek yang terkait dengan persoalan ini. Pada makalah ini dikemukakan suatu metode heuristik untuk menyelesaikan persoalan penentuan rute kendaraan dimana setiap pelanggan menetapkan batas awal dan akhir waktu pengiriman, yang dikenal sebagai Vehicle Routing Problem with Time Windows (VRPTW). Penentuan rute ditujukan  tidak  hanya  untuk  meminimumkan  total  ongkos  perjalanan  tetapi  juga  total  waktu  pelanggan menunggu.  Karena  metode  heuristik  yang  dibahas  melibatkan  sejumlah  parameter,  pada  makalah  ini  juga dilakukan analisis untuk mengetahui pengaruh nilai parameter terhadap solusi yang diperoleh.
Kata kunci: Vehicle routing, Time windows, Heuristik

## I. PENDAHULUAN 1

## 1.1 Latar Belakang
Bagi  perusahaan  manufaktur  maupun  jasa, sistem distribusi/ transportasi memiliki peranan yang  sangat  penting  dalam  memberikan pelayanan kepada konsumen. Untuk mengendalikan seluruh aktivitas distribusi dan untuk  mengefisienkan  penggunaan  sumber- sumber  sistem  ini,  persoalan  yang  harus diselesaikan  dapat  dikelompokkan  ke  dalam persoalan  yang  sifatnya  strategis,  taktis, maupun  operasional.  Persoalan  strategis berkaitan  dengan  perancangan  jaringan  fisik,
*) tjutjutarliah@unpas.ac.id
penentuan  lokasi  fasilitas,  dan  pengadaan sumber-sumber  yang  diperlukan,  sedangkan persoalan  yang  bersifat  taktis  berkaitan dengan  pengalokasian  sumber-sumber  yang ada  untuk  memperbaiki  kinerja  sistem  secara keseluruhan. Persoalan pada level operasional  berkaitan  dengan  penentuan  rute kendaraan  yang  melakukan  perjalanan  dari depot atau gudang ke sejumlah pengecer atau pelanggan, untuk meminimumkan total ongkos perjalanan  yang  terjadi.  Ada  dua  model persoalan  operasional  yang  banyak  dibahas para  peneliti,  yaitu Travelling  Salesman Problem ( TSP )  dan Vehicle  Routing  Problem ( VRP ).
Pada  model VRP ,  setiap  kendaraan  dengan kapasitas  angkut  tertentu  dan  seragam  akan melakukan  perjalanan  dari  depot  untuk melakukan pengiriman komoditas ke sejumlah pelanggan  dengan  tingkat kebutuhan tertentu, dan  kembali  ke  depot.  Total  kebutuhan  yang dilayani  setiap  rute  tidak  melebihi  kapasitas angkut  kendaraan.  Setiap  pelanggan  hanya dilayani  oleh  satu  kendaraan  dan  setiap  rute pengiriman  hanya  boleh  mengunjungi  setiap pelanggan  satu  kali.  Tujuannya  adalah  agar setiap  pelanggan  terpenuhi  kebutuhannya dengan total ongkos yang minimum.
Jika diberlakukan batasan waktu tertentu, baik batasan  waktu  untuk  kendaraan  berangkat dari dan kembali ke depot maupun saat paling cepat dan paling lambat untuk kendaraan tiba di masing-masing pelanggan, maka persoalannya dikenal sebagai Vehicle Routing Problem  with  Time  Window  (VRPTW) .  Pada model VRPTW ini  yang  harus  diselesaikan tidak  hanya  menentukan  rute  tetapi  juga jadwal keberangkatan setiap kendaraan untuk meminimumkan  total  ongkos  perjalanan  dan total waktu pelanggan menunggu.

## 1.2 Tujuan Pembahasan
Meskipun  persoalan  yang  melibatkan  model VRP banyak  dijumpai  dalam  kehidupan sehari-hari,  tetapi  untuk  memperoleh  solusi optimalnya  tidaklah  mudah  karena VRP
merupakan  persoalan NP-hard (Solomon  [1]).
Hal  ini  telah  memotivasi  para  peneliti mengembangkan  berbagai  metode  heuristik agar  dapat  digunakan  untuk  menyelesaikan persoalan-persoalan  dalam  kehidupan  sehari- hari,  yang  pada  umumnya  berukuran  besar (Solomon  dkk.  [2]),  (Solomon  dkk.  [3]), (Thangiah dkk. [4]), (Ioannou dkk. [5]).
Pada  makalah  ini  dibahas  suatu  metode heuristik  untuk  menyelesaikan  persoalan VRPTW , dengan menggunakan metoda Insertion Heuristik-I1 sebagai dasar pengembangan.  Metoda Insertion Heuristik-I1 sendiri pada dasarnya
merupakan pengembangan  dari  metoda Saving  Heuristic yang  dikembangkan  oleh  Clarke  dan  Wright untuk  persoalan VRP klasik  (Ghiani  dkk.  [7]).
Bagian  3  dari  makalah  ini  menguraikan formulasi  persoalan  yang  akan  diselesaikan serta  model  matematisnya,  sedang  metode heuristik  yang  dibahas  disajikan  pada  bagian 4.  Untuk  memudahkan  pemahaman  terhadap metode yang dibahas, pada bagian 5 disajikan suatu  ilustrasi  numerik  lengkap  dengan  hasil perhitungan. Analisis terhadap  nilai parameter yang  digunakan  dalam  proses  pencarian solusi  disajikan  pada  bagian  6.  Sebagai penutup  dari  seluruh  pembahasan,  pada bagian  7  dikemukakan  beberapa  hal  yang berkaitan  dengan  metoda  heuristik  yang dibahas.

## 1.3 Formulasi Persoalan
Untuk menjelaskan model VRPTW , perhatikan suatu graph  (N,A) .  Set node N terdiri  dari suatu set pelanggan  yang dinyatakan sebagai C , dimana node 0 dan node n+1 adalah depot.
Set arc  A menyatakan  hubungan  di  antara node  satu  dengan  node  yang  lain.  Tidak  ada arc yang berakhir di node 0 dan tidak ada arc yang berawal dari node n+1 . Setiap rute akan berawal dari node 0 dan akan berakhir di node n+1 .  Setiap arc  (i,j  )  A ditandai  dengan ongkos C ij dan  waktu  tempuh t ij .  Karena besarnya ongkos dianggap proporsional terhadap  jarak  dan  waktu  tempuh  maka besarnya  unit  ongkos  bisa  dinyatakan  sama dengan 1. Setiap pelanggan berkaitan dengan kebutuhan d i dan waktu pelayanan t i , i  C . Set kendaraan  dinyatakan  sebagai V dimana setiap  kendaraan  memiliki  kapasitas  angkut yang  seragam,  yaitu q .  Pelayanan  di  setiap pelanggan  harus  dilaksanakan  dalam  interval waktu  [ a i ,b i ], i  C .  Setiap  kendaraan  harus meninggalkan  depot  dalam  interval  waktu  [ a 0 , b 0 ] dan harus kembali ke depot dalam interval waktu  [ a n+1 ,  b n+1 ].  Kendaraan  yang  datang  di pelanggan  sebelum  awal time  window harus menunggu  hingga  pelayanan  dapat  dimulai, tetapi  tidak  boleh  datang  setelah  batas  atas time window .
Untuk  memformulasikan  model  matematis
VRPTW digunakan dua variabel berikut:
X ijk =  1  jika  kendaraan k melakukan perjalanan dari node i ke j (  ( i,j ) 
A,  k  V ) = 0 jika tidak
S ik (  i  N ,  k  V )  menyatakan  saat kendaraan k memulai pelayanan di pelanggan i ( i  C )
Dalam  hal  ini  dapat  diasumsikan S 0k =  0  k . S n+1,k menyatakan saat kepulangan kendaraan k di  depot.    Model  matematis VRPTW dapat diformulasikan sebagai berikut:
ijk V k A ) j , i ( ij X C Min    
(1)
dengan pembatas:
1      V k N j ijk X
 i  C (2)
q X d N j ijk C i i     
 k  V (3)
1 0    N j jk X  k  V (4)
0       N j hjk N i ihk X X
 h  C,  k  V (5) 1 1     N i k , n , i X
 k  V (6)
0     ) S t t S ( X jk ij i ik ijk  ( i,j )  A,  k  V (7)
i ik i b S a
   k  V,  k  V (8) } {0,1  ijk X
 ( i,j )  A,  k  V (9)
Fungsi  tujuan  (1)  menyatakan  bahwa  total ongkos  harus  diminimumkan.  Pembatas  (2)
menyatakan  bahwa  setiap  pelanggan  hanya dilayani oleh satu kendaraan, sedang pembatas  (3)  menyatakan  setiap  kendaraan hanya  akan  melayani  konsumen  sebatas kapasitasnya.  Pembatas  (4),  (5),  dan  (6) menyatakan  bahwa  setiap  kendaraan k akan berangkat  dari  depot,  meninggalkan  node h , ( h  C )  jika  kendaraan  itu  memasuki  node h , dan  akan  kembali  ke  depot. Arc ( 0,  n+1 ) dimasukkan ke dalam network untuk mengikut sertakan  perjalanan  awal  dari  depot  dan perjalanan  kembali  ke  depot.  Pembatas  (7) menyatakan bahwa jika kendaraan k melakukan  perjalanan  dari i ke j maka kendaraan tesebut akan tiba di node j setelah
ij i ik t t S   .  Pembatas  (8)  menyatakan setiap  kendaraan k akan  tiba  di  pelanggan i dalam batas time window pelanggan tersebut,
sedangkan  pembatas  (9)  adalah  pembatas integralitas.

## II. METODE PENYELESAIAN

## 2.1 Metode Heuristik
Metode  heuristik  yang  dibahas  pada  makalah ini  pada  dasarnya  adalah  suatu  prosedur pembentukan  rute  yang  dilakukan  dengan cara  memilih  pelanggan  (dinyatakan  sebagai node)  yang  akan  disisipkan  ke  dalam  suatu rute  yang  sudah  ada.  Proses  penyisipan dilakukan  hingga  rute  yang  bersangkutan dinyatakan “penuh”, baik berdasarkan kapasitas  kendaraan  maupun  jadwal  waktu pelayanan  di masing-masing pelanggan.
Tujuannya adalah untuk membentuk satu atau beberapa rute pelayanan dengan total ongkos perjalanan yang minimum. Diasumsikan besarnya  ongkos  proporsional  terhadap  jarak dan waktu tempuh.
Proses  pemilihan  dan  penyisipan  node  ke dalam rute dilakukan sebagai berikut:
Langkah 0 (Inisialisasi)
o Nyatakan seluruh node (tidak
termasuk  depot)  yang  belum  masuk ke dalam rute sebagai node bebas
o Pilih  satu  node  bebas  untuk  dijadikan node  awal  dari  rute  yang  akan dibentuk,  nyatakan  node  tersebut sebagai  node  i.  Pemilihan  node  awal bisa  didasarkan  pada  jarak  node terhadap  depot  atau  berdasarkan jadwal waktu pelayanan.
o Tetapkan  rute  awal  sebagai  R  =  {0,  i,
n+1} dengan 0 dan n+1 adalah depot Langkah 1 (Penetapan nilai parameter) o Nyatakan node bebas yang dipertimbangkan untuk disisipkan sebagai node u
o Tetapkan nilai parameter μ yaitu bobot yang diberikan terhadap penghematan jarak  yang  diperoleh  jika  dilakukan penyisipan node u.  μ ≥ 0
o Tetapkan  nilai  parameter  α1  yaitu bobot  yang  diberikan  terhadap  total jarak  yang  terjadi  akibat  penyisipan node  u  dan  parameter  α2  yaitu  bobot
yang  diberikan  terhadap  perubahan waktu  pelayanan  akibat  penyisipan node u.  α1 + α2 = 1
o Tetapkan nilai parameter λ yaitu bobot yang diberikan bagi ongkos perjalanan dari depot ke node u jika node u  tidak disisipkan ke dalam rute.  λ ≥ 0 Langkah  2  (Pemilihan  dan  penyisipan node)
o Nyatakan rute saat ini sebagai R = { 0, i1 , ..., j }  (0 dan j adalah depot)
o Untuk  setiap  node  bebas  u,  hitung total  tambahan  jarak  yang  terjadi  jika node u disisipkan,
dengan menggunakan formula
Z 11 (i, u, j) = d iu + d uj – μ d ij ; μ ≥ 0 o diu  ,  duj  ,  dan  dij    masing-masing adalah  jarak  antara  node  i  dengan node  u,  node  u  dengan  node  j,  dan node i dengan node j
o Hitung tambahan waktu untuk
kendaraan
tiba dan
memulai
pelayanan  di  node  i  jika  node  u disisipkan, dengan menggunakan formula
Z 12 (i, u, j ) = t 0u +  t u +  t ui -  t 0i o t 0u ,  t ui , dan t 0i adalah  waktu  tempuh dari  depot  ke  node u ,  dari  node u ke node i ,  dan  dari  depot  ke  node i , sedang t u adalah  waktu pelayanan  di node u
o Hitung  besarnya  ongkos  penyisipan yang  besarnya  proporsional  terhadap
tambahan  jarak  dan  tambahan  waktu tempuh untuk tiba di node i jika node u disisipkan,  dengan  menggunakan formula
Z 1 (i, u, j) = α 1 Z 11 (i, u, j) +  α 2 Z 12
(i, u, j) ; α 1 ≥ 0 ; α
2 ≥ 0 ; α 1 + α 2 = 1 o
Sisipkan  node  bebas u yang  memiliki nilai Z 1 (i, u, j) minimum ke dalam rute, di  antara  node i dan  node j yang
sudah ada o Jika  kapasitas  kendaraan  dan  batas waktu pelayanan masih memungkinkan,  lakukan  penyisipan berikutnya berdasarkan nilai Z 2 (i, u, j) maksimum, dimana
Z 2 (i, u, j ) = λ d 0u -  Z 1 (i, u, j) ; λ ≥ 0 menyatakan  selisih  antara  ongkos yang  terjadi  jika  node u ditempuh langsung  dari  depot  dengan  ongkos yang  terjadi  jika  node u disisipkan  ke dalam rute
Langkah 3 (Pengulangan)
Jika  masih  ada  node  bebas,  ulangi langkah  2  hingga  seluruh  node  masuk  ke dalam rute.
Langkah 4 (Perbaikan solusi)
Untuk  setiap  rute  yang  telah  terbentuk, lakukan  perubahan  posisi  node  atau urutan  pelanggan  yang  dikunjungi,  untuk memperoleh  total  jarak  dan  total  waktu menunggu yang minimum.

## 2.2 Ilustrasi Numerik
Misalkan  ada  suatu  depot  yang  melayani pengiriman suatu komoditas ke 12 pelanggan. Pada Tabel 1 disajikan data tingkat kebutuhan komoditas  (dalam  unit)  dan  jadwal  waktu pelayanan  di  masing-masing  pelanggan.  Data jarak  (dalam  Km)  serta  waktu  tempuh  (dalam menit)  dari  depot  ke  pelanggan  dan  antar
pelanggan  adalah  seperti  pada  Tabel  2. Kapasitas  setiap  kendaraan  adalah  30  unit, sedangkan  lama  waktu  pelayanan  di  setiap pelanggan adalah 15 menit. Setiap kendaraan harus  meninggalkan  depot  pada  pukul  9:00 dan harus sudah kembali ke depot pada pukul 12:00.

## Tabel 1

## Data tingkat kebutuhan dan jadwal pelayanan
Pelanggan (node) 1 2 3 4 5 6
7 8 9 10 11 12 Tingkat Kebutuhan 7 8 6 8 6 7 8
7 6 7 5 9 Batas Awal Pelayanan 9:00 9:00 9:00 11:00 9:00 11:00 9:00 10:00 9:00 9:00 10:00 10:00 Batas Akhir Pelayanan 11:30 12:30 12:30 12:30 12:30 12:30 12:30 12:30 10:30 11:15 12:45 12:30
Tabel 2 Data jarak (di bawah diagonal) dan waktu tempuh (di atas diagonal) Node 0 1 2 3 4 5 6 7 8 9 10 11 12 0 0 30.0 31.0 30.0 30.0 27.0 23.0 25.0 30.0 41.0 31.0 24.0 33.0 1 9.8 0 14.0 18.0 5.0 16.0 28.0 29.0 12.0 13.0 13.0 28.0 6.0 2 10.1 4.6 0 7.0 11.0 5.0 21.0 20.0 5.0 15.0 6.0 24.0 13.0 3 9.8 6 2.2 0 15.0 5.0 21.0 20.0 9.0 23.0 12.0 24.0 17.0 4 9.9 0.9 3.6 4.9 0 16.0 28.0 29.0 12.0 12.0 13.0 28.0 6.0 5 8.9 5.3 0.7 1.4 5.3 0 18.0 17.0 8.0 19.0 10.0 21.0 16.0 6 7.6 9.1 7 7 9.1 5.8 0 5.0 21.0 32.0 23.0 5.0 31.0 7 8.1 9.5 6.5 6.5 9.5 5.4 0.6 0 23.0 34.0 24.0 5.0 32.0 8 9.8 3.9 1.4 2.9 3.9 2.6 7 7.5 0 11.0 5.0 28.0 8.0 9 13.4 4.3 4.9 7.5 3.7 6.1 10.5 11.08 3.5 0 10.0 35.0 10.0 10 10.1 4.3 1.9 3.8 4.3 3.1 7.5 8 0.5 3.3 0 30.0 7.0 11 7.8 9.2 7.9 7.7 9.2 6.7 0.7 0.9 9.3 11.5 9.7 0 33.0 12 10.9 1.9 4.1 5.6 1.7 5.2 10.1 10.6 2.6 3.1 2.1 10.9 0
Untuk  menyelesaikan  persoalan  di  atas ditetapkan nilai μ = 1 ; α 1 = α 2 = 0.5 ; dan λ = 1.  Dari  data  di  atas  diketahui  bahwa  total kebutuhan  di  seluruh  pelanggan  adalah  84
unit.  Karena  kapasitas  kendaraan  adalah  30 unit  maka  diperlukan  3  unit  kendaraan,  yang berarti  juga  akan  terbentuk  tiga  rute  yang berasal dan berakhir di depot.
Iterasi 1:
Sebagai node awal pada rute R 1 dipilih node 9 yang  merupakan  pelanggan  dengan  batas awal  dan  batas  akhir  pelayanan  paling  cepat, sehingga R 1 =  {0,  9,  0} .  Karena  kapasitas
kendaraan dan jadwal waktu pelayanan masih memungkinkan  maka  selanjutnya  dilakukan pemilihan  node u yang  akan  disisipkan.  Hasil perhitungan disajikan pada Tabel 3.
Tabel 3 Hasil perhitungan untuk iterasi 1 i u d(i,u) d(u,0)  d(i,0) Z11 t(0,u) t(u,i) t(0,i) Z12 Z1 Z2 9 1 4.3 9.8 13.4 0.7 30.0 13.0 41.0 17 8.85 0.95 2 4.9 10.1 13.4 1.6 31.0 15.0 41.0 20 10.8 -0.7 3 7.5 9.8 13.4 3.9 30.0 23.0 41.0 27 15.45 -5.65 4 3.7 9.9 13.4 0.2 30.0 12.0 41.0 16 8.1 1.8 5 6.1 8.9 13.4 1.6 27.0 19.0 41.0 20 10.8 -1.9 6 10.5 7.6 13.4 4.7 23.0 32.0 41.0 29 16.85 -9.25 7 11.08 8.1 13.4 5.78 25.0 34.0 41.0 33 19.39 -11.29 8 3.5 9.8 13.4 -0.1 30.0 11.0 41.0 15 7.45 2.35 10 3.3 10.1 13.4 0 31.0 10.0 41.0 15 7.5 2.6 11 11.5 7.8 13.4 5.9 24.0 35.0 41.0 33 19.45 -11.65 12 3.1 10.9 13.4 0.6 33.0 10.0 41.0 17 8.8 2.1
Berdasarkan  nilai Z 1 maka  node  yang  harus disisipkan  di  antara  node  9  dan  depot  adalah node  8  sehingga  diperoleh  rute R 1 =  {0,  9,  8,
0} .  Proses  penyisipan  masih  dapat  dilakukan
dengan  memperhatikan  nilai Z 2 sehingga akhirnya  diperoleh  rute R 1 =  {0,  9,  8,  10,  12,
0}. Resume  hasil  perhitungan  untuk  rute R 1 disajikan pada Tabel 4.

## Tabel 4
Resume hasil perhitungan iterasi 1 Node Tiba Berangkat Waktu menunggu Kumulatif unit Kumulatif jarak Depot 9:00 Pelanggan 9 9:41 9:56 - 6 13.4 Pelanggan 8 10:07 10:22 - 13 16.9 Pelanggan 10 10:27 10:42 - 20 17.4 Pelanggan 12 10:49 11:04 - 29 19.5 Depot 11:37 30.4 Dengan cara yang
sama dilakukan perhitungan  untuk  memperoleh  rute  kedua dan ketiga sehingga diperoleh R 2 = {0, 1, 4, 5,
2, 0} dan R 3 = {0, 3, 6, 7, 11, 0} . Kedua rute ini tidak  fisibel  karena  menyebabkan  kendaraan tiba  di  depot  lebih  dari  pukul  12:00.  Hal  ini
terjadi  karena  dari  rute R 2 diperoleh  waktu tunggu  selama  70  menit  di  pelanggan  4, sedangkan  dari  rute R 3 diperoleh  waktu tunggu  selama  54  menit  di  pelanggan  6. Karena  itu  maka  dilakukan  evaluasi  terhadap
urutan
pelayanan pelanggan untuk
memperoleh rute baru yang fisibel. Hasil yang diperoleh adalah R 2 = {0, 1, 5, 2, 4, 0} dan R 3 = {0, 3, 7, 11, 6, 0} . Resume hasil perhitungan disajikan pada Tabel 5 dan Tabel 6.
Tabel 5 Resume hasil perhitungan iterasi 2 Node Tiba Berangkat Waktu menunggu Kumulatif unit Kumulatif jarak Depot 9:00 Pelanggan 1 9:30 9:45 - 7 9.8 Pelanggan 5 10:01 10:16 - 13 15.1 Pelanggan 2 10:21 10:37 - 21 15.8 Pelanggan 4 10:48 11:15 12 menit 29 19.4 Depot 11:45 29.3 Tabel 6 Resume hasil perhitungan iterasi 3 Node Tiba Berangkat Waktu menunggu Kumulatif unit Kumulatif jarak Depot 9:00 Pelanggan 3 9:30 9:45 - 6 9.8 Pelanggan 7 10:06 10:21 - 14 16.3 Pelanggan 11 10:26 10:41 - 19 17.2 Pelanggan 6 10:46 11:15 14 menit 26 17.9 Depot 11:38 25.5

## 6. ANALISIS NILAI PARAMETER
Metode  heuristik  yang  dibahas  pada  makalah ini  menggunakan  formula  yang  sederhana sehingga  dapat  dengan  mudah  diselesaikan secara  manual,  meskipun  untuk  persoalan yang  berukuran  besar.  Karena  solusi  yang diperoleh akan ditentukan oleh nilai parameter-parameter μ,  α 1 ,  α 2 ,  dan λ yang digunakan,  maka  perlu  dilakukan  analisis terhadap  nilai  parameter-parameter  tersebut untuk memperoleh solusi terbaik (berdasarkan kriteria yang ditetapkan).
Analisis  dilakukan  dengan  skenario  sebagai berikut:
1.  Perubahan nilai parameter
 Nilai  parameter µ akan  dirubah mulai  dari µ =  1  hingga µ =  9 dengan perubahan nilai sebesar 1
 Nilai parameter α 1 akan dirubah mulai  dari α 1 =  0,1  hingga α 1 =
0,9  dengan  perubahan  sebesar
0,1 ( α 2 = 1- α 1 )
 Nilai  parameter λ akan  dirubah mulai  dari λ =  1  hingga λ =  9 dengan perubahan sebesar 1 2.  Pengulangan perhitungan 1
 Perhitungan diawali dengan menetapkan µ =  1; α 1 =  0,1; α 2 = 1- α 1 dan λ = 1
 Ulangi  perhitungan  dengan µ =
1; α 1 = 0,2; α 2 =  1- α 1 dan λ =  2 kemudian  dengan µ =  1; α 1 = 0,3; α 2 =  1- α 1 dan λ =  3  dan seterusnya sehingga terjadi pengulangan sebanyak 9 kali
 Ulangi perhitungan
dan
pengulangan  dengan µ =  2 hingga µ =  9  sehingga  total diperoleh 81 hasil perhitungan
3.  Pengulangan perhitungan 2
 Lakukan  proses  yang  sama diawali  dengan  menetapkan α 1 = 0,1; α 2 = 1- α 1 tetapi dengan µ = 1 dan λ = 1 hingga µ = 9 dan λ = 9  Ulangi
perhitungan
dan pengulangan  dengan α 1 =  0,2 hingga α 1 =  0,9  sehingga  total diperoleh 81 hasil perhitungan 4.  Pengulangan perhitungan 3
 Lakukan  proses  yang  sama diawali dengan menetapkan nilai λ =  1;  tetapi  dengan α 1 = 0,1; α 2 = 1- α 1 dan µ = 1 hingga α 1 = 0,9; α 2 = 1- α 1 dan µ = 9 
Ulangi
perhitungan
dan
pengulangan  dengan λ =  2
hingga λ =  9  sehingga  total diperoleh 81 hasil perhitungan
Untuk nilai µ = 1 dengan α 1 , α 2 , dan λ berubah hasil  perhitungan  memberikan  total  jarak tempuh  yang  berbeda  seperti  ditunjukkan pada Gambar 1.
Gambar 1
Hasil perhitungan untuk µ = 1 dengan α 1 , α 2 , dan λ berubah
Gambar  di  atas  menunjukkan  bahwa  untuk parameter µ = 1, total jarak terpendek = 106,8 diperoleh saat nilai α 1 = 0,2 dan λ = 2
Adapun  hasil  keseluruhan  dari  pengulangan perhitungan  1 ( µ tetap, α 1 , α 2 , dan λ berubah) ditunjukkan pada Tabel 7 dan  Gambar 2.

## Tabel 7
Resume Hasil Perhitungan untuk µ tetap, α 1 , α 2 , dan λ berubah
µ λ 1 1
0.2 0.8 2 106.8 km 2 2 0.2 0.8 2 106.8 km 3 3 0.2 0.8 2 106.8 km 4 4 0.2 0.8 2 106.8 km 5 5 0.2 0.8 2 106.8 km 6 6 0.2 0.8 2 106.8 km 7 7 0.2 0.8 2 106.8 km 8 8 0.2 0.8 2 106.8 km 9 9 0.2 0.8 2 106.8 km
perubahan Parameter NO total jarak _1 _2

## Gambar 2
Gambar 2. Grafik perbandingan hasil perhitungan untuk µ tetap, α 1 , α 2 , dan λ berubah
Rute yang terbentuk adalah:
R 1 = {0, 9, 8, 10, 12, 0}, R 2 = {0, 1, 2,5, 0}, R 3 = {0, 3, 6, 7, 0}, dan R 4 = {0, 11, 4, 0}.
Hasil keseluruhan  pengulangan  perhitungan 2 ( α 1 ,  α 2 tetap, µ dan λ berubah)  ditunjukkan pada Tabel 8 dan Gambar 3.

## Tabel 8
Resume Hasil Perhitungan untuk α 1 , α 2 tetap, µ dan
λ berubah
Rute yang terbentuk adalah:
R 1 = {0, 9, 8, 10, 12, 0}, R 2 = {0, 1, 2,5, 0}, R 3 = {0, 3, 6, 7, 0}, dan R 4 = {0, 11, 4, 0}.

## Gambar 3
Grafik perbandingan hasil perhitungan untuk α 1 , α 2 tetap, µ dan λ berubah
Hasil keseluruhan  pengulangan  perhitungan 3 ( α 1 ,  α 2 tetap, µ dan λ berubah)  ditunjukkan pada Tabel 9 dan Gambar 4.

## Tabel 9
Resume Hasil Perhitungan untuk λ tetap, µ dan α 1 ,
α 2 berubah
µ λ 1 2
0.1 0.9 2 106.8 km 2 1 0.2 0.8 1 106.8 km 3 1 0.6 0.4 1 106.8 km 4 1 0.7 0.3 1 106.8 km 5 1 0.8 0.2 1 106.8 km perubahan Parameter NO total jarak 1 2 µ λ 1
6 0.6 0.4 1 106.8 km 2 7 0.7 0.3 1 106.8 km 3 8 0.8 0.2 1 106.8 km 4 9 0.9 0.1 1 106.8 km 5 1 0.1 0.9 2 106.8 km 6 2 0.2 0.8 2 106.8 km 7 3 0.3 0.7 2 106.8 km 8 4 0.4 0.6 2 106.8 km 9 5 0.5 0.5 2 106.8 km 10 6 0.6 0.4 2 106.8 km 11 7 0.7 0.3 2 106.8 km 12 8 0.8 0.2 2 106.8 km 13 9 0.9 0.1 2 106.8 km 14 1 0.1 0.9 3 106.8 km 15 2 0.2 0.8 3 106.8 km 16 3 0.3 0.7 3 106.8 km 17 4 0.4 0.6 3 106.8 km 18 5 0.5 0.5 3 106.8 km 19 6 0.6 0.4 3 106.8 km 20 1 0.1 0.9 4 106.8 km 21 2 0.2 0.8 4 106.8 km 22 3 0.3 0.7 4 106.8 km 23 4 0.4 0.6 4 106.8 km 24 1 0.1 0.9 5 106.8 km
NO perubahan Parameter total jarak
_1 _2
R 1 = {0, 9, 8, 10, 12, 0}, R 2 = {0, 1, 2,5, 0}, R 3 = {0, 3, 6, 7, 0}, dan R 4 = {0, 11, 4, 0}.

## Gambar 4
Grafik perbandingan hasil perhitungan untuk λ tetap, µ dan α 1 , α 2 berubah

## IV. PENUTUP
Pendisribusian  suatu  komoditas  dari  depot atau gudang ke sejumlah agen atau pelanggan  merupakan  permasalahan  yang umum  dijumpai  dalam  kehidupan  sehari-hari, sekaligus  merupakan  permasalahan  yang tidak  mudah  untuk  diselesaikan  dengan menggunakan    model  optimasi.  Karena  itu perlu dikembangkan suatu metode penyelesaian  yang  sederhana  dan  mudah dilakukan,  tetapi  dapat  memberikan  solusi yang  cukup  baik  dan  mendekati  solusi optimalnya.
Metode  heuristik  yang  dibahas  pada  makalah ini  mengasumsikan  bahwa  ongkos  bersifat
proporsional terhadap jarak dan waktu tempuh. Apabila asumsi ini tidak berlaku maka pada  proses  pemilihan  node  yang  akan disisipkan  (langkah  2),  nilai Z 11 (i,  u,  j  ) dan Z 12 (i, u, j ) harus dikalikan dengan unit ongkos yang  berlaku.  Demikian  juga  dengan  ( λ  d 0u ) harus  dikalikan  dengan  unit  ongkos  yang berlaku sebelum menghitung nilai Z 2 (i, u, j ) .

## DAFTAR PUSTAKA
[1] Solomon, M.M. (1987), “Algorithms for the  Vehicle  Routing  and  Scheduling Problems with Time Window Constraints”, Operations Research 35,
254  265.
[2]
Solomon,  M.M.,  E.K.  Baker  and  J.R.
Schaffer  (1988),  “Vehicle  Routing  and Scheduling Problems with Time Window Constraints: Efficient Implementations of Solution Improvement  Procedures”,  in Vehicle Routing:  Methods  and  Studies ,  B. Golden  and  A.  Assad  (eds),  85 –106, Elsevier Science Publishers, Amsterdam.
[3] Solomon,  M.M.  and  J.  Desrosiers (1988),  “Time  Window  Constrained
Routing  and  Scheduling  Problems”,
Transportation Science 22, 1  13.
[4] Thangiah,  S.R.,  I.H.  Osman,  R.
Vinayagamoorthy  and  T.  Sun  (1995), ”Algorithms  for  the  Vehicle  Routing Problems  with  Time  Deadlines”,
American Journal of Mathematical and Management Sciences 13, 323  355.
[5] Ioannou,  G.,  M.  Kritikos  and  G.
Prastacos  (2001),  “A  Greedy  Look- Ahead  Heuristic  for  the  Vehicle
Routing Problem with Time Windows”,
Journal  of  the  Operational  Research Society 52, 523  537.
[6] Ghiani,  G.,  G.  Laporte,  and  R.
Musmanno  (2004),  “ Introduction  to Logistics Systems Planning and
Control ”,  John  Wiley  &  Sons  Ltd.
England, 273  279.