## PERANCANGAN GEOGRAPHIC INFORMATION SYSTEM UNTUK TRACKING DAN ROUTING MENGGUNAKAN ALGORITMA DIJKSTRA PADA KENDARAAN ANGKUTAN UMUM
Muh. Aristo Imdrajaya
Fakultas Teknik, Jurusan Teknik Elektro, Universitas Tadulako Email : aristo@untad.ac.id

## Abstract
The ability to do tracking  and routing of  a  motorized  vehicle  is  very  useful  in everyday  life,  such  as  security  on  private vehicles,  public  transportation  systems,  mass transportation  fleet  management  and  others. In  this  study,  we  designed  a  Geographic Information  System  (GIS)  application  that will  be  applied  to  public  transport  services. This system will in real time track the position of  each  vehicle  (taxi)  and  be  able  to  perform automatic service for every taxi request by the customer.
Dijkstra's  algorithm  is  a  graph  search algorithm  that  solves  the  shortest  path problem  that  originates  from  one  node  for  a graph  where  the  weight  of  the  node  must  not be negative. The analysis is done by examining the  node  with  the  smallest  weight  and inserting  it  into  the  set  of  solutions  with  the initial  search  for  the  origin  node  requiring knowledge of all paths and weights. Dijkstra's algorithm  which  is  applied  to  this  system  will function  to  find  the  most  suitable  taxi  for customers  by  using  distance  parameters  and traffic density levels as the weight value.
Keywords:  GPS,  GIS,  GSM,  Dijkstra,  TCP  / IP

## I. Pendahuluan
Pertumbuhan  jumlah  kendaraan  secara global  diperkirakan  akan  semakin  meningkat seiring  dengan  pertumbuhan  ekonomi  serta jumlah  masyarakat  kelas  menengah  yang semakin  meningkat,  seperti  di  Cina  dan  India. Meskipun  pertumbuhan  jumlah  kendaraan  selain memberi dampak positif yaitu semakin bertambahnya  jumlah  penduduk  kelas  menengah keatas,    akan  tetapi  pengembangan  sistem pelacakan ( tracking ) dan perutean (routing) suatu kendaraan  yang  juga  merupakan  bagian  yang sangat  penting  pada  sebuah  sistem  transportasi masih  sangat  kurang.  Penggunaan  sistem
tracking dan routing pada  mode  transportasi akan  sangat  bermanfaat  untuk  berbagai  macam aspek  termasuk  aspek  keamanan  maupun ekonomi pada kendaraan pribadi, sistem transportasi  masal,  kendaraan  niaga  dan  lain sebagainya.  Untuk  angkutan  penumpang  dan barang,  sistem tracking dan routing ini  dapat digunakan untuk melakukan menejemen terhadap  armada  angkutan  khususnya  untuk pengaturan  terhadap  rute  yang  akan  dilalui sehingga  akan  meningkatkan  efisiensi  terhadap waktu  tempuh  dan  pemakaian  bahan  bakar  yang harganya terus mengalami lonjakan.
Di sisi lain, sistem navigasi GPS ( Global Positioning  System )  telah  diadopsi  secara  luas sebagai  sistem  navigasi  kendaraan  saat  ini  dan harganya kian terjangkau. Perangkat ini digunakan  oleh  pengemudi  untuk  membantu menemukan  tujuan  mereka  melalui  instruksi  – instruksi.  Sistem  GPS  ini  juga  akan  dapat digunakan  untuk  melakukan tracking terhadap posisi  suatu  kendaraan  berdasarkan  pembacaan koordinatnya  dan  dengan  menganalisa  data  dari GPS,  kecepatan  sebuah  kendaraan  juga  dapat diketahui  dengan  pasti.  Dengan  membangun aplikasi  GIS  ( Geographic  Information  System ) berbasis web ,  maka  posisi  dan  kecepatan  suatu kendaraan  dapat  diketahui  melalui  perangkat mobile yang terhubung ke internet.
Tujuan utama dari penelitian kami adalah membangun sebuah sistem yang mampu melacak posisi suatu kendaraan secara otomatis ( automatic  vehicle  location  tracking  system ) yang dapat menunjang kinerja angkutan penumpang  khususnya  armada  taksi.  Pada umumnya penyedia layanan taksi masih menggunakan metode manual dengan mengandalkan pemancar radio untuk memberikan  informasi  mengenai  pemesanan taksi  kepada  pengendara  yang  dilakukan  oleh seorang  operator.  Hal  ini  menyebabkan  belum adanya  konfirmasi  taksi  mana  yang  akan melayani pemesanan taksi nantinya serta memperpanjang  waktu  pelayanan  utamanya  di jam-jam  sibuk.  Pencarian  taksi  terdekat  untuk
pemesan  taksi  terdekat  juga  tidak  bisa  dilakukan tanpa  mengetahui  lokasi  pemesan  taksi  secara otomatis.
Dengan  menggunakan  sistem  ini,  selain posisi setiap taksi akan terpantau melalui sebuah aplikasi  GIS  ( Geographic  Information  System ) berbasis web , sistem ini akan mampu  melakukan pemilihan  taksi  yang  paling  layak  diberikan kepada  pelanggan  berdasarkan  data  posisi kendaraan  dan  tingkat  pendapatan  dari  tiap pengendara  taksi  sehingga  akan  memberikan keuntungan  bukan  hanya  bagi  calon  penumpan saja  tapi  juga  bagi  pengendara  itu  sendiri  yang akan  berdampak  pada  pemerataan  pendapatan bagi tiap – tiap pengendara taksi.

## II. Metode Penelitian
Penelitian  yang  dilakukan  memiliki tahapan berikut :

## a. Perancanaan sistem secara umum
Pada  tahapan  ini  dilakukan  perencanaan mengenai  komponen  apa  saja  yang diperlukan  dalam  pembuatan  sistem  ini seperti tipe perangkat GPS receiver serta sistem operasi yang akan digunakan pada unit server .  Selain  itu  diperhitungkan pula  mengenai  parameter  apa  saja  yang menentukan  kinerja  dari  sistem  yang akan  dibangun.  Desain  dari  sistem  yang dibangun dapat dilihat pada Gambar 3.2.

## b. Instalasi web server dan database server
Pada  tahapan  ini  dilakukan  proses instalasi  terhadap  server  yang  akan berfungsi  menampilkan  aplikasi  peta berbasis  web  serta  menyiapkan  server yang  berfungsi  sebagai  database  bagi sistem  yang  dirancang.  Aplikasi  yang akan  dipasang  pada  server  adalah Apache  untuk  menjalankan  aplikasi  http dan  MySql  untuk  menjalankan  aplikasi database . Server yang  akan  digunakan akan  memiliki ip  public sehingga  dapat diakses secara online .
c. Pembuatan  aplikasi  monitoring  pada pada perangkat GPS Pada  tahap  ini,  dibangun  aplikasi  yang mampu melakukan data acuisition terhadap  data  posisi  dan  kecepatan  dari tiap  –  tiap  kendaraan.  Selain  itu  aplikasi
ini  akan  mampu  mengirimkan  data  yang telah didapatkan menuju server menggunakan melalui jaringan GSM dan data  akan  dikirimkan  menuju server dalam  bentuk  TCP packet .  Aplikasi  ini akan  di install pada  perangkat  GPS berupa smartphone dengan sistem operasi  Android  dengan  menggunakan bahasa  pemrograman  Java.  Sebuah smartphone yang  telah  mengaplikasikan sistem  GPS  akan  mampu  melacak  posisi dengan  baik  dan  dapat  diterapkan sebagai  perangkat tracking pada  sistem transportasi umum [10].
d. Pembuatan aplikasi GIS berbasis web.
Pada  tahapan  ini  dibangun  sebuah aplikasi  GIS  ( Geographic  Information System )  yang  berfungsi  menampilkan secara  mendetail  setiap  posisi  dan kecepatan  dari  kendaraan  yang  dipantau melalui  layanan  berbasis web serta memberikan  akses  bagi  calon  pelanggan yang  ingin  melakukan  pemesanan  taksi. Aplikasi  ini  akan  dijalankan  pada  unit server yang  telah  memiliki ip  public sehingga  dapat  diakses  dimana  saja dengan  menggunakan  perangkat mobile . Seorang pelanggan yang akan melakukan pemesanan  angkutan  atau  taksi  dapat mengakses  sistem  ini  secara online . Ketika  pelanggan  telah  memasukkan posisinya saat ini, maka aplikasi ini akan langsung  mencari  taksi  dengan  posisi terdekat  dari  penumpang  menggunakan Algoritma Dijkstra.

## e. Pengujian Sistem
Setelah  sistem  selesai  dibangun,  tahap selanjutnya  adalah  dengan  melakukan pengujian dari sistem yang dibangun ini. Pengujian ini dilakukan untuk mengetahui  keakuratan  dari  kecepatan dan  posisi  kendaraan  yang  berhasil dilacak,  besarnya delay yang  terjadi ketika  pengiriman  data  dilakukan  dari kendaraan  menuju  ke  server  serta mengetahui  waktu  yang  diperlukan  oleh sistem untuk melakukan reponse terhadap setiap permintaan oleh pelanggan.

## III. Hasil dan Pembahasan.
Gambar 1 . Aplikasi GIS yang dibangun.
Interface dari sistem yang telah dibangun dapat  diakses  melalui  layanan  berbasis web . Ketika sistem telah diakses dan penumpang telah setuju  dengan  transaksi  yang  telah  dilakukan maka  sistem  akan  melakukan  pencarian  dengan posisi  paling  dekat  dari  pelanggan  seperti  yang dapat dilihat pada  Gambar 1.
Sistem  akan  mengirimkan  notifikasi berupa alamat dari pelanggan kepada pengemudi taksi  melalui  layanan  berbasis  push  e-mail seperti  yang  dapat  dilihat  pada  Gambar  4.2. Melalui  layanan  ini  pengemudi  taksi  dapat memilih untuk menerima atau menolak pemesanan.  Jika  pengemudi  menolak,  maka sistem  dapat  melakukan  pencarian  kembali  taksi terdekat. Setiap tanggapan yang
dilakukan  oleh  pengemudi  taksi  baik menerima  atau  menolak  order,  pelanggan  akan menerima tanggapan dari sistem  melalui layanan SMS ( Shor Message Service ).
Proses  yang  berjalan  pada  sistem  yang dibangun  ini  dapat  dipahami  dengan  mengikuti skenario  pengujian  berikut.  Pengujian  dilakukan dengan  melibatkan  tujuh  orang  yang  terdiri  dari enam  orang  yang  bertindak  sebagai  pengendara taksi  dan  satu  sebagai  pelanggan.  Posisi  dari pengendara disebar ke berbagai sudut kota untuk menyesuaikan  dengan  kondisi  yang  terjadi sehari-hari.
Data posisi terbaru dari penumpang dan pengendara  taksi  yang  berupa  data latitude dan longitude disimpan  di  dalam  database  pada server  yang  digunakan.  Di  dalam  database  akan ditampung  posisi  seluruh  taksi,  jarak  antara  tiap taksi  satu  sama  lain  dan  jarak  antara  tiap  taksi dengan pelanggan yang melakukan transaksi.

## IV. Kesimpulan
1. Algoritma Dijkstra yang diterapkan pada sistem yang dibangun mampu melakukan pencarian node atau taksi dengan kriteria terbaik  dengan  waktu  rata-rata  0,3911 detik. 2. Jumlah  node  atau  taksi  yang  ada  akan mempengaruhi  seberapa  cepat  sistem yang dibangun mampu melakukan pencarian  node  atau  taksi  yang  paling tepat bagi pelanggan. 3. Penambahan parameter tingkat kepadatan  selain  parameter  jarak  yang telah digunakan sebelumnya serta penggunaan  Algoritma  MDSP  yang merupakan  modifikasi  dari  Algoritma Dijkstra  pada  sistem  yang  dibangun mampu  memberikan  hasil  yang  lebih valid dalam pencarian node taksi.

## V. Daftar Pustaka
1. Almomani, I.M., et al . (2011), “Ubiquituous GPS  Vehicle  Tracking  and  Management System”, IEEE Jordan  Conferences  on
Applied Electrical Engineering and
Computing Technologies (AEECT) .
2. Aloquili,  O.,  Elbanna,  A.,  Al-Azizi,  A. (2009),  “Automatic  Vehicle  Location
Tracking System Based on GIS Environment”,
The Institution of
Engineering and Technology , Vol. 3, No. 4, hal. 255-263.
3. Cho  H.J.,  &  Cho  M.,  (2013),  “Effective Position  Tracking  Using  B-Spline  Surface Equation Based on Wireless Sensor Networks  and  Passive                    UHF-RFID”, IEEE  Transactions  on  Instrumentation  and Measurement , Vol. 62, No. 9.
4. Dat,  H.  P.,  Drieberg,  M.,  Cuong,  C.N. (2013),  “Development  of  Vehicle  Tracking System  using  GPS  and  GSM  Modem”. IEEE  Conference on Open Systems ,
Sarawak.
5. Davis,  S.  (2007), GIS  for  Web  Developers , The Pragmatic Programmers.
6. Gintoro, Iwan Wijaya Suharto, et al . (2010), “Analisis dan Perancangan Sistem Pencarian Taksi Terdekat Dengan Pelanggan  Menggunakan  Layanan  Berbasis Lokasi”. Seminar Nasional Aplikasi
Teknologi Informasi , Yogyakarta.
7. Jerath K., & Brennan, N. (2012), “GPS Free Train-Based  Vehicle  Tracking  on  Road Networks”, American  Control  Confrence ,
Faimont Queen Elizabeth, Montreal.
8. Johnson,  M.C.,  &  Thomas,  L.E.  (2000), Automatic  Vehicle  Location  Successful Transit  Aplications ,  U.S.  Department  of Transportations, Washington, DC.
9. Joyner, D., Nguyen V.H., Cohen, N. (2011), Algorithmic Graph Theory .
10. Lammle,  T.,  (2007), Cisco  Certified Network  Associate  Study  Guide ,          Wiley Publishing, Inc., Indianapolis.
11. Lee,  S.,  Tewolde,  G.,  Kwon,  J.,  (2014), “Design  and  Implementation  of  Vehicle Tracking  System  Using  GPS/GSM/GPRS Technology  and  Smartphone  Application”,
IEEE World Forum on Internet of Things . 12. McWilliam, N., et al . (2005), GIS, GPS and Remote  Sensing ,  The  Expedition  Advisory Centre  Royal  Geographical  Society  1 Kensington Gore, London.
13. Menard,  T., et  al .  (2011),  “Comparing  The
GPS Capabilities of The Samsung Galaxy S, Motorola  Droid  X,  and  The  Apple  iPhone
for Vehicle Tracking Using Freesim_Mobile”, International IEEE Conference  on  Intelligent  Transportation System ,   Washington, DC.
14. Menard, T., & Miller, J., (2011), “Comparing  The  GPS  Capabilities  of  The iPhone  4  and  iPhone  3G  for  Vehicle Tracking  Using  FreeSim_Mobile”, IEEE Iintelligent  Vehicles  Symposium ,  Baden- Baden.
15. Odom,  W.,  (2007), CCENT/CCNA  ICND1 Official  Exam  Certification  Guide ,  Cisco Press, Indianapolis.
16. Sathiamoorthy,  M.  (2009),  “On  GPS Tracking  of  Mobile  Devices”, International Conference on Networking and Services ”.
17. Sivakumar,  S.,  &  C.  Chandrasekar.  (2014), Modified
Dijkstra’s Shortest Path Algorithm”, International Journal of
Innovative  Research  in  Computer  and Communication Engineering , Vol. 2.
18. Yi  Z.,  Ding  W.,  Yanfei  Y.  (2009),  “On Dynamic  Scheduling  of  Vehicles  Based  on GPS  /  GIS  /  RFID”, Department  of Computer Science & Technology , Harbin.
19. Yuan  G., et  al .  (2008),  “Research  and Design  of  GIS  in  Vehicle  Monitoring System”, Internation Conference of Internet Computing in Science and Engineering .