JURNAL SAINS DAN SENI POMITS Vol. 2, No.1, (2013) 1-6
1
PENENTUAN RUTE OPTIMAL PADA KEGIATAN PENJEMPUTAN PENUMPANG TRAVEL MENGGUNAKAN ANT COLONY SYSTEM Laksana Samudra dan Imam Mukhlash Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Teknologi Sepuluh Nopember Jl. Arief Rahman Hakim, Surabaya 60111 E-mail:
[email protected]
Abstrak— Penentuan rute optimal merupakan suatu masalah yang sangat penting untuk dipecahkan karena berpengaruh terhadap waktu dan biaya operasional kendaraan. Penentuan rute optimal diperlukan untuk mendapatkan rute yang efisien. Pada Tugas Akhir ini bertujuan untuk mengimplementasikan algoritma Ant Colony System (ACS) dalam menyelesaikan salah satu Traveling Salesman Problem (TSP). Salah satu permasalahan dalam TSP adalah penentuan rute optimal pada kegiatan penjemputan penumpang travel di wilayah Kota Surabaya. Dengan objek yang dinamis menjadikan penelitian Tugas Tkhir ini berbeda dengan penelitian sebelumnya yang memiliki objek tetap. Perancangan ACS diintegrasikan dengan pendekatan Sistem Informasi Geografis (SIG) untuk memperoleh gambaran geografis sesungguhnya. Hasil ujicoba menunjukkan bahwa algoritma ACS dapat digunakan dalam permasalahan penjemputan penumpang travel di wilayah kota Surabaya. Sistem ini menghasilkan rute optimal, rincian perjalanan, dan jarak antar lokasi.
Kata Kunci--- Ant Colony System, Penjemputan Penumpang Travel, Sistem Informasi Geografis, Traveling Salesman Problem.
I. PENDAHULUAN
A
NGKUTAN antar-jemput penumpang atau travel sekarang semakin berkembang dengan pesat. Antusias para penumpang antarkota menggunakan jasa travel dapat dilihat dengan semakin banyaknya perusahaan-perusahaan travel yang mudah dijumpai, khususnya di Kota Surabaya. Kelebihan angkutan antar-jemput penumpang atau travel ini memiliki sistem layanan penjemputan dan pengantaran penumpang sampai ke tempat tujuan sesuai dengan trayek / jurusan yang dilayani (Door to Door Service). Dengan kelebihan yang dimiliki travel ini menjadikan jenis alat transportasi ini menjadi pilihan penumpang yang hendak melakukan perjalanan antarkota dibandingkan dengan jenis alat transportasi lainnya. Untuk menjaga kualitas layanan yang diberikan kepada penumpang, pengelola travel sebisa mungkin meminimalkan hambatan-hambatan yang ada, salah satunya adalah bagaimana menentukan rute penjemputan penumpang yang dimulai dari pangkalan travel dan menjemput satupersatu penumpang yang telah siap untuk dijemput. Untuk Kota Surabaya yang merupakan salah satu kota metropolitan banyak rute menuju tempat-tempat penumpang yang akan
dijemput. Dalam pelaksanaan kegiatan penjemputan penumpang, penentuan rute bergantung sepenuhnya pada pengetahuan supir terhadap lokasi-lokasi penumpang yang akan dijemput sehingga hal ini dirasa kurang optimal. Penentuan rute yang kurang optimal berdampak pada biaya operasional travel serta para penumpang yang akan dijemput menunggu terlalu lama dan sampai di tujuan tidak tepat waktu. Hal tersebut dapat menyebabkan kurangnya kualitas pelayanan yang diterima oleh penumpang. Untuk itu dibutuhkan metode yang dapat menyelesaikan permasalahan tersebut. Ant Colony System (ACS) merupakan salah satu metode untuk menentukan rute optimal. ACS pernah diteliti oleh Harmerita, 2010[1]. Dengan objek yang dinamis menjadikan penelitian tugas akhir ini berbeda dengan penelitian sebelumnya yang memiliki objek tetap. Pada tugas akhir ini penulis akan menggunakan algoritma Ant Colony System (ACS) untuk menyelesaikan masalah penentuan rute optimal pada kegiatan penjemputan penumpang yang dipandang sebagai salah satu permasalahan Travelling Salesman Problem (TSP). Mengingat prinsip algoritma yang didasarkan pada perilaku koloni semut dalam menemukan jarak perjalanan paling pendek tersebut, ACS sangat tepat digunakan untuk diterapkan dalam penyelesaian masalah optimasi, salah satunya adalah untuk menentukan rute optimal pada permasalahan TSP[8]. Sehingga jarak tempuh yang dibutuhkan untuk kegiatan penjemputan penumpang menjadi optimal. Hal tersebut sangat penting untuk diselesaikan agar dapat menjaga kualitas pelayanan angkutan antar-jemput (travel). Permasalahan yang akan dibahas pada tugas akhir ini adalah bagaimana mendapatkan rute penjemputan penumpang yang optimal di wilayah Kota Surabaya menggunakan Ant Colony System (ACS) serta tujuan dari penelitian tugas akhir ini adalah membuat aplikasi untuk mendapatkan rute optimal pada kegiatan penjemputan penumpang di wilayah Kota Surabaya menggunakan Ant Colony System (ACS). Adapun permasalahan dalam penelitian tugas akhir ini dibatasi oleh beberapa hal, yaitu Aplikasi ini menggunakan peta digital Kota Surabaya yang pernah di teliti oleh Sunarendro, 2006[2], lokasi penumpang hanya terbatas pada nama jalan, tidak dengan nomor, blok, RT /RW, nama perumahan maupun gang-gang kecil, dengan pertimbangan data koordinat lokasi yang disediakan pada peta terbatas pada nama
JURNAL SAINS DAN SENI POMITS Vol. 2, No.1, (2013) 1-6 jalan utama atau protocol, kendaraan maksimal menampung 8 penumpang. II. DASAR TEORI A. Sistem Informasi Geografis Dalam Sistem informasi geografis merupakan sebuah sistem berbasis komputer yang dapat digunakan untuk memetakan dan menganalisa berbagai hal dan kejadian alam yang terjadi di muka bumi. Yang membedakan sistem ini dengan sistem informasi lainnya adalah visualisasi dari peta digital. Dari peta tersebut dapat dilakukan operasi pada basis data yang telah terhubung dengan peta tersebut sehingga dapat dilakukan manajemen data dan menampilkan informasi geografis tertentu. Sistem informasi geografis dapat didefinisikan sebagai sebuah pengorganisasian antara hardware, software, data geografis, sumber daya manusia, serta metode yang didesain untuk secara efisien menyimpan, mengedit, memanipulasi serta menganlisa dan menampilkan segala bentuk informasi yang berhubungan dengan geografis.[3] B. Peta
Peta adalah gabungan dari beberapa bentuk seperti titik, garis, dan polygon/wilayah yang didefinisikan dari lokasinya dengan memakai acuan sistem koordinat maupun pada atribut non-spatialnya. Atribut non-spatial didefinisikan melalui warna-warna dan simbol-simbol yang disimpan dalam suatu tabel yang disebut Legenda Peta (Map Legend). Untuk menyusun bentuk dasar peta digunakan beberapa elemen data gambar, antara lain titik (point), garis (line), wilayah (area), simbol, pixel, sel grid. C. Graf Berarah Sampai sekarang baru banyak dibicarakan tentang graf dan dapat dilihat bagaimana graf itu dapat menggambarkan bermacam-macam situasi dengan berbagai objek (disajikan sebagai titik) yang berelasi satu sama lain dengan cara tertentu (interrelasi ini ditunjukkan sebagai sisinya). Secara khusus terlihat bagaimana graf dapat menyajikan peta jalan. Situasi ini memiliki satu hal penting, yaitu grafnya memberi tahu pada kita tentang titik mana yang dihubungkan. Tetapi graf itu tidak mengimplikasikan adanya titik yang lebih dominan dari titik lainnya. Objek semacam itu disebut graf berarah, yang biasanya dipendekkan sebutannya menjadi digraf (directed graf). Noktah-noktahnya disebut titik, dan ‘garis-garis berarahnya’ atau ‘panah-panahnya’ disebut busur. Seperti halnya dengan graf, terminologi (istilah) yang digunakan tidak sepenuhnya baku. Misal beberapa penulis mengartikan digraf sebagai graf dengan memberikan arah[5]. D. Travelling Salesman Problem (TSP) Masalah Travelling Salesman Problem (TSP) adalah salah satu contoh yang paling banyak dipelajari dalam combinatorial optimization. Masalah ini mudah untuk dinyatakan tetapi sangat sulit untuk diselesaikan. TSP termasuk kelas NP-Hard problem dan tidak dapat diselesaikan
2 secara optimal dalam polynomial computation time dengan algoritma eksak. Bila diselesaikan secara eksak waktu komputasi yang diperlukan akan meningkat secara eksponensial seiring bertambah besarnya masalah. TSP dapat dinyatakan sebagai permasalahan dalam mencari jarak minimal sebuah tour tertutup terhadap sejumlah n kota dimana kota-kota yang ada hanya dikunjungi sekali. TSP direpresentasikan dengan menggunakan sebuah graph lengkap dan berbobot G = (V, E) dengan V himpunan vertek yang merepresentasikan himpunan titik - titik, dan E adalah himpunan dari edge. Setiap edge (r,s) ∈ E adalah nilai (jarak) drs yang merupakan jarak dari kota r ke kota s, dengan (r,s) ∈ V. Dalam TSP simetrik (jarak dari kota r ke titik s sama dengan jarak dari titik s ke titik r), drs = dsr untuk semua edge (r,s) ∈ E. Misalkan terdapat n buah titik maka graph !
tersebut memiliki
(
)! !
buah edge, sesuai
rumus kombinasi, dan juga memiliki mungkin[6].
(
)!
dengan
buah tour yang
E. Ant colony system (ACS) Ant colony system (ACS) merupakan salah satu algoritma ant colony yang akan digunakan untuk menyelesaikan permasalahan pada penelitian ini. ACS merupakan pengembangan dari ACO dengan memiliki tingkat efisiensi yang lebih tinggi. Ada aspek mendasar yang membedakan ACS dengan ACO, yaitu[4]:
1. Aturan Transisi Status Aturan transisi status pada ACS diberikan untuk menyeimbangkan antara penjelajahan (eksplorasi) ruasruas yang baru dengan eksploitasi dari sebuah priori dan pengetahuan yang dihimpun mengenai masalah yang ada. Kemungkinan simpul s akan dipilih oleh semut k yang sedang berada pada simpul r dinyatakan dalam perhitungan matematika secara heuristik sebagai berikut: =
)
<
(
)
≥
(
)
.(
arg max ∈
dimana S didapat dari
=
∑
[ ∈
].[ [
] ].[
]
0
∈
∉
merupakan probabilitas dari semut k pada simpul r yang memilih untuk menuku ke simpul s. q adalah bilangan random adalah parameter perbandingan eksploitasi terhadap dan adalah jumlah pheromone pada sisi dari simpul eksplorasi. r ke simpul s. adalah invers panjang sisi dari simpul r ke adalah himpunan yang berisi simpul-simpul yang simpul s. telah dikunjungi oleh semut dan u adalah simpul yang berada dalam . adalah parameter perbandingan jumlah pheromone relatif terhadap jarak.
JURNAL SAINS DAN SENI POMITS Vol. 2, No.1, (2013) 1-6
3 2. Data Proses Berikut adalah data-data proses inisialisasi dan proses ACS Tabel 1 Data Proses
Nama Data
2. Aturan Pembaruan Pheromone Lokal Aturan pembaruan pheromone lokal digunakan saat semut membangun sebuah solusi. Jumlah pheromone akan berubah sesuai dengan aturan di bawah ini: = (1 − ). ∆
=
+ .∆
.
Matriks Jarak
Tipe Data double
Matriks Visibility
double
Data Jalur
array
Nearest Neighbor
array
Matriks Pheromone Awal
double
dimana adalah parameter pheromone lokal yang hilang dan ∆ adalah jumlah total pheromone pada sisi dari simpul r ke adalah panjang tour yang diperoleh dari inisialisasi awal s. menggunakan Nearest Neighbor dan c adalah jumlah lokasi.
3. Aturan Pembaruan Pheromone Global Aturan pembaruan pheromone global hanya dilakukan pada lintasan dengan tour terbaik. Jumlah pheromone akan berubah sesuai dengan aturan di bawah ini: = (1 − ). ∆
=
+ .∆ ( , ) ∈ 0
Dimana adalah parameter pheromone global yang hilang dan adalah panjang jalur terpendek pada akhir siklus. III. PERANCANGAN SISTEM A. Perancangan Data 1. Data Masukan Data masukan yang digunakan dalam perangkat lunak ini adalah berupa data spatial, data spatial berupa peta digital yang mempunyai tabel atribut. Berikut ini di jelaskan data masukan yang digunakan : a. Tabel Jalan Data ini berupa tabel atribut dari peta jalan. Tiap-tiap record dari atribut ini menyimpan informasi dari unit peta jalan tertentu yang bersesuaian pada peta. Pada proses pencarian rute terpendek suatu lokasi data field jalan digunakan untuk proses penterjemahan ke dalam bentuk graf sehingga dapat memberikan hasil. b. Tabel Lokasi Data ini berupa tabel atribut dari peta bangunan. Tiap-tiap record dari atribut ini menyimpan informasi dari unit peta bangunan tertentu yang bersesuaian pada peta. Pada proses pencarian rute terpendek suatu lokasi data field lokasi digunakan untuk acuan pencarian rute terpendek suatu lokasi dengan lokasi yang bersangkutan
Keterangan Data ini berupa matriks hasil pencarian panjang path semua node menggunakan algoritma dijkstra Data ini berupa matriks hasil invers dari masing-masing path pada Matriks Jarak Data ini berupa data jalur yang di peroleh dari proses pencarian antar node menggunakan algoritma dijkstra Data ini berupa nilai pencarian solusi rute terpendek dengan menghubungkan titik-titik terdekat Data ini berupa nilai invers dari Nearest Neighbor dikalikan dengan banyak lokasi yang dipilih
Data Luaran Data luaran yang dihasilkan dari proses pencarian rute terpendek beberapa lokasi berupa data jalan dengan cara pewarnaan yang digambarkan di peta, serta tampilan data urutan lokasi dan jalan yang dicari. . 3.
B. Gambaran Sistem Secara Umum Gambaran sistem secara umum proses pencarian rute optimal dalam bahasan ini adalah sebagai berikut. 1. Langkah pertama adalah pengambilan data beberapa lokasi dari peta digital untuk diterjemahkan ke dalam suatu graf. 2. Langkah kedua adalah apabila telah tercipta suatu graf maka dapat dilakukan proses pencarian rute terpendek semua lokasi yang dimaksud dengan menggunakan algoritma Dijkstra sebagai algoritma dasar yang telah diimplemantasikan oleh Sunarendro, 2006[2]. Setelah proses tersebut akan menghasilakan matriks jarak yang selanjutnya akan di proses dengan menggunakan algoritma Ant Colony System, sehingga nantinya dapat memecahkan permasalahan yang dalam penjemputan penumpang travel. 3. Langkah ketiga adalah dari hasil yang didapatkan dalam langkah kedua akan diterjemahkan kembali kedalam bentuk digital. Gambaran penentuan rute optimal pada kegiatan penjemputan penumpang travel menggunakan Ant Colony System ini dapat dilihat pada Gambar 1 berikut:
JURNAL SAINS DAN SENI POMITS Vol. 2, No.1, (2013) 1-6
4 Setelah mendapatkan lokasi yang akan dip roses yang dilakukan berikutnya adalah menentukan parameter ACS yang dapat dilihat pada gambar di bawah ini.
Gambar 3 Parameter ACS
Nilai-nilai parameter ACS antara lain, Alpha ( ) adalah parameter penguapan pheromon global (0< <1), Beta( ) adalah parameter perbandingan jumlah pheromon relatif adalah parameter perbandingan terhadap jarak ( > 0), antara eksplorasi dan eksploitasi (0 ≤ q ≤ 1), Ro ( ) adalah parameter pheromone lokal yang menguap ( 0 < < 1). B. Proses Inisialisasi Proses inisialisasi berisi penentuan nilai-nilai yang nantinya akan dip roses pada tahap ACS antara lain, penentuan nilai matriks jarak, matriks visibility, nearest neighbor,matriks pheromone awal. 1. Penentuan Matriks Jarak Dari data lokasi yang sudah ada akan di dapatkan matriks jarak dengan menghubungkan semua titik lokasi satu dengan yang lain menggunakan algoritma dijkstra dari penelitian sebelumnya. Matriks jarak yang dihasilkan dapat dilihat pada gambar 4 di bawah ini.
IV. HASIL DAN PENGUJIAN Perangkat yang digunakan dalam pengujian sistem terdiri dari beberapa perangkat keras dan perangkat lunak. Perangkat keras yang digunakan yaitu komputer dengan Prosesor Intel Core i3 / 2.4 GHz ( Dual-Core ), Memory 4 GB DDR3, dan Hard Disk 500 GB. Sedangkan perangkat lunak yang digunakan adalah Sistem Operasi Windows 7 Ultimate 32-bit SP1 dan perangkat lunak Visual Basic 6.0. A. Pengambilan data lokasi Data yang digunakan adalah data geografis yang telah dikerjakan oleh Sunarendro, 2006[2]. Pengujian pengambilan data lokasi bertujuan untuk menunjukkan bahwa sistem mampu membaca input yang dimasukkan oleh pengguna. Dapat dilihat pada gambar di bawah untuk contoh pengujian terdapat pangkalan yang terletak di Terminal T.O Wilangun dan empat lokasi penumpang yang akan diproses pada tahap inisialisasi.
Gambar 4 Matriks Jarak
Penentuan Matriks Visibility Matriks Visibility merupakan hasil invers dari matriks jarak yang telah didapat sebelumnya. Matriks Visibility yang dihasilkan dapat dilihat pada gambar 5 di bawah ini. 2.
Gambar 5 Matriks Visibility
Penentuan Nearest Neighbor Nearest Neighbor di dapat dari menghubungkan lokasilokasi terdekat pada matriks jarak yang nantinya akan menjadi solusi awal untuk membangun matriks pheromone awal. Penentuan Nearest Neighbor yang dihasilkan dapat dilihat pada gambar 6 di bawah ini. 3.
Gambar 2 Data Lokasi Penumpang
JURNAL SAINS DAN SENI POMITS Vol. 2, No.1, (2013) 1-6
5
Gambar 6 Nearest Neighbor
4. Penentuan Matriks Pheromone Awal Matriks pheromone awal di dapat dari invers hasil kali total jarak yang diperoleh Nearest Neighbor dikalikan dengan jumlah lokasi penumpang. Penentuan matriks pheromone awal yang dihasilkan dapat dilihat pada gambar 7 dibawah ini.
Gambar 9 Pheromone Update Global
Dapat dilihat pada gambar, Pheromone yang bernilai lebih besar dari yang lain merupakan solusi optimal dari proses ACS. 3. Data Hasil Data Hasil dapat dilihat pada gambar di bawah Gambar 7 Matriks Pheromone Awal
C. Proses ACS Setelah proses inisialisasi selesai dilakukan, tahap selanjutnya adalah proses ACS. Proses ACS dapat di lihat pada gambar 1. Hasil dari proses ACS sebagai berikut: 1. Data Tabulist Data tabulist merupakan data yang berisi urutan lokasi yang dikunjungi oleh semua semut di semua iterasi, data tabulist dapat dilihat pada gambar di bawah ini.
Gambar 10 Data Hasil
Dimulai dari pangkalan, pheromone yang bernilai besar dimiliki oleh penumpang 1, dari penumpang 1 yang memiliki pheromone yang bernilai besar adalah penumpang 3, dari penumpang 3 yang memiliki pheromone yang bernilai besar adalah penumpang 4, dan yang terakhir setelah penumpang 4 adalah penumpang 2. Jadi urutan optimal yang dihasilkan oleh algoritma ACS adalah Pangkalan-Penumpang1-Penumpang3Penumpang4-Penumpang2 dengan total jarak 28656,8 m. Hasil pewarnaan rute pada peta digital dapat dilihat pada gambar 11 dibawah ini.
Gambar 8 Data Tabulist
2. Pheromone Update Global Pheromone Update Global adalah pheromone yang telah di update secara global sebanyak iterasi yang telah di tentukan di awal. Hasil dari pheromone update global dapat di lihat pada gambar di bawah ini. Gambar 11 Rute Pada Peta Digital
JURNAL SAINS DAN SENI POMITS Vol. 2, No.1, (2013) 1-6 V. KESIMPULAN Berdasarkan analisis terhadap hasil pengujian sistem penentuan rute optimal pada kegiatan penjemputan penumpang menggunakan algoritma Ant Colony System , maka dapat diambil beberapa kesimpulan sebagai berikut: 1. Sistem ini telah berhasil menampilkan rute, rincian perjalanan, dan jarak dari beberapa lokasi penumpang yang telah di optimalkan menggunakan algoritma Ant Colony System. 2. Algoritma ACS mampu memperbaiki solusi awal yang didapat dari penentuan Nearest Neighbor dengan panjang rute 30418,59 m setelah proses ACS menjadi 28656,8 m dengan peningkatan efisiensi sebesar 5,79 % 3. Pada penentuan Nearest Neighbor menghasilkan rute atau jalur yang dapat digunakan sebagai jalur alternatif. DAFTAR PUSTAKA [1]
[2]
[3] [4]
[5]
[6]
Harmerita. 2010. “Penyelesaian Vehicle Routing Problem With Time Windows (VRPTW) Menggunakan Algoritma Ant Colony System” . Tugas Akhir S1 Jurusan Matematika ITS. Surabaya. Widodo, Sunarendro. 2006. “Pencarian Rute Terpendek Antar Lokasi Pada Peta Digital (SIG)”. Tugas Akhir S1 Jurusan Matematika ITS. Surabaya. Prahasta, Eddy. 2007. “Sistem Informasi Geografi ”. Bandung:informatika. Bandung. Dorigo, M., Gambardella, L. M. 1997. “Ant Colony System: A Cooperative Learning Approach to the Travelling Salesman Problem”, IEEE Transactions on Evolutionary Computation, Vol.1, No.1. Susilo, B., Efendi, R., Maulinda, S. 2011. “Implementasi Analisa Kinerja Algoritma Ant System (AS) dalam penyelesaian Multiple Travelling Salesman Problem (MTSP)”. Program Studi Teknik Informatika Universitas Bengkulu. Bengkulu. Leksono, Agus. 2009. “Algoritma Ant Colony Optimization (ACO) Untuk Menyelesaikan Travelling Salesman Problem (TSP)”. Tugas Akhir S1 Jurusan Matematika UNDIP. Semarang.
6
