## PEMECAHAN MASALAH RUTE KENDARAAN DENGAN TRIP MAJEMUK, JENDELA WAKTU DAN PENGANTARAN-PENJEMPUTAN SIMULTAN MENGGUNAKAN ALGORITMA GENETIKA

## Suprayogi*, Muhammad Syafaruddin Mahaputra
Fakultas Teknologi Industri, Institut Teknologi Bandung
(Received: Octobre 18, 2016/ Accepted: July 17, 2017)

## Abstrak
Masalah rute kendaraan (MRK) merupakan salah satu masalah  keputusan yang memegang peranan penting  dalam  kegiatan  transportasi  dan  distribusi  dalam  manajemen  logistik.  MRK  terkait  dengan penentuan  rute-rute  kendaraan  yang  meminimumkan  total  jarak  yang  ditempuh  dengan memperhatikan  pembatas-pembatas  berikut:  (1)  tiap  rute  berawal  dan  berakhir  di  depot,  (2)  tiap kendaraan  hanya  melayani  satu  rute,  (3)  tiap  pelanggan  dilayani  oleh  satu  rute,  (4)  seluruh pelanggan  harus dilayani, dan (5) total  muatan untuk tiap rute tidak melebihi  kapasitas kendaraan. Dalam literatur, definisi ini merupakan definisi untuk MRK dasar atau klasik. Makalah ini membahas perluasan dari MRK dasar yang mencakup karakteristik-karakteristik berikut: (1) trip majemuk (TM), (2)  jendela  waktu  (JW)  dan  (3)  pengantaran-penjemputan  simultan  (AJS).  Metode  pemecahan berbasis  algoritma  genetika  (AG)  diusulkan  untuk  memecahkan  MRK  yang  dibahas  dalam  makalah ini. AG yang diusulkan diuji-coba dengan menggunakan beberapa contoh hipotetik.
Kata  kunci: masalah  rute  kendaraan;  rute  majemuk;  jendela  waktu;  pengantaran-pengambilan simultan; algoritma genetika.

## Abstract
Vehicle routing problem (VRP) is one of decision problems having an important role in transportation and distribution  activity in  the logistic management. The VRP  deals  with determining  vehicle routes that minimizes total distance by satisfying the following constraints: (1) each route starts and ends at the  depot,  (2)  each  vehicle  serves  only  one  route,  (3)  each  costumer  is  served  by  one  route,  (4)  all customers must be served, and (5) total load for each route does not exceed the vehicle capacity. In literature,  this  definition  is  the  definition  for  the  basic  or  classical  VRP.  This  paper  discusses  an extension  of  the  basic  VRP  including  the  following  characteristics:  (1)multiple  trips  (MT),  (2)  time windows  (TW),  and  (3)  simultaneous  pickup-delivery  (SPD).  A  solution  method  based  on  genetic algorithm (GA) is proposed to solve the VRP discussed in this papaer. The proposed GA is examined using some hypothetical instances.
Keywords: evhicle  routing  problem;  multiple  trips,  time  windows;  simultaneous  pickup-delivery; genetic algorithm

## Pendahuluan
Masalah  rute  kendaraan  (MRK),  yang  pertama kali  diperkenalkan  oleh  Dantzig  dan  Ramser  (1959), merupakan salah satu permasalahan yang memegang peranan  penting  dalam  kegiatan  transportasi  dan distribusi  dalam  manajemen  logistik.  MRK  terkait dengan penentuan rute-rute kendaraan yang meminimumkan  total  jarak  dengan  memperhatikan pembatas-pembatas berikut: (1) tiap rute berawal dan berakhir di depot, (2) tiap kendaraan hanya melayani satu  rute,  (3)  tiap  pelanggan  dilayani  oleh  satu  rute,
(4)  seluruh  pelanggan  harus  dilayani,  dan    (5)  total muatan  untuk  tiap  rute  tidak  melebihi  kapasitas kendaraan.  Dalam  literatur,  definisi  ini  merupakan definisi  untuk  MRK  dasar  atau  klasik.  Makalah  ini membahas  tentang  perluasan  dari  MRK  dasar  yang mencakup  karakteristik-karakteristik  berikut:  (1) trip majemuk  (TM),  (2)  jendela  waktu  (JW)  dan  (3) pengantaran-penjemputan simultan (AJS).
Selanjutnya,  MRK  yang  dibahas  dalam  makalah  ini disingkat dengan MRK-TM-JW-AJS.
TM  merupakan salah karakteristik dalam  MRK yang  sering  muncul  dalam  situasi  praktis.  Dalam MRK  dasar,  tiap  kendaraan  diasumsikan  hanya melayani  satu  rute  sepanjang  horison  perencanaan.
MRK-TM  merupakan MRK  yang  mengijinkan suatu
-------------------------------------------------------------
*) Penulis Korespondensi. email: yogi@mail.ti.itb.ac.id
kendaraan  untuk  melayani  satu  rute  atau  lebih sepanjang horison perencanaan. Salah satu pembahasan  awal  dari  MRK-TM  antara  lain dilakukan oleh Taillard dkk. (1996). Dalam  literatur, MRK-TM  dikenal  juga  dengan  istilah  MRK  dengan pengunaan  kendaraan  majemuk.  Dalam  konteks MRK-TM,  terdapat  dua  istilah  umum  yang digunakan  seperti  didefinisikan  oleh  Brandão  dan Mercer  (1997),  yaitu trip (rute)  dan  tur.  Suatu trip atau  rute  merupakan  suatu  urut-urutan  kunjungan kendaraan yang berawal dan berakhir di depot. Suatu tur merupakan kumpulan satu atau lebih trip atau rute yang dilayani oleh satu kendaraan yang sama.
Dalam MRK dasar, tiap pelanggan diasumsikan dapat  dikunjungi  kapan  pun  sepanjang  horizon perencanaan. Dalam MRK-JW, tiap pelanggan hanya dapat  dilayani  oleh  suatu  kendaraan  pada  suatu interval  waktu  tertentu  dalam  horizon  perencanaan. Interval  waktu  ini  disebut  dengan  jendela  waktu. Suatu jendela waktu dicirikan oleh saat buka dan saat tutup.  Pelayanan  pada  tiap  pelanggan  hanya  dapat dimulai  tepat  pada  atau  setelah  saat  buka.  Jika kendaraan  tiba  pada  suatu  pelanggan  sebelum  saat bukanya,  maka  kendaraan  tersebut  harus  menunggu. Pelayanaan  pada  tiap  pelanggan  harus  diakhiri sebelum  atau  tepat  pada  saat  tutup.  MRK-JW  telah banyak dibahas dalam literatur. Beberapa diantaranya adalah  Solomon  (1987).  Dalam  konteks  adanya  JW, MRK  tidak  hanya  terkait  aspek  spasial  (penentuan rute),  namun  juga  terkait  dengan  aspek  temporal (penentual  jadwal)  seperti  dikemukakan  oleh  Bodin dan Golden (1981).
MRK  dasar  hanya  berkaitan  dengan  operasi pengantaran  atau  penjemputan  saja,  tidak  keduanya. Di sini, permintaan pada tiap pelanggan hanya terkait dengan permintaan pengantaran (untuk kasus operasi pengantaran)  atau  permintaan  penjemputan  (untuk kasus penjemputan). Dalam situasi nyata, adakalanya tiap pelanggan memiliki permintaan pengantaran dan penjemputan  sekaligus.  MRK  dengan  karakteristik ini  disebut  dengan  MRK-AJS  yang  pertama  kali diperkenalkan oleh Min (1989).
Kombinasi  karakteristik-karakteristik  TM,  JW dan  AJS  dalam  MRK  telah  dibahas  dalam  literatur. Kombinasi  antara  TM  dan  JW  telah  dibahas  antara lain  oleh:  Brandão  dan  Mercer  (1997),  Suprayogi (2003),  Suprayogi  dan  Imawati  (2005),  Suprayogi dkk.  (2005,  2007,  2011),  Battarra  dkk.  (2009),  Azi (2010)  dan  Hernandez  dkk.  (2014,  2016).  Ong  dan Suprayogi  (2011)  membahas  MRK-TM-JW  dalam konteks backhauls .  Nguyen  dkk.  (2013)  membahas MRK-TM-JW  dalam  kaitan  pembatas  sinkronisasi waktu. Cattaruzza dkk. (2014) membahas MRK-TM- JW  dengan  melibatkan  atribut release  date .    MRK dengan  kombinasi  karakteristik-karakteristik  JW  dan AJS  (MRK-JW-AJS)  telah  dibahas  oleh  Mingyong dan  Erbao  (2010),  Fan  (2011),  Wang  dan  Chen (2012,  2013),  Liu  dkk.  (2013),  Avci  dan  Topaloglu (2015) dan Wang dkk. (2015).
Sepanjang  pengetahuan,  MRK-TM-JW-AJS sangat sedikit dibahas dalam literatur. Suprayogi dan Priyandari  (2007,  2009)  merupakan  literatur  yang membahas MRK-TM-JW-AJS. Suprayogi dan Priyandari  (2007)  mengusulkan  metode  pemecahan yang  berbasis  algoritma  penyisipan  sekuensial  yang merupakan  metode  heuristik  konstruksi.  Suprayogi dan Priyandari (2009) mengusulkan metode heuristik perbaikan  dalam  bentuk  metode  pencarian  lokal ( local search ) dengan menggunakan solusi awal yang dibangkitkan menggunakan metode penyisipan sekuensial  dari  Suprayogi  dan  Priyandari  (2007). Struktur  ketetanggaan  dibentuk  dengan  menerapkan operasi-operasi  perbaikan  yang  terdiri  atas  operator- operator relokasi, pertukaran dan persilangan. Ketiga operator ini dimodifikasi dari Suprayogi dkk. (2007) yang sebelumnya diterapkan untuk MRK dengan trip majemuk dan jendela waktu.
MRK  dasar  dan  perluasannya  merupakan  salah masalah  optimisasi  kombinatorial  yang  sulit  seperti dikemukan  oleh  Lenstra  dan  Rinnooy-Kan  (1981). Oleh  karena  itu,  pemecahan  MRK  dan  varian- variannya  banyak  menggunakan  metode-metode heuristik.
Makalah  ini  mengusulkan  metode  algoritma genetika  (AG).  AG  merupakan  salah  satu  metode metaheuristik  yang  mengambil  analogi  dari  konsep evolusi.  AG  banyak  digunakan  untuk  memecahkan masalah-masalah optimisasi kombinatorial yang sulit, termasuk  MRK.  Kontribusi  dari  makalah  ini memberikan  metode  alternatif  untuk  pemecahan MRK-TM-JW-AJS.

## Definisi Masalah
Definisi  dari  MRK  dengan trip majemuk, jendela  waktu  dan  pengantaran  dan  penjemputan simultan  dalam  makalah  ini  diambil  dari  Suprayogi dan  Priyandari  (2007,  2009).  Misal  terdapat  satu depot dan sejumlah n pelanggan. Untuk simplifikasi, misal  depot  disimbolkan  dengan  angka  0  dan pelanggan-pelanggan dinyatakan dengan angka  bulat 1  sampai  dengan n . Misal C={0,1,..,n} menyatakan himpunan pelanggan. Misal himpunan N menyatakan gabungan  depot  dan  himpunan  pelanggan,  yaitu N=C  {0} . Tiap  pelanggan i  C berasosiasi  dengan kuantitas    permintaan  penjemputan p i ,  kuantitas permintaan  pengantaran  d i dan  jendela  waktu  ( e i ,l i ) dengan e i dan l i masing-masing  menunjukkan  saat buka  dan  saat  tutup.  Waktu  pelayanan  pada  tiap pelanggan i  C , dinotasikan dengan s i , menunjukkan waktu bongkar-muat dan diasumsikan tidak tergantung  pada  kuantitas  yang  dibongkar-muat. Asumsi bahwa s i ≤ l i ─ e i untuk tiap i  C . Terdapat sejumlah kendaraan  yang  berpangkalan di  depot dan diasumsikan  tak  terbatas.  Kendaraan-kendaraan
diasumsikan  homogen  dengan  kapasitas  muatan  tiap kendaraan  dinyatakan  dengan Q .  Asumsi  bahwa Q ≥ p i dan Q ≥ q i untuk tiap i  C . Waktu perjalanan antara i  N dan j  N adalah diketahui dan dinyatakan dengan t ij serta diasumsikan bahwa waktu perjalanan adalah simetris, yaitu t ij = t ji . Terdapat jendela waktu pada depot yang dinyatakan dengan e 0 , l 0 dengan e 0 dan l 0 masing-masing menyatakan saat buka dan saat tutup.  Selisih  antara l 0 dan e 0 pada  dasarnya menunjukkan panjang horison perencanaan h . MRK-TM-JW-AJS  terkait  dengan  penentuan rencana tur yang  mencakup  informasi tentang tur-tur kendaraan  dan  jadwal.  Rencana  tur  yang  diperoleh harus  memperhatikan  pembatas-pembatas  sebagai berikut:  (1)  suatu  tur  paling  sedikit  mencakup  satu rute  ( trip ),  (2)  tiap  tur  tepat  dilayani  oleh  satu kendaraan,  (3)  tiap  rute  ( trip )  berawal  dan  berakhir pada  depot,  (4)  total  muatan  pada  suatu  rute  ( trip ) kendaraan  tidak  melebihi  kapasitas  kendaraan,  (5) semua  pelanggan  harus  terlayani,  (6)  tiap  pelanggan tepat  dikunjungi  satu  kali,  (5)  saat  pelayanan bongkar-muat (di depot dan pelanggan) harus dimulai pada  atau  setelah  saat  buka,  (6)  saat  pelayanan bongkar-muat  (di  depot  dan  pelanggan)  harus diakhiri pada atau sebelum saat tutup.
Terdapat tiga ukuran kinerja yang dipertimbangkan  yang  semuanya  diminimumkan, yaitu  jumlah  kendaraan  yang  digunakan NV ,  total waktu durasi tur TDT , dan rentang waktu durasi tur RDT .  Waktu  durasi  tur  tiap  kendaraan  mencakup waktu  perjalanan,  waktu  pelayanan  dan  waktu menunggu.  Waktu  durasi  tur  didefinisikan  sebagai selisih antara saat kendaraan mengakhiri pelayanan di depot  untuk  terakhir  kali  dengan  saat  kendaraan mengawali  pelayanan  di  depot  untuk  pertama  kali pada suatu tur. Di sini, saat pelayanan di depot untuk pertama  kali  pada  suatu  tur  tidak  harus  terjadi  pada saat  buka e 0 . Definisi  waktu  durasi  ini  diadopsi  dari Savelsbergh (1992). Rentang waktu durasi tur adalah selisih  antara  waktu  durasi  tur  maksimum  dan minimum.  Meminimumkan  rentang  waktu  durasi  tur digunakan  dalam  usaha  untuk  menghasilkan  waktu durasi tur yang seimbang mungkin untuk seluruh tur.
Pencapaian  ukuran  kinerja  dilakukan  dengan urutan  prioritas  sebagai  berikut:  jumlah  kendaraan, total  waktu  durasi  tur  dan  rentang  waktu  durasi  tur. Pencapaian  ukuran  kinerja  yang  lebih  rendah  tetap harus  mempertahankan  pencapaian  ukuran  kinerja yang  lebih  tinggi.  Misal v menyatakan  solusi (rencana  tur),  penangangan  ukuran  kinerja  majemuk dilakukan  dengan  metode  jumlah  terbobot  ( weighted sum ) seperti dinyatakan dalam persamaan berikut:
F(v) = w NT NT(v) + w TDT TDT(v) + w RDT RDT(v) (1)
dengan  notasi-notasi w NT , w TDT ,  dan w RDT masing- masing  menunjukkan  bobot  yang  berasosiasi  dengan jumlah kendaraan, total waktu durasi tur dan rentang waktu  durasi  tur.  Pemilihan  nilai-nilai  bobot dilakukan  sedemikian  rupa  sehingga  menjamin pemenuhan urutan prioritas, yaitu
w NT NT ( v ) > w TDT TDT ( v ) > w RDT RDT ( v )

## Algoritma Genetika
Kerangka Algoritma Genetika MRK dengan trip majemuk,  jendela waktu dan pengantaran-penjemputan  simultan  yang  dibahas dalam  makalah  ini  dipecahkan  dengan  algoritma genetika  (AG).  AG  dimulai  dengan  pembangkitan populasi  awal  sebanyak  ukuran  populasi  yang  telah ditetapkan.  Tiap  individu  atau  kromosom  dalam populasi  awal  dibangkitkan  dengan  algoritma penyisipan sekuensial. Nilai fitness dari tiap individu pada  suatu  populasi  dihitung  berdasarkan  jumlah tertimbang  dari  ketiga  ukuran  kinerja  seperti  telah ditunjukkan  dalam  persaamaan  (1).  Berdasarkan populasi saat ini, populasi yang baru dibentuk dengan menerapkan  tiga  operator  genetika  secara  paralel. Operator-operator  genetika  yang  digunakan  adalah elitisme ( elitism ), persilangan ( crossover ) dan mutasi ( mutation ).  Jumlah  individu  yang  dibentuk  dari ketiga  operator  ditentukan  berdasarkan  tingkat proporsi  yang  ditetapkan.  Khusus  untuk  operator persilangan,  jumlah  individu  yang  terbentuk  harus merupakan  angka  genap.  Prosedur  AG  berhenti  jika iterasi  telah  mencapai  jumlah  generasi  maksimum yang  telah  ditetapkan.    Secara  umum,  langkah- langkah  AG  yang  diterapkan  ditunjukkan  pada Gambar 1.

## Representasi Individu
Individu  direpresentasikan  sebagai  bilangan bulat.  Depot  diwakili  oleh  angka  nol  dan  pelanggan diwakili  oleh  bilangan  bulat  positif  yang  lebih  besar daripada  nol.  Sebuah  tur  kendaraan  dengan  dua  rute diperlihatkan oleh contoh berikut:
0 – 4 – 6 – 2 – 0 – 1 – 10 – 0
0 – 26 – 30 – 1 – 0 – 25 – 53 – 0

## Populasi Awal
Tiap  individu  dalam  populasi  awal  dibentuk dengan menggunakan algoritma penyisipan sekuensial. Setiap individu dibangkitkan secara acak. Gambar  2  dan  Gambar  3  menunjukkan  diagram  alir dari  prosedur  pembentukan  individu  dalam  populasi awal  dengan  menggunakan  algoritma penyisipan sekuensial.
START Pembentukan Generasi Nol (Populasi Awal) Awal Generasi Pertama i = 1 i <= Maksimum Generasi ? Elitis Crossover Mutasi Generasi Berikutnya i = i + 1 END Ya Tidak
Gambar 1 . Diagram alir dari prosedur AG yang dikembangkan

## Penentuan nilai fitness
Untuk  tiap  individu,  nilai fitness dihitung menggunakan  persamaan  (1).  Nilai fitness ini menunjukkan nilai fungsi tujuan.

## Operator-operator genetika
Operator-operator  genetika  digunakan  untuk membentuk  populasi  baru  dari  populasi  saat  ini. Seperti  telah  dijelaskan  sebelumnya,  terdapat  tiga operator  genetika  yang  digunakan,  yaitu  elitisme, persilangan dan  mutasi.   Dalam  AG  yang diusulkan, ketiga  operator  dilakukan  secara  paralel.  Jumlah individu  yang  dibentuk  dari  tiap  operator  ditentukan berdasarkan perkalian antara proporsi masing-masing yang  telah  ditetapkan  dikalikan  dengan  ukuran populasi.

## Elitisme
Elitisme  merupakan  operator  yang  melakukan pengambilan  individu  terbaik  generasi  sebelumnya. Elitisme  diperlukan  untuk  menjamin  bahwa  individu terbaik  tetap  dipertahankan  pada  populasi  dari  satu generasi ke generasi berikutnya.

## Persilangan.
Persilangan  merupakan  proses  penggabungan dua  string  induk  menjadi  dua  string  anak  yang berbeda  dengan  string  induknya  dengan  cara mempertukarkan  (mengambil  informasi)  bagian  dari string  induk.  Berdasarkan  nilai-nilai fitness ,  dua individu  terbaik  dari  kedua  induk  dan  kedua  anak dipilih  untuk  menjadi  individu  pada  populasi  baru. Untuk  setiap  operasi  persilangan,  dua  induk  dipilih dengan metode roulette wheel .  Misal v adalah suatu individu  dalam  populasi P dengan  nilai fitness yang
berasosiasi  dinyatakan  dengan f ( v ).  Probabilitas untuk individu v  P yang terpilih dinyatakan dengan:
( (2)

## Mutasi.
Mutasi  berperan  dalam  melakukan  perubahan pada suatu individu.  Pemilihan induk yang dimutasi dilakukan  secara  acak  dari  individu-individu  dalam populasi  saat  ini.    Berdasarkan  nilai-nilai fitness , individu  terbaik  dari  induk  dan  anak  dipilih  untuk menjadi individu pada populasi.

## Hasil Percobaan
AG  yang  dikembangkan  diimplementsikan dalam suatu program komputer menggunakan bahasa pemrograman  Visual  Basic  6.0.  Dalam  percobaan, piranti  lunak  aplikasi  dijalankan  dengan  komputer dengan  spesifikasi  sebagai  berikut:  prosesor  Intel Pentium  IV  1.8  GHz,  memori  DDRAM  256  MB, sistem  operasi Microsoft  Windows  XP  Professional Edition .  Gambar  4  menunjukkan  beberapa  tampilan dari piranti lunak aplikasi yang dikembangkan.
AG  yang  diusulkan  diuji  coba  menggunakan sembilan  contoh  hipotetik  seperti  yang  terdapat dalam Suprayogi dan Priyandari (2007). Tiap contoh hipotetik  memiliki  100  pelanggan.  Lokasi-lokasi pelanggan  dibangkitkan  secara  random  antara koordinat  (0,0)  dan  (600,600).  Koordinat  depot berada  pada  koordinat  (300,300).  Karakteristik jendela  waktu  untuk  pelanggan  dikelompokkan menjadi  tiga,  yaitu:  sempit,  lebar  dan  tercampur. Jendela  waktu  sempit  dibangkitkan  secara  random antara  10  hingga  50.  Jendela  waktu  lebar dibangkitkan  antara  395  hingga  539.  Jendela  waktu campuran  memiliki  lebar  antara  10  sampai  501. Karakteristik-karakteristik  dari  kesembilan  contoh data  hipotetik  ditunjukkan  pada  Tabel  1.  Gambar  5 menunjukkan lokasi  pelanggan yang  teracak, terkelompok dan tercampur.
Data-data yang lain adalah berikut ini:
● Waktu  layanan  baik  depot  maupun  pelanggan adalah 10 menit.
● Kuantitas permintaan penjemputan dan kuantitas  permintaan  pengantaran  adalah  acak dengan rentang 1 hingga 10 unit.
● Kecepatan kendaraan adalah 40 km/ jam.
● Kapasitas kendaraan adalah 20 unit.
● Saat  buka  dan  saat  buka  dari  depot  masing- masing adalah 0 dan 540.
● Penggunaan  skala  dalam  data  hipotetik  adalah 1:60.
Dalam eksperimen, parameter-parameter algoritma  genetika  yang  digunakan  adalah  berikut ini:  jumlah  generasi  maksimum  =  20,  ukuran populasi  =  20,  tingkat  proporsi  elitisme  =  50%, tingkat  proporsi  persilangan  =  30%,  dan  tingkat proporsi  mutasi  =  20%.  Untuk  perhitungan fitness ,
nilai bobot masing-masing adalah: w 1 = 100.000, w 2 =  0,4  dan w 3 =  0,00005.  Hasil  percobaan  dengan
melakukan 10 replikasi untuk setiap contoh hipotetik ditunjukkan pada Tabel 2.
START Buat tur pertama dan pelanggan pertama t = 1 k = 1 Semua pelanggan dialokasikan? Bangkitkan pelanggan berikutnya yang belum dialokasikan Sisipkan pelanggan berikutnya ini di antara depot dan pelanggan-pelanggan yang telah dialokasikan Ya Tidak Ya Bisa Disisipkan ? Semua pelanggan yang belum dialokasikan telah dibangkitkan ? Tidak Tidak Buat tur baru t = t + 1 k = 1 Semua pelanggan telah dialokasikan ? Tidak Ya END Ya Pelanggan berikutnya k = k + 1 Panggil subrutin Atur_Rute (tur t)
Gambar 2 . Diagram Alir Utama dari Prosedur Pembentukan Individu dalam Populasi Awal
START (t) Beban Isi = 0 Beban Kosong = 0 Waktu = 0 Pelanggan Pertama i = 1 i <= Total Pelanggan Hitung Total Pelanggan yang telah dialokasikan untuk kendaraan t Temp beban isi = Beban Isi + Pelanggan(i).Delivery Temp beban kosong = Beban Kosong + Pelanggan(i).Pickup Temp beban isi <= Kapasitas Kendaraan Temp beban kosong <= Kapasitas Kendaraan Ya Beban Isi = Temp beban isi Beban Kosong = Temp beban kosong Waktu < Pelanggan(i).Early_Time Waktu = Pelanggan(i).Early_Time Ya Waktu = Waktu + Pelanggan(i-1).Service_Time + Jarak(Pelanggan(i-1), Pelanggan(i)) / Kendaraan.Kecepatan * 60 menit Tidak Pelanggan berikutnya i = i + 1 Ya Sisipkan depot ( multiple trips )
Beban Isi = 0 Beban Kosong = 0
Waktu = Waktu + Pelanggan(i-1).Service_Time + Jarak(Pelanggan(i-1), Depot) / Kendaraan.Kecepatan * 60 menit
Temp waktu = Waktu + Depot.Service_Time + Jarak(Depot, Pelanggan) / Kendaraan.Kecepatan * 60 menit + Pelanggan(i).Service_Time
Temp waktu <=
Pelanggan(i).Deadline Beban Isi = Beban Isi + Pelanggan(i).Delivery Beban Kosong = Beban Kosong + Pelanggan(i).Pickup Waktu = Temp waktu Tidak Tidak Tidak Ya End Ya Tidak
Gambar 3. Diagram Alir untuk Subrutin Pengaturan Rute pada Pembentukan Individu dalam Populasi Awal
Tampilan login Tampilan data Tampilan proses
Tampilan peta tur Gambar 4 . Beberapa Tampilan dari Piranti Lunak Aplikasi
Tabel 1 . Karakteristik-Karakteristik untuk Contoh-Contoh Hipotetik
Jendela waktu Sempit Lebar Tercampur Lokasi pelanggan Teracak R1 R2 R3 Terkelompok C1 C2 C3 Tercampur M1 M2 M3
Lokasi pelanggan teracak Lokasi pelanggan terkelompok Lokasi pelanggan tercampur Gambar 5 . Lokasi Pelanggan Tabel 2 . Hasil-Hasil Percobaan Contoh Jumlah Kendaraan Total waktu durasi tur Rentang waktu durasi tur Nilai fitness Waktu komputasi (detik) R1 Terbaik 8,00 3515,09 111,59 801406,1 122,0 Rata-rata 8,00 3552,94 131,93 801422,1 146,2 R2 Terbaik 4,00 1704,54 312,18 400681,8 59,0 Rata-rata 4,00 1704,54 312,18 400681.8 60,0 R3 Terbaik 6,00 2905,94 112,11 600195,3 84,0 Rata-rata 6,00 2944,76 136,05 601077,9 84,7 C1 Terbaik 7,00 3188,66 59,05 701275,7 115,0 Rata-rata 7,00 3318,59 155,00 701327,5 247,9 C2 Terbaik 4,00 1713,20 157,70 400685,3 61,0 Rata-rata 4,00 1719,68 291,34 400687,9 62,3 C3 Terbaik 5,00 2575,27 8,77 501030,1 78,0 Rata-rata 5.30 2706,46 82,55 531082,6 124,5 M1 Terbaik 7,00 2718,07 115,38 701148,5 168,0 Rata-rata 7.69 3006,35 435,68 771302,7 195,9 M2 Terbaik 4,00 1729,48 173.50 400691,8 60,0 Rata-rata 4,00 1732,91 223,22 400693,2 61,5 M3 Terbaik 5,00 2563,62 13,69 501025,4 76,0 Rata-rata 5,00 2593,90 24,91 501037,5 126,2

## Kesimpulan dan Saran Tindak Lanjut Penelitian
Makalah ini telah membahas salah satu perluasan dari  masalah  rute  kendaraan  (MRK)  dasar  dengan karakteristik-karakteristik  yang  mencakup:  (1) trip majemuk  (TM),  (2)  jendela  waktu  (JW) dan  (3) pengantaran-penjemputan simultan (AJS). MRK yang dibahas  dalam  makalah  ini  (disingkat  dengan  MRK- TM-JW-AJS) memiliki ukuran kinerja majemuk, yaitu meminimumkan  jumlah  kendaraan  yang  digunakan, meminimumkan total waktu durasi tur dan meminimumkan rentang waktu durasi tur. Penanganan ukuran  kinerja  majemuk  dilakukan  dengan  metode jumlah terbobot.
Metode  pemecahan  yang  berbasis  algoritma genetika  (AG))  telah  dikembangkan  sebagai  metode pemecahan. Algoritma penyisipan sekuensial diterapkan  untuk  menghasillkan  individu-individu dalam  populasi  awal.  Metode  pemecahan  yang dikembangkan  telah  diimplementasikan  dalam  suatu piranti lunak.
Penelitian  lanjutan  dapat  dilakukan  dengan mengembangkan  lebih  lanjut  dari  teknik  pemecahan yang  diusulkan,  misalnya  dengan  menerapkan  teknik hibrid.  Pengembangan  lanjutan  ini  diharapkan  dapat meningkatkan kinerja dari metode pemecahan.

## Daftar Pustaka
Avci,  M.,  Topaloglu,  S.  (2015).  An  adaptive  local search  algorithm  for  vehicle  routing  problem with  simultaneous  and  mixed  pickups  and deliveries. Computers  &  Industrial  Engineering
83 , 15–29.
Azi, N., Gendreau, M., Potvin, J. -Y. (2010). An exact algorithm  for  a  vehicle  routing  problem  with time  windows  and  multiple  use  of  vehicles. European Journal of Operational Research 202, 756–763.
Battarra,  M.,  Monaci,  M.,  Vigo,  D.  (2009).  An adaptive  guidance  approach  for  the  heuristic solution  of  a  minimum  multiple  trip  vehicle routing  problem. Computers  &  Operations Research 36, 3041--3050.
Bodin, L., Golden, L. (1981). Classification in vehicle routing and scheduling, Networks 11, 97-108. Brandão,  J.,  Mercer,  A.  (1997).  A  tabu  search algorithm  for  the  multi-trip  vehicle  routing  and scheduling  problem, European  Journal  of Operational Research 100, 180-191. Cattaruzza, D., Asbi, N., Feillet, D. (2014). The multi trip  vehicle  routing  problem  with  time  windows and release dates. Working Paper EMSE CMP– SFL  2014/1,  Ecole  des  Mines  de  Saint-Etienne, Department  of  Manufacturing  Sciences  and Logistics.
Dantzig, G., Ramser, J. (1959). The truck dispatching problem, Management Science 6, 80-91.
Fan,  J.  (2011).  The  vehicle  routing  problem  with simultaneous  pickup  and  delivery  based  on customer  satisfaction. Procedia  Engineering, Volume 15, 5284-5289.
Hernandez,  F.,  Feillet,  D.,  Giroudeau,  R.,  Naud,  O. (2014).  A  new  exact  algorithm  to  solve  the multi-trip  vehicle  routing  problem  with  time windows  and  limited  duration. 4QR  -  Q  J  Oper Res 12, 235-259.
Hernandez,  F.,  Feillet,  D.,  Giroudeau,  R.,  Naud,  O. (2016).  Branch-and-price  algorithms  for  the solution  of  the  multi-trip  vehicle  . European Journal of Operational Research 249, 551–559. Lenstra, J.K., Rinnooy-Kan,  A H. (1981) Complexity of  the  vehicle  routing  and  scheduling  problems, Networks 11, 221-227. Liu,  R.,  Xie,  X.,  Augusto,  V.,  Rodriguez,  C.  (2013). Heuristic  algorithms  for  a  vehicle  routing problem  with  simultaneous  delivery  and  pickup and  time  windows  in  home  health  care. European Journal of Operational Research 230 , 475–486.
Marcedo,  R.,  Alves,  C.,  de  Carvalho,  V.,  Clautiaux, F.,    Hanafi,  S.  (2011).  Solving  the  vehicle routing problem with time windows and multiple routes exactly using a pseudo-polynomial model. Europeam Journal of Operational Research 214, 536-545.
Min, H. (1989). The multiple vehicle routing problem with  simultaneous  delivery  and  pick-up  point, Transportation Research 23 A (5), 377-386. Mingyong,  L.,  Erbao,  C.  (2010).  An  improved differentia  levolution  algorithm  for  vehicle routing  problem  with  simultaneous  pickup  sand deliveries  and  time  windows. Engineering Applications  of  Artificial  Intelligence 23,  188– 195.
Nguyen, P. K., Crainic, T. G., Toulouse, M. (2013). A tabu search for time-dependent multi-zone multi- trip vehicle routing problem with time windows. European Journal of Operational Research 231, 43–56.
Ong,  J.  O.,  &  Suprayogi.  (2011).  Vehicle  routing problem  with  backhaul,  multiple  trips  and  time windows. Jurnal Teknik Industri 13 (1), 1-10. Savelsbergh,  M.  (1992).  The  vehicle  routing  problem with  time  windows:  Minimizing  route  duration, ORSA Journal of Computing 4 (2), 146-154. Solomon,  M.M.  (1987).  Algorithms  for  the  vehicle routing  and  scheduling  problem  with  time window  constraints, Operations  Research 35, 254-265.
Suprayogi.  (2003).  Sequential  insertion  algorithm  for solving  the  vehicle  routing  problem  with multiple  trips  and  time  windows. Jurnal  Teknik dan Manajemen Industri 23 (3) , 30-46. Suprayogi;  Imawati,  D.  (2005).  Sequential  insertion algorithm with forward and backward passes for solving  the  vehicle  routing  problem  with multiple trips and time windows (in Indonesian). Jurnal  Teknik  dan  Manajemen  Industri 25  (1), 41-54.
Suprayogi;  Priyandari,  Y.  (2007)  Teknik  penyisipan sekuensial  untuk  penentuan  rute  kendaraan
dengan  karakteristik  banyak  trip,  jendela  waktu dan  pengantaran-pengambilan  simultan, Jurnal Teknik dan Manajemen Industri, 27 (3), 103-124. Suprayogi;  Priyandari,  Y.  (2009).  Vehicle  routing problem  with  multiple  trips,  time  windows,  and simultaneous  delivery  and  pickup  services, Proceedings  of  Asia  Pacific  Conference  on Industrial Engineering and Management , Kitakyushu, Japan, 1543-1552.
Suprayogi;  Hardianto,  A.,  Yamato,  H.  (2005).  Local search  and  genetic  algorithm  techniques  for solving  vehicle  routing  problem  with  multiple trips  and  time  windows. Proceedings  of International  Conference  on  Operations  and Supply  Chain  Management ,  (pp.  J17-J24).  Bali, Indonesia.
Suprayogi;  Hidayat,  Y.  A.,  Imawati,  D.  (2011). Simulated  annealing  for  solving  the  vehicle routing  and  scheduling  problem  with  multiple trips  and  time  windows  (in  Indonesian). Proceedings of 6th National Industrial Engineering  Conference  2011 ,  (pp.  242-249). Surabaya, Indonesia.
Suprayogi;  Imawati,  D.,  Hardianto,  A.  (2007).  Local search  technique  for  solving  the  vehicle  routing problem  with  multiple  trips  and  time  windows (in  Indonesian). Jurnal  Teknik  dan  Manajemen
Industri 27 (2) , 57-75.
Suprayogi; Imawati, D., Hardianto, A. (2007). Teknik local  search untuk  pemecahan vehicle  routing problem  with  multiple  trips  and  time  windows , Jurnal  Teknik  dan  Manajemen  Industri 27  (2),
57-75.
Taillard,  E.  D.,  Laporte,  G.,  Gendreau,  M.  (1996). Vehicle  routeing  with  multiple  use  of  vehicles, Journal  of  the  Operational  Research  Society 47 (8), 1065-1070.
Wang, C., Mu, D., Zhao, F., Sutherland, J. W. (2015). A  parallel  simulated  annealing  method  for  the vehicle  routing  problem  with  simultaneous pickup–delivery  and  time  windows. Computers & Industrial Engineering 83, 111-122. Wang,  H.,  Chen,  Y.  Y.  (2013).  A  coevolutionary algorithm  for  the  flexible  delivery  and  pickup problem  with  time  windows. International Journal of Production Economics 141, 4-13. Wang, H. -F., Chen, Y. Y. (2012). A genetic algorithm for  the  simultaneous  delivery  and  pickup problems  with  time  windows. Computers  & Industrial Engineering 62, 84–95.