JURNAL APLIKASI PENENTUAN RUTE OPTIMAL DELIVERY MENGGUNAKAN ALGORITMA DIJKSTRA

JURNAL

APLIKASI PENENTUAN RUTE OPTIMAL DELIVERY MENGGUNAKAN ALGORITMA DIJKSTRA DETERM INATION OF OPTIM UM ROUTE DELIVERY APPLICATIONS USING DIJKSTRA ALGORITHM

Oleh: ASNA MAULIAN AMRONI 12.1.03.02.0181 Dibimbing oleh : 1. Fatkur Rohman,M.Pd. 2. Resty Wulanningrum, M.Kom

PROGRAM STUDI TEKNIK INFORMATIKA FAKULTAS TEKNIK UNIVERSITAS NUSANTARA PGRI KEDIRI TAHUN 2017

Artikel Skripsi Universitas Nusantara PGRI Kediri

Asna Maulian Amroni | 12.1.03.02.0181 Teknik – Teknik Informatika

simki.unpkediri.ac.id || 1||





APLIKASI PENENTUAN RUTE OPTIMAL DELIVERY MENGGUNAKAN ALGORITMA DIJKSTRA Asna Maulian Amroni 12.1.03.02.0181 Teknik – Teknik Informatika [email protected] Fatkur Rohman,M.Pd. dan Resty Wulanningrum, M.Kom. UNIVERSITAS NUSANTARA PGRI KEDIRI

ABSTRAK Penelitian ini dilatar belakangi berdasarkan hasil pengamatan pada salah satu rumah makan di Kediri yang mempunyai jasa Delivery yang masih menggunakan pengetahuan pengantar untuk menentukan jalur delivery. Sehingga dalam delivery ini kurang efektif dan efesien. Akibatnya delivery membutuhkan waktu yang lama dan boros biaya . Untuk mengatasi masalah yang terjadi diatas, maka dalam hal ini masalah yang dapat dirumuskan adalah bagaimana merancang sistem optimasi jalur delivery di kecamatan Kota, kota Kediri menggunakan metode Algoritma Dijkstra. Tujuan yang hendak dicapai dalam penelitian ini untuk menerapkan Metode Algoritma Dijkstra dalam sistem penentuan rute optimal dalam delivery untuk mebantu memberikan informasi mengenai pemilihan jalur terpendek. Aplikasi pencarian rute ini menggunakan algoritma dijkstra sebagai penghitung jarak terpendek. Algoritma dijkstra merupakan algoritma untuk menentukan jarak terpendek antar vertex dengan graf berbobot. Sehingga algoritma ini cocok untuk diimplementasikan dalam mencari rute optimal untuk delivery. Aplikasi ini dibuat berbasis web dengan script PHP dan MySQL sebagai pengelola basis datanya. Hasil dari algoritma dijkstra yaitu dapat membantu memberikan rute terpendek dari node - node yang dituju. Sehingga pelaksanaan delivery dapat menjadi lebih efesien karena jarak yang ditempuh menjadi lebih pendek serta dapat menghemat waktu dan bahan bakar. KATA KUNCI : Delivery, Dijkstra, Rute optimal, Sistem Pendukung Keputusan.




I.

Melakukan optimasi dalam delivery

Pendahuluan

dapat

1.1. Latar Belakang Permasalahan Seiring dengan perubahan gaya hidup masyarakat saat ini, dengan berbagai lebih

kesibukan

yang

menginginkan

praktis,

cepat,

dimiliki

sesuatu dan

yang

ekonomis,

meminimalkan

waktu

yang

dibutuhkan untuk mengantar pesanan, serta

meminimalkan

biaya

bahan

bakar yang digunakan. Dengan

banyaknya

perjalanan

yang

alternatif

mungkin

untuk

dilewati ke lokasi pemesan.

Oleh

terutama untuk masyarakat di daerah

karena itu agar dapat lebih efisien

perkotaan yang sering menjalankan

maka

aktivitasnya di luar rumah. Berbagai

terhadap

kesibukan

yang

oleh

menentukan rute mana yang akan

masyarakat

di

ini

dilewati agar mengoptimalkan waktu

dimiliki era

sekarang

menyebabkan mereka tidak memiliki waktu

lagi

kebutuhan

untuk dasar

makanan.

Oleh

diperlukan lokasi

sebuah

analisa

pemesan

untuk

dan bahan bakar.

menyiapkan mereka

karena

yaitu

1.2. Rumusan Masalah Berdasarkan

itu rumah

latar

belakang

makan sego bantingan membuat jasa

yang telah dijelaskan diatas, maka

delivery order. Adanya jasa delivery

dapat

order

berikut :

dapat

membantu

untuk

dirumuskan

a. Bagaimana

mengantar makanan ke pemesan. Dalam melakukan delivery hal

jalur

masalah sebagai

cara

mendapatkan

optimal dalam mengantar

yang paling diutamakan adalah waktu

pesanan menggunakan Algoritma

pengiriman.

Dijkstra?

masih pengantar delivery.

Selama

ini

menggunakan untuk

delivery

pengetahuan

mementukan

Sehingga

jalur dapat

b. Bagaimana membuat

merancang sistem

yang

dan dapat

menentukan jalur optimal?

memperlambat waktu pengiriman dan membuat

pelanggan

kecewa.




II.

1.3. Tujuan Penelitian Tujuan

dari penelitian

Metode Penelitian

ini sebagai Metodologi yang digunakan pada

berikut: 1. Mendapatkan dalam

jalur

optimal

mengantar

pesanan

menggunakan

Algoritma

implementasi

Algoritma

Dijkstra

dalam sistem untuk menentukan Rute Terdekat

adalah

model Waterfall.

Langkah awal dalam penelitian ini

Dijkstra. 2. Dapat merancang dan membuat sistem yang dapat menentukan

adalah mengumpulkan data, baik data primer maupun data sekunder. Hal ini dilakukan

jalur optimal.

dengan

menggunakan

metode observasi, wawancara, dan studi

1.4. Batasan Masalah Batasan

masalah

pada

sistem ini

1. Penerapan

aplikasi

di wilayah

pemesan

berada

di

wilayah kecamatan kota Kediri. 3. Kendaraan

diasumsikan

kondisi

tidak

baik

kepada

analisa

model

arsip.

waterfall

sebuah

ini

pendekatan

perkembangan

perangkat

lunak yang sistematik dan sekuensial

kecamatan kota Kediri

dalam

mengalami

yang

mulai

kemajuan

pada sistem

tingkat pada

dan sebuah

Planning, analisis, desain, coding dan pengujian. Untuk lebih jelasnya tahap-

bocor ban. 4. Lokasi

Selanjutnya mengusulkan

adalah:

2. Rumah

dokumentasi/

rumah

hanya

terbatas

pada nama jalan, tidak dengan

tahap dari paradigma waterfall dapat dilihat pada gambar dibawah ini

nomor, blok, RT /RW. 5. Hanya mengambil nama jalan di kecamatan

Kota,

kota

Kediri

untuk tujuan pengantaran. 6. Aplikasi menggunakan

yang bahasa php

dibuat dan

basis data MySQL. Asna Maulian Amroni | 12.1.03.02.0181 Teknik – Teknik Informatika

Gambar 1.1 Paradigma Waterfall simki.unpkediri.ac.id || 5||


1.1.

Graf

(Vi,Vj). Secara geometri graf dapat

Graf

digunakan

untuk

merepresentasikan objek-objek diskrit dan

hubungan

antara

objek-objek

(G)

merupakan

tersebut.

Graf

pasangan

himpunan

(V,E)

(vertex), dan E=himpunan sisi (edge) yang menghubungkan sepasang titik dapat

ditulis

dengan

notasi

G=(V,E). Titik biasa digunakan untuk melambangkan objek, sedangkan sisi biasa

digunakan

melambangkan antara

dua

jalan objek.

untuk penghubung Definisi

graf

menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi, sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi titiknya harus ada minimal satu. Graf dengan

satu

titik

dan

tidak

mempunyai sisi disebut graf trivial Titik

pada

graf

dapat

dinomori

dengan huruf, seperti a, b, c, … dengan bilangan asli 1, 2, 3, ... atau gabungan

keduanya.

sebagai

sekumpulan

titik di dalam bidang dua dimensi yang

dihubungkan

dengan

sekumpulan sisi[5].

dengan

V=himpunan tidak kosong dari titik

atau

digambarkan

Sedangkan

E

adalah sisi yang menghubungkan titik Vi dengan titik Vj, maka E dapat

1.2. Algoritma Dijkstra algoritma

Dijkstra

masalah

pencarian

(sebuah

lintasan

menyelesaikan jalur

yang

terpendek mempunyai

panjang minimum) dari verteks a ke verteks z dalam graf berbobot, bobot tersebut adalah bilangan positif jadi tidak dapat dilalui oleh node negatif. Misalkan

G

adalah

graf

berlabel dengan titik-titik {v1,v2,…,vn}

dan

berarah V(G) =

path terpendek

yang dicari adalah dari v1 ke vn. Algoritma Dijkstra dimulai dari titik v1. Dalam iterasinya, algoritma akan mencari

satu

titik

yang

jumlah

bobotnya dari titik 1 terkecil. Titiktitik

yang

terpilih dipisahkan,

dan

titik-titik tersebut tidak diperhatikan lagi

dalam

Langkah-langkah lintasan

iterasi

berikutnya.

dalam menentukan

terpendek

pada

algoritma

Dijkstra yaitu:

ditulis sebagai E = (Vi, Vj) atau E = Asna Maulian Amroni | 12.1.03.02.0181 Teknik – Teknik Informatika



a. Pada

awalnya

pilih

node

sebagai

node

awal,

sumber

1.3. GIS(Geographic

Information

System)

diinisialisasikan dengan ‘1’. b. Bentuk tabel yang terdiri dari node,

status,

predecessor.

bobot,

dan

Pengertian

Information System atau Sistem

Lengkapi kolom

Informasi

bobot yang diperoleh dari jarak

sangatlah

node sumber ke semua node

terlihat

yang

SIG yang beredar di berbagai

langsung

terhubung

dengan node sumber tersebut.

Geografis beragam.

sumber

pustaka.

kemungkinan

maka tetapkan sebagai node

berkembang,

terpilih.

sedikit

d. Tetapkan node terpilih dengan

(SIG) Hal

ini

dari banyaknya definisi

c. Jika node sumber ditemukan

Definisi besar

masih

bertambah,

bervariasi,

SIG

karena

dan SIG

merupakan suatu bidang kajian

label permanen dan perbaharui

ilmu

node yang langsung terhubung.

digunakan oleh berbagai bidang

e. Tentukan node sementara yang terhubung

pada

node

yang

dan

atau

teknologi

disiplin

yang

ilmu,

dan

berkembang dengan cepat. Dapat

sudah terpilih sebelumnya dan

disimpulkan

merupakan

terkecil

SIG merupakan sebuah sistem

dilihat dari tabel dan tentukan

atau teknologi berbasis komputer

sebagai

yang

bobot

node

terpilih

berikutnya. f.

Geographic

Apakah

disimpulkan

dibangun

dengan

untuk node

tujuan

mengumpulkan,

terpilih

menyimpan,

merupakan node tujuan?. Jika

menganalisa,

ya,

data dan informasi dari suatu

maka

terpilih

kumpulan

atau

merupakan menunjukkan

yang

bahwa

node

predecessor

rangkaian

yang lintasan

terpendek[10]. Asna Maulian Amroni | 12.1.03.02.0181 Teknik – Teknik Informatika

objek berkaitan

mengolah serta

atau

keberadaanya

menyajikan

fenomena

dengan di

dan

letak

yang atau

permukaan

bumi[7]. simki.unpkediri.ac.id || 7||


1.4. Perancangan Sistem

e) Menu, kumpulan menu-menu

1.4.1. Flowchart Admin

(user

admin,

jarak,rute) Berikut

ini

adalah

flowchart

data

yang

tempat,

disediakan

utntuk admin.

dari sub sistem yang terdapat pada

f) Input, edit, delete data user

sistem Penentuan Rute terpendek

admin, proses yang digunakan

yang digunakan pada admin :

untuk menambah, mengubah

no

Menu Login

Start

ataupun menghapus user admin

Username Password

Valid ?

yang digunakan untuk login ke yes

menu admin.

Menu

yes no

no Lanjut?

Lanjut?

yes

no Lanjut?

yes

yes

g) Input, edit, delete data tempat,

no Lanjut?

Lanjut?

yes

yes

A

Input, Edit, delete data user admin

Input, Edit, delete data lokasi

Lihat hapus,rute

Input Pilih awal & tujuan Tujuan

Data User admin

Data lokasi

Data Jarak rute

Penentuan rute terpendek

Laporan data User Admin

Laporan Data lokasi

Laporan Jarak Rute

Laporan Rute terpendek

Logout

proses yang digunakan utuk menambah, mengubah ataupun menghapus data tempat ( nama

Apakah Ingin Mengulang?

jalan). no

End

Gambar 5.9 flowchart Admin

h) View data jarak rute, proses yang

digunakan

utuk

menampilkan data jarak rute. i) .Logout, proses yang digunakan

a) Start b) Login, proses untuk masuk ke halaman utama admin c) User

name

–

password,

tampilan menu login yang akan diisi oleh admin. d) Apakah valid? Jika “yes” maka akan masuk kedalam tampilan inti admin, jika “no” maka kembali ke tampilan login,


untuk keluar dari program. j) Apakah ingin mengulang? Jika “yes” maka akan kembali ke menu, jika “no” maka program akan berakhir k) End. 1.4.2. Konteks Diagram Konteks

diagram

adalah

diagram yang terdiri dari suatu proses

dan

ruang

lingkup

menggambarkan suatu

sistem. simki.unpkediri.ac.id || 8||


Diagram

konteks

merupakan

1.4.4. Perancangan Database

level tertinggi dari DFD yang lihat

menggambarkan ke

sistem

seluruh

atau

output

db_admin

input dari

sistem.

memilih

# id_admin Integer o nm_user Text o Password Text ...

Rute db

db_user # ID_user Integer o nm_user Text o Password Text ...

# id_rute Integer o rute Text o panjang rute Integer ...

memasukkan

memiilih

db_lokasi # id_lokasi Integer o nm_lokasi Text o nomor Text ... gunakan

menentukan

db_koordinat # Id_koordinat Integer o nm_koordinat Text o koordinat Text ...

Gambar 5.7 Entity Relashionship Diagram Gambar 5.5 Konteks Diagram

adalah

diagram

permodelan

yang

untuk

Tahap

selanjutnya setelah

profesional

perancangan

adalah

tahap

mengambarkan

implementasi

program.

Pada

implementasi

ini,

memungkinkan sistem

Hasil dan Kesimpulan 3.1. Implementasi Program

1.4.3. Data Flow Diagram DFD

III.

sistem sebagai suatu jaringan

tahap

proses

aplikasi dibuat

dihubungkan

fungsional,

yang

satu

lain

sama

dengan sebuah alur data.

menggunakan

bahasa PHP dan basis data MySQL.

3.1.1. Tampilan Login User

Form

login

dapat

digunakan oleh user yang Gambar 5.6 DFD Level 1

telah derdaftar sebelumnya. Dengan

mengisi

username

dan password maka user Asna Maulian Amroni | 12.1.03.02.0181 Teknik – Teknik Informatika



dapat

masuk

ke

dalam

sistem.

akan

menjadi

tujuan

pada

aplikasi ini. Data lokasi hanya dapat

di

administrator,

lihat

oleh

admin

dapat

mengedit dan menghapus data lokasi.

Gambar 5.10. form login user Gambar 5.13 Form Lokasi 3.1.2. Tampilan login admin Form

login

dapat

digunakan oleh admin yang sudah

diberi

Form Koordinat berisi

akses

informasi koordinat koordinat

akses

node yang akan dilalui oleh

berupa nama dan password

lintasan pada peta kecamatan

admin.

Kota, kota Kediri.

sebelumnya.

hak

3.1.4. Tampilan Form Koordinat

Hak

Gambar 5.12 form Admin

3.1.3. Tampilan Form Lokasi Form

Lokasi

berisi

informasi tempat tempat yang Asna Maulian Amroni | 12.1.03.02.0181 Teknik – Teknik Informatika

Gambar 5.14 Form Daftar Koordinat simki.unpkediri.ac.id || 10||


3.1.5. Tampilan Form Pencarian rute Form

Pencarian

berisi

pencarian

terpendek dalam

rute rute

yang ditampilkan

peta.

User

harus

memasukkan pilihan

tujuan

yang akan dituju oleh user.

Gambar 5.16 Tampilan Output Pencarian rute 3.2.

Simpulan

1. Sistem Pendukung Keputusan Dalam pencarian jarak optimal delivery menggunakan Metode Gambar 5.15 Form Pencarian

dijkstra dapat berjalan dengan baik

rute

sehingga dihasilkan suatu

sistem yang dapat membantu 3.1.6. Tampilan Output Hasil

lintasan

Pencarian Rute Pada tampilan aplikasi di atas

merupakan

memberikan

tampilan

hasil dari proses pencarian rute terpendek berdasarkan data yang telah dimasukkan oleh user.

informasi terpendek

untuk

delivery. 2. Metode terapkan

dijkstra

dapat

kedalam

di

Sistem

Pencarian rute optimal delivery dengan cara memberikan hasil Output

rute

delivery

di

kecamatan Kota ,kota Kediri.




3.3. Saran

Sumatera Bagian Selatan. Jurnal Sistem Informasi (JSI), VOL. 5,

Berdasarkan diharapkan mengembangkan ini

menjadi

tersebut menentukan

di

hasil

uji

coba,

pembaca

dapat

sistem

Pencarian

lebih

baik.

antaranya tujuan

NO. 2, The Informatics and Business Institute Darmajaya Bandar Lampung Indonesia

Saran dapat

berdasarkan

lokasi GPS

pengguna. Serta dapat

langsung

menentukan

jarak

[3] Hasan, I., 2002. Pokok – Pokok Materi Teori Pengambilan Keputusan. Jakarta: Ghalia Indonesia.

terpendek antar node pilihan dan dapat diperluas area untuk delivery. IV.

Daftar Pustaka

[1] Ekadinata A, Dewi S, Hadi D,

[4] Lipschutz,Seymour.2002. Matematika diskrit.Jakarta : Salemba Teknika

Nugroho D, dan Johana F. 2008. Sistem Informasi Geografis Untuk Pengelolaan Bentang Lahan Berbasis Sumber Daya

[5] Munir, Rinaldi. 2005. Matematika Diskrit. Bandung : Informatika

Alam. Buku 1: Sistem Informasi Geografis dan Penginderaan Jauh Menggunakan ILWIS Open Source. Bogor: World

[6] Munir, Rinaldi. 2009. Matematika Diskrit Edisi ketiga. Bandung : Informatika

Agroforestry Centre [7] Prahasta, Eddy. 2009. Sistem [2] Fitria, Apri Triansyah.2013. Implementasi Algoritma Dijkstra Dalam Aplikasi Untuk Menentukan Lintasan Terpendek

Informasi Geografis : Konsepkonsep Dasar (Perspektif Geodesi & Geomatika).Bandung: Informatika.

Jalan Darat Antar Kota Di Asna Maulian Amroni | 12.1.03.02.0181 Teknik – Teknik Informatika



[8] Rich, Elaine, 1991, Artificial

[12] Suprayogi, Dwi

Intelligence. New York:

aris,Mahmudi,WayanF. 2015.

McGraw-Hill.

Penerapan Algoritma Genetika Traveling Salesman Problem

[9] Satyananda, Darmawan. 2012.

with Time Window: Studi Kasus

Struktur Data. Malang:

Rute Antar Jemput Laundry.

Universitas Negeri Malang.

Jurnal Buana Informatika Vol 6, No 2. Universitas Atma Jaya

[10] Siang, Jong Jek. (2004),

Yogyakarta

Matematika Diskrit dan Aplikasinya pada Ilmu Komputer,

[13] Surbakti, Irfan. 2002. Sistem

Yogyakarta: CV Andi Offset.

Pendukung Keputusan (Decision Support System). Surabaya:

[11] Sihombing, Jemmy. 2014.

Jurusan Teknik Informatika

Perancangan Aplikasi Pencarian

Fakultas Teknologi Informasi

Jalur Terpendek Untuk Daerah

Institut Teknologi Sepuluh

Kota Medan Dengan Metode

November.

Steepest Ascent Hill Climbing. Jurnal Pelita Informatika

[14] Turban, Erfraim, et al. 2005.

Budidarma VOL.VI No.2.

Decision Support Systems and

STMIK Budidarma. Medan.

Intelligent Systems 7th Ed. New Jersey: Pearson education .



JURNAL APLIKASI PENENTUAN RUTE OPTIMAL DELIVERY MENGGUNAKAN ALGORITMA DIJKSTRA

Recommend Documents