## SAINTEKS: JURNAL SAIN DAN TEKNIK Volume 5 Nomor 1 Tahun 2023

## E-ISSN : 2685-8304
Changes on Recycling Behaviors Based on Governmental Programs (Study Case in Bendungan Village, Indonesia) Dafi Dinansyah Wiradimadja, Hisatsuna Mori, Riza Rizkiah 1 –10 The study of tuff breccia for Batik Wasterwater Treatment Media in Bayat, Klaten District, Central Java Wawan Budianta, Johan Syafri Mahathir Ahmad, I Wayan Warmada 11 –18 Analysis of Frame Construction Strength in Belt Conveyor Design Using Ansys Workbench Anggi Pratama, Delvis Agusman
19 –28
Mitigation of Insert Separator Damage in Open-End Machines Filly Pravitasari, Afriani Kusumadewi, Feny Nurherawati 29 –35
Motorcycle Tracking System Using Telegram Integrated Quectel L80 GPS Pri Hartini, Ibrahim, Reni Rahmadewi, Tiara Nurhuda
36 –46
Optimization of Distribution Costs with a Transportation Model in UMKM making  Tempe Ardhini Rhisnu Fadylla, Fahriza Nurul Azizah
47 –56
Decision Model and Industry Optimization in Production: A Systematic Literature review Armando Tirta Dwilaga
57 –71
Analysis of the Influence of Occupational Health Aspects at PT. Plasticolors Eka Perkasa on Employee Performance Chairul Falah, Risma Fitriani 72 –79 Re-Layout of Puskesmas X Post Covid 19 Pandemic Through the ARC, Conventional and Promodel Simulation Methods
Tombak Gapura Bhagya, Dini Yulianti, Graha Prakarsa, Antari Nurayban Gitardiana
80 –91
Evaluation of the Mental Workload of PSIT Employees at SIT XYZ Institutions Teguh Aprianto, Agus Rahmat Hermawanto, Rimba Krisnha Sukma Dewi, Angling Sugiatna, Abdul Fatah 92 –101
Genetic Algorithm for Improving Route of Travelling Salesman Problem Generated by Savings Algorithm Muhammad Ardhya Bisma, Ekra Sanggala
102 –111
Noodle Grouping Based on Nutritional Similarity with Hierarchical Cluster Analysis Method Ai Nurhayati, Riri Mardaweni, Raden Meina Widiastuti
112 –125
Diterbitkan Oleh :
UNIVERSITAS INSAN CENDEKIA MANDIRI dh UNIVERSITAS BANDUNG RAYA
Jl. Pasir Kaliki No. 199 Bandung – Jawa Barat http://ejournal.uicm-unbar.ac.id/index.php/sainteks UICM – UNBAR www.uicm.ac.id
Volume 5 Nomor 1 Tahun 2023 http://ejournal.uicm-unbar.ac.id/index.php/sainteks/

## Genetic Algorithm for Improving Route of Travelling Salesman Problem Generated by Savings Algorithm
Genetic Algorithm Untuk Memperbaiki Rute Travelling Salesman Problem Yang Dihasilkan Dari Savings Algorithm
Muhammad Ardhya Bisma* 1) , Ekra Sanggala 2) , 1) Universitas Logistik dan Bisnis Internasional. Jalan Sariasih No. 54, Bandung, 40151 Email: bisma@ulbi.ac.id
2) Universitas Logistik dan Bisnis Internasional. Jalan Sariasih No. 54, Bandung, 40151 Email: ekrasanggala@mail.ru *) Corresponding Author
Abstract: Travelling Salesman Problem (TSP) is the problem for finding the shortest route starting from start node then visiting number of nodes exactly once and finally go back to start node. If a TSP has a lot of nodes, it will be a NP-Hard Problem. Algorithms working based on heuristic and metaheuristic can be a solution for solving NP- Hard Problem. Savings Algorithm is a heuristic algorithm, so it’s solution may be not the best solution, therefore there is a chance to improve it. Genetic Algorithm is a metaheuristic that can be applied on  many optimization  problems,  including  TSP.  This paper  will discuss about GA for  improving route TSP generated by Savings Algorithm. On testing of 10 instances, showing that algorithm based on GA can improve route of TSP generated by Savings Algorithm.
Keywords: Genetic Algorithm, Savings Algorithm, Travelling Salesman Problem
Abstrak: Travelling Salesman Problem berfokus pada penentuan rute paling pendek yang dimulai dari titik awal guna mengunjungi sekumpulan titik tujuan tepat satu kali yang kemudian diakhiri dengan kembali ke titik awal. TSP dengan banyak titik dapat diklasifikasikan sebagai NP-Hard Problem yang pada umumnya diselesaikan  dengan heuristic dan metaheuristic. Algoritma  yang  termasuk  dalam heuristic tidak  selalu menghasilkan solusi terbaik. Dalam konteks ini, Savings Algorithm termasuk kedalam heuristic, sedangkan Genetic  Algorithm ( GA )  termasuk  kedalam metaheuristic. Hal  ini  mengindikasikan  bahwa solusi  yang dihasilkan  oleh Savings  Algorithm belum  tentu  solusi  yang  paling  baik,  sehingga  masih  terdapat kemungkinan  untuk  diperbaiki  lebih  lanjut  dengan  penggunaan Genetic  Algorithm ( GA ).  Penelitian  ini melakukan  pengujian  dengan  menggunakan  sepuluh  (10) instance, dan  didapatkan  bahwa Genetic Algorithm ( GA ) dapat memperbaiki rute TSP yang sebelumnya dihasilkan oleh Savings Algorithm . Kata Kunci: Genetic Algorithm , Savings Algorithm , Travelling Salesman Problem
DOI: http://dx.doi.org/ 10.37577/sainteks.v%vi%i.542 Received: 01, 2023.  Accepted: 02, 2023 Published: 03, 2023

## PENDAHULUAN
Travelling Salesman Problem (TSP) berfokus pada penentuan rute paling pendek yang dimulai dari titik awal guna mengunjungi sekumpulan titik tujuan tepat satu kali yang kemudian diakhiri dengan  kembali  ke  titik  awal.  Berbagai  fenomena  di  dunia  ini  dapat  didefinisikan  dengan pendekatan  TSP,  seperti  rute  perjalanan  wisatawan,  rute  transportasi  publik,  rute pendistribusian  komoditi  dan  sebagainya.  TSP  dapat  dimodelkan  dalam  bentuk integer programming seperti berikut ini (Lavrov, 2020):
𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑒  ∑ ∑ 𝑐 𝑖𝑗 𝑥 𝑖𝑗
𝑛 𝑗=1 𝑛 𝑖=1
Genetic Algorithm for Improving Route of TSP Generated by Savings Algorithm
∑ 𝑥 𝑖𝑗 = 1 1≤𝑖≤𝑛 𝑖≠𝑗 𝑓𝑜𝑟 𝑒𝑎𝑐ℎ 𝑗 = 1,2, … , 𝑛
∑ 𝑥 𝑗𝑘 = 1
1≤𝑘≤𝑛 𝑘≠𝑗 𝑓𝑜𝑟 𝑒𝑎𝑐ℎ 𝑗 = 1,2, … , 𝑛
Ketika  TSP  memiliki  banyak  titik,  maka  TSP  tersebut  akan  menjadi NP-Hard  Problem (nondeterministic  polynomial  time).  Sebagaimana  yang  diketahui,  bahwa  NP-Hard  Problem memerlukan  waktu  yang  lama  guna  mendapatkan  penyelesaiannya  (Applegate  et  al.,  2006). Meskipun demikian, NP-Hard Problem dapat diselesaikan dalam jangka waktu yang wajar dengan menggunakan  algortima heuristic  serta  metaheuristic  meskipun  solusi  yang  dihasilkan  belum tentu menjadi solusi yang terbaik (Labadie et al. 2016).
Savings Algorithm merupakan salah satu heuristic yang populer dalam menyelesaikan TSP (Chiarandini,  2020). Savings  Algorithm  pertama  kali  diprakarsai  oleh  Clarke  dan  Wright  pada tahun 1964 (Clarke, 1964). Adapun prinsip pokok dari Savings Algorithm adalah penghematan ( savings)  jarak  tempuh  yang  diperoleh  berdasarkan  penggabungan  dua  rute  yang  berbeda. Ilustrasi penggabungan tersebut tercantum pada gambar 1, dimana titik 0 merupakan merupakan titik asal, dan titik i serta titik j adalah titik tujuannya (Lysgaard, 2007).
Gambar 1: Contoh Penggabungan 2 rute (Lysgaard, 2007).
Pada gambar 1(a) diketahui bahwa titik i dan titik j dicapai oleh rute yang berlainan, sedangkan pada gambar 1(b) didapatkan bahwa titik i dan titik j dicapai oleh rute yang sama. Dapat diketahui jarak tempuh D a pada gambar 1(a) dapat diterjemahkan dengan persamaan sebagai berikut ini (Lysgaard, 2007):
D a = d 0i + d i0 + d 0j + d j0
Sedangkan untuk jarak tempuh D b pada gambar 1(b) dapat diterjemahkan dengan persamaan ini: (Lysgaard, 2007):
D b = d 0i + d ij + d j0
Nilai Savings diperoleh dengan mengurangkan jarak tempuh D a dengan jarak tempuh D b , sehingga persamaan nilai Savings S ij menjadi seperti ini (Lysgaard, 2007):
S ij = D a – D b = d i0 + d 0j - d ij
Pada Savings  Algorithm,  langkah  utama  yang  harus  dilakukan  adalah  melakukan perhitungan  nilai  penghematan  ( savings)  untuk  setiap  pasangan  titik.  Setelah  setiap  nilai penghematan (savings) untuk masing – masing pasangan sudah diperoleh, maka hal selanjutnya yang harus dilakukan adalah melakukan pengurutan dimulai dari nilai Savings terbesar hingga ke nilai Savings terkecil. Solusi berupa rute tersebut akan didapatkan dengan menyisipkan rangkaian
titik  yang  berkorespondensi  dan  memiliki  nilai  penghematan  ( savings)  lebih  tinggi  (Lysgaard, 2007).
Adapun Genetic Algorithm (GA) pada dasarnya adalah proses dengan pendekatan heuristic yang  dapat  diterapkan  guna  menyelesaikan  berbagai  permasalahan  terkait  optimasi  (Frutos, 2012).  Pada  dasarnya Genetic  Algorithm  memiliki  mengacu  pada  ide  yang  didasarkan  pada evolusi dan proses seleksi alam. Suatu “solusi” dari sebuah permasalahan dianalogikan sebagai spesies yang memiliki kemampuan untuk beradaptasi, menghasilkan keturunan dan berkembang hingga akhirnya mampu menjadi spesies yang optimal (Awad, 2018). Hal tersebut memberikan justifikasi yang relevan, bahwa dengan berbagai permasalahan optimasi dapat dilakukan dengan mengadopsi prinsip – prinsip evolusi. Konsep tersebut dituangkan ke dalam beberapa tahapan umum pada Genetic Algorithm sebagai berikut (Kramer, 2017):
1. Setting Parameters Pada  langkah  ini,  ditentukan  nilai-nilai parameters  dan  Genetic  Algorithm.  Parameters tersebut  antara  peluang  terjadinya Crossover,  peluang  terjadinya  Mutation,  banyaknya individu yang akan terseleksi dan banyaknya generasi yang harus tercapai agar tercapai kondisi Termination (Talbi, 2009).
2. Initialize Population
Merupakan penentuan individu-individu yang akan menjadi populasi awal atau populasi yang hidup di generasi 0 (Talbi, 2009).
3. Crossover
Crossover merupakan perkawinan silang yang dilakukan oleh sepasang orang tua (Talbi, 2009).
4. Mutation
Mutation  merupakan  perubahan  susunan  gen  yang  terjadi  pada  suatu  individu  (Talbi, 2009).
5. Genotype-phenotype Mapping Genotype  adalah  susunan  gen  pada  individu  yang  belum  menjadi  solusi  untuk menyelesaikan permasalahan. Genotype ini harus diterjemahkan menjadi phenotype agar dapat menjadi sebuah solusi (Talbi, 2009).
6. Fitness
Fitness adalah sebuah nilai yang menyatakan seberapa baik kualitas suatu individu (Talbi, 2009).
7. Selection
Selection adalah pemilihan sejumlah individu untuk digunakan pada proses selanjutnya (Talbi, 2009).
8. Termination
Termination adalah suatu kondisi dimana proses evolusi dihentikan (Talbi, 2009).
Penelitian  ini  berfokus  pada  penerapan  GA  guna  memperbaiki  solusi  rute  TSP  yang dihasilkan    oleh Savings  Algorithm.  Dalam  konteks  ini,  rute  TSP  yang  dihasilkan  oleh  Savings Algorithm akan  dijadikan  sebagai  bakal  solusi  yang  mengalami  “seleksi  alam”  dan  “evolusi” sebagaimana yang direpresentasikan pada tahapan – tahapan GA. Dengan demikian diharapkan solusi rute yang diperoleh akan menjadi lebih baik.
Genetic Algorithm for Improving Route of TSP Generated by Savings Algorithm
METODOLOGI
Secara umum tahapan – tahapan yang dilakukan adalah sebagai berikut:
1. Pemilihan instance
Instance  digunakan  sebagai  kumpulan  data  awal  yang  akan  menjadi  acuan  pengerjaan pada  penelitian  ini.  Seluruh instance  tersebut  didapatkan  melalui  laman http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/ . Instance  ini  pernah digunakan  pada  penelitian  sebelumnya  (Sanggala,  2021).  Adapun  penelitian  ini menggunakan sepuluh (10) instance sebagai berikut:
a) berlin52
b) eil51
c) eil76
d) eil101
e) kroA100
f) kroB100
g) kroC100
h) kroD100
i) kroE100
j) pr76
Kesepuluh instance yang akan digunakan, dibuat oleh author yang berbeda-beda, tetapi struktur penulisan pada file text-nya sudah sama sehingga semuanya dapat diperlakukan secara sama (Reinelt, 1995).
2. Penerapan Savings Algorithm pada instance dan Pengembangan Algoritma Menggunakan Genetic Algorithm Instance  yang  dipilih  diselesaikan  terlebih  dahulu  dengan  menggunakan  Savings Algorithm,  kemudian  rute  yang  dihasilkan  berdasarkan  Savings  Algorithm  tersebut dijadikan  bakal  solusi  untuk  selanjutnya  diproses  dengan  menggunakan  tahapan – tahapan pada Genetic Algorithm (crossover, mutation dan selection).
3. Pengujian atas Algoritma yang dikembangkan Algoritma yang didapatkan pada tahapan sebelumnya diujikan kembali pada instance. Hal ini  dilakukan  untuk  membandingkan  dan  memverifikasikan  performa  dari  rute  yang dihasilkan  dengan Saving  Algorithm  dengan  rute  baru  yang  dihasilkan  berdasarkan Saving Algorithm yang kemudian dilanjutkan dengan pendekatan Genetic Algorithm.

## HASIL PENELITIAN DAN PEMBAHASAN
Instance yang digunakan merupakan instance yang umum digunakan oleh para peneliti lain guna menguji  hasil  pengembangan  algoritma  yang  didapatkan.  Adapun  data  dari instance  tersebut dapat dilihat pada Tabel 1.

## Tabel 1: Instance yang Digunakan
Masing – masing instance  tersebut  kemudian  diproses  dengan  menggunakan  Savings Algorithm dan menghasilkan rute yang sebagaimana tercantum pada tabel 2.
Genetic Algorithm for Improving Route of TSP Generated by Savings Algorithm
Tabel 2: Rute yang Dihasilkan dari Savings Algorithm
Genetic Algorithm for Improving Route of TSP Generated by Savings Algorithm
Tabel 2: Rute yang Dihasilkan dari Savings Algorithm (Lanjutan)
Setelah mendapatkan rute dari Savings Algorithm, hal selanjutnya yang dilakukan adalah menjadikan  rute – rute  tersebut  sebagai  bakal  solusi  dengan  algoritma  berdasarkan Genetic Algorithm.  Adapun  parameter – parameter  yang  digunakan  dalam  prosesnya  adalah  sebagai berikut:
1. Mutated Individual Size Parameter  ini  memberikan  jumlah  individu  yang  terbentuk  dari  hasil  mutasi tanpa crossover/perkawinan. Dalam penelitian ini, nilai yang ditetapkan untuk parameter ini adalah sebesar 30 individu, yang mana sama dengan nilai populasinya.
2. Maximum Mutated Individual Pair Gen Parameter ini digunakan untuk menentukan jumlah maksimal pasangan gen yang akan mengalami mutasi. Adapun nilai Maximum Mutated Individual Pair Gen yang ditetapkan dalam  penelitian  adalah  45%  dari  banyaknya  titik  pada instance.  Dalam  prosesnya, dilakukan pembulatan ke bawah jika nilai yang dihasilkan berupa pecahan.
3. One Point Crossover Couple Size One  Point  Crossover  Couple  Size  mendefinisikan  jumlah  pasangan  yang  akan melakukan crossover (perkawinan). Nilai parameter ini ditetapkan sebesar 50%. Dalam prosesnya, dilakukan pembulatan ke bawah jika nilai yang dihasilkan berupa pecahan.
4. Maximum Mutated One Point Crossover Individual Pair Gen Parameter ini menentukan jumlah individu yang akan bermutasi dari hasil crossover sebelumnya.  Nilai  parameter  yang  ditetapkan  adalah  45%  dari  titik  instance.  Dalam prosesnya, dilakukan pembulatan ke bawah jika nilai yang dihasilkan berupa pecah
5. Survivor Size
Parameter  ini  menentukan  jumlah  individu  yang  akan  terus  hidup  pada  generasi selanjutnya.  Nilai  yang  ditetapkan  adalah  sebesar 5 6 dari  jumlah  individu  dalam populasi.  Dalam  prosesnya,  dilakukan  pembulatan  ke  atas  jika  nilai  yang  dihasilkan berupa pecahan. Sebagai contoh jika populasi yang ditetapkan adalah 30 individu, maka jumlah individu yang berhasil hidup pada generasi selanjutnya adalah sebesar 5 6 𝑥 30 =
25 individu.
Genetic Algorithm for Improving Route of TSP Generated by Savings Algorithm
6. Random Individual Size
Parameter ini menentukan jumlah individu yang akan muncul secara acak ketika nilai populasi berada di bawah parameter yang ditetapkan sebelumnya. Hal ini berhubungan dengan parameter sebelumnya. Sebagai contoh pada perhitungan poin (5) didapatkan nilai populasi sebesar 25 individu. Nilai tersebut masih berada di bawah nilai populasi yang ditetapkan, yakni 30 individu. Dengan demikian, akan muncul 5 individu dengan susunan gen yang acak agar memenuhi nilai populasi sebesar 30 individu.
7. Maximum Repeat Shortest Length
Parameter  ini  pada  dasarnya  mengindikasikan  iterasi  perhitungan  yang  dilakukan. Secara  spesifik,  pemeter  ini  menentukan  jumlah  maksimal  kelanjutan  generasi  yang harus  dilewati  oleh  individu/solusi  terbaik  yang  telah  terpilih  pada  generasi sebelumnya. Nilai yang ditentukan dalam penelitian ini adalah 1000 generasi. Hal ini berarti  individu  terbaik  tersebut  harus  mampu survive/tetap  menjadi  yang  terbaik selama 1000 generasi berikutnya.
Dalam pelaksanaannya, algoritma yang sudah dikembangkan ini dituliskan ulang ke dalam bahasa  pemrograman  pada  GNU  Octave.  Hal  ini  dilakukan  agar  proses  komputasi  dari  TSP  ini dapat  dilakukan  dengan  menggunakan  komputer. GNU  Octave  sendiri  merupakan  tools  untuk membantu proses komputasi numerik (Hansen, 2011). Adapun hasil rute yang didapatkan dari pengembangan algoritma tersebut dapat dilihat pada tabel 3 berikut:
Tabel 3: Rute yang Dihasilkan dari Algoritma yang Dikembangkan Berdasarkan GA
Genetic Algorithm for Improving Route of TSP Generated by Savings Algorithm
Tabel 3: Rute yang Dihasilkan dari Algoritma yang Dikembangkan Berdasarkan GA (Lanjutan)
Setelah  dilakukan  perbandingan,  maka  didapatkan  bahwa  performa  solusi  rute  yang dihasilkan dari algoritma yang dikembangkan dengan mengacu pada Genetic Algorithm mampu memperbaiki  solusi  yang  sebelumnya  telah  dihasilkan  oleh Savings  Algorithm  sebagaimana tercantum pada tabel 4 berikut:
Tabel 4: Perbandingan Performa Algoritma

## SIMPULAN
Pendekatan heuristic  seperti  Savings  Algorithm  tidak  selalu  memberikan  solusi  yang  optimal. Peluang perbaikan atas solusi dari pendekatan heuristic tersebut dapat diperoleh menggunakan pendekatan metaheuristic  seperti  Genetic  Algorithm.  Dalam  penelitian  ini,  algoritma  yang dikembangkan dengan mengacu pada Genetic Algorithm mampu memperbaiki solusi rute yang dihasilkan dari Savings Algorithm dengan batasan 10 instance. Meskipun begitu, algoritma yang dikembangkan ini perlu terus diujikan pada jenis instance lain guna mengukur konsistensi atas performanya.

## DAFTAR PUSTAKA
Awad,  H. ,  Elshaer,  R.,  Abdelmo’ez,  A.  &  Nawara,  G. (2018).  An  Effective  Genetic  Algorithm  for Capacitated  Vehicle Routing  Problem, International  Conference on Industrial  Engineering and Operations Management Bandung, Indonesia, March 6-8, 2018.
Applegate, D.L., Bixby, R.E., Chvatal, V., & Cook, W.J. (2006). The Traveling Salesman Problem A Computational Study, Princeton University Press – New Jersey
Bhagya, T.G. (2021). Algoritma Genetik Pada Penjadwalan Transportasi Kapal Laut (Studi Kasus PT. Pelni). Journal of Industrial and Manufacture Engineering, 5(2), 81-92.
Chiarandini,  M.  (2020). Construction  Heuristics  for  Traveling  Salesman  Problem,  University  of Southern – Denmark
Clarke,  G.,  &  Wright,  J.W.  (1964).  Scheduling  of  Vehicles  from  A  Central  Depot  to  A  Number  of Delivery Points, Operations Research Frutos, M., & Tohme, F. (2012). A New Approach to The Optimization of The CVRP through Genetic Algorithm, American Journal of Operations Research Hansen, J.S. (2011). GNU Octave Beginner’s Guide , PACKT – Birmingham Kramer, O. (2017). Genetic Algorithm Essentials, Springer – Switzerland Labadie, N., Prins, C., & Prodhon, C. (2016). Metaheuristics for Vehicle Routing Problem, ISTE – London Lavrov, M. (2020). The Traveling Salesman Problem, University of Illinois at Urbana-Champaign - USA
Lysgaard, J. (2007). Clarke & Wright’s Savings Algorithm , Department of Management Science and Logistics – The Aarhus School of Business – Denmark
Reinelt,  G.  (1995). TSPLIB  95,  Institut  fur  Angewandte  Mathematik – Universitat  Heidelberg – Germany
Sanggala, E., Dimyati, T.T., & Yogaswara, Y. (2021). Genetic Algorithm Untuk Memperbaiki Rute Travelling Salesman Problem Yang Dihasilkan Dari Nearest Neighbour, Jurnal Logistik Bisnis – Politeknik POS Indonesia
Talbi, E. (2009). Metaheuristics from Design to Implementation, John Wiley & Sons – USA
http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/ , diakses 2 Januari 2023