Jurnal Teknik Informatika dan Sistem Informasi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal. 1984-1997 E- ISSN 2503-2933 1984

## Penyelesaian Urban Transit Routing Problem

## Menggunakan Algoritma Hyper-Heuristics Berbasis
Modified Particle Swarm Optimization Based On Gravitational Field Interactions
Shof Rijal Ahlan Robbani* 1 , Ahmad Muklason 2 1,2 Jurusan Sistem Informasi Teknologi Sepuluh November e-mail: * robbani.18052@mhs.its.ac.id

## Abstrak
Kemacetan  lalu  lintas  dapat  diatasi  dengan  adanya  public  transport.  Penerapan public  transport  yang  optimal  perlu  dilakukan  penentuan  rute  yang  baik.  Untuk mendapatkan  rute  public  transport  yang  optimal,  maka  perlu  dilakukan  beberapa percobaan  kombinasi  antara  jarak  titik  awal  dan  tujuan.  Sehingga  masalah  dapat dikatakan sebagai masalah kombinatorik. VRP merupakan permasalahan kombinatorik. Oleh karena itu permasalahan dapat diselesaikan menggunakan metode metaheuristik.
Penelitian  ini  akan  menggunakan  algoritma  Modified  Particle  Swarm Optimization  (MPSO-GI)  dengan  pendekatan  Hyper-heuristics  untuk  menyelesaikan masalah  penentuan  rute  public  transport.  Data  yang  digunakan  merupakan  dataset Mumford dan Mandl yang digunakan pada beberapa penelitian sebelumnya. Penelitian dilakukan  dengan  membandingkan  hasil  solusi  yang  dihasilkan  oleh  metode  yang ditawarkan  dengan  hasil  pada  penelitian  sebelumnya.  Sehingga  dapat  diketahui kelebihan dan kekurangan dari metode yang ditawarkan.
Berdasarkan  hasil  uji  coba  dapat  ketahui  bahwa  algoritma  MPSO-GI  dengan pendekatan  Hyper-Heuristics  dapat  diimpelmentasikan  dan  menyelesaikan  masalah UTRP.  MPSO-GI  dengan  pendekatan  Hyper-Heuristics  berhasil  memperbaiki  solusi hill-climbing  di  hamper  semua  dataset  dengan  nilai  yang  stabil.  Hasil  metode  MPSO- GI  dengan  pendekatan  Hyper-Heuristics  unggul  dalam  menghasilkan  solusi  biaya penumpang  pada  dataset  Mandl4,  Mandl6,  Mandl7,  Mandl8  dan  biaya  operator  pada dataset  Mandl4  dan  Mandl6  jika  dibandingkan  dengan  metode  pada  penelitian sebelumnya.
Kata  kunci —  Vehicle  Routing  Problem,  Urban  Transit  Routing  Problem, Metaheuristics, Hyper-heuristics, Particle Swarm Optimization

## Abstract
Traffic  congestion  can  be  overcome  by  public  transport.  The  optimal implementation  of  public  transport  is  necessary  to  determine  a  best  route.  To  get optimal  route  of  public  transport,  it  is  necessary  to  do  some  combination  experiments between  the  distance  from  the  starting  point  and  the  destination.  So  that  the  problem
1985 Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal . 1984-1997 E-ISSN 2503-2933
Robbani , et., al [ Penyelesaian Urban Transit Routing Problem Menggunakan Algoritma Hyper-Heuristics Berbasis Modified Particle Swarm Optimization Based On Gravitational Field Interactions ]
Title of manuscript is short and clear, implies research results (First Author)
can be said as a combinatoric problem. VRP is a combinatoric problem. Therefore, the problem can use a metaheuristic method.
In  this  studies,  Modified  Particle  Swarm  Optimization  algorithm  with  a  Hyper- heuristic  approach  used  to  solve  problem  public  transport  routes.  Data  used  is  the Mumford and Mandl dataset used in several previous studies. Research was conducted by  comparing  results  of  the  solutions  generated  by  proposed  methods  with  results  of previous studies. Therefore, can find out the advantages and disadvantages of proposed methods.
Based  on  this  studies,  MPSO-GI  algorithm  with  the  Hyper-Heuristics  approach can  be  implemented  and  solve  an  UTRP.  MPSO-GI  algorithm  with  Hyper-Heuristics approach  succeeded  in  improving  hill-climbing  solutions  in  almost  all  datasets  with stable values. MPSO-GI algorithm with the Hyper-Heuristics approach are superior in producing  passenger  cost  solutions  on the  Mandl4,  Mandl6,  Mandl7,  Mandl8  datasets and  operator  costs  on  the  Mandl4  and  Mandl6  datasets  when  compared  to  previous studies.
Keywords — Vehicle Routing Problem, Urban Transit Routing Problem, Metaheuristics, Hyper-heuristics, Particle Swarm Optimization

## 1. PENDAHULUAN
Kemacetan  lalu  lintas  telah  menjadi  masalah  serius  di  dunia  dan  tidak  mudah untuk  ditangani  [1].  Oleh  karena  itu  adanya public  transport merupakan  salah  satu solusi untuk mengatasi masalah kemacetan. Namun, penerapan public transport belum optimal  di  berbagai  negara.  Setelah  penerapan public  transport dilakukan,  maka  perlu menentukan  rute  yang  optimal  untuk  distribusi public  transport kepada  masyarakat, agar dapat mengganti peran kendaraan pribadi.
Untuk  mengoptimalkan  penerapan  penentuan  rute public  transport tersebut diperlukan  penentuan  rute  dan  jumlah  transportasi  pada  titik  titik  tertentu  pada  kota tersebut. Masalah penentuan rute menjadi penting agar pelayanan public transport dapat menggatikan  peran  kendaraan  pribadi.  Untuk  mendapatkan  rute  yang  optimal,  maka perlu dilakukan beberapa percobaan kombinasi antara jarak titik awal dan tujuan, hal ini akan  memerlukan  waktu  dan  tenaga  yang  besar.  Sehingga  masalah  yang  ada  dapat dikatakan sebagai masalah kombinatorik.
Permasalahan dalam mencari rute yang optimal dalam pendistribusian kendaraan dapat  disebut  juga  dengan Vehicle  Routing  Problem (VRP).  VRP  pertama  kali diperkenalkan  oleh  Dantzig  dan  Ramser  (1959)  dalam  bentuk  rute  dan  penjadwalan truk.  VRP  juga  bisa  dikatakan  sebagai  permasalahan  penentuan  rute  terpendek  untuk kendaraan  yang berangkat ke tujuan tertentu dan kembali lagi ke tempat awal  yang di sebut  dengan  depot.  Karena  lokasi  halte  tersebar  pada  beberapa  regional.  Maka,  perlu adanya  penentuan  rute  tujuan  sebelum  melakukan  pendistribusian  agar  dapat meminimumkan total jarak tempuh. VRP merupakan permasalahan kombinatorik. Oleh karena itu, permasalahan dapat diselesaikan menggunakan metode metaheuristik.
Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal. 1984-1997 E- ISSN 2503-2933 1986
Robbani , et., al [ Penyelesaian Urban Transit Routing Problem Menggunakan Algoritma Hyper-Heuristics Berbasis Modified Particle Swarm Optimization Based On Gravitational Field Interactions ]
Metode metaheuristik yang dapat digunakan menyelesaikan permasalahan VRP, antara lain: Genetic  Algorithm (GA), Algoritma Simulated  Annealing (SA), Algoritma Tabu  Search ,  Algoritma Particle  Swarm  Optimization (PSO,  dsb  [2].  Metode metaheuristik  memiliki  pengembangan  yaitu  metode  hyper-heuristik.  Metode  hyper- heuristik memiliki perbedaan utama dengan metaheuristik yaitu, metode hyper-heuristik secara  langsung  mencari  solusi  pada space  of  heuristic daripada  ke space  of  problem solutions [3]. Metode hyper-heuristik bertujuan untuk menemukan kombinasi yang tepat dari  heuristik low-level yang  mudah  diterapkan  dan  menghasilkan  solusi  domain  yang dapat diterima [4]. Hyper-heuristik juga telah digunakan untuk permasalahan VRP dan menghasilkan menunjukkan bahwa hyper-heuristik yang dirancang dengan baik berguna untuk membangun dan meningkatkan solusi [5].
Pada  beberapa  penelitian  sebelumnya,  permasalahan  VRP  telah  diselesaikan dengan menggunakan beberapa metode meta-heursirtik, antara lain: GA, PSO, dan TS . Penyelesaian  VRP  menggunakan  metode Hybrid GA  menunjukkan  bahwa  metode Hybrid GA  memiliki  kinerja  yang  lebih  baik  daripada  metode  GA  normal  [6]. Penyelesaian  VRP  menggunakan Modified PSO  menunjukkan  bahwa  metode  MPSO memiliki  kinerja  lebih  baik  daripada  PSO  dalam  mencapai  rute  kendaraan  yang berfokus pada permasalahan dengan mempertimbangkan biaya yang lengkap yang akan mengurangi total biaya dan emisi [7]. Penyelesaian VRP menggunakan metode Hybrid TS  menghasilkan  kinerja  yang  lebih  baik,  waktu  komputasi  yang  lebih  minimal  serta sangat  efektif  untuk  menemukan  solusi  permasalahan  [8].  Dari  hasil  penelitan sebelumnya  menunjukkan  bahwa  metode  metaheuristik  yang  sudah  dilakukan modifikasi  atau hybrid dapat  menjadi  sebuah  solusi  untuk  mendapatkan  urutan  rute yang  mendekati  solusi  optimal  yang  ingin  dicapai  dengan  waktu  pemrosesan  yang cepat.
Adapun  pengembangan  model  VRP  yang  bertujuan  untuk  penentuan  rute  bus pada suatu regional atau  yang disebut dengan Urban  Transit  Routing  Problem . UTRP berujuan  untuk  menemukan  rute  perjalanan  yang  efisien  untuk  sistem  transportasi umum.  UTRP  memiliki  multi  objective  yaitu  sudut  pandang  penumpang  dan  operator [9].  Sudut  pandang  penumpang  dikatakan  efisien  jika  total  waktu  tempuh  dan  total waktu perpindahan dapat diminimalkan. Sedangkan dari sudut pandang operator jumlah rute,  dan  jumlah  total  semua  panjang  rute  bus  dapat  diminimalkan.  Metode  meta- heursitik  dan  hyper-heuristik  dapat  membantu  mencari  fungsi  tujuan  yang  optimal dengan memberikan beberapa kombinasi kemungkinan solusi.
Beberapa  penelitian  mengenai  UTRP  telah  banyak  dilakukan.  Salah  satunya adalah  penyelesaian  masalah  penentuan  rute  bus  menggunakan  metode New  Heuristic and  Evolutionary  Operators ,  menunjukkan  bahwa  metode  yang  diusulkan  dapat mengungguli  penelitan  sebelumnya  pada  biaya  penumpang  dan  batas  bawah  biaya operator [10]. Penelitian lainnya mengusulkan penyelesaian masalah penentuan rute bus menggunakan  metode Selection  Hyper-heuristics .  Penelitian  dilakukan  dengan membandingan hasil beberapa metode dari Selection Hyper-heuristic . Diketahui bahwa metode sequence-based  selection  method  combined  with  the  great  deluge  acceptance memiliki peforma terbaik dalam biaya penumpang dan operator [11].  Penelitian lainnya mengusulkan  penyelesaian  penentuan  rute  bus  dengan  mengunakan  metode sequence- based selection method combined with the great deluge acceptance (SS-GD) [12] .
1987 Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal . 1984-1997 E-ISSN 2503-2933
Robbani , et., al [ Penyelesaian Urban Transit Routing Problem Menggunakan Algoritma Hyper-Heuristics Berbasis Modified Particle Swarm Optimization Based On Gravitational Field Interactions ]
Title of manuscript is short and clear, implies research results (First Author)
Berdasarkan beberapa penelitian sebelumnya, masalah UTRP dapat diselesaikan menggunakan metode hyper-heuristik. Namun belum adanya penelitan mengenai UTRP yang melakukan kombinasi algoritma Hyper-Hueristics dan metahueristics. Oleh karena itu dalam penelitian ini dilakukan penyelesaian Urban Transit Route Problem (UTRP) dengan  menggunakan  algoritma Modified  Particle  Swarm  Optimization  based  on Gravitational  Search  Interactions (MPSO-GI)  dengan  pendekatan  hyper-heuristics dengan  pemilihan  LLH  menggunakan Simple  Random agar  mendapatkan  solusi permasalahan  yang  lebih  optimal . Penggunaan  algoritma  MPSO  didasarkan  pada penelitian sebelumnya  yang menjelaskan bahwa  algoritma MPSO memiliki hasil  yang lebih baik daripada PSO standar dalam masalah VRP [7]. MPSO-GI memodifikasi PSO dengan pendekatan Gravitational Search Algorithm dan menunjukkan hasil yang lebih optimal daripada PSO standar [13]. Penggunaan algoritma PSO dan pendekatan hyper- heuristik telah dilakukan dalam penilitan mengenai penyelesaian Resource Constrained Project  Scheduling  Problem (RCPSP)  dan  memiliki  hasil  solusi  yang  kompetitif  jika dibandingkan dengan metode lain [14].
Dataset  yang  digunakan  dalam  penelitian  ini  adalah  dataset  pada  penelitan sebelumnya  yaitu Mandl dan Mumford [10]. Data Mandl merupakan data representasi rute  bus  pada  15  kota  di  Swiss.  Sedangkan,  dataset  Mumford  merupakan  representasi dari  jaringan  transportasi  kecil  dan  rute  bus  di  kota  (Yubei,  Brighton  dan  Cardiff). Dataset diperoleh dari website [15]. Hasil penelitian ini akan dibandingkan dengan hasil penelitian  sebelumnya  yang  menggunakan  dataset  yang  sama.  Sehingga  dapat mengetahui  kelebihan  dari  metode  yang  ditawarkan  dalam  menyelesaikan  masalah UTRP.

## 2. METODE PENELITIAN
Penelitian  ini  dilakukan  dengan  melalui  beberapa  tahapan  yaitu  desain algoritma, implementasi, dan analisis hasil. Adapun metode penelitian dapat dijelaskan pada Gambar 1.

## 2. 1 Desain Algoritma
Pada  bagian  ini,  dilakukan  lima  langkah  meliputi  :  Konversi  Data  dan  Hard Constrains,  pembentukan  solusi  awal,  pemilihan  LLH  menggunakan  Simple  Random, Penggunaan move acceptance algoritma MPSO-GI. Seacar garis besar desain algoritma akan  digunakan  pemilihan  LLH  menggunakan  Simple  Random  dan  langkah  move acceptance MPSO-GI.

## 2. 1.1 Konversi Data dan Hard Constrains
Pada  langkah  ini,  dilakukan  pembacaan  dataset  yang  digunakan  dalam  format .txt.  Selanjuntya  dataset  tersebut  dikonversikan  menjadi  array  dengan  melakukan penyesuaian  agar  dapat  dibaca  opleh  program.  Penyesuaian  dilakukan  dengan menggantikan nilai “Inf” menjadi 0 pada dat TravelTimes, agar propses pencarian hard constrains dapat lebih mudah. Selanjutnya data dapat diperoleh dalam bentuk array data TravelTimes dan Demand .  Data  tersebut  kemudian  dapat  dilakukan  proses  optimasi sesuai  dengan  algoritma  yang  diinginkan  dengan  program  yang  telah  di  buat.
Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal. 1984-1997 E- ISSN 2503-2933 1988
Robbani , et., al [ Penyelesaian Urban Transit Routing Problem Menggunakan Algoritma Hyper-Heuristics Berbasis Modified Particle Swarm Optimization Based On Gravitational Field Interactions ]
Selanjutnya dilakukan pencarian hard contrains dengan melakukan penelusuruan apakah titik antar array memiliki nili 0. Jika iya maka titik tersebut tidak dapat terkoneksi.

## 2. 1.2 Inisialisasi Solusi Awal
Pada  langkah  ini,  dilakukan  pembentukan  solusi  awal  dari  dataset  yang  dipilih dan  diimplementasikan.    Langkah  pertama  pada  pembentukan  solusi  awal  adalah, menentukan  parameter  dari  tiap  dataset.  Parameter  yang  perlu  ditentukan  meliputi banyaknya rute, serta panjang MIN dan MAX pada tiap rute. Parameter yang digunakan sesuai  dengan  spesifikasi  tiap  dataset  yang  telah  dijabarkan.  Selanjutnya  solusi  awal dapat diperoleh dengan menentukan titik awal solusi pada tiap rute dengan menentukan titik  yang  memiliki  koneksi  terbanyak  dengan  titik  lain.titik  berikutnya  dipilih berdasrkan  hard  constrains  dari  titik  awal  yang  telah  didapatkan.  Pembentukan  solusi awal dapat dijelaskan dengan pseudocode pada Gambar 2.
Gambar 1. Alur Metode Penelitian
Identifikasi Masalah Studi Literatur Pengumpulan Data Model Matematis Analisis Performa Hasil dan Kesimpulan Desain Algoritma Uji Coba
1989 Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal . 1984-1997 E-ISSN 2503-2933
Modified Particle Swarm Optimization Based On Gravitational Field Interactions ]
Title of manuscript is short and clear, implies research results (First Author)
1: procedure getNewRoute(data, min, max, r, datasize)
2:  rute array rute awal 3:  dataC getConnected(data) 4:  startNode titik awal tiap rute
5: for i = 0 to i < r do 6: for j = 0 to j < max do 7:         if(j==0) 8:            rute[i][0] startNode 9:            chosen startNode 10:        else 11:           random random(dataC[chosen]) 12:           nextNode dataC[chosen][random]
13: while (rute[i] !contains nextNode) do 14:                rute[i][j] nextNode
15:                chosen = nextNode
16: while (Unused not empty) do 17: randRute pilih rute acak 18:        rute[randRute] = clear() 19:        rute[randRute][0] startNode 20:        chosen startNode 21:        for i=0 to i<max do 22:           line 11 to line 15
23: return rute

## Gambar 2. Psuedocode Solusi Awal
1: procedure getRouteHC()
2:  rand1 pilih acak rute
3:  rand2 pilih acak titik baru
4: if (rute[rand1]<max) 5: while (rute[rand1] not contains rand2) do 6:           rute[rand1] = add(rand2) 7: if (isValid!=true)
8:        rute[rand1] 1989embali awal
9: else
10:    temp1 rute[rand1][0] 11:    temp2 rute[rand1][rute[rand1].length-1]
12:    rute[rand1][0] = temp1; 13:    rute[rand1][rute[rand1].length-1] = temp2; 14:    line 7 to 8 15: return rute

## Gambar 3. Psuedocode Hill Climbing

## 2. 1.3 Hill Climbing
Pada  bagian  ini,  penelitian  dilakukan  dengan  menggunakan  hasil  dari  solusi awal yang telah di bentuk meliputi rute awal dan nilai biaya penumpang dan operator. Selanjutnya  hasil  dari  solusi  awal  di  olah  menggunakan  metode hill  climbing untuk mendapatkan hasil yang lebih baik. Metode hill climibing yang dilakukan adalah make- small-change seperti  yang  dilakukan  pada  penelitan  sebelumnya  [16]. Psuedocode metode hill climbing dapat dilihat pada Gambar 3.
Langkah pertama hill-climbing adalah, menentukan secara acak rute mana yang akan  dilakukan  modifikasi.  Setelah  mendapatkan  rute  yang  dipilih,  selanjutnya menentukan  kemungkinan  yang  dapat  digunakan.  Kemungkinan  pertama  dapat digunakan,  jika  panjang  sebuah  rute  yang  dipilih  kurang  dari  parameter MAX .  Serta kemungkinan  terakhir  dapat  digunakan,  jika  rute  tersebut  tidak  dapat  menjalankan kemungkinan pertama.
Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal. 1984-1997 E- ISSN 2503-2933 1990
Robbani , et., al [ Penyelesaian Urban Transit Routing Problem Menggunakan Algoritma Hyper-Heuristics Berbasis Modified Particle Swarm Optimization Based On Gravitational Field Interactions ]
Setelah  melakukan  kemungkinan  prosedur  dari  metode Make-small-change maka  rute  baru  diperoleh.  Selanjutnya  melakukan  pengecakan  terhadap  rute  apakah memenuhi  persyaratan  sebagai  rute  dalam  permasalahan  UTRP.  Jika  rute  tersebut dinyatakan valid, maka  rute menggatikan  rute sebelumnya dan dapat digunakan untuk perhitungan nilai biaya penumpang dan operator yang baru.

## 2.1 4 Hyper Heurisctics Dengan Simple Random
Metode Simple Random bekerja memilih LLH yang akan dalam iterasi dengan cara nilai acak antara banyaknya LLH yang digunakan. Pada penelitian ini, jumlah LLH [11] yang digunakan sebagai berikut:
1. LLH0:  Memilih  rute  secara  acak  dan  posisi  dari  rute  tersebut.  Lalu  menambahkan titik nilai acak kedalam psosisi dan rute yang telah di pilih.
2. LLH1: Memilih rute secara acak dan 2 posisi dalam rute secara acak. Lalu menukar keuda posisi yang telah di pilih
3. LLH2:  Memili  rute  secara  acak  dan  dua  posisi  dalam  rute  secara  acak.  Lalu  titik pertama menggantikan titik kedua, titik kedua menjadi titik terkahir
4. LLH3: Memilih 2 rute secara acak dan 1 posisi pada tiap rute. Lalu memasukkan titik pad arute pertama ke dalam rute kedua spada titik kedua yang di pilih.
5. LLH4: Milih dua rute secara acak dan satu posisi pada tiap rute. Lalu menukar tiitik yang telah di pilih pada tiap rute.

## 2. 1.4 Move Acceptance Dengan Modified Particle Swarm Optimization
Pada  bagian  ini,  langkah move  acceptance dilakukan  setelah  pemilihan  LLH. Move acceptance yang digunakan adalah Modified Particle Swarm Optimization based on Gratvitational field Interactions (MPSO-GI). MPSO-GI dilakukan dengan membuat pilihan  solusi  yang  ditentukan  oleh  partikel  dan  dijalankan  sebanyakan  iterasi  yang diinginkan.
Langkah  awal  MPSO-GI  adalah  menentukan  parameter  partikel  dan  iterasi. Selanjutnya  memilih  secara  acak,  rute  yang  akan  dilakukan  perubahan  menggunakan MPSO-GI.  Setelah  mendapatkan  rute,  maka  rute  tersebut  diolah  menjadi  solusi  baru sebanyak  partikel  yang  ditentukan.  Selanjutnya  solusi  baru  tersebut  dihitung  nilai tujuannya.  Apabila  nilai  tujuan  lebih  baik,  maka  nilai  tujuan  dapat  di  terima  dan menggantikan nilai tujuan sebelumnya. Proesedur penerapan move  acceptance MPSO- GI dapat dilihat pada Gambar 4.
1991 Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal . 1984-1997 E-ISSN 2503-2933
Title of manuscript is short and clear, implies research results (First Author)
1: procedure MPSO()
2:  partikel banyaknya solusi 3:  iterasi, MaxIterasi jumlah iterasi 4: generatePosisiAwal(); 5:  gerateKecepatanAwal();
6:  solusiTiapPartikel(); 7: while(iterasi<maxIterasi)do
8:            kecepatanBaru();
9:            posisiBaru(); 10:           solusiTiapPartikel(); 11: if(bestFit<fitness)
12:              fitness = bestFit
13:              updateRute();
14: return ruteSR
Gambar 4. Algoritma MPSO-GI
Gambar 5. Flowchart Hyper-Heuristics
Proses hyper-heuristics dilakukan sebanyak iterasi yang telah ditentukan dan di batasi  oleh timelimit . Move  acceptance digunakan  pada  tiap  iterasi.  Adapun  prosedur hyper-heuristics dapat  di  lihat  pada  flow  chart  Gambar  5.  Dari  Gambar  tersebut
Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal. 1984-1997 E- ISSN 2503-2933 1992
Robbani , et., al [ Penyelesaian Urban Transit Routing Problem Menggunakan Algoritma Hyper-Heuristics Berbasis Modified Particle Swarm Optimization Based On Gravitational Field Interactions ]
dijelaskan  bahwa  proses  optimasi  UTRP  dengan  hyperheuristics  dilakukan  dengan dengan  simple  random  untuk  memilih  LLH  dan  dilanjutkan  dengan  MPSO-GI  hingga mencapai iterasi yang diinginkan.

## 2. 2 Implementasi Algoritma
Algoritma  diimplementasikan  dalam  bahasa  pemrograman  java  menggunakan IDE Eclipse. Spesifikasi computer yang digunakan meliputi : Inte i5-8250U @1.60Ghz, 8129MB RAM dan Windows 10 Home. Program dijalankan pada tiap dataset sebanyak 200 iterasi dan dijalakan sebanyak 10 kali. Pasda optimasi menggunkan hyperheuristics terdapat parameter timelimit untuk membatasi waktu dari iterasi yang digunakan  yaitu 10 menit.

## 2. 3 Analisis Hasil
Hasil  dari  implementasi  algoritma,  selanjutnya  akan  di  analisa    dan dibandingkan  antar  metode  serta  hasil  dari  penelitian  sebelumnya.  Perbandingan  hasil dari  tiap  tiap  algortima  akan  disajikan  dalam  garifk  untuk  memlihat  performa  dari masing masing algoritma.

## 3. HASIL DAN PEMBAHASAN
Uji  coba  dilakukan  dengan  parameter  yang  sama  antara  hill  climbing  dan MPSO-GI  dengan  pendekatan Hyper-heuristics .  Namun  pada  MPSO-GI  dengan pendekatan Hyper-heuristics selain menggunakan iterasi juga terdapat batas waktu yang ditentukan, dalam penelitian ini ditentukan 10 menit. Serta move acceptance memiliki parameter sebagai berikut: partikel=5 dan iterasi=10. Hasil uji coba dengan metode hill- climbing  berupa  nilai  biaya  penumpang  dan  operator  terbaik  dibandingkan  dengan solusi awal dapat dilihat pada Tabel 1. Sedangkan hasil uji coba dengan menggunakan MPSO-GI dengan pendekatan Hyper-heuristics dapat dilihat pada Tabel 2. Selanjutnya membandingkan  hasil  dari  kedua  metode  yaitu  hill  climbing  dan  hyper-heuristics dengan membandingkan nilai biaya penumpang dan operator terbaik dapat di lihat pada Tabel 3. Selanjutnya hasil dari kedua metode dibandingkan dengan beberpa penelitian sebelumnya  yaitu:  [10]  dan  [11]  sebagai  pembanding  perfoma  hasil  metode  yang ditawarkan dapat dilihat pada Tabel 4 dan Gambar 6.

## Tabel 1. Hasil Uji Coba Hill Climbing
Fungsi Tujuan Metode Dataset Mandl4 Mandl6 Mandl7 Mandl8 Mumford0 Mumford1 Mumford2 Mumford3 Cp Init 49 52 57 43 35
68 87 out of time HC 18 16 16 10 19 34 70
out of time Co Init 107 130 151 178
437 1106 3948 out of time HC 53 98 107 117 419 1074
3938 out of time
1993 Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal . 1984-1997 E-ISSN 2503-2933
Modified Particle Swarm Optimization Based On Gravitational Field Interactions ]
Title of manuscript is short and clear, implies research results (First Author)

## Tabel 2. Hasil Uji Coba Hyper-heuristics
Fungsi Tujuan Metode Dataset Mandl4 Mandl6 Mandl7 Mandl8 Mumford0 Mumford1 Mumford2 Mumford3 Cp Inisialisasi 49 52 57 43 35
68 87 out of time HH 8 9 8 7 17 45 72
out of time
Co
Inisialisasi 107 130 151 178 437
1106 3948 out of time HH 41 53 75 93 384 964 3905
out of time
Tabel 3. Hasil Perbandingan Hill-Climbing dan Hyper-Heuristics
Fungsi Tujuan Metode Dataset Mandl4 Mandl6 Mandl7 Mandl8 Mumford0 Mumford1 Mumford2 Cp HC 18 16 16 10 19 34 70 HH 8 9 8 7 17 45 72
Persentase 55.56% 43.75% 50.00% 30.00% 10.53% -32.35% -2.86% Co HC 53 98 107 117 419 1074
3938
HH 41 53 75 93 384 964
3905 Persentase 22.64% 45.92% 29.91% 20.51% 8.35% 10.24% 0.84%

## Tabel 4. Hasil Perbandingan dengan Penelitian Sebelumnya
Dataset
HC HH NH-EO SS-GD
Mandl4 Cp 18 8 10.57 10.48
Co 53 41 63 63 Mandl6 Cp 16 9 10.27 10.18
Co 98 53 63 63 Mandl7 Cp 16 8 10.22 10.1 Co 107 75 63 63 Mandl8 Cp 10 7 10.17 10.08 Co 117 93 63 63 Mumford0 Cp 19 17 16.05 14.09 Co 419 384 111 94 Mumford1 Cp 34 45 24.79 21.69 Co 1074 964 568 403 Mumford2 Cp 70
72 28.65 25.19 Co 3938 3905 2244 1330
Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal. 1984-1997 E- ISSN 2503-2933 1994
Modified Particle Swarm Optimization Based On Gravitational Field Interactions ]

## Gambar 6. Perbandingan Biaya Penumpang Dengan Penelitian Sebelumnya
Berdasarkan  hasil  metode  hill-climbing  pada  tabel  1,  diketahui  bahwa  metode hill-climbing  dapat  memperbaiki  solusi  awal  dan  menyelesaikan  masalah  UTRP  di hampir semua dataset, kecuali pada dataset Mumford3. Dataset Mumford3 tidak dapat diselesaikan  karena  tidak  dapat  menghasilkan  solusi  hingga  waktu  yang  ditentukan. Oleh karena itu pada penelitian ini, dataset Mumford3 tidak diikutsertakan. Selanjutnya berdasarkan  tabel  2  metode  MPSO-GI  dengan  pendekatan  hyper-heuristics  memiliki solusi  yang  lebih  baik  dari  solusi  awal  di  semua  dataset  pada  biaya  penumpang  dan operator. Hasil dari perbandingan metode hill-climbing dan hyper-heuristics pada tabel 3,  diketahui  bahwa  solusi  biaya  penumpang  metode  hyper-heuristis  memiliki keunggulan daripada hill climbing pada dataset Mandl4, Mandl6, Mandl7, Mandl8 dan Mumfor0. Sedangkan pada biaya operator pada semua dataset. Metode hyper-heuristics juga memiliki perbaikan solusi baiya penumpang yang signifikan terhadap hill-climbing sebesar lebih dari 50% pada dataset Mandl4 dan Mandl7. Untuk mengetahui kesatbilan distribusi jhasil solusi pada 10 kali percobaan dan 200 iterasi maka dapat dilihat pada Gambar  7  dan  Gambar  8.  Selanjutnya  hasil  dari  perbandingan  kedua  metode  dengan penelitian sebelumnya pada tabel 4 menunjukkan bahwa metode hyper-heuristics dapat memperbaiki  solusi  biaya  penumpang  pada  dataset  kecil  yaitu:  Mandl4,  Mandl6, Mandl7 dan Mandl8. Sedangkan pada biaya operator pada dataset Mandl4 dan Mandl6.
Gambar 7. BoxPlot Perbandingan Hasil Data Mandl
0 20 40 60 80 M a n d l4 M a n d l6 M a n d l7
M a n d l8 M u m fo rd 0 M u m fo rd 1 M u m fo rd 2 B ia y a P e n u m p a n g Dataset HC HH NH-EO SS-GD
1995 Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal . 1984-1997 E-ISSN 2503-2933
Title of manuscript is short and clear, implies research results (First Author)

## Gambar 8. BoxPlot Perbandingan Hasil Data Mumford
Berdasarkan  gambar    7  dan  gambar  8  mengenai  distribusi  hasil  metode  hill climbing  dan  hyper-heuristics  pada  dataset  yang  digunakan  dapat  diketahui  bahwa metode  MPSO-GI  dengan  pendekatan Hyper-heuristics mempunyai  kerapatan  hasil yang  lebih  baik  daripada hill-climbing pada  semua  dataset.  Oleh  karena  itu,  dapat dikatakan bahwa hasil dari metode MPSO-GI dengan pendekatan Hyper-heuristics lebih stabil.

## 4. KESIMPULAN
Kontribusi  penelitian  yang  dilakukan  adalah,  menerapkan  kombinasi  antara pemilihan low  level  heuristics dan  algoritma Modified  Particle  Swarm  Optimization based  on  Gravtioational  field  Interactions (MPSO-GI)  dalam  penyelesaian Urban Transit Routing Problem (UTRP) untuk memperbaiki solusi .
Secara  lebih  spesifik  kesimpulan  yang  dapat  ditarik  dari  penelitian  ini  sebagai berikut: Kombinasi pemilihan LLH dan MPSO-GI dapat diterapkan untuk penyelesaian UTRP,  Metode  MPSO-GI  dengan  pendekatan Hyper-heuristics memiliki  hasil  biaya penumpang  dan  operator  yang  lebih  baik  jika  dibandingkan  dengan  metode  hill- climbing pada hampir seluruh dataset  yang digunakan, kecuali biaya penumpang pada Mumford1  dan  Mumford2,  Hasil  metode  MPSO-GI  dengan  pendekatan Hyper- heuristics memiliki  nilai  yang  stabil  jika  dibandingkan  dengan  metode  hill  climbing dalam mennjalakan program dengan parameter 10 kali percobaan dan 200 iterasi, Hasil metode  MPSO-GI  dengan  pendekatan Hyper-heuristics memiliki  keunggulan  dalam biaya  penumpang  pada  dataset  Mandl4,  Mandl6  Mandl7  dan  Mandl8.  Serta  biaya operator  pada  Mandl4  dan  Mandl6.  Jika  dibandingkan  dengan  beberpaa  penelitian sebelumnya. Hal ini menunjukkan bahwa metode MPSO-GI dengan pendekatan Hyper- heuristics dapat menghasilkan solusi yang baik pada data kecil, dan Metode MPSO-GI dengan  pendekatan Hyper-heuristics masih  belum  bisa  mengalahkan  metode  pada penelitian sebelumnya pada data besar.
Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal. 1984-1997 E- ISSN 2503-2933 1996
Modified Particle Swarm Optimization Based On Gravitational Field Interactions ]

## 5. SARAN
Penerapan  Hyper-heuristics  dengan  menggunakan  pemeilihan  LLH  Simple Random dan Move Acceptance MPSO-GI dapat diimplementasikan untuk penyelesaian UTRP namun masih kurang sempurna pada data yang berukuran besar. Untuk penelitian selanjutnya diharapkan dapat menyelesaikan permasalahan tersebut dengan melakukan variasi pada pemilihan LLH dan kombinasi urutan kota. Serta dapat dikembangkan pula menggunakan  dataset  yang  lebih  nyata.  Agar  solusi  yang  dihasilkan  dapat  bermanfaat bagi banyak pihak.

## DAFTAR ISI
[1] A. Ko ź lak and D. Wach, 2018, " Causes  of  Traffic  Congestion  In  Urban  Areas. Case in Poland," SHS Web of Conferences, Vol. 57, pp. 1-9.
[2] M.  Blocho,  2019, "Heuristics,  Metaheuristics,  and  Hyperheuristics  For  Rich  Vehicle Routing Problems," in Smart Delivery Systems , J. Nalepa, Ed., Cambridge, Elsevier Inc., pp. 101-156.
[3] Tarhini, K. Danach and A. Harfouche, 2020, "Swarm Intelligence-Based Hyper-Heuristic For  The  Vehicle  Routing  Problem  With  Prioritized  Customers," Annals  of  Operations Research , Vol. -, No. -, pp. -,
[4] E. K. Burke, M. Gendreau, M. Hyde, G. Kendall, G. Ochoa, E. Özcan and R. Qu, " 2013, Hyper-Heuristics:  A  Survey  of  The  State  of  The  Art," Journal  of  The  Operational Research Society, Vol. 64, p. 1695–1724,.
[5 ]D.  A.  Rodriguez,  P.  P.  Oteiza  and  N.  B.  Brignole , 2019, "An  Urban  Transportation Problem  Solved  by  Parallel  Programming  With  Hyper-Heuristics," Engineering Optimization, pp. 1965-1979.
[6 ]M.  Rabbani,  P.  Pourreza,  H.  Farrokhi-Asl  and  N.  Nouri,  2018, "A  Hybrid  Genetic Algorithm  For  Multi-Depot  Vehicle  Routing  Problem  With  Considering  Time  Window Repair and Pick-Up," Journal of Modelling in Management, Vol. 13, No. 3, pp. 698-717..
[7] Y.  Li,  M.  K.  Lim  and  M.-L.  Tseng,  2018, "A  Green  Vehicle  Routing  Model  Based  On Modified  Particle  Swarm  Optimization  For  Cold  Chain  Logistics," Industrial Management & Data Systems, Vol. 119, No. 3, pp. 473-494.
[8] J. Euchi, 2017, "The Vehicle Routing Problem With Private Fleet And Multiple Common Carriers:  Solution  With  Hybrid  Metaheuristic  Algorithm," Vehicular  Communications, Vol. 9, No. 1, pp. 987-108.
[9] L.  Fan,  C.  L.  Mumford  and  D.  Evans,  2009. "A  Simple  Multi-Objective  Optimization Algorithm  For  The  Urban  Transit  Routing  Problem," 2009  IEEE  Congress  on Evolutionary Computation, pp. 1-7.
1997 Jatisi ISSN 2407-4322 Vol. 8, No. 4, Desember 2021, Hal . 1984-1997 E-ISSN 2503-2933
Modified Particle Swarm Optimization Based On Gravitational Field Interactions ]
Title of manuscript is short and clear, implies research results (First Author)
[10]  C.  L.  Mumford,  2013. "New  Heuristic  and  Evolutionary  Operators  for  The  Multi- Objective  Urban  Transit  Routing  Problem," 2013  IEEE  Congress  on  Evolutionary Computation, pp. 939-946,
[11]  L.  Ahmed,  C.  Mumford  and  A.  Kheiri,  2018, "Solving  Urban  Transit  Route  Design Problem using Selection Hyper-heuristics," European Journal of Operational Research, Vol. 274, No. 2, pp. 545-559.
[12]  L.  Ahmed,  P.  Heyken-Soares,  C.  Mumford  and  Y. Mao, 2019 ,  "Optimising  Bus  Routes with  Fixed  Terminal  Nodes:  Comparing  Hyper-heuristics  with  NSGAII  on  Realistic Transportation  Networks," GECCO  '19:  Proceedings  of  the  Genetic  and  Evolutionary Computation Conference, pp. 1102-1110,
[13]  M.  Spichakova,  2016, "Modified  Particle  Swarm  Optimization  Algorithm  Based  On Gravitational  Field  Interactions," Proceedings  of  The  Estonian  Academy  of  Sciences, Vol. 65, No. 1, p. 15–27,
[14]  G.  Koulinas,  L.  Kotsikas  and  K.  Anagnostopoulos, "A  Particle  Swarm  Optimization Based  Hyper-Heuristic  Algorithm  For  The  Classic  Resource  Constrained  Project Scheduling Problem," Information Sciences, Vol. 277, pp. 680-693, 2014.
[15]  C. Mumford, 2014, "Research On The Urban Transit Routing Problem (Bus Routing)," . [Online]. Available:
http://users.cs.cf.ac.uk/C.L.Mumford/Research%20Topics/UTRP/Outline.html. [Accessed 9 October 2020].
[16]  L. Fan and C. Mumford, 2010, " A Metaheuristic Approach to The Urban Transit Routing Problem," Journal of Heuristics, Vol. 16, pp. 353-372,