## TEORI PERMUTASI DAN PENGGUNAAN API MAPBOX UNTUK PENCARIAN RUTE TERPENDEK
Suryo Atmojo S.Kom, M.Kom 1
1 Universitas Wijaya Putra Surabaya , Email : suryoatmojo@uwp.ac.id

## Abstrak
Permasalahan untuk mencari rute terkecil dari satu titik (node) awal ke titik (node) tujuan bias disebut pencarian  rute  terpendek  (shortest  path  problem).  Metode  matematika  yang  dapat  digunakan  untuk mencari ruter terpedek  adalah permutasi. Metode permutasi digunakan untuk mencari  rute terpendek dengan  mengatur  elemen-elemen  dari  sebuah  himpunan  dengan  memperhatikan  urutan  dari  masing- masing elemen. Metode permutasi memungkinkan untuk mendapatkan kombinasi dari beberapa node, sehingga  kombinasi  node  dengan  jarak  terpendek  dapat  dipilih.  API  Mapbox  adalah  sebuah webservice  yang  menyediakan  informasi  tentang  geocoding  dan  direction  dari  dua  buah  node. Berdasarkan  hasil  penelitian,  rute  terpendek  merupakan  rute  tercepat  tetapi  jarak  terpendek  tidak berarti rute terpendek karena memperhitungkan faktor nilai bobot kemacetan jalan.

## Kata Kunci: Permutasi, PHP, codeigniter, Map

## Abstract
The problem of finding the smallest route from one node to the biased destination node is called the shortest path problem. A mathematical method that can be used to search for a rotor is a permutation. The permutation method is used to find the shortest route by arranging elements of a set with respect to the order of each element. Permutation method allows to get combination of several nodes, so that combination  of  node  with  the  shortest  distance  can  be  selected.  Mapbox  API  is  a  webservice  that provides information about geocoding and direction of two nodes. Based on the results of research, the shortest route is the fastest route but the shortest distance does not mean the shortest route because it takes into account the value factor for the weight of road congestion.
Keyword: Permutation, PHP, Codeigniter, Map

## Pendahuluan
Pada dasarnya, segala  aktifitas  yang  ada dalam  kehidupan  sehari-hari  adalah  hasil  dari serangkaian  proses  yang  melibatkan  banyak pihak mulai dari proses produksi yang meliputi pemasokkan  bahan  baku  untuk  diolah  dan menjadi barang jadi, hingga proses
pendistribusian yang merupakan proses penting  dalam  pemasaran  produk  dari  pabrik manufacture ke  konsumen.  Secara  umum Proses pendistribusian barang yang di lakukan saat  ini  adalah  dengan  cara  acak  dan  manual yaitu  dalam  penentuan  rute  pedistribusian tanpa  memikirkan  efisien  waktu  dalam pengiriman  barang  ke  tempat  tujuan.  Dalam sekali  pengiriman  barang  ada  lebih  dari  satu tempat dan satu barang yang akan di distribusi oleh  satu  kendaraan.  Dari  proses  pengiriman barang  tersebut  menyebabkan  pengiriman barang  akan  membutuhkan    waktu  yang  lebih lama.
Dengan  adanya  permasalahan  tersebut maka  peneliti  ingin  membuat  pengoptimalan rute  transportasi  secara  terkomputerisasi  yang dapat  membantu  mendukung  pengambilan keputusan  yang  dilakukan  untuk  menentukan rute transportasi yang lebih optimal dan merata serta  dapat  meminimalisir  waktu  tempuh dengan  menggunakan  metode  permutasi  dan API Mapbox.
API  Mapbox dipilih  sebagai  webservice di  karenakan  penggunaan  API  tersebut cenderung  lebih  mudah,  serta  informasi  yang di hasilkan cukup lengkap, mulai dari distance, coordinates, street name, hingga waypoints.
Sebagai contoh pemanfaatan api Mapbox  dapat  dilihat  seperti  gambar  dibawah ini.

## METODE PENELITIAN

## PENGUMPULAN TITIK
Pada  tahapan  ini  akan  ditentukan  titik  titik yang  akan  dilewati,  untuk  nantinya  dicari kombinasi  dari  titik  tersebut  yang  mana rutenya terpendek. Pada penelitian kali ini, titik titik yang dipilih adalah
 112.793018,-7.306827,
 112.745502,-7.289148,
 112.748575,-7.265537,
 112.734064,-7.255276

## PERMUTASIKAN TITIK
Permutasi adalah pengaturan elemen-elemen dari sebuah himpunan dimana urutan dari elemen elemen tersebut diperhatikan. Secara matematik, dari sebuah himpunan yang mempunyai elemen sebanyak n , banyaknya permutasi dengan ukuran (permutasi dengan jumlah elemen) r ditulis sebagai P ( n , r ) atau n P r atau n P r .
Rumusnya adalah
P ( n , r ) = n P r = n P r = n ! ( n - r )!
dimana n ! ( n faktorial) = n × ( n -1) × ( n -2) × ... × 1 dan 0! = 1.
Contoh,  dari  himpunan  huruf-huruf  {a,b,c}, permutasi-permutasi dengan ukuran 2 (ambil 2 elemen  dari  himpunan  tersebut)  adalah  {a,b},
permutasi titik Pengumpulan Titik Check Distance

## Get informasi jalur terpendek
{b,a},  {a,c},  {c,a},  {b,c},  dan  {c,b}. Perhatikan  bahwa urutan dari  elemen-elemen itu  adalah  penting,  dengan  kata  lain  {a,b} adalah
berbeda dengan
{b,a}.
Banyaknya permutasi adalah 6.

## HASIL PENELITIAN DAN PEMBAHASAN
Dari  kasus  ini,  terdapat  4  titik  dimana  jika dipermutasikan  ada  24  kombinasi  titik  seperti dibawah ini:
PERMUTASI : 0 112.793018,-7.306827,112.745502,- 7.289148,112.748575,-7.265537,112.734064,- 7.255276 PERMUTASI : 1 112.745502,-7.289148,112.793018,-
7.306827,112.748575,-7.265537,112.734064,- 7.255276
PERMUTASI : 2 112.793018,-7.306827,112.748575,- 7.265537,112.745502,-7.289148,112.734064,- 7.255276
PERMUTASI : 3 112.748575,-7.265537,112.793018,- 7.306827,112.745502,-7.289148,112.734064,-
7.255276
PERMUTASI : 4 112.745502,-7.289148,112.748575,- 7.265537,112.793018,-7.306827,112.734064,-
7.255276
PERMUTASI : 5 112.748575,-7.265537,112.745502,- 7.289148,112.793018,-7.306827,112.734064,- 7.255276
PERMUTASI : 6
112.793018,-7.306827,112.745502,- 7.289148,112.734064,-7.255276,112.748575,- 7.265537
PERMUTASI : 7 112.745502,-7.289148,112.793018,- 7.306827,112.734064,-7.255276,112.748575,-
7.265537
PERMUTASI : 8 112.793018,-7.306827,112.734064,-
7.255276,112.745502,-7.289148,112.748575,- 7.265537
PERMUTASI : 9
112.734064,-7.255276,112.793018,- 7.306827,112.745502,-7.289148,112.748575,-
7.265537
PERMUTASI : 10 112.745502,-7.289148,112.734064,- 7.255276,112.793018,-7.306827,112.748575,- 7.265537
PERMUTASI : 11 112.734064,-7.255276,112.745502,- 7.289148,112.793018,-7.306827,112.748575,- 7.265537
PERMUTASI : 12
112.793018,-7.306827,112.748575,- 7.265537,112.734064,-7.255276,112.745502,-
7.289148
PERMUTASI : 13
112.748575,-7.265537,112.793018,- 7.306827,112.734064,-7.255276,112.745502,-
7.289148
PERMUTASI : 14
112.793018,-7.306827,112.734064,- 7.255276,112.748575,-7.265537,112.745502,-
7.289148
PERMUTASI : 15
112.734064,-7.255276,112.793018,- 7.306827,112.748575,-7.265537,112.745502,- 7.289148
PERMUTASI : 16
112.748575,-7.265537,112.734064,-
7.255276,112.793018,-7.306827,112.745502,- 7.289148 PERMUTASI : 17
112.734064,-7.255276,112.748575,- 7.265537,112.793018,-7.306827,112.745502,- 7.289148
PERMUTASI : 18 112.745502,-7.289148,112.748575,- 7.265537,112.734064,-7.255276,112.793018,-
7.306827
PERMUTASI : 19
112.748575,-7.265537,112.745502,-
7.289148,112.734064,-7.255276,112.793018,-
7.306827
PERMUTASI : 20
112.745502,-7.289148,112.734064,-
7.255276,112.748575,-7.265537,112.793018,- 7.306827
PERMUTASI : 21 112.734064,-7.255276,112.745502,- 7.289148,112.748575,-7.265537,112.793018,- 7.306827
PERMUTASI : 22 112.748575,-7.265537,112.734064,- 7.255276,112.745502,-7.289148,112.793018,- 7.306827
PERMUTASI : 23 112.734064,-7.255276,112.748575,- 7.265537,112.745502,-7.289148,112.793018,- 7.306827

## CHECK DISTANCE
Dengan memanfaatkan api Mapbox, kita dapat menentukan jarak kedua buah titik yang sudah kita kobinasikan.
Pada api Mapbox, kita dapat mengukur jarak dari dua buak titik dengan memanfaatkan URL dengan format:
https://api.mapbox.com/directions/v5/map box/driving/<coordinat asal>;coordinat tujuan.json?access_token=<token>&steps =true&geometries=geojson Contoh:
https://api.mapbox.com/directions/v5/map box/driving/112.7929657,- 7.3068258;112.779259,- 7.289899.json?access_token=pk.eyJ1Ijoic 3VyeW9hdG0iLCJhIjoiY2pjb2NwcmdqMD E0NzJ4b2MwYXNxZjl4aiJ9.GslBgWjg1GJ hkemepRGCBQ&steps=true&geometries= geojson
dengan memanfaatkan api Mapbox maka
didapatkan hasil PERMUTASI : 0 distance : 7854.6 distance : 3582.1 distance : 2594.7 distance : 13704.2 TOTAL DISTANCE : 27735.6
PERMUTASI : 1 distance : 7321.5 distance : 10336.1 distance : 2594.7 distance : 6122 TOTAL DISTANCE : 26374.3
PERMUTASI : 2 distance : 10336.1 distance : 4742.5 distance : 6176.8 distance : 13704.2 TOTAL DISTANCE : 34959.6
PERMUTASI : 3 distance : 11212.9 distance : 7854.6 distance : 6176.8 distance : 2720.2 TOTAL DISTANCE : 27964.5
PERMUTASI : 4 distance : 3582.1 distance : 11212.9 distance : 15404.7 distance : 6122 TOTAL DISTANCE : 36321.7
PERMUTASI : 5 distance : 4742.5 distance : 7321.5 distance : 15404.7 distance : 2720.2 TOTAL DISTANCE : 30188.9
distance : 7854.6 distance : 6176.8 distance : 2720.2 distance : 11212.9 TOTAL DISTANCE : 27964.5
PERMUTASI : 7 distance : 7321.5 distance : 15404.7 distance : 2720.2 distance : 4742.5 TOTAL DISTANCE : 30188.9
PERMUTASI : 8 distance : 15404.7 distance : 6122 distance : 3582.1 distance : 11212.9 TOTAL DISTANCE : 36321.7
PERMUTASI : 9 distance : 13704.2 distance : 7854.6 distance : 3582.1 distance : 2594.7 TOTAL DISTANCE : 27735.6
PERMUTASI : 10 distance : 6176.8 distance : 13704.2 distance : 10336.1 distance : 4742.5 TOTAL DISTANCE : 34959.6
PERMUTASI : 11 distance : 6122 distance : 7321.5 distance : 10336.1 distance : 2594.7 TOTAL DISTANCE : 26374.3
PERMUTASI : 12 distance : 10336.1 distance : 2594.7 distance : 6122 distance : 7321.5 TOTAL DISTANCE : 26374.3
PERMUTASI : 13 distance : 11212.9 distance : 15404.7 distance : 6122 distance : 3582.1 TOTAL DISTANCE : 36321.7
PERMUTASI : 14 distance : 15404.7 distance : 2720.2 distance : 4742.5 distance : 7321.5 TOTAL DISTANCE : 30188.9
PERMUTASI : 15 distance : 13704.2 distance : 10336.1 distance :
4742.5 distance : 6176.8 TOTAL DISTANCE : 34959.6
PERMUTASI : 16 distance : 2594.7 distance : 13704.2 distance : 7854.6 distance : 3582.1 TOTAL DISTANCE : 27735.6
PERMUTASI : 17 distance : 2720.2 distance : 11212.9 distance : 7854.6 distance : 6176.8 TOTAL DISTANCE : 27964.5
PERMUTASI : 18 distance : 3582.1 distance : 2594.7 distance : 13704.2 distance : 7854.6 TOTAL DISTANCE : 27735.6
PERMUTASI : 19 distance : 4742.5 distance : 6176.8 distance : 13704.2 distance : 10336.1 TOTAL DISTANCE : 34959.6
PERMUTASI : 20 distance : 6176.8 distance : 2720.2 distance : 11212.9 distance : 7854.6 TOTAL DISTANCE : 27964.5
PERMUTASI : 21 distance : 6122 distance : 3582.1 distance : 11212.9 distance : 15404.7
TOTAL DISTANCE : 36321.7 PERMUTASI :
22 distance : 2594.7 distance : 6122 distance : 7321.5 distance : 10336.1 TOTAL DISTANCE : 26374.3
PERMUTASI : 23 distance : 2720.2 distance : 4742.5 distance : 7321.5 distance : 15404.7 TOTAL DISTANCE : 30188.9

## KESIMPULAN DAN SARAN
Dengan metode permutasi serta pemanfaatan api mapbox  dapat  menghasilkan  data  perhitungan jarak seperti dibawah ini :
Jarak Terpendek : 26374.3
array(1)  {  [1]=>  array(4)  {  [0]=>  string(20)  "- 7.289148,112.745502" [1]=> string(20) "- 7.306827,112.793018" [2]=> string(20) "- 7.265537,112.748575" [3]=> string(20) "- 7.255276,112.734064" } } array(1)  {  [1]=>  array(4)  {  [0]=>  string(20) "112.745502,-7.289148" [1]=> string(20) "112.793018,-7.306827" [2]=> string(20) "112.748575,-7.265537" [3]=> string(20) "112.734064,-7.255276" } }
dari p0 ke p1 https://api.mapbox.com/directions/v5/mapbox/dr iving/112.745502,-7.289148;112.793018,- 7.306827.json?access_token=pk.eyJ1Ijoic3Vye W9hdG0iLCJhIjoiY2pjb2NwcmdqMDE0NzJ4b 2MwYXNxZjl4aiJ9.GslBgWjg1GJhkemepRGC BQ&steps=true&geometries=geojson distance : 7321.5 jumlah coodinate : 15 color : blue
dari p1 ke p2 https://api.mapbox.com/directions/v5/mapbox/dr iving/112.793018,-7.306827;112.748575,- 7.265537.json?access_token=pk.eyJ1Ijoic3Vye W9hdG0iLCJhIjoiY2pjb2NwcmdqMDE0NzJ4b 2MwYXNxZjl4aiJ9.GslBgWjg1GJhkemepRGC BQ&steps=true&geometries=geojson distance : 10336.1 jumlah coodinate : 22 color : red
dari p2 ke p3
https://api.mapbox.com/directions/v5/mapbox/dr iving/112.748575,-7.265537;112.734064,- 7.255276.json?access_token=pk.eyJ1Ijoic3Vye W9hdG0iLCJhIjoiY2pjb2NwcmdqMDE0NzJ4b 2MwYXNxZjl4aiJ9.GslBgWjg1GJhkemepRGC BQ&steps=true&geometries=geojson distance : 2594.7 jumlah coodinate : 22 color : green
dari p3 ke p4 https://api.mapbox.com/directions/v5/mapbox/dr iving/112.734064,-7.255276;112.745502,- 7.289148.json?access_token=pk.eyJ1Ijoic3Vye W9hdG0iLCJhIjoiY2pjb2NwcmdqMDE0NzJ4b 2MwYXNxZjl4aiJ9.GslBgWjg1GJhkemepRGC BQ&steps=true&geometries=geojson distance : 6122 jumlah coodinate : 26 color : yellow
dari  data  di  atas,  jarak  terpendek  yang  didapat adalah  26374.3.  Dari  hasil  contoh  yang dimodelkan  di  atas,  dapat  dilihat  bahwa  teori permutasi  dapat  menjadikan  tool  untuk  mencari solusi pada masalah pencarian rute terpendek
Saran  untuk  Penelitian  selanjutnya  adalah pengembangan  aplikasi  untuk  pemanfaatan UMKM  terkait  dengan  pencarian  rute  terpendek ketersediaan bahan baku pendukung UMKM.

## DAFTAR PUSTAKA
Apriliani, V., Nurdin, A., & Aryanti, A. (2018). PENENTUAN RUTE TERPENDEK PADA OPTIMALISASI JALUR PENDISTRIBUSIAN BARANG DI PT.X DENGAN MENERAPKAN ALGORITMA FLOYD-WARSHALL. Seminar Nasional Inovasi dan Aplikasi Teknologi di Industri. Malang: ITN. Kriswanto, Y. R., Bendi, R. K., & Aliyanto, A. (2014). Penentuan Jarak Terpendek Rute Transmusi dengan Algoritma Floyd- Warshall. SEMINAR NASIONAL TEKNOLOGI INFORMASI & KOMUNIKASI TERAPAN . Siswoyo, B., & Andrianto. (2009). STUDI KOMPARATIF ALGORITMA ANT DAN ALGORITMA GENETIK PADA TRAVELLING SALESMAN PROBLEM. Jurnal Computech & Bisnis, Vol. 3, No. 1, Juni 2009, , 30-36. Sitanggang, Y. C., Dewi, C., & Wihandika, R. C.
(2018). Pemilihan Rute Optimal Penjemputan Penumpang Travel Menggunakan Ant Colony Optimization pada Multiple Travelling Salesman Problem (M-TSP). Jurnal Pengembangan Teknologi Informasi dan Ilmu Komputer , 3138-3145.
Utami, P. Y., Suhery, C., & Ilhamsyah. (2014). APLIKASI PENCARIAN RUTE TERPENDEK MENGGUNAKAN ALGORITMA GENETIKA. Jurnal Coding Sistem Komputer Universitas Tanjungpura , 19 – 25.