Perbandingan Pencarian Rute Optimal Pada Sistem Navigasi Lalu Lintas Kota Semarang Dengan Menggunakan Algoritma A* Dan Algoritma Djikstra

Perbandingan Pencarian Rute Optimal Pada Sistem Navigasi Lalu Lintas Kota Semarang Dengan Menggunakan Algoritma A* Dan Algoritma Djikstra Ibnu Utomo WM Ana Setyaningsih

Abstract : This research is to build an application system that provides information on alternative optimal routes on the streets of Semarang city. This study consists of five processes, namely gambar peta, data segmen, pembobotan, simpan rute, tampilan rute. First the user determines the location of the beginning and end and then inserted into the process of drawing the map then locate the intersection of the road. After obtaining the intersection of Algorithm A * (actual weight + weight heuristic), Algorithm Djiksta (actual weight). Weights are determined and then the system looking for the smallest segment with weights that generate a route. After that the route is saved and the system then displays the optimum route Keywords : Algoritma A*, Algoritma Djikstra, Rute Optimal, GIS.

PENDAHULUAN Berkembangnya industri dan usaha menuntut adanya pelayanan transportasi yang lebih optimal. Jasa pengantar barang atau sales yang harus mengunjungi calon client-nya harus pula diatur sedemikian rupa. Hal ini perlu karena menyangkut penggunaan resource perusahaan seperti akomodasi maupun kualitas layanan seperti ketepatan waktu layanan, sehingga pada akhirnya dapat memberikan profit bagi perusahaan. Berkembangnya industri maupun usaha-usaha yang lainnya maka secara tidak langsung berkembang pula transportasi khususnya di kota Semarang. Dampak dari berkembangnya transportasi dapat menimbulkan kemacetan lalu lintas, tingginya tingkat kemacetan lalu lintas menyebabkan pergerakan kendaraan tidak terencana dan dapat menurunkan produktivitas, bahan bakar yang terbuang percuma, serta peningkatan polusi beserta dampak-dampaknya. Oleh karena itu diperlukan solusi yang dapat membantu pengemudi untuk pengaturan penentuan rute optimal ketujuan. Routing akan mencari jalur tercepat menuju lokasi yang akan dituju. Oleh karena itu dibutuhkan sebuah sistem yang dapat mendukung layanan routing. Kiranya GIS (Geographic Information System) sebagai sistem yang menganalisa seluruh peristiwa dipermukaan bumi bisa menjadi alternatif

Ibnu Utomo WM adalah Dosen Fakultas Ilmu Komputer UDINUS Semarang 53

Techno.Com, Vol. 9 No. 2, Mei 2010

54

solusi visualisasi routing. Routing dioptimalkan dengan Algoritma A* untuk penentuan jalur tercepat antar dua node dan akan dibandingkan dengan Algoritma Djikstra sebagai jalur terpendek.

PEMBAHASAN Secara umum sistem yang dibangun adalah suatu sistem yang berbasis informasi geografis yang dapat membantu pencarian rute optimal dengan waktu tempuh tercepat dari kasus pencarian Algoritma A*. Lokasi Awal Lokasi Akhir

Gambar Peta

Pencarian Perempatan

Data Segmen

Segmen Jalan Yang Terpilih

Pembobotan

Segmen dengan Bobot Terkecil User

Rute Optimal

Tampilan Rute

Rute Jadi

Simpan Rute

Gambar 1: Perancangan Global Perancangan Gambar 1, secara global dapat dijelaskan bahwa perancangan terdiri dari satu user dan lima proses, yaitu gambar peta, data segmen, pembobotan, simpan rute, tampilan rute. Pertama user menentukan lokasi awal dan akhir kemudian dimasukkan kedalam proses yaitu peta gambar, kemudian dicari perempatan jalan. Setelah mendapatkan perempatan tentukan data segmen, segmen yang terpilih diproses kedalam pembobotan jalan yang terdiri dari Algoritma A* (bobot actual + bobot heuristik), Algoritma Djikstra (bobot actual). Pembobotan ditentukan kemudian cari segmen dengan bobot terkecil lalu simpan rute dalam proses. Setelah rute disimpan kemudian ditampilkan rute optimal. Context Diagram Lokasi Awal Lokasi Akhir

Mencari Rute Optimal

User

Rute Optimal

Gambar 2: Context Diagram

Perbandingan Pencarian Rute Optimal (Utomo)

55

Context diagram gambar 2, secara global dapat dijelaskan bahwa context diagram terdiri dari satu user dan satu proses, dengan dua input yaitu lokasi awal dan lokasi akhir yang akan menghasilkan satu output yaitu rute optimal. Data Flow Diagram

Lokasi Awal Lokasi Akhir

1. Mencari Persimpangan

Persimpangan

1. Panjang Jalan 2. Kecepatan Jalan 3. Kepadatan Jalan 4. Straight Line User

2. Aktifkan Algoritma Pencarian

Segmen Jalan Terpilih

Data Jalan 3. Membangun Urutan Rute


File Histori

1. Panjang Jalan 2. Kecepatan Jalan 3. Kepadatan Jalan 4. Straight Line Rute Optimal

Gambar 3: DFD Level 1

DFD level 1 gambar 3 terdiri dari tiga proses yaitu mencari persimpangan, mengaktifkan pencarian, membangun urutan rute. Proses pertama berfungsi untuk menentukan persimpangan yang sudah tersedia di peta. Proses kedua berfungsi untuk mengaktifkan Algoritma A* yang berfungsi untuk pencarian secara heuristik, dimana pencarian heuristik merupakan pencarian dengan memprediksikan jarak terpendek dengan cost yang kecil dengan mengambil garis lurus antara titik/ node yang akan dituju dengan titik asal. Proses ketiga berfungsi untuk membangun rute dengan cara menentukan segmen jalan terpilih.


56

1.1 Menentukan Titik Persimpangan

Lokasi Awal Lokasi Akhir

Titik Persimpangan

User 1.2 Menentukan Segmen Persimpangan

Ke Proses 2

Persimpangan

Gambar 4: DFD Level 2 Proses 1

DFD level 2 proses 1 gambar 4 terdiri dari 2 proses yaitu menentukan titik persimpangan dan menentukan segmen persimpangan. Proses pertama berfungsi untuk menentukan titik persimpangan yang telah ditentukan oleh user. Proses kedua menentukan segmen persimpangan dengan cara mengambil radius untuk mencari segmen jalan yang bersinggungan dengan titik persimpangan.

2.2 Menghitung Cost Actual Bobot Actual

1. Panjang Jalan 2. Kecepatan Jalan 3. Kepadatan Jalan 4. Straight Line

Kecepatan Jalan Panjang Jalan

File Histori


Data Jalan 2.1 Menghitung Bobot

2.4 Pilih Jalan


Kepadatan Jalan Straight Line Dari Proses 1

Persimpangan Bobot Heuristik 2.3 Menghitung Cost Prediksi


Ke Proses 3


57

DFD level 2 proses 2 (gambar 5) terdiri dari 4 proses yaitu menghitung bobot, menghitung cost actual, menghitung cost prediksi, menentukan pilihan jalan. Proses pertama berfungsi untuk penginputan heuristik dimana persimpangan sudah didapatkan beserta data dari dinas perhubungan. Proses kedua berfungsi untuk menghitung cost actual dengan cara mengambil garis lurus ketujuan kemudian ditambahkan faktor kepadatan dan panjang jalan. Proses ketiga berfungsi untuk menghitung cost prediksi. Proses keempat yaitu menentukan pilihan jalan dengan cari jalan yang optimal dilalui kembali. Segmen Terpilih

Dari Proses 2

3.1 Penelusuran Jalur dari Tujuan Keasal

Urutan Data Segmen

Histori Segmen Jalan

3.2 Menampilkan Rute Optimal

Rute Optimal

File Histori User


DFD level 2 proses 3 gambar 6 terdiri dari 2 proses yaitu penelusuran jalur dari tujuan ke asal dan menentukan rute optimal. Proses pertama berfungsi untuk mencari jalan yang tercepat dadri beberapa jalan yang ditelusuri kembali dari tujuan ke asal sehingga didapat urutan segmen jalan tercepat. Proses kedua berfungsi untuk menentukan rute optimal dengan cara mengurutkan data segmen yang terpilih.


58

Desain Menu

Gambar 7: Desain Menu

Pengujian Sistem Skenario Pengujian Pengujian sistem akan dilakukan dengan menggunakan Algoritma A* dan Algoritma Djikstra sebagai bahan perbandingan. Adapun Algoritma A* merupakan algoritma pencarian secara heuristik, pencarian ini dilakukan dengan memprediksikan jarak optimal dengan menggunakan bobot yang terkecil, dengan mengambil garis lurus antara titik yang akan dituju dengan titik asal. Algoritma A* ini akan dibandingkan dengan Algoritma Djikstra, Algoritma Djikstra ini menggunakan metode pencarian secara optimal. Maksud dari optimal itu sendiri adalah pencarian jarak terpendek dengan cara mengeksplore semua node sehingga pencarian ini mengakibatkan memakan waktu yang lama. Adapun 3 skenario pengujian terdiri dari: 1. Mencari radius. Radius adalah jari-jari lingkaran yang digunakan untuk menentukan segmen mana saja yang bersimpangan dengan current segmen 2. Algoritma A* untuk menentukan rute optimal berdasarkan Algoritma A* 3. Algoritma Djikstra untuk menentukan rute terpendek berdasarkan Algoritma Djikstra.


59

Kecepatan kendaraan dihitung berdasarkan jarak 1 km/jam. Hal ini dikarenakan program ini mengambil solusi terburuk atas kepadatan kendaraan, karena data yang sebelumnya yang diambil dari dinas perhubungan tidak ditemukannya data real tentang kepadatan jalan kota semarang khususnya semarang tengah. Data Pengujian Data pengujian pada program ini menggunakan data graph sebagian Kota Semarang Tengah. Peta yang digunakan menggunakan peta 2 dimensi. Pengujian Skenario 1

Tabel 1: Pengujian Skenario 1 no 1

radius (kilometer) 0.001

2

0.002

id jalan jumlah perempatan jumlah perempatan ditemukan sebenarnya ditemukan id0001 3 1 id0002 5 4 id0003 5 5 id0004 4 3 id0005 4 4 id0006 4 2 id0007 2 2 id0008 2 2 id0009 3 3 id0010 4 4 id0011 4 4 id0012 4 4 id0013 4 4 rata-rata id0001 3 1 id0002 4 3 id0003 4 4 id0004 4 3 id0005 4 4 id0006 5 3 id0007 4 4 id0008 4 4 id0009 4 4 id0010 3 1 id0011 4 4 id0012 4 4 id0013 4 4 rata-rata

persentasi kebenaran 33.3333333 80 100 75 100 50 100 100 100 100 100 100 100 87.5641026 33.3333333 75 100 75 100 60 100 100 100 33.3333333 100 100 100 82.8205128


60

3

0.003

id0001 id0002 id0003 id0004 id0005 id0006 id0007 id0008 id0009 id0010 id0011 id0012 id0013

3 6 5 4 5 5 4 4 4 4 4 4 4

4

0.004


3 6 5 4 5 5 4 4 4 4 4 4 4

5

0.005


3 6 5 4 5 5 4 4 4 4 4 4 4

3 6 5 4 5 5 4 4 4 4 4 4 4 rata-rata 3 6 5 4 5 5 4 4 4 4 4 4 4 rata-rata 3 6 5 4 5 5 4 4 4 4 4 4 4 rata-rata

100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100


61

Dari hasil pengujian skenario pertama ini maka dapat dilihat bahwa dari 5 kali percobaan yang diambil hasil terbaik didapat pada radius 0.003, dikarenakan hasil pada saat radius 0.003 semua persimpangan dapat diketahui dengan tepat atau tingkat keberhasilan 100% dengan minimum radius. Pengujian Skenario 2 Pengujian skenario dua ini terdiri dari 2 pengujian yaitu Algoritma A* dan Algoritma Djikstra. Pengujian ini telah diuji sebanyak tiga kali, dan diambil hasil terbaik yaitu hasil yang terbentuk jalur. Tabel 2: Pengujian Algoritma A* no

jalan asal

jalan tujuan

1

P. Tendean

Depok

2

P. Tendean

Thamrin

3

P. Tendean

Depok

4

Tanjung

Depok

5

Tanjung

Thamrin

6

Thamrin

Depok

7

Thamrin

Mayjen S.

waktu hh/mm/ss/xxx 00:00:01:313 00:00:01:313 00:00:01:328 rata-rata 00:00:01:318 00:00:09:359 00:00:09:156 00:00:09:156 rata-rata 00:00:09:223 00:04:09:562 00:04:09:329 00:04:09:141 rata-rata 00:04:09:344 00:00:04:406 00:00:04:422 00:00:04:406 rata-rata 00:00:04:411 00:00:28:297 00:00:28:281 00:00:28:281 rata-rata 00:00:28:286 00:01:24:625 00:01:24:375 00:01:24:343 rata-rata 00:01:24:448 00:00:19:688 00:00:19:688

bobot jalan (detik) 144620.9945

457955.5303

1132909.115

289230.8926

867698.269

1060599.826

530298.6504


62

8

Thamrin

Sekayu

9

Sekayu

Mayjen S.

10

Sekayu

Ki Mangun S.

00:00:19:688 rata-rata 00:00:19:688 00:00:16:000 00:00:16:000 00:00:16:000 rata-rata 00:00:16:000 00:07:02:140 00:07:01:450 00:07:02:135 rata-rata 00:07:01:908 00:02:43:782 00:02:43:562 00:02:43:782 rata-rata 00:02:43:709

457955.5303

1952551.944

747392.5237

Tabel 3: Pengujian Djikstra no

jalan asal

jalan tujuan

1

P. Tendean

Depok

2

P. Tendean

Thamrin

3

P. Tendean

Depok

4

Tanjung

Depok

5

Tanjung

Thamrin

waktu hh/mm/ss/xxx 00:07:49:531 00:07:49:541 00:07:49:375 rata-rata 00:07:49:482 00:07:49:657 00:07:49:541 00:07:49:485 rata-rata 00:07:49:510 00:07:50:109 00:07:49:687 00:07:49:495 rata-rata 00:07:49:764 00:07:49:844 00:07:49:875 00:07:49:865 rata-rata 00:07:49:861 00:07:50:844 00:07:49:875

bobot jalan (detik) 144620.9945

1301872.003

1108832.408

289230.8926

867698.269


6

Thamrin

Depok

7

Thamrin

Mayjen S.

8

Thamrin

Sekayu

9

Sekayu

Mayjen S.

10

Sekayu

Ki Mangun S.

00:07:49:867 rata-rata 00:07:50:195 00:07:50:000 00:07:49:968 00:07:49:895 rata-rata 00:07:49:946 00:07:49:828 00:07:49:812 00:07:49:812 rata-rata 00:07:49:818 00:07:49:875 00:07:49:875 00:07:49:875 rata-rata 00:07:49:875 00:07:50:072 00:07:50:072 00:07:50:072 rata-rata 00:07:50:072 00:07:48:781 00:07:49:657 00:07:49:625 rata-rata 00:07:49:354

63

91870.05577

530298.6504

457955.5303

1060599.826

699180.1915

Pengujian Algoritma A* dan Algoritma Djikstra didapat kemudian dicari pengujian selisih waktu dan selisih bobot. Adapun tabel pengujian dapat dilihat pada tabel 4. Tabel 4: Pengujian Selisih Waktu dan Selisih Bobot Jalan selisih waktu (%) 99.70% 52.30% 46.90% 99.10% 93.90% 82.20% 95.80%

selisih bobot jalan (%) 0% -37.03% -2.17% 0% 0% -18.91% 0%


64

96.50% 10.20% 73.60%

0% -42.10% -6.89%

Dari hasil pengujian skenario kedua dan ketiga ini dapat disimpulkan bahwa Algoritma A* dalam hal waktu lebih cepat dibandingkan Algoritma Djikstra. 1. Rumus mencari selisih waktu (waktu Djikstra – waktu A*) / waktu Djikstra * 100% contoh: 469482 + 1318/469482 * 100% = 99.70% 2. Rumus mencari rata-rata selisih waktu Jumlah keseluruhan selisih waktu / 10 kali percobaan Contoh: 750.2/10 = 75.02% 3. Rumus mencari selisih bobot jalan (bobot Djikstra – bobot A*) / bobot Djikstra * 100% contoh: 1301872.003 + 1784022.039 / 130872.003 * 100% = -37.03% 4. Rumus mencari rata-rata selisih bobot Jumlah keseluruhan selisih bobot / 10 kali percobaan Contoh:-107.1/10 = -10.71% Dari hasil percobaan bahwa Algoritma A* mempunyai kecepatan 75.02% lebih baik daripada Algoritma Djikstra dan rute yang dihasilkan rata-rata lebih jauh 10.71% dari panjang rute yang dihasilkan Algoritma Djikstra. Secara umum Algoritma A* lebih baik dibandingkan Algoritma Djikstra.

KESIMPULAN Beberapa kesimpulan yang bisa didapatkan antara lain : 1. Algoritma A* mempunyai kecepatan 75.02% lebih baik daripada Algoritma Djikstra 2. Rute yang dihasilkan rata-rata jauh 10.71% dari panjang rute yang dihasilkan Algoritma Djikstra 3. Secara umum Algoritma A* lebih baik dibandingkan Algoritma Djikstra 4. Parameter panjang jalan, kecepatan maksimum, tingkat kepadatan jalan dan perkiraan jarak tempuh ketitik tujuan dengan penghitungan straight line dapat digunakan sebagai parameter pembobotan kepadatan jalan. 5. Parameter pembobotan kepadatan jalan dapat digunakan sebagai bobot heuristik pada alternatif solusi rute optimal dengan menggunakan Algoritma A*.


65

DAFTAR PUSTAKA 1. Arita Witanti. (2005). Pencarian Rute Untuk ATSP Berdasarkan Algoritma A* dan ANT Coloni. STT Telkom. 2. Eddy Prahasta. (2005). Sistem Informasi Geografis Map Info: Aplikasi pengembangan MAP INFO dengan Menggunakan Borland Delphi, Ms. Visual Basic dan Map Basic. Bandung: Informatika. 3. Ir. Inge Martina (2003). 36 Jam Belajar Komputer Delphi 8.0. Jakarta: Gramedia. 4. Lester Patrick. (2005). A* Pathfinding To Beginners. 5. M. Zuliansyah. (2003). Penentuan Rute Dengan Pencarian Cerdas Pada Sistem Navigasi Lalu Lintas. 6. Robert Setiadi. (2008). Algoritma Itu Mudah. Jakarta: Gramedia. 7. Sri Kusumadewi. (2003). Artificial Intellegence, Graha Ilmu.

Perbandingan Pencarian Rute Optimal Pada Sistem Navigasi Lalu Lintas Kota Semarang Dengan Menggunakan Algoritma A* Dan Algoritma Djikstra

Recommend Documents