## MULTI TRAVELING SALESMAN PROBLEM (MTSP) DENGAN ALGORITMA GENETIKA UNTUK
MENENTUKAN RUTE LOPER KORAN DI AGEN SURAT KABAR

## Fitriana Yuli Saptaningtyas
Jurusan Pendidikan Matematika FMIPA UNY fitrianatya@uny.ac.id

## Abstrak
Permasalahan  pendistribusian  oleh  beberapa  loper  koran  di  suatu  agen  surat  kabar  pada pelanggan  sering  mengalami  keterlambatan.  Bagaimana  menentukan rute  optimum  bagi  beberapa  loper koran di sebuah agen surat kabar akan dimodelkan secara matematis dan akan diselesaikan menggunakan algoritma genetika. Permasalahan ini masuk dalam kategori Multi Travelling Salesman Problem (MTSP) Algoritma  genetika  yang  mengadopsi  proses  evolusi  makhluk  hidup,  pada  penerapannya mengikuti langkah pembentukan populasi, menentukan nilai fitness , melakukan proses seleksi, melakukan pindah silang dan mutasi, dan  membentuk individu baru.
Algoritma genetika dapat digunakan untuk menentukan rute optimum perjalanan beberapa loper koran di suatu agen surat kabar. Penentuan rute perjalanan beberapa loper koran di suatu agen surat kabar dengan  langkah  mendefinisikan  populasi,menentukan  nilai fitness, melakukan  proses  seleksi  dengan metode  seleksi  rangking,  pindah  silang  dengan order  cross  over, melakukan  mutasi  dengan swapping mutation , dan memperoleh individu baru yang menuju ke penyelesaian optimum. Dari hasil  simulasi di suatu agen surat kabar dengan delapan loper Koran dan 160 pelanggan diperoleh jarak terpendek  sejauh 144.16 km pada iterasi ke 98. Semakin banyak iterasi yang digunakan maka akan semakin memberi solusi yang lebih optimum.
Kata Kunci: Algoritma Genetika, Loper Koran, Agen Surat Kabar, MTSP

## PENDAHULUAN
Algoritma genetika cukup efektif dalam menyelesaikan permasalahan optimasi. Dalam perkembangannya telah diapliakasikan  dalam  pencarian  rute optimum, penjadwalan, Travelling Salesman  Problem (TSP),  dan  lain sebagainya.  Prosedur  dalam  pencarian solusi  yang  mengadopsi  proses  evolusi makhluk  hidup  dapat  digunakan  untuk menyelesaiakan masalah yang memerlukan banyak perhitungan dengan menggunakan  algoritma  konvensional menjadi lebih sederhana. Pada permasalahan pendistribusian surat kabar oleh beberapa orang loper koran di suatu
agen  surat  kabar  dapat  dikategorikan dalam  masalah  MTSP.  Loper  koran  di suatu  agen  surat  kabar  bertugas  untuk menyampaikan  surat  kabar  di  pagi  hari. Beberapa  permasalahan  yang  sering dialami  dalam  pendistribusian  surat kabar adalah keterlambatan waktu penyampaian surat kabar pada pelanggan.  Pada  umumnya  pelanggan surat  kabar  adalah  para  pegawai  kantor dengan  jam  keberangkatan  bekerja adalah  jam  07.00  WIB  sehingga  para pelanggan  menginginkan  koran  sampai ke  pelanggan  sebelum  jam  tersebut. Surat  kabar  siap  untuk  diedarkan  dari sebuah  agen  pukul  05.00  WIB,  para
loper  koran  hanya  memiliki  waktu sekitar dua jam
untuk mendistribusikannya.  Sebuah  agen  surat kabar  memiliki  beberapa  orang  loper untuk  mendistribusikan  ke  pelanggan. Untuk  mempercepat  penyampaian  surat kabar ke pelanggan langsung, para loper koran menggunakan kendaraan bermotor dengan  kapasitas  angkut  surat  kabar maksimal  sebanyak  70  surat  kabar. Bagaimana  beberapa  orang  loper  koran di suatu agen surat kabar menghantarkan koran  pada  para  pelanggan    dapat dimodelkan secara matematis.
Permasalahan  pendistribusian  koran  di sebuah  agen  surat  kabar  dengan  lebih dari  seorang  loper  dapat  dimodelkan dalam multi traveling salesman problem (MTSP).
Masalah MTSP merupakan
masalah  optimasi yang merupakan perluasan dari masalah travelling salesman  problem (TSP).  Permasalahan ini dapat dijadikan acuan dalam mencari rute  terpendek maupun melakukan penjadwalan berbagai permasalahan optimasi. Permasalahan MTSP merupakan  pengembangan  dari  masalah travelling  salesman  problem ,  dimana yang  melakukan  perjalanan  tidak  hanya seorang sales tapi lebih dari satu ( Shalini Singh,  2014 ).  Menurut  Bertas(2006)
permasalahan MTSP didefinisikan dalam sebuah  graf  G=(V,A),  dengan  V  adalah himpunan  titik  yang  merepresentasikan kota,  A  adalah  himpunan  sisi  yang menghubungkan  antar  kota  dengan  i,j adalah  penghubung  antar  titik  kota,  dan
, adalah  variable  biner  dengan ketentuan , =1  jika  sisi  i,j  dikunjungi oleh sales dan 0 untuk sisi i,j yang tidak dikunjungi  serta , adalah  jarak  antar kota ke-i dan kota ke-j.
Permasalahan MTSP dapat diselesaikan dengan menggunakan berbagai  metode.  Algoritma  heuristic cukup  efektif  untuk  menyelesaikan masalah  ini,  walaupun  solusi  yang diperoleh  merupakan  solusi  pendekatan. Salah  satu  algoritma  heuristic  adalah algoritma  genetika.  Algoritma  genetika mengadopsi  pada  kemampuan  mahluk hidup  dalam  proses  seleksi  alam  untuk mencapai optimasinya. Algoritma genetika  mengadopsi  sebuah  populasi individu  yang  merupakan  himpunan solusi secara berulang. Algoritma genetika  memilih  individu  secara  acak dari  populasi  untuk  dijadikan  induk  dan menggunakannya  untuk  menghasilkan keturunan  pada  generasi  berikutnya. Individu  yang  mampu  bertahan  dalam proses seleksi alam analog dengan solusi optimal dalam masalah optimasi.
Algoritma genetika cukup bagus diaplikasikan da lam menyelesaikan masalah  TSP.  Salah  satu  kelebihan algoritma genetika menurut suyanto(2005 ) adalah kemudahan implementasi  dan  kemampuannya  untuk menemukan  solusi  yang  ‘bagus’  (bisa diterima)  secara  tepat  untuk  masalah- masalah  berdimensi  tinggi.  Karena masalah  MTSP  merupakan  bagian  dari masalah  TSP  maka  masalah  MTSP  juga dapat  diselesaikan  dengan  algoritma genetika.  Penelitian  terkait  algoritma genetika  pada  rute  seorang  loper  koran telah  dilakukan  oleh  Antonios  (2013) yaitu  mengenai  masalah  TSP  dengan hasil yang cukup baik ditinjau dari solusi optimal  yang  diperoleh.  Pada  kajian  ini, menerapkan  algoritma  genetika  untuk menyelesaikan  masalah  MTSP  pada pendistribusian  surat  kabar  oleh  lebih dari  satu  loper  di  sebuah  agen  surat kabar.  Digunakan  simulasi  data  dari suatu  agen  surat  kabar  dengan  delapan loper  koran,  dari  hasil  simulasi  akan dianalisa  pengaruh  banyaknya  iterasi terhadap solusi optimum yang dihasilkan.

## PEMBAHASAN
Model matematika dalam masalah  MTSP  dalam  perkembanganya
memiliki  berbagai  bentuk  variasi,  dalam kajian  ini  model  matematika  yang  akan dibangun berdasarkan kondisi rute pendistribusian surat kabar oleh beberapa  orang  loper  di  sebuah  agen surat  kabar.  MTSP  dengan  kondisi bahwa  beberapa  orang  sales  harus mengunjungi    beberapa  tempat  hanya sekali  dan  kembali  ke  tempat  semula dengan  semua  tempat  telah  dikunjungi oleh  salah  satu  dari  sales  yang  ada. Adapun model matematika dari permasalahan ini adalah:
Fungsi Objektifnya adalah = ∑ ∑ …………… ……(1) Dengan kendala: ∑ = (2) ∑ = (3)
∑ = 1, = 2,3, … , (4) ∑ = 1, = 2,3, … , (5)
Dari  fungsi  tujuan  di  atas  dalam persamaan  (1)  dapat  diketahui  akan meminimumkan perjalanan yaitu dengan meminimumkan  biaya/jarak ,dengan merupakan  jalan  dari  kota  ke  i  ke  j yang  bernilai  0  atau  1,  yang  artinya  0 jalan  tersebut  tidak  dikunjungi    dan  1 jalan  tersebut  dikunjungi.  Kendala  pada persamaan  (2)  dan  (3)  berarti  bahwa yang  akan  mengunjungi  n  kota  adalah
sebanyak m sales. Persamaan (4) dan (5) menunjukkan  bahwa  masing  masing kota hanya dikunjungi satu kali.
Permasalahan  MTSP  di  atas dapat diselesaikan dengan menggunakan algoritma genetika. Secara umum
langkah–langkah  dalam  menyelesaikan permasalahan  optimasi  menggunakan algoritma genetika menurut David Goldberg  (1996)  dapat  ditampilkan dalam alur berikut ini:
Gambar 1. Flow Chart Algoritma Genetika menurut David Goldberg (1996) Dari alur di atas dapat dijelaskan  bahwa pada pembentukan populasi awal merupakan kumpulan solusi yang mungkin  dari  masalah  optimasi  yang akan diselesaikan. Proses evaluasi fitness merupakan suatu proses untuk mengetahui  kemampuan  makhluk  hidup dalam bertahan analog dengan mengetahui  bagus  tidaknya  suatu  solusi dalam  masalah  optimasi.    Seleksi individu  merupakan  proses    pemilihan orang  tua yang akan  disilangkan sehingga menghasilkan keturunan. Proses  pindah  silang  ( cross  over )
merupakan proses menghasilkan keturunan baru yang akan diuji kemampuan bertahannya. Mutasi merupakan proses untuk mengubah nilai dari  suatu  gen  dalam  kromosom.  Proses mutasi  dalam  kromosom  digunakan untuk  memperoleh  individu  baru  yang mempunyai nilai fitness yang lebih baik.
Dari  hasil  proses  ini  diperoleh  poulasi baru  yang  akan  diuji  nilai fitness . Individu  dengan  nilai fitness terbaik merupakan solusi yang optimum.
Pada permasalahan pendistribusian koran di suatu agen surat Populasi Awa l
Evaluasi Fitness Seleksi Individu Pindah Silang dan Mutasi Individu baru
kabar  dengan  beberapa  orang  loper koran memenuhi asumsi berikut:
1. Terdapat    banyak  pelanggan  yang harus  dikunjungi  tepat  satu  kali. Dalam  hal  ini  yang  akan  digunakan
untuk  simulasi  yaitu  terdapat  160 pelanggan yang diasumsikan menjadi 40 pelanggan dengan ketentuan  bahwa  pelanggan  yang berjarak  kurang  dari  20  meter dianggap satu tempat.
2. Terdapat  m  sales,  dalam  hal  ini memiliki 8 loper Koran.
3. Setiap  loper  koran  akan  melakukan perjalanan  dari  agen  ke  pelanggan dan kembali lagi ke agen.
Permasalahan yang
akan dipecahkan adalah bagaimana rute masing-masing loper koran agar mendapatkan jarak yang optimum dengan menggunakan algoritma genetika. Adapun langkah-langkah penyelesaian  masalah  tersebut  dengan menggunakan algoritma genetika adalah:
1. Membangun  populasi  awal  dengan individu  adalah  urutan  perjalanan dari  8  loper  yang  masing  masing loper  berawal  dan  berakhir  di  agen. Contoh individu -1 (1 2 3 4 5 1) (1 6 7 8 9 10 1) (1 11 12 13
14 15 1) (1 16 17 18 19 20 1) (1 21
22 23 24 25 1) (1 26 27 28 29 30 1)
(1 31 32 33 34 35 1) (1 36 37 38 39
40 1)
2. Menghitung nilai fitness yaitu menggunaakan = ∑ , yaitu satu dibagi jarak rute yang
dikunjungi semua sales.
3. Proses  seleksi  yang  digunakan menggunakan seleksi rangking.
Menurut Sri  Kusuma   Dewi (2003), prosedur  dalam  seleksi  rangking adalah:
Menghitung  nilai fitness dari masing-masing individu, mengurutkan  nilai fitness dari  yang paling  besar,  kromosom  terburuk diberi  nilai  1  dan  seterusnya, dihitung total fitness semua individu,  dan  dihitung  probabilitas masing-masing  individu,  dihitung jatah  pada  masing-masing  individu, dibangkitkan  bilangan  random,  dari bilangan  random  dipilih  individu yang  akan  terpilih  dalam  proses seleksi.
4. Proses  pindah  silang  menggunakan teknik order  cross  over. Proses pindah  silang  dilakukan  dengan pertukaran gen pada dua induk yang bersesuaian  untuk  menghasilkan individu  baru.  Teknik  pindah  silang yang  digunakan  adalah order  cross
over menurut Davis (Suyanto, 2005).
5. Proses mutasi menggunakna swapping  mutation .  Proses  mutasi ini  bertujuan  untk  mengubah  gen– gen dalam kromosom. Teknik swapping mutation menurut Suyanto (2005)  diawali  dengan  memilih bilangan  acak  kemudian  gen  yang berada  pada  posisi  bilangan  acak pertama  ditukar  dengan  gen  yang berada  pada  bilangan  acak  kedua dalam probabilitas tertentu.
Pada  kajian  ini  akan  ditampilkan simulasi  dengan  menggunakan  Software Matlab  dari  permasalahan  bagaimana menentukan  rute  optimum  dari  delapan orang loper yang akan mengunjungi 160 tempat  yang  direduksi  menjadi  40 tempat.  Pada  kajian  ini  akan  dilakukan
percobaan dengan melakukan perubahan pada banyaknya iterasi.
Pada  simulasi  yang  pertama dipilih  banyaknya  iterasi  yaitu  98 diperoleh jarak total adalah 144 km. Dari gambar di bawah ini dapat diketahui rute masing  masing  loper  dengan  rata-rata jarak  yang  ditempuh  adalah  18  km. Apabila loper koran  menempuh jarak 18 km  dengan  kecepatan  rata  –rata  50 km/jam  maka  memerlukan  waktu    27 menit  untuk  melakukan  perjalanan.  Jika waktu yang diperlukan untuk memberikan  koran  pada  20  pelanggan adalah 60  menit,  maka waktu total  yang diperlukan  sales  untuk  menyelesaikan tugas membagikan koran pada pelanggan  adalah1  jam  27  menit. Dengan hasil ini surat kabar akan sampai keseluruh  pelanggan  sebelum  jam  07.00 WIB.
Gambar 2. Rute Optimum Pendistribusian Surat Kabar oleh delapan loper Koran menggunakan Algoritma Genetika dengan banyak iterasi 98
0 5 10 15 20 25 30 35 40 0 5 10 15 20 25 30 35 40 Total Distance = 144.1600, Iteration = 98
Pada  percobaan  kedua  dipilih banyaknya  iterasi  adalah  86.  Dari  hasil ini  diketahui  bahwa  rute  optimumnya
lebih  jauh  yaitu  145.8  km  dengan  rute masing-masing  sales  seperti  gambar  di bawah ini.
Gambar 3. Rute Optimum Pendistribusian Surat Kabar oleh delapan loper Koran menggunakan Algoritma Genetika dengan banyak iterasi 86
Pada  percobaan  ketiga  dipilih banyaknya  iterasi  adalah  80.  Dari  hasil ini  diketahui  bahwa  rute  optimumnya
lebih  jauh  yaitu  156.34  km  dengan  rute masing-masing  sales  seperti  gambar  di bawah ini.
Gambar 4. Rute Optimum Pendistribusian Surat Kabar oleh delapan loper Koran menggunakan Algoritma Genetika dengan banyak iterasi 80
0 5 10 15 20 25 30 35 40 0 5 10 15 20 25 30 35 40 Total Distance = 145.8000, Iteration = 86 0 5 10 15 20 25 30 35 40 0 5 10 15 20 25 30 35 40 Total Distance = 156.3400, Iteration = 80
Pada  percobaan  keempat  dipilih banyaknya  iterasi  adalah  76.  Dari  hasil ini  diketahui  bahwa  rute  optimumnya
lebih  jauh  yaitu  184.38  km  dengan  rute masing-masing  sales  seperti  gambar  di bawah ini.
Gambar 5. Rute Optimum Pendistribusian Surat Kabar oleh delapan loper Koran menggunakan Algoritma Genetika dengan banyak iterasi 76
Pada  percobaan  kelima  dipilih banyaknya  iterasi  adalah  57.  Dari  hasil ini  diketahui  bahwa  rute  optimumnya
lebih  jauh  yaitu  193.4  km  dengan  rute masing-masing  sales  seperti  gambar  di bawah ini.
Gambar 6. Rute Optimum Pendistribusian Surat Kabar oleh delapan loper Koran menggunakan Algoritma Genetika dengan banyak iterasi 57
0 5 10 15 20 25 30 35 40 0 5 10 15 20 25 30 35 40 Total Distance = 184.3800, Iteration = 76 0 5 10 15 20 25 30 35 40 0 5 10 15 20 25 30 35 40 Total Distance = 193.4400, Iteration = 57
Dari  hasil  simulasi  di  atas  dapat diketahui  bahwa  semakin  banyak  iterasi yang digunakan maka memberikan jarak yang semakin pendek. Pada permasalahan pendistribusian surat kabar kepada  160  pelanggan  dengan  delapan sales  di  sebuah  agen  koran  masih memungkinkan untuk terselesaikan kurang dari dua jam. Dengan menggunakan algoritma genetika diperoleh  solusi  optimum  dari  hasil simulasi  yang  dilakukan  adalah  sejauh 144.16 km.

## SIMPULAN DAN SARAN
Algoritma genetika
dapat digunakan untuk menentukan rute optimum  perjalanan  beberapa  loper koran  di  suatu  agen  surat  kabar. Penentuan  rute  perjalanan  beberapa loper  koran  di  suatu  agen  surat  kabar dengan algoritma genetika menggunakan langkah mendefinisikan populasi,menentukan nilai fitness, melakukan proses seleksi dengan metode seleksi  rangking,  pindah  silang  dengan order  cross  over, melakukan  mutasi dengan swapping mutation , dan memperoleh  individu  baru  yang  menuju ke  penyelesaian  optimum.  Dari  hasil simulasi  data  di  suatu  agen  surat  kabar dengan delapan loper dan 160 pelanggan
diperoleh jarak terpendek  sejauh 144.16 km  pada  iterasi  ke  98.  Semakin  banyak iterasi  yang  digunakan  maka  akan semakin memberi solusi yang lebih baik.
Pada  kajian  ini  baru  dapat menganalisa  banyaknya  iterasi  dengan variable  yang  lain dianggap sama, dapat dikaji lebih lanjut pengaruh variable lain misalnya  banyak  individu  dan  lain sebagainya.  Dapat  digunakan  berbagai tehnik  mutasi  dan  pindah  silang  yang lain dalam menemukan solusi optimum.

## DAFTAR PUSTAKA
Bektas,T.(2006).The  multiple  traveling salesman  problem:  an  overview  of formulations and solution procedures. OMEGA: The
International Journal of Management Science, 34(3), 209-219.
Goldberg,David. (1999). An introduction to  genetic  Algorithms  for  scientists and Engineers. Singapure:Uso-Print
Shalini  Singh  dan  Ejaz  Aslam  Lodhi . (2014). Comparison Study of Multiple Traveling Salesmen Problem using Genetic Algorithm.IJCSNS International
Journal  of  Computer  Science  and Network  Security,  VOL.14  No.7, July 2014
Sri  Kusuma  Dewi.  (2003).  Artificial Intelligent (Teknik dan Aplikasinya). Yogyakarta:Graha Ilmu Suyanto.(2005). Algoritma Genetika dalam  MATLAB.  Yogyakarta:  Andi Ofset
Wayan Firdaus  Mahmudy.  (2008).
Optimasi  Multi  Travelling  Salesman
Problem (M-TSP) Menggunakan Algoritma Genetika. Seminar
Nasional  BasicScience  V ,  FMIPA,
UniversitasBrawijaya,  Malang,  16
February