Transportation Salesman Problem – Genetic Algorithm – Google Map API

146

Transportation Salesman Problem – Genetic Algorithm – Google Map API

Latar Belakang

Untuk dapat berkembang dan memenangkan persaingan, sebuah perusahaan harus didukung sistem informasi yang baik. Sistem informasi dapat didefinisikan secara teknis sebagai satu hubungan yang saling terkait antara komponen yang mengumpulkan, memproses, menyimpan, dan mendistribusikan informasi untuk mendukung pengambilan keputusan dan kontrol dalam suatu organisasi. [1]

Informasi adalah data yang telah diolah menjadi suatu bentuk yang bermakna dan berguna bagi manusia. Data, sebaliknya, adalah aliran mentah atau fakta yang mewakili peristiwa yang terjadi di organisasi atau lingkungan fisik sebelum mereka diolah dan diorganisasikan ke dalam bentuk yang dapat dimengerti dan gunakan oleh manusia. Tiga kegiatan dasar pada sistem informasi yaitu  ​​input, pemrosesan, dan output. [1]

Sistem informasi merupakan bagian integral dari organisasi. Unsur-unsur kunci dari suatu organisasi adalah orang-orangnya, struktur, proses bisnis, politik, dan budaya.  Menggunakan sistem informasi secara efektif membutuhkan pemahaman tentang organisasi, manajemen, dan teknologi informasi yang membentuk sistem. Suatu sistem informasi menciptakan nilai bagi perusahaan sebagai solusi organisasi dan manajemen untuk tantangan yang ditimbulkan oleh lingkungan. [1]

King Data Group Semarang adalah penjual besar atau distributor yang menjual kartu perdana Subscriber Identity Module (kartu SIM), voucer isi ulang pulsa telepon, dan kartu paket data (paket internet) di kota Semarang. Selain menjual secara retail atau ecer di gerai, King Data Group juga memberikan layanan business to business (B2B) berupa layanan pesan antar kepada gerai pulsa lain. Hal ini dilakukan untuk memenangkan persaingan terhadap distributor lainnya.

King Data Group telah memiliki sebuah website company profile. Website  ini sangat penting peranannya untuk memperkenalkan profil perusahaan, memperkenalkan produk, memberikan informasi harga produk, dan melakukan promosi penjualan. Pelanggan mencari informasi produk terbaru dan harga produk terbaru melalui website ini. Tetapi website belum mampu untuk menangani pemesanan secara online.

Pemesanan produk dilakukan melalui saluran telepon dan SMS (Sort Message Service). Kegiatan administrasi dilakukan dengan bantuan buku catatan dan aplikasi perkantoran (Microsoft Access dan Microsoft Word). Buku catatan yang ada diantaranya pembelian, catatan produk dan harga produk, catatan pesanan pelanggan, dan catatan pengiriman barang. Bekerja dengan banyak buku catatan memiliki resiko kekeliruan yang tinggi. Data stok barang juga tidak dapat diketahui secara up-to-date. Belum lagi kegiatan menghasilkan laporan bulanan. Dibutuhkan waktu satu sampai dua hari untuk menyusun laporan pembelian dan laporan penjualan bulanan. King Data Group membutuhkan sistem informasi pemesanan produk online yang terintegrasi website profil perusahaan, yang dapat juga digunakan untuk mengelola data  supplier, data pembelian, data pelanggan, data pesanan, dan data pengiriman barang.

Selain kebutuhan akan sistem informasi pemesanan online (toko online), terdapat permasalahan di proses pengiriman barang. Permasalahan timbul ketika karyawan harus menentukan rute perjalanan terbaik yaitu rute perjalanan terdekat sehingga hemat bahan bakar (hemat biaya) dan hemat waktu. Karyawan pengiriman tidak dapat bekerja optimal jika hanya memperoleh informasi berupa alamat tujuan. Karyawan pengiriman membutuhkan informasi berupa peta lokasi tujuan pengiriman dan saran rute perjalanan yang harus ditempuh.

Permasalah tentang rute perjalanan karyanan ini sering disebut dengan permasalahan perjalanan salesman atau travelling salesman problem (TSP). Deskripsi permasalahan travelling salesman problem adalah : “Seorang salesman harus mengunjungi N kota (atau titik) secara bergantian. Dalam sekali perjalanan dia hanya berkunjung sekali pada masing-masing kota, dan perjalanan berakhir dikota dimana dia mulai perjalanan. Bagaimana urutan/rute yang harus diambil untuk meminimalkan jarak tempuh?”

Terdapat beberapa metode mengelesaikan permasalah tersebut yaitu The shortest path algorithm, The simple Insertion Algorithms, Genetic Algorithm, The Elastic Net Methods, The Simulated Annealing Algorithm, dan Ant Algorithm. [2] Masing-masing algoritma tersebut memiliki kelebihan dan kekurangan. Algoritma genetika dinilai sebagai algoritma yang sangat efisien dan merupakan pendekatan optimasi yang akurat. Bahkan algoritma ini dikatakan masih yang terbaik menyangkut penyelesaian masalah combinatorial optimization. [3]

Algoritma genetika memiliki kelebihan yaitu waktu komputasi yang stabil, dan mampu memberikan jarak terpendek meski  dengan jumlah kota yang besar. Kekurangan algoritma genetika adalah sangat bergantung pada pemilihan parameter input, yaitu ukuran populasi, besar maksimum generasi, ukuran peluang crossover, dan ukuran peluang mutation. [3] Kekurangan yang lain adalah penggunaan memory yang boros dan algoritma ini cenderung berubah-ubah atau lebih bervariasi terhadap nilai yang berikan. Walaupun demikian, tingkat akurasi algoritma cukup tinggi sehingga terbukti bahwa algoritma ini dapat bekerja dengan baik dalam menemukan rute terpendek. [4]

Implementasi algoritma genetika dapat menggunakan library kode sumber terbuka (opensource) berbasis javascript. [4] Apabila dikombinasikan dengan google map Application Programming Interface (API) maka akan dapat menampilkan peta dan jalur/rute perjalanan dengan baik. Google map API sendiri adalah kode atau mekanisme yang diberikan oleh google agar programmer dapat memanfaatkan peta google dalam aplikasi berbasis web yang dikembangkannya.

Berdasarkan latar belakang diatas, penulis ingin melakukan penelitian dengan judul “Penerapan algoritma genetika dan google map API untuk mencari rute terpendek pengiriman barang di Sistem Informasi Pemesanan Barang King Data Group Semarang”. Dengan menghasilkan sistem informasi pemesanan barang online (toko online) diharapkan dapat mempermudah bagian administrasi mengelola data transaksi pemesanan barang, mengelola data pengiriman barang, dan menghasilkan laporan dengan cepat. Dengan ditambahkan fitur pencarian rute terbaik menggunakan algoritma genetika diharapkan membantu karyawan pengiriman untuk dapat mengirimkan barang lebih cepat dan lebih hemat.

 

Rumusan Masalah

Permasalahan penelitian yaitu :

  1. Bagaimana membuat sistem informasi pemesanan barang online (toko online) untuk King Data Group Semarang?
  2. Bagaimana menerapkan algoritma genetika dan google map API untuk menghasilkan peta rute pengiriman barang terpendek bagi karyawan King Data Group Semarang?

 

Batasan Masalah

Adapun batasan-batasan masalah dalam penelitian ini adalah sebagai berikut:

  1. Sistem informasi pemesanan barang online (toko online) ditujukan untuk menerima pesanan dari konter pulsa dalam layanan kerjasama (business to business).
  2. Fitur sistem informasi pemesanan barang online yang akan dibuat adalah kelola data karyawan, kelola data produk, kelola data supplier, kelola transaksi pembelian, kelola data gerai atau pelanggan, kelola transaksi penjualan, dan dapat menampilkan laporan transaksi pembelian, laporan transaksi penjualan, dan laporan stok barang.
  3. Algoritma yang digunakan untuk mencari rute terpendek adalah algoritma genetika.
  4. Pengembangan perangkat lunak menggunakan model proses prototyping. Bahasa pemodelan yang digunakan Unified Modeling Language (UML). Implementasi menggunakan bahasa pemrograman PHP dan basisdata MySQL.

 

Tujuan Penelitian

Tujuan dari penelitian ini adalah :

  1. Merancang dan menghasilkan suatu sistem pemesanan barang online (toko online) King Data Group Semarang.
  2. Mempelajari dan menerapkan algoritma genetika di sistem pemesanan barang online untuk mencari dan menampilkan rute terpendek pengiriman barang terbaik bagi karyawan pengiriman barang King Data Group Semarang.

 

FITUR APLIKASI

  • Sama dengan toko online pada umumnya yaitu pesan barang online, barang diantar. Pembayaran cash on delivery.
  • Terdapat fitur pencarian rute terbaik. Lokasi antar bisa dipilih,, rute akan diberikan.
  • Algoritma GA dilakukan di kode javascript. Langkah perhitungan dikeluarkan sebagai salah satu hasil selain peta dan rute jalan.

 

PRINTSCREEN

jalur terbaik terpendek hasil algoritma genetika
jalur terbaik terpendek hasil algoritma genetika
langkah algoritma genetika
langkah algoritma genetika
80%
Good
  • Design
  • Code
  • Kelengkapan
  • Design

Anda mungkin ingin membaca ini