Optimasi Rute Perjalanan Ambulance Menggunakan Algoritma A-Star Marhaendro Bayu Setyawan, Nurlita Gamayanti, Abdullah Alkaff Jurusan Teknik Elektro FTI - ITS
minimum cost. Biaya lintasan adalah jumlah biaya semua arc yang membentuk lintasan tersebut. Ada beberapa asumsi yang digunakan dalam perhitungan lintasan terpendek, yaitu: 1. Jaringan berarah (directed network). 2. Ada lintasan berarah dari satu node sumber ke semua node lain. 3. Tidak ada siklus negatif, yaitu siklus dengan total biaya negatif. 4. Biaya tiap arc merupakan bilangan bulat. Formulasi masalah dalam permasalahan lintasan terpendek dapat dinyatakan dalam bentuk aliran minimum dimana tiap node yang dituju dianggap memiliki permintaan sebesar satu unit dan node sumber memiliki supply sebanyak yang diminta. Lintasan terpendek dari nose S (node sumber) ke node T (node tujuan) diformulasikan sebagai berikut :
Abstraksi— Tugas akhir mencoba untuk menciptakan sebuah sistem routing yang diterapkan untuk mencari rute ambulans pada jaringan jalan untuk menjemput pasien dan mengantarkan ke rumah sakit. Jalan raya yang digunakan untuk tugas akhir, berasal dari data spasial, dimana pada kasus ini kita menggunakan Peta Surabaya. AStar Algoritma yang digunakan untuk menyelesaikan masalah routing ambulans dengan kondisi dinamis tentang lokasi pasien, jumlah yang diminta ambulans, kondisi patiens, dan ketersediaan ambulans di rumah sakit.
I. PENDAHULUAN Permasalahan distribusi adalah bagian dari permasalahan logistik yang didefinisikan sebagai penyediaan barang dan jasa dari titik persediaan ke titik permintaan. Persoalan distribusi terdapat di berbagai bidang pelayanan umum, misalnya persoalan pengangkutan sampah, persoalan jemputan penumpang bus, persoalan pengiriman barang, dan penentuan jalur pembersihan jalan. Dalam permasalahan distribusi, penentuan rute merupakan permasalahan yang cukup vital. Dengan penentuan rute yang baik sebuah armada dapat melaksanakan tugas distribusi (baik barang maupun) dengan optimal. Sistem routing pertama kali diperkenalkan tahun 2004 oleh tim peneliti yang terdiri dari Ryujiro Fujita, Hiroto Inoue, Naohiko Ichihara, Takehiko Shioda. Penelitian yang melibatkan tim peneliti tersebut, di danai oleh Pemerintah Jepang, bertujuan untuk mengatasi kepadatan lalu lintas yang terjadi di beberapa kota besar di Jepang[3]. Sistem ini berfungsi untuk mencari semua rute perjalanan yang dapat dilalui oleh seorang pengendara kendaraan dalam mencapai tempat tujuan. Sistem yang diperkenalkan oleh para peneliti ini menggunakan algoritma Dijkstra dalam pencarian rute. Namun seiring dengan perkembangan ilmu pengetahuan, metode Dijkstra mempunyai kekurangan dalam waktu pencarian yang kurang efektif dan dinilai lamban. Untuk mengatasi permasalahan, pada penelitian yang dilakukan oleh penulis, dibahas penerapan sistem routing menggunakan algoritma A* sebagai alternatif untuk mempercepat proses pencarian rute. Sistem routing yang dikerjakan oleh penulis, di terapkan ke dalam aplikasi penentuan rute ambulance dengan menggunakan Surabaya sebagai tempat implementasi penelitian. Penentukan rute ambulance ini ditujukan agar didapatkan rute terpendek secara keseluruhan untuk melayani semua permintaan pasien sehingga pasien dapat segera dijemput dan diantarkan menuju rumah sakit.
B. Data Spasial Data spasial adalah data yang memiliki referensi ruang kebumian (georeference) dimana berbagai data atribut terletak dalam berbagai unit spasial. Saat ini data spasial menjadi media penting untuk perencanaan pembangunan dan pengelolaan sumber daya alam yang berkelanjutan pada cakupan wilayah continental, nasional, regional maupun lokal. Secara spasial, obyek (entities) dapat dibedakan menjadi tiga yaitu titik (point), garis (line), dan area (polygon). Titik (point) merupakan representasi dari X,Y yang membentuk satu koordinat. Garis (lines) merupakan kumpulan dari X,Y koordinat yang membentuk sebuah garis. Sedangkan Area (polygon) adalah kumpulan garis yang membentuk suatu area tertentu. Secara digital, titik, garis dan area tersebut direpresentasikan menjadi dua model data yaitu vektor dan raster. Dalam data vektor, posisi suatu obyek di definisikan oleh koordinat (X,Y). Kenampakan spasial dalam data vektor dihadirkan dan disimpan dalam bentuk kode kode tertentu atau label. Dalam data raster, data spasial disusun dan disimpan dalam bentuk piksel yang merupakan elemen terkecil suatu gambar. Pada gambar 5 terdapat contoh untuk membedakan data vektor dan raster.
II. DASAR TEORI A. Permasalahan Lintasan Terpendek Permasalahan lintasan tependek dapat digambarkan sebagai upaya pencarian lintasan yang memiliki biaya
1
A adalah simpul yang sedang dijalankan dalam algortima pencarian jalan terpendek. Simpul adalah petak-petak kecil sebagai representasi dari area pathfinding. Bentuknya dapat berupa persegi, lingkaran, maupun segitiga. Open list adalah tempat menyimpan data simpul yang mungkin diakses dari starting point maupun simpul yang sedang dijalankan. Closed list adalah tempat menyimpan data simpul sebelum A yang juga merupakan bagian dari jalur terpendek yang telah berhasil didapatkan. Harga (F) adalah nilai yang diperoleh dari penjumlahan, nilai G merupakan jumlah nilai tiap simpul dalam jalur terpendek dari starting point ke A, dan H adalah jumlah nilai perkiraan dari sebuah simpul ke simpul tujuan. Sehingga dapat diformulasikan f(x) = g(x)+h(x). Simpul tujuan yaitu simpul yang dituju. Halangan adalah sebuah atribut yang menyatakan bahwa sebuah simpul tidak dapat dilalui oleh A. Prinsip algoritma ini adalah mencari jalur terpendek dari sebuah simpul awal (starting point) menuju simpul tujuan dengan memperhatikan harga (F) terkecil. Diawali dengan menempatkan A pada starting point, kemudian memasukkan seluruh simpul yang bertetangga dan tidak memilik atribut rintangan dengan A ke dalam open list. Kemudian mencari nilai H terkecil dari simpulsimpul dalam open list tersebut. Kemudian memindahkan A ke simpul yang memiliki nilai H terkecil. Simpul sebelum A disimpan sebagai parent dari A dan dimasukkan ke dalam closed list. Jika terdapat simpul lain yang bertetangga dengan A (yang sudah berpindah) namun belum termasuk kedalam anggota open list, maka masukkan simpul-simpul tersebut ke dalam open list. Setelah itu, bandingkan nilai G yang ada dengan nilai G sebelumnya (pada langkah awal, tidak perlu dilakukan perbandingan nilai G). Jika nilai G sebelumnya lebih kecil maka A kembali ke posisi awal. Simpul yang pernah dicoba dimasukkan ke dalam closed list. Hal terebut dilakukan berulang- ulang hingga terdapat solusi atau tidaka ada lagi simpul lain yang berada pada open list. Deskripsi A* dalam sebuah graph dapat diamati pada gambar 7. Berikut ini gambaran kerja dari algoritma A* (gambar 6):
Gambar 5. Contoh data vektor dan data raster
C. Algoritma A-Star (A*) Algoritma ini pertama kali diperkenalkan pada 1968 oleh Peter Hart, Nils Nilsson, dan Bertram Raphael[4]. Dalam ilmu komputer, A*(yang diucapkan dengan ―A star‖) merupakan salah satu algoritma pencarian graph terbaik yang mampu menemukan jalur dengan biaya pengeluaran paling sedikit dari titik permulaan yang diberikan sampai ke titik tujuan yang diharapkan (dari satu atau lebih mungkin tujuan)[5]. Algoritma ini menggunakan fungsi distance - plus - cost (biasanya di notasikan dengan f(x)) untuk menentukan urutan kunjungan pencarian node di dalam tree. Gabungan jarak - plus – biaya merupakan penjumlahan dari dua fungsi, yaitu fungsi path - cost (selalu dinotasikan dengan g(x), dimungkinkan bernilai heuristik ataupun tidak), dan sebuah kemungkinan penerimaan atas ―perkiraan heuristis‖ jarak ke titik tujuan (dinotasikan dengan h(x)). Fungsi path - cost g(x) adalah jumlah biaya yang harus dikeluarkan dari node awal menuju node yang akan dituju. Dengan h(x) bagian dari fungsi f(x) yang harus dapat heuristis, yang mana tidak diperbolehkan untuk terlalu jauh memperkirakan jarak ke arah tujuan. Oleh karena itu untuk aplikasi seperti routing, h(x) mungkin mewakili garis lurus jarak ke titik tujuan, karena hal ini secara nyata dimungkinkan adanya jarak terpendek diantara dua titik yang dapat dirumuskan sebagai : Dimana : x = Koordinat x dari node awal y = Koordinat y dari node awal x1 = Koordinat x dari node lokasi ke n y1 = Koordinat y dari node lokasi ke n 1) Deskripsi Algoritma: Seperti pada kebanyakan algoritma pencarian informasi, terlebih dahulu dicari rute yang tampaknya mempunyai kemungkinan besar untuk menuju ke arah tujuan. Apa yang membuat A * algoritma satu satunya pertama yang terbaik dalam proses pencarian adalah algoritma ini mengambil jarak perjalanan ke arah tujuan (dimana g (x) bagian dari heuristis adalah biaya dari awal, dan tidak sekedar menjadi biaya lokal sebelum node diperluas). Beberapa terminologi dasar yang terdapat pada algoritma ini adalah starting point, simpul (nodes), A, open list, closed list, harga (cost), halangan (unwalkable). Starting point adalah sebuah terminologi untuk posisi awal sebuah benda.
Gambar 6. Proses pelacakan jalur pada algoritma A*
Gambar 7. Proses pencarian jalur terpendek pada algoritma A*
2
Pada table atribut ruas jalan terdapat field_ruas yang merupakan kode dari ruas, field node_asal dan node_tujuan dan field jarak yang menyatakan panjang dari ruas jalan yang bersangkutan. Sedangkan untuk table atribut aturan ruas jalan terdapat field kode_ruas dan next_ruas yang menyatakan jalan yang dapat dilalui dari ruas yang bersangkutan sesuai dengan aturan belokan yang ada. Dari jaringan jalan diatas maka pemodelan dalam bentuk graph dapat dibentuk menjadi seperti gambar 9 berikut :
Pada gambar 7, sebuah graph memiliki 7 buah simpul, yang masing - masing simpul mempunyai nilai G dan H, starting point berada pada simpul saling pojok kiri atas (simpul berwarna hijau), dan simpul tujuan berada di pojok kanan bawah (simpul berwarna biru). Hasil pelacakan jalur terpendek menggunakan A* menghasilkan garis tebal warna orange dengan simpul d, dan e dikunjungi, sehingga menghasilkan jalur terpendek yang menghubungkan starting point menuju simpul tujuan. III. PERANCANGAN SISTEM A. Pemodelan Jalan Jalan yang terdapat pada dunia nyata dapat dimodelkan dalam bentuk graph. Dimana setiap persimpangan jalan direpresentasikan dengan sebuah node dan ruas jalan yang menghubungkan antar persimpangan tersebut direpresentasikan dalam bentuk arc. Apabila jalan yang menhubungkan kedua node adalah jalan dua arah maka direpresentasikan dengan dua arc yang memiliki arah berlawanan yang menghubungkan kedua node tersebut. Permasalahan yang dihadapi dalam menerapkan algoritma yang ada pada jaringan jalan adalah adanya aturan belok pada node persimpangan. Untuk itu dibutuhkan pemodelan graph yang dapat mengatasi permasalahan tersebut. Untuk mengatasi permasalahan aturan belokan tersebut, maka perlu dilakukan perubahan terhadap pemodelan jaringan yang ada.Perubahan yang dilakukan adalah node yang digunakan merupakan segmen jalan dan arc menyatakan hubungan antara tiap segmen dengan besarnya biaya adalah jarak dari segmen asal. Sebagai contoh untuk jaringan jalan seperti gambar 8 berikut :
Gambar 9. Representasi jaringan jalan dalam bentuk graph
B. Pengumpulan Data Data yang digunakan dibedakan dalam dua kelompok. Kelompok yang pertama merupakan data statis, yaitu data yang tidak mengalami perubahan dalam jangka waktu yang lama, dan kelompok yang kedua merupakan data dinamis, yaitu kelompok data yang sering mengalami perubahan. Adapun data yang termasuk dalam data statis diantaranya data ruas jalan, data aturan jalan, dan data lokasi rumah sakit. Sedangkan yang temasuk dalam kelompok data dinamis adalah data permintaan ambulance yang meliputi nama jalan serta titik pasien meminta ambulance, kondisi pasien, serta ketersediaan ambulance dari masing-masing rumah sakit 1) Data ruas jalan : Untuk mendapatkan data jalan yang diinginkan, digunakan peta serabaya yang diterbitkann Bina Citra. Pengkodean data jalan dilakukan pada jalan artileri dan jalan kolektro yang berkaitan dengan posisi pasien. Contoh data ruas jalan seperti terdapat pada tabel 3 berikut : Tabel 3. Contoh data ruas jalan
Gambar 8. Jaringan jalan dengan aturan belokan
Table atribut untuk jaringan jalan pada Gambar 8 sebagai berikut : Kode_ruas 101 102 103 104 105 106
Tabel 1. Atribut ruas jalan Node_asal Node_tujuan 1 2 2 3 2 4 4 2 5 2 2 5
Panjang 4 5 6 6 3 3
2) Data aturan jalan : Aturan ruas jalan yang dimaksud adalah ruas jalan mana saja yang dapat dilalui dari suatu ruas jalan. Dari data aturan jalan dapat terlihat apakah jalan tersebut satu arah atau dua arah. Contoh data aturan jalan seperti terdapat pada tabel 4 berikut :
Tabel 2. Atribut aturan jalan Kode_ruas Next_ruas 101 102 101 103 104 102 104 106 105 102 105 103
Tabel 4. Contoh data aturan jalan
3
3) Data lokasi rumah sakit : Data lokasi rumah sakit didapatkan dari call center 118. Data yang digunakan adalah data lokasi rumah sakit yang tersebar di Surabaya dengan beberapa diantara lokasi rumah sakit diasumsikan ke jalan terdekat yang telah diperoleh dari data ruas jalan yang ada. Gambar 10 menunjukkan contoh data rumah sakit.
START
Panggilan masuk ke 118
Pengisian data pasien meliputi nama, alamat, node, jumlah ambulance yang diminta, serta kondisi pasien
Tabel 5. Contoh data lokasi rumah sakit
Kondisi pasien = darurat ?
Bangkitkan ambulance dari pusat Call center 118
Y
N Cari rute terdekat menuju pasien
Cari rumah sakit dengan total jarak terdekat
Jumlah ambulance yang diminta = jumlah ambulance yang diminta – ambulance tersedia
N
Jumlah ambulance tersedia = jumlah ambulance yang diminta
Y
Jemput pasien
STOP
Gambar 11. Arsitektur rancangan sistem
C. Perancangan Perangkat Lunak Perancangan perangkat lunak permasalahan rute perjalanan ambulance terdiri dari beberapa bagian. Pada bagian awal adalah pembuatan database jaringan jalan yang direpresentasikan dalam perangkat lunak using interface. Hasil dari proses ini berupa tabel. Setelah mendapatkan masukan dari user, kemudian table tersebut diolah di dalam perangkat lunak optimasi. Skema perangkat lunak tersebut dapat digambarkan pada gambar 10 berikut :
Dari gambar di atas arsitektur sistem yang dirancang secara garis besar dapat dibagi menjadi 4 bagian, yaitu : 1) Penentuan data pasien Pada tahap ini dilakukan pendataan data pasien yang membutuhkan ambulance. Pendataan yang dilakukan dalam tahap ini meliputi nama pasien, alamat pasien, kondisi pasien, serta banyaknya ambulance yang diminta oleh pasien. Dalam tahap ini akan didapatkan lokasi dari pasien untuk membangkitkan rute perjalanan ambulance dari rumah sakit terdekat berdasarkan kondisi pasien. 2) Proses Routing Pada tahap proses routing ini akan dilakukan proses pemilihan/pencarian rumah sakit dari database rumah sakit di Surabaya yang berdekatan dengan lokasi pasien berdasarkan dari kondisi pasien. Apabila kondisi pasien dalam kondisi yang darurat maka ambulance yang dibangkitkan adalah ambulance dari rumah sakit terdekat, tetapi jika tidak darurat maka akan dibangkitkan dari pusat ambulance call center 118. Penentuan rumah sakit terdekat dilakukan dengan menggunakan algoritma A-Star sekaligus menentukan rute perjalanan ambulance berdasarkan jarak terpendek menuju pasien. 3) Proses Checking Ambulance Pada proses ini dilakukan pengecekan terhadap ketersediaan ambulance pada rumah sakit terdekat hasil proses routing. Apabila ambulance yang tersedia memenuhi dari jumlah permintaan dari pasien maka akan dilanjutkan ke proses eksekusi. Sedangkan jika jumlah ambulance kurang memenuhi maka akan dilakukan proses routing kembali untuk mencari rumah sakit berikutnya yang menuhi sisa ketersediaan ambulance dari permintaan pasien.
User output
input
User Interface II tabular
User Interface I - penentuar rute - urutan jalan -
tabular
Optimasi
Gambar 10. Skema perangkat lunak
Setelah melalui proses optimasi didapat penentuan rute dan urutan jalan yang harus dilalui. Proses selanjutnya adalah menampilkan hasil optimasi tersebut pada perangkat lunak user interface berupa list. Pada sistem perencanaa rute ambulance yang dirancang, penyelesaian jarak terpendek terjadi dalam dua tahap.Tahap pertama merupakan perhitungan jarak terpendek antara satu node ke semua node lainnya.Perhitungan jarak dilakukan dengan menggunakan algoritma A-Star. Tahap berikutnya adalah menyusun urutan node yang harus dikunjungi sekaligus mengelompokkan node-node menjadi beberapa cluster, sehingga didapatkan rute dengan jarak yang terpendek secara keseluruhan. Arsitektur perangkat lunak yang dirancang adalah seperti gambar 11 berikut :
4
4) Proses eksekusi/ penjemputan pasien Pada proses ini setelah ditemukan rute perjalanan ambulance yang ketersediaannya memenuhi permintaan pasien maka akan dibangkitkan ambulance untuk menjemput pasien.
menjelaskan tentang jarak ambulance menuju pasien. Nama rumah sakit menjelaskan dari mana ambulance dibangkitkan untuk menjemput pasien, urutan jalan yang dilewati dan node yang dilewati sebagai rute ambulance dalam menjemput pasien. Dalam gambar 13 dapat diketahui bahwa untuk membangkitkan ambulance sejumlah permintaan yang diminta pasien (gambar 12). Dalam gambar tersebut diketahui bahwa untuk membangkitkan 4 buah ambulance menuju node pasien (243) dengan keadaan darurat menggunakan algoritma A-Star, ambulance tersebut dibangkitkan dari RS. Katholik St Vincentius A Paulo sebanyak 3 buah dan 1 buah ambulance sisanya dibangkitkan dari Poliklinik Latansa. Adapun urutan node dan jalan yang harus dilewati oleh ambulance dari RS. Katholik St Vincentius A Paulo serta total jarak yang harus ditempuh adalah sebagai berikut : Urutan node : 264-243 Urutan Jalan : DIPONEGORO – DIPONEGORO Total jarak : 15.7727384 Sedangkan untuk urutan node dan jalan yang harus ditempuh oleh ambulance dari Poliklinik Latansa adalah sebagai berikut : Urutan node : 141-152-164-174-185-210-231-243 Urutan Jalan : PUTAT JAYA - JARAK - JARAK BANYU URIP WETAN V - BANYU URIP WETAN V - BANYU URIP WETAN V - BANYU URIP WETAN V – DIPONEGORO Total jarak : 15.7727384 Kebetulan dalam penerapan algoritma A-Star hasil yang didapatkan adalah sama dengan Djikstra
VI. IMPLEMENTASI DAN PENGUJIAN SISTEM A. Implementasi Sistem Pada bagian implementasi kali ini, di tampilkan hasil desain sistem yang telah dibahas pada bagian 3 proceeding ini. Desain sisem yang dirancang dalam platform Borland Delphi 7 akan memberikan tampilan user interface untuk input data pasien seperti pada gambar 12.
Gambar 12. User interface input data pasien
Pada gambar user interface input data pasien tersebut terdapat input data berupa nama, alamat, node, dan kondisi pasien serta jumlah ambulance yang diminta. Selain itu ada 3 tombol yang terdapat pada user interface tersebut, yaitu : SEARCH, CANCEL, dan EXIT. Tombol SEARCH digunakan untuk mengeksekusi program berdasarkan inputan yang telah diberikan untuk dibangkitkan ambulance beserta rute yang harus dilewati oleh ambulance tersebut. Tombol CANCEL digunakan untuk menmbersihkan data input jika terdapat kesalahan pada pemasukan data input. Tombol EXIT digunakan untuk keluar dari perangkat lunak yang dijalankan. Setelah data input dimasukkan dengan benar dan tombol SEARCH ditekan. Maka proses optimasi akan berjalan dan akan menghasilkan output berupa user interface seperti gambar 13 berikut :
B. Pengujian Sistem Untuk mengetahui lebih jauh tentang keoptimalan sistem yang telah dirancang, maka sistem akan diuji dengan 10 data pasien dengan lokasi pasien yang berbeda dan jumlah ambulance yang diminta berbeda untuk masing-masing kondisi pasien dan akan dibandingkan dengan algoritma Djikstra sebagai algoritma peenentuan rute terpendek lainnya. Untuk pasien dengan kondisi darurat didapatkan data hasil pengujian sistem seperti tabel 6. Tabel 6. Data hasil pengujian sistem pasien darurat
Gambar 13. User interface output
Pada gambar 13 tersebut dapat dijelaskan bahwa setelah dilakukan optimasi, hasil output akan ditampilkan dalam informasi berupa total jarak, nama rumah sakit, urutan jalan yang dilewati, serta urutan node yang dilewati. Total jarak
tabel di atas memberikan informasi tentang lokasi pasien (node awal) dengan jumlah ambulance yang diminta. Dapat
5
diketahui bahwa node awal dibangkitkannya ambulance tidak selalu sama. Dari tabel di atas dapat diketahui juga bahwa untuk pasien dengan kondisi darurat penggunaan algoritma A-Star cenderung memberikan total jarak yang lebih besar dari djikstra. Dengan kata lain Algoritma A-star memiliki hasil yang kurang optimal jika dibandingkan dengan Algoritma Djikstra dengan rata-rata nilai keoptimalan -7.982335197%. Untuk pasien dengan kondisi tidak darurat didapatkan data hasil pengujian sistem seperti tabel 7.
BIODATA PENULIS Marhaendro Bayu Setyawan lahir di Lumajang pada tanggal 22 Juni 1988. Anak kedua dari pasangan Supadil dan Suhartini. Mendapatkan pendidikan di SD Wonoasih I, SLTP Negeri 5 Probolinggo, dan SMA Taruna Dra. Zulaeha-Leces. Setelah lulus dari SMA pada tahun 2006 kemudian melanjutkan pendidikannya di Institut Teknologi Sepuluh Nopember Surabaya Jurusan Teknik Elektro Bidang Studi Teknik Sistem Pengaturan sampai dengan sekarang. Penulis aktif di dalam sebagai Asisten Laboratorium Analisa Sistem di Jurusan Teknik Elektro FTI ITS. Penulis memiliki motto hidup yaitu do the best and be the best
Tabel 7. Data hasil pengujian sistem pasien tidak darurat
Dari tabel di atas dapat diketahui juga bahwa untuk pasien dengan kondisi tidak darurat penggunaan algoritma A-Star cenderung memberikan total jarak yang lebih besar dari djikstra. Dengan kata lain Algoritma A-star memiliki hasil yang kurang optimal jika dibandingkan dengan Algoritma Djikstra dengan rata-rata nilai keoptimalan -2.540229571% . V. KESIMPULAN Setelah melalui tahapan implementasi dan melewati tahap pengujian sistem, maka diperoleh beberapa kesimpulan antara lain : 1. Pencarian jarak terpendek dalam jaringan jalan dapat dimodelkan dalam permasalahan lintasan terpendek dan dengan pemodelan yang sesuai dapat diselesaikan dengan menggunakan algoritma AStar. 2. Algoritma A-Star dapat digunakan sebagai metode pencarian lintasan terpendek yang optimal walaupun masih kalah jika dibandingkan dengan algoritma Djikstra. DAFTAR PUSTAKA [1] Ahuja, Ravindra. K., Magnanti, Thomas. L., and Orlin, James. B., 1993.Network Flow : Theory, Algorithm, and Applications. PrenticeHall Int., Inc. [2] Alkaff. A., Diktat Kuliah : Analisis Jaringan. Jurusan Teknik Elektro Institut Teknologi Sepuluh November. [3] Japanese Patent Application No. 2004-106186 filed on Mar. 31, 2004. [4] Hart, P. E.; Nilsson, N. J.; Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics SSC4 4 (2): 100–107. doi:10.1109/TSSC.1968.300136 [5] Pearl, Judea (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley. ISBN 0-201-05594-5 [6] Fredivianus, Nugroho. 2005. “Penggunaan Model Multiple Vehicle Routing Problem Dalam Optimasi Jaringan Distribusi Part Di PT. Astra Internasional Tbk. Toyota Sales Operation Auto2000 Surabaya”, Institut Teknologi Sepuluh Nopember, Surabaya. [7] Kusdiawan, Wawan. 2010. ‗ Cara Mudah dan Cepat Membuat Program Aplikasi Databasse dengan Delphi. Yogyakarta.
6
