PENCARIAN RUTE UNTUK ATSP (ASYMMETRIC TRAVELLING SALESMAN PROBLEM ) BERDASARKAN ALGORITMA A* DAN ANT COLONY BERBASIS GIS (GEOGRAPHIC INFORMATION SYSTEM) (ROUTE SEARCH FOR ATSP USED A* AND ANT COLONY ALGORITHM BASED ON GIS) Arita Witanti
[email protected]
Mochammad Zuliansyah,ST.MT
[email protected]
Dade Nurjannah,Ir.MT
[email protected]
Jurusan Teknik Informatika – Sekolah Tinggi Teknologi Telkom Jl. Telekomunikasi 1, Dayeuhkolot Bandung 40257 Indonesia
ABSTRAK Travelling Salesman Problem (TSP) adalah masalah menemukan sebuah jalur tertutup antar node yang mempunyai nilai minimal dimana setiap node dikunjungi cukup sekali. Asymmetric Travelling Salesman Problem (ATSP) adalah masalah TSP dimana ada biaya node A ke node B tidak sama dengan biaya nodeB ke nodeA Salah satu teknik solusi ATSP yang akan digunakan adalah kombinasi algoritma A* dan Algoritma Ant Colony System (ACS). Algoritma A* akan memvalidkan pencarian jalur tercepat antar dua node dan Algoritma ACS akan memanfaatkan outputan A* untuk melakukan pencarian jalur tercepat solusi ATSP. Representasi dari ATSP dan solusinya akan diimplementasikan dalam GIS. Dalam Tugas Akhir ini akan disimulasikan perangkat lunak yang dapat menjadi solusi pencarian rute dengan waktu tempuh tercepat bagi sales untuk akses ke beberapa node pelanggan dengan berbasis GIS. Implementasi menggunakan bahasa pemrograman VB 6.0, MapInfo 7.0,Mapbasic 6.5 dan MS.Access 2003 Kata Kunci : ATSP, A*,Ant Colony system, GIS
ABSTRACT Travelling Salesman Problem (TSP) is a is the problem of finding a minimal cost closed tour that visits each node once. Asymmetric Travelling Salesman Problem (ATSP) is TSP which there is the cost where node A to node B different with the cost from node B to node A. One of ATSP solution technique is the combination between A* algorithm and Ant Colony System(ACS) Algorithm. A* Algorithm for search quick route of two node and ACS Algorithm will use the output of A* for find best tour to ATSP solution. The representation of ATSP dan its solution will implement in GIS. On this final project, we will simulate the implementation that became the optimal route finding solution for sales to access customers based on GIS. The implementation will use programming language : VB 6.0, MapInfo 7.0, Map Basic 6.5 and MS Access 2003. Keywords : ATSP, A*,Ant Colony system, GIS
1.
Pendahuluan Pengaturan layanan perusahaan yang berhubungan dengan akses ke pelanggan dapat dibantu dengan penentuan rute dengan waktu tempuh tercepat ke pelanggan. Routing akan mencari jalur tercepat menuju lokasi serta menghindari node pelanggan dilewati lebih dari sekali. Masalah ini dapat direpresentasikan dengan ATSP Salah satu solusi untuk ATSP adalah pemanfaatan kombinasi algoritma A* dan Ant Colony System untuk mencari jalur dengan waktu tempuh tercepat. A* untuk pencarian jalur tercepat antara 2 node yang kemudian akan dijadikan input bagi ACS untuk menemukan jalur solusi ATSP nya. Untuk mendukung hal tersebut dalam Tugas Akhir ini dikembangkan suatu simulasi yang dapat menjadi solusi pencarian rute dengan waktu tempuh tercepat untuk ATSP dengan memanfaatkan kedua metode diatas. Adapun yang menjadi tujuan dalam Tugas Akhir ini adalah menganalisa kemampuan kombinasi
Algoritma A* dan Ant-Colony pada pencarian rute untuk ATSP dan membangun perangkat lunak simulasi yang dapat menjadi solusi pencarian rute dengan waktu tempuh tercepat bagi sales untuk akses ke beberapa node pelanggan berbasis GIS Tugas Akhir ini, dengan batasan masalah sebagai berikut: 1. Node tujuan dibatasi sejumlah 10 node. 2. Kurir mulai dan selesai pada node yang sama, dan tidak ada pengulangan kunjungan node. 3. Sistem berkonsentrasi pada aplikasi pencarian rute yang ATSP dan pengimplementasiannya dengan GIS 4. Kendaraan yang melewati jalur kurir dianggap satu tipe yaitu mobil box roda empat. 5. Analisa data jalan tidak memperhitungkan tanjakan dan turunan / kontur yang dilewati kendaraan. 6. Studi kasus yang diambil pada suatu area di wilayah Kodya Bandung.
1
7.
Data yang dipakai adalah data statistik dari Dinas Perhubungan kota Bandung dan SatLanTas PolWilTabes Bandung.
2.
Travelling Salesman Problem Traveling Salesman Problem (TSP) adalah suatu masalah yang dapat digambarkan sebagai berikut: seorang penjual/sales yang harus mengunjungi sejumlah kota tepat satu kali untuk setiap kota. Sales/penjual yang memberikan jasa ke pelanggannya untuk membuat perencanaan rute dan jadwal dari permintaan pelanggan yang dapat meminimimasi total biaya transportasi, serta memenuhi semua permintaan pelanggan dengan memperhatikan lokasi-lokasi masing permintaan dan waktu pengantaran. TSP adalah masalah untuk menentukan urutan dari sejumlah kota yang harus dilalui oleh seorang sales, setiap kota hanya boleh dilalui sekali dan hanya sekali dalam perjalanan, dan perjalanan berakhir pada kota awal dimana seorang sales memulai perjalananya dengan akumulasi jarak tempuh yang minimum dimana jarak antar kota telah diketahui, dan perjalanan penjual/sales tersebut dari kota asal hingga kembali lagi disebut dengan rute/lintasan. Dalam TSP ini diharapkan hasil pencarian memperoleh jalur dengan waktu tempuh yang tercepat. 2.1 Asymmetric Travelling Salesman Problem ATSP adalah seperti masalah TSP. Perbedaannya pada nilai jarak tempuh dari node A ke Node B belum tentu sama dengan jarak tempuh dari Node B ke Node A sehingga jika jarak tempuh dilambangkan dengan δ, maka δ(a,b) ≠ δ(b,a). Pada tugas akhir ini ketidak samaan jarak tempuh ini akan dipengaruhi oleh tingkat kemacetan yang sebanding dengan kecepatan kendaraan. 3. Teori Graph dan Pencarian Rute 3.1 Pengertian Sebuah graf G didefinisikan sebagai pasang himpunan (V,E) dalam hal ini : V adalah himpunan berhingga dan tidak kosong dari simpul-simpul (vertek atau node) = {v1,v2,…vn} E adalah himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul = {e1,e2,…en} Ditulis G = (V,E). 3.2
Shortest Path Penentuan rute terpendek merupakan salah satu permasalahan terbesar dalam teori graf. Pada dasarnya semua algoritma pencarian rute terpendek bertujuan sama, yaitu mencari lintasan/jalur yang mempunyai nilai akumulasi bobot-bobot busur terkecil antara 2 titik simpul. Masalah penentuan rute terpendek dapat dibagi menjadi beberapa tipe masalah yang berbeda, yaitu : 1. Lintasan terpendek antara 2 simpul tertentu 2. Lintasan terpendek antara semua pasangan simpul 3. Lintasan terpendek antara sebuah simpul tertentu ke semua simpul lainnya
4.
Lintasan terpendek antara simpul-simpul tertentu yang melewati simpul tertentu 5. Gabungan kedua, ketiga dan seterusnya Masalah traveling salesman termasuk kategori keempat, dimana terdapat batasan tambahan, yaitu semua simpul harus dikunjungi hanya sekali (tidak ada simpul yang dikunjungi lebih dari sekali). Batasan selanjutnya dalam masalah traveling salesman yaitu bahwa simpul awal sama dengan simpul akhir, artinya perjalanan kembali ke simpul awal (membentuk sirkuit Hamiltonian). 3.3
Algoritma A* Merupakan algoritma pencarian jarak terpendek (optimal) dari dua node menggunakan fungsi heuristik. Algoritma ini mempertimbangkan harga sesungguhnya ditambah harga perkiraan dengan persamaan f’(n) = g(n)+h’(n). Dimana f’(n) adalah jarak yang diharapkan dan menjadikannya komplete dan optimal, g(n) adalah jarak sebenarnya dan h (n) adalah nilai heuristik yatitu jarak garis lurus dari node n menuju node tujuan. Pada algoritma ini digunakan dua senarai yaitu Open dan Close. Algoritma A* adalah sebagai berikut : Priorityqueue Open List Closed Astarsearch s.g = 0 // s adalah node awal s.h = GoalDistEstimate (s) s.f = s.g + s.h s.parent = null push s on open while Open is not empty Pop node n from open // n dgn f terkecil If n is a goal node Contruct path, return success For each successor n’ of n Newg = n.g + cost (n,n’) If n’ is in Open or Closed, and n’.g <=newg Skip n’.parent = n n’.g = newg n’.h = goalDistEstimate (n’) n’.f = n,.g+n’h if n’ is in Closed remove it from closed if n’ is not yet in Open push n’ on Open push n onto Closed return failure // f oatg tudaj dutemukan Tugas Akhir ini menggunakan Algoritma A* sebagai pencari jarak antar 2 node sedangkan ACS digunakan untuk mencari rute ASTPnya. Output A* berupa shortest path akan dimanfaatkan ACS untuk mencari rute ATSP. 3.4
Ant System Sesuai dengan namanya, Ant colony system ini diinspirasikan berdasar penelitian terhadap koloni semut secara riil. Semut adalah social 2
insect, tinggal pada suatu koloni yang mempunyai perilaku survival terhadap koloninya. Suatu perilaku semut yang menarik adalah perilaku ketika mereka melakukan pencarian makan, khususnya bagaimana semut dapat menemukan jalur terpendek antara sumber makanan dan sarang mereka. Ketika berjalan dari sumber makanan ke sarang dan sebaliknya, semut meletakan suatu unsur disepanjang jalur yang disebut pheromone. Pheromone adalah suatu zat/hormon yang diproduksi oleh kelenjar endokrin yang memungkinkan korespondensi antar semut yang memberikan isyarat kimiawi, dan ketika disekresikan sebagai isyarat oleh seekor semut maka semut yang lain bisa mengenalinya.
- Suatu kali saat semut telah menyelesaikan jalur mereka, jumlah pheromone pada sisi akan diubah lagi (dengan menerapkan aturan update global). - Sebagai mana kasus dalam ant system, semut-semut dipandu, ketika membangun jalurnya, dengan kedua informasi heuristik (mereka lebih memilih sisi yang pendek), dan dengan informasi pheromone: Sebuah sisi dengan banyak pheromone adalah sebuah pilihan yang diharapkan. - Aturan update pheromone telah didesain sehingga semut-semut cenderung memberikan pheromone lebih pada sisi yang memang seharusnya dikunjungan oleh semut. Algoritma ACS dituliskan secara global sebagai berikut : Inisialisasi Loop /* pada level ini masing-masing pengulangan dipanggil sebagai iterasi*/ Masing-masing semut ditempatkan pada sebuah node awal Loop /* pada level ini masing-masing pengulangan disebut step step */ Masing-masing semut menerapkan sebuah aturan transisi state untuk membangun solusi secara bertahap dan sebuah aturan update pheromone secara lokal Until semua semut telah membangun sebuah solusi yang lengkap Sebuah aturan update pheromone secara global diterapkan Until Kondisi berhenti
Gambar 1. Bagaimana sebenarnya semut menemukan jalur . A) semut-semut dantan pada point persimpangan. B) Beberapa semut memilih jalur atas dan sebagian jalur bawah. Pilihan secara random. C) Selama semut bergerak kira-kira dengan kecepatan yang sama, semut-semut akan memilih jalur bawah, pendek, jalur menjangkau titik persimpangan yang berlawanan lebih cepat dari pada yang memilih jalur atas,panjang. D) Pheromone terakumulasi pada saat rata-rata tertinggi dari jalur terpendek. Jumlah garis bertanda kira-kira sebanding dengan jumlah pheromonde yang disimpan oleh semut. 3.5
Algoritma Ant Colony System ACS bekerja sebagai berikut : - m semut ditempatkan pada n kota dipilih berdasarkan beberapa aturan inisialisasi (contohnya secara random). - Masing-masing semut membangun sebuah jalur(sebagai contoh sebuah solusi TSP yang mungkin) dengan menerapkan secara berulang sebuah atuan stochastic greedy (aturan transisi state). - Selama pembangunan jalurnya, seekor semut juga merubah jumlah pheromone pada kunjungan ke sisi dengan menerapkan aturan local update.
3.5.1. Aturan Transisi State Seekor semut yang ditempatkan pada node i memilih node j untuk perpindahan dengan probability q0 – exploitation [2]
{
j = arg max j∈N k τ ij (t )ηijβ
}
2.1 Keterangan : q0 = sebuah parameter eksploitasi dimana (0 ≤ q0 ≤1) dan q eksplorasi j = node tujuan yang akan dipilih Nik = Himpunan node-node yang dikunjungi oleh semut k setelah dari node i = pheromone pada sisi i ke j τij(t) ηij = 1/ δ adalah kebalikan dari jarak δ(i,j) β = parameter penentu seberapa pentingnya pheromone dibanding jarak dimana ( β>0). Sedangkan aturan untuk perpindahan state antar node untuk membangun sub-solution dengan (1- q0): Exploration [2] sebagai berikut : i
⎧ [τ ij (t )]α [ηij ]β if j ∈allowedk ⎪⎪ α β pijk (t ) = ⎨ ∑[τ ik (t )] [ηik ] ⎪ k∈allowedk ⎪⎩0 otherwise
2.2
Keterangan : 3
pijk (t) τij(t) ηij τik(t) ηik α 0< α<1 β
= kemungkinan semut k pada node i memilih bergerak menuju kota j = pheromone pada sisi i ke j = 1/ δ adalah kebalikan dari jarak δ(i,j) = pheromone pada sisi i ke k = 1/ δ adalah kebalikan dari jarak δ(i,k) = parameter rusaknya pheromone dimana = parameter penentu seberapa pentingnya pheromone dibanding jarak dimana ( β>0).
3.5.2. Aturan Update Global Update global dilakukan setelah semua semut menyelesaikan jalur mereka Pada setiap akhir dari iterasi , solusi terbaik akan mendapatkan point extra berupa peng-update-an level pheromone pada jalur terbaik yang dilalui. Adapun aturan dari update global sebagai berikut [2]: 2.4 τ ( r , s ) ← (1 − α ) ⋅ τ ( r , s ) + α ⋅ ∆ τ ( r , s ) Global
where ∆ τ ( r , s ) Global
=
1 L best
Keterangan :
τ (r , s)
0< α<1 Lbest
= pheromone sisi r ke s = parameter rusaknya pheromone = panjang dari jalur global terbaik.
3.5.3. Aturan Update Local Jika sisi (r,s) dikunjungi oleh semut saat membangun sebuah solusi maka diterapkan aturan update local sebagai berikut [2] :
τ ( r , s ) ← (1 − ρ ) ⋅ τ ( r , s ) + ρ ⋅ ∆ τ ( r , s ) With
∆τ (r , s ) = τ 0 2.3
Keterangan :
τ (r , s) =
pheromone sisi r ke s 0< ρ<1 = sebuah parameter 4.
Geographic Information System GIS adalah suatu sistem berbasis komputer yang berguna dalam melakukan pemetaan (mapping) dan analisis berbagai hal dan peristiwa yang terjadi diatas permukaan bumi. GIS mempunyai 5 komponen yaitu : 1. Hardware 2. Software 3. People 4. Data 5. Method
Gambar 2 Komponen GIS Ada 5 proses essensial dalam GIS yaitu :
1. 2. 3. 4. 5.
Input Data Manipulasi Data Manajemen Data Query dan Analisa Visualisasi Dalam tugas akhir ini GIS sebagai platform implementasi sistem. 5.
Gambaran Sistem Secara umum sistem yang dibangun adalah suatu sistem yang berbasis informasi geografis yang dapat membantu pencarian rute dengan waktu tempuh tercepat dari kasus ATSP. Sistem akan mensimulasikan perjalanan seorang sales mengunjungi sejumlah node pelanggan. Nodenode yang dikunjungi sudah ditentukan diawal. Rute yang dimodelkan sebagai jalan kota bandung. Data jarak diketahui dari system, kepadatan tempuh kendaraan dari data statistik dinas perhubungan. Sales harus memulai dan mengkhiri perjalanan pada tempat yang sama. Pencarian rute memakai dua metode yaitu A* dan ACS. Fungsi Heuristik dari A* akan diambil dari kepadatan dan waktu tempuh. Untuk ACS parameter nya akan ditentukan diawal berdasarkan data dari referensi. Adapun alur proses yang terjadi adalah sebagai berikut : 1. Kenali Node Proses pengenalan node yang diinputkan oleh user untuk diposisikan pada peta. System akan memberikan posisi koordinat dari tiap node. 2. Temukan Sisi dari Node Temukan sisi yang menjadi himpunan semesta dari node untuk setiap node sehingga node berada pada range sisi yang memungkinkan. 3. Bangun Jalur ATSP a. Pembangunan Jalur ATSP digenerate menggunakan algoritma ACS. b. Bangun Jalur Untuk waktu tempuh tercepat Antar Node untuk jalur yang tidak punya sisi langsung dengan node utama, dibutuhkan A* untuk membangun jalur tersebut. Jalur tercepat hasilnya akan dijadikan jalur dasar bagi proses pencarian ATSP. 4. Tampilkan Jalur Solusi Dalam Peta Solusi jalur ATSP yang dihasilkan akan ditampilkan dalam peta . Dari sini juga akan terlihat urutan kunjungan node dan waktu yang dibutuhkan untuk membangun jalur tersebut 6.
Analisa Kebutuhan Spesifikasi kebutuhan merupakan deskripsi dari apa yang dibutuhkan oleh sistem yang akan dibangun. Telah disebutkan sebelumnya bahwa tujuan dari Tugas Akhir ini adalah tujuan dalam Tugas Akhir ini adalah menganalisa kemampuan Algoritma A* dan Ant-Colony pada pencarian rute untuk ATSP dan membangun perangkat lunak yang dapat menjadi solusi pencarian rute nya. Adapun hal-hal yang harus dicapai adalah: • Solusi ATSP dengan tercapainya rute dengan waktu tempuh tercepat yang diharapkan serta 4
• •
mengetahui node-node mana saja yang harus dilewati. Solusi diimplementasikan dalam GIS dalam bentuk peta rute. Analisa kemampuan penerapan kombinasi metode A* dan ACS dengan melakukan perbandingan dengan metode lain.
6.1
Inputan Sistem Sistem penentuan rute ini memerlukan ini masukan dari user berupa : • Node awal yang sekaligus sebagai node akhir • Node antara yang harus dilalui oleh sales 6.2
Pencarian Jalur Antara Dua Node Pencarian jalur antar dua node menggunakan metode A*. Fungsi A* disini untuk memvalidkan pemilihan jalur. Apabila diketahui : • G ( V, E) adalah graf berarah berbobot dengan bobot non-negatif • j ∈ V adalah node awal dan k ∈ V adalah node tujuan • l ( j, k) adalah panjang jarak sisi (j,k) ∈ E • S(k) adalah jarak sesungguhnya dari sumber menuju k • S’(k) adalah jarak perkiraan (heuristik) dari sumber menuju k • V(k)min adalah kecepatan minimum kendaraan dari sumber menuju k • Vmax adalah kecepatan maksimum kendaraan Untuk mencari jalur tercepat kita perlu mendefinisikan waktu tempuh (T(k))sesungguhnya dari sumber ke tujuan k antara satu node dengan node lainnya dengan rumus : S (k ) 3.1 T (k ) = V (k )
min
Sedangkan untuk nilai lainnya akan diperoleh dari data dan inputan user system. Semua nilai yang berhubungan dengan jarak dikonversi menjadi waktu tempuh dengan persamaan 3.1 atau 3.2 6.4
Spesifikasi Perangkat Lunak dan Perangkat Keras Berikut merupakan spesifikasi daftar perangkat lunak yang akan digunakan dalam pembangunan sistem ini: • Visual Basic 6.0 • Sistem Operasi: Microsoft Windows XP • DBMS MS Access 2003 • MapInfo 7 dan MapBasic 6.5 Sedangkan spesifikasi perangkat keras yang akan digunakan dalam pengujian adalah: • Prosesor: AMD Athlon XP 2000+ • Memori: 256 MB • Harddisk: 20 GB • Display Super VGA 64 MB. 7.
Perancangan
7.1
Use Case Diagram Berdasarkan kebutuhan yang telah disebutkan di atas, maka dapat digambarkan use case diagram yang menjelaskan hubungan antara kasus dengan aktor sebagai berikut: <
> Cari Rute ATSP
User system
Bangun Jalur antar Node
Kemudian waktu tempuh perkiraan untuk membangun fungsi heuristiknya ((T’(k)) diperoleh dari T ' (k ) =
S ' (k ) Vmax
3.2
Sehingga apabila persamaan heuristik adalah f’(n) = g(n)+h’(n) , maka diperoleh fungsi heuristik jalur tercepat. f’(k) = T(k) + T’(k) 6.3
<>
Pembangunan Rute ATSP Pembangunan rute ini menggunakan algoritma ACS. ACS sendiri memerlukan parameter awal. Pengesetan nilai parameter diperoleh berdasarkan daftar pustaka. Adapun parameter tersebut adalah : • τ = pheromone awal pada tiap sisi saat t= 0 • β = parameter penentu seberapa pentingnya pheromone dibanding waktu dimana ( β>0) • α = parameter rusaknya pheromone dimana 0< α<1 • ρ = sebuah parameter yang mengontrol bobot intersitas η dimana 0< ρ<1 • Jumlah iterasi semut • Jumlah semut
Menentukan node
Gambar 3 Use Case Diagram 7.2 System Sequence Diagram Diagram berikut menggambarkan interaksi yang terjadi antar objek.Berikut adalah system sequence diagram untuk masing-masing use case
: User system
: Node
: Peta
doMakeNode() GetPosisi
PlotFromNearEdge( )
Gambar 4. Sequence Diagram penentuan Node
5
Ant : Node
Jalan : Peta
: OpenNode
: closeNode
Pheromone : Single Status : Boolean
: Jalur
: User system
LocalUpdatePheromone() : Boolean TransitionState() GlobalUpdatePheromone() PlacedAnt() GetShortestPath()
GetTime EstimateCoverage()
1..*
Jalur
GetWaktuTempuhAsli()
Panjang : Single Pheromone : Single waktutempuh kepadatan : single
1..*
GetWaktuTempuhHeuristik()
Node Longitute : Single Latitute : Float SuccNode() PredNode() PlotFromNearEdge() GetPosisi()
MakeJalur() OpenNode
ConstrucPath() GetBestNode
2..*
1..*
1
EstimateCoverage() GetTime() GetWaktuTempuhAsli() GetWaktuTempuhHeuristik() MakeJalur() ConstrucPath() GetBestNode() GetShortestPath()
Rute panjang : single waktutempuh : single
1..*
1
SaveRoute() MakeRoute() SetParameter() GetShortestRoute()
1..*
ClosedNode GetShortestPath
closeNode
OpenNode
1
: Rute
: Ant
1
PlotFromNearEdge() FirstPheromone() ShowSolution() doMakeNode()
Gambar 5 Sequnce Diagram Bangun Jalur Node
: Jalur
<
