PENYELESAIAN VEHICLE ROUTING PROBLEM (VRP) MENGGUNAKAN ALGORITMA GENETIKA
TUGAS AKHIR
Diajukan sebagai Salah Satu Syarat untuk Memperoleh Gelar Sarjana Sains pada Jurusan Matematika
0leh : BAMBANG HERMANSYAH 10454025642
FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS ISLAM NEGERI SULTAN SYARIF KASIM RIAU PEKANBARU 2011
PENYELESAIAN VEHICLE ROUTING PROBLEM (VRP) MENGGUNAKAN ALGORITMA GENETIKA
BAMBANG HERMANSYAH 10454025642
Tanggal Sidang : 30 Juni 2011 Periode Wisuda :
November 2011
Jurusan Matematika Fakultas Sains dan Teknologi Universitas Islam Negeri Sultan Syarif Kasim Riau Jl. HR. Soebrantas No 155 Pekanbaru
ABSTRAK Tugas Akhir ini membahas tentang Vehicle Routing Problem (VRP) dengan contoh kasus pada pengiriman pesanan air galon dengan 2 kendaraan dan 2 orang pemesan untuk menentukan rute terpendek dengan menggunakan Algoritma Genetika (GA). Berdasarkan hasil penelitian diperoleh bahwa lintasan dengan jarak terpendek dan waktu terkecil pada kendaraan I adalah kromosom I dengan jarak 4700 Meter dan waktu 113,16 Menit. Lintasan dengan jarak terpendek dan waktu terkecil pada kendaraan II adalah kromosom VI dengan jarak 6030 Meter dan waktu 135,24 Menit. Kata kunci:
Algoritma Genetika, Vehicle Routing Problem
vii
KATA PENGANTAR Syukur alhamdulillah penulis panjatkan kehadirat Allah SWT yang telah melimpahkan rahmat dan hidayah-Nya sehingga penulis dapat menyelesaikan Tugas Akhir ini tepat pada waktunya. Tugas Akhir ini merupakan salah satu syarat kelulusan tingkat sarjana. Penyusunan dan penyelesaian Tugas Akhir ini penulis tidak terlepas dari bantuan berbagai pihak, baik langsung maupun tudak langsung. Untuk itu sudah sepantasnya penulis mengucapkan terimakasih yang tidak terhingga kepada kedua orang tua tercinta Bapak (Saharuddin) dan Mamak (Asrah) yang tidak pernah lelah dan tiada henti melimpahkan kasih sayang, perhatian, motivasi yang membuat penulis mampu untuk terus dan terus melangkah, pelajaran hidup, juga materi yang tidak mungkin bisa terbalaskan. Jasa-jasamu akan selalu kukenang hingga akhir hayatku dan semoga Allah menjadikan jasa-jasamu sebagai amalan soleh, Amin. Selanjutnya ucapan terima kasih kepada : 1. Bapak Prof. Dr. H. M. Nazir selaku Rektor Universitas Islam Negeri Sultan Syarif Kasim Riau. 2. Ibu Dra. Hj. Yenita Morena, M.Si selaku Plt Dekan Fakultas Sains dan Teknologi Universitas Islam Negeri Sultan Syarif Kasim Riau. 3. Ibu Yuslenita Muda, M.Sc. selaku Ketua Jurusan Matematika yang telah banyak membantu, memberikan kritikan dan saran serta dukungan dalam penulisan Tugas Akhir ini Fakultas Sains dan Teknologi Universitas Islam Negeri Sultan Syarif Kasim Riau. 4. Ibu Sri Basriati, M.Sc. dan Bapak Wartono, M.Sc. selaku pembimbing yang
telah
banyak
membantu,
mengarahkan,
mendukung,
dan
membimbing penulis dalam penulisan Tugas Akhir ini. 5. Bapak M. Soleh, M.Sc dan Bapak M. Nizam Muhaijir, S.Si. selaku penguji yang telah banyak membantu, memberikan kritikan dan saran serta dukungan dalam penulisan Tugas Akhir ini. 6. Ibu Fitri Aryani, M.Sc sebagai koordinator Tugas Akhir.
ix
7. Bapak dan Ibu Dosen di lingkungan FST UIN SUSKA Riau, khususnya di Jurusan Matematika. 8. Untuk adik-adikku yang tersayang Junaidi Hermansyah dan Deni Saputra yang selalu memberi semangat dan motivasi kepada abang. 9. Untuk Siti Zulaiha, AMK yang selalu memberikan semangat, perhatian, kasih sayang dan motivasi dalam menyelesaikan tugas akhir ini. 10. Untuk saudara-saudara dan family yang memberikan motifasi, Om Taufik Ucu Syarifah, Kak Anti, Adek, Angah Iyang, Angah Atok, Kak Pepen, Bang Kifli, Uwo, dan lain-lain yang tidak bisa disebutkan satu persatu. 11. Untuk sahabat-sahabat yang selalu memberikan arahan dan motifasi, Debi Chandra, S.Sos, M. Jamil, M. Ikhsan, ST, dan masih banyak lagi yang tidak bisa penulis sebutkan namanya. 12. Teman-teman Matematika, khususnya Laina, Bidayasari, Wina, Devi, Abang Roni, Ryan, Lukman, Lutfi, Ratna yang selalu semangat dan memberikan motivasi kepada penulis. 13. Rekan-rekan dan adik-adik Racana UIN SUSKA Riau dan DKD 04 Gerakan Pramuka Riau yang selalu memberikan dukungan kepada penulis. 14. Abang Roni yang selalu memberikan dan mengajarkan pengalaman ilmu dalam menyelesaikan Tugas Akhir. 15. Semua pihak yang telah memberi bantuan dari awal sampai selesai Tugas Akhir ini yang tidak bisa disebutkan satu persatu. Dalam penyusunan Tugas Akhir ini penulis telah berusaha semaksimal mungkin. Walaupun demikian tidak tertutup kemungkinan adanya kesalahan dan kekurangan baik dalam penulisan maupun dalam penyajian materi. Untuk itu penulis mengharapkan kritik dan saran dari berbagai pihak demi kesempurnaan Tugas Akhir ini. Pekanbaru, 30 Juni 2011
Penulis
ix
DAFTAR ISI Halaman LEMBAR PERSETUJUAN ...................................................................... ii LEMBAR PENGESAHAN ....................................................................... iii LEMBAR HAK ATAS KEKAYAAN INTELEKTUAL ......................... iv LEMBAR PERNYATAAN ....................................................................... v LEMBAR PERSEMBAHAN..................................................................... vi ABSTRAK ................................................................................................. vii ABSTRACT ................................................................................................. viii KATA PENGANTAR................................................................................ ix DAFTAR ISI .............................................................................................. xi DAFTAR GAMBAR ................................................................................. xiii DAFTAR TABEL ...................................................................................... xiv DAFTAR SIMBOL.................................................................................... xv BAB I. PENDAHULUAN 1.1 Latar Belakang ........................................................................ I-1 1.2 Perumusan Masalah ................................................................ I-3 1.3 Batasan Masalah...................................................................... I-3 1.4 Tujuan dan manfaat Penelitian ................................................ I-4 1.4.1 Tujuan Penelitian............................................................ I-4 1.4.2 Manfaat Penelitian.......................................................... I-4 1.5 Sistematika Penulisan ............................................................. I-4 BAB II. LANDASAN TEORI 2.1 Graf......................................................................................... II-1 2.1.1 Beberapa istilah yang berkaitan sengan graf................ II-1 2.2 Vehicle Routing Problem....................................................... II-2 2.2.1Model Vehicle Routing Problem (VRP)........................ II-2 2.3 Jalur dan Penjadwalan ........................................................... II-5 2.3.1 Metode Optimal/Eksak................................................. II-6 2.3.2 Metode Heuristik.......................................................... II-6 2.4 Algoritma Genetika................................................................ II-7
xi
2.4.1 Individu dalam Algoritma Genetika............................. II-8 2.4.2 Kromosom.................................................................... II-9 2.4.3 Fungsi Fitness .............................................................. II-9 A. Starategi Menentukan nilai Fungsi Fitness ............. II-9 2.4.4 Langkah-langkah penyelesaian dengan GA.................. II-11 BAB III. METODOLOGI PENELITIAN BAB IV. PENYELESAIAN VEHICLE ROUTING PROBLEM (VRP) MENGGUNAKAN ALGORITMA GENETIKA. 4.1 Contoh.................................................................................... IV-1 BAB V. KESIMPULAN DAN SARAN.................................................... V-1 5.1 Kesimpulan............................................................................ V-1 5.2 Saran ..................................................................................... V-1 DAFTAR PUSTAKA DAFTAR RIWAYAT HIDUP
xii
DAFTAR TABEL Tabel
Halaman
2.1 Klasifikasi Penentuan Jalur dan Penjadwalan Kendaraan...............
II-5
4.1 Data Kendaraan I untuk Jalur 1 Dian...............................................
IV-1
4.2 Data Kendaraan I untuk Jalur 2 Dian...............................................
IV-2
4.3 Data Kendaraan I untuk Jalur 3 Dian...............................................
IV-2
4.4 Data Kendaraan I untuk Jalur 4 Dian...............................................
IV-3
4.5 Data Kendaraan I untuk Jalur 5 Dian...............................................
IV-3
4.6 Data Kendaraan II untuk Jalur 1 SMPN..........................................
IV-5
4.7 Data Kendaraan II untuk Jalur 2 SMPN..........................................
IV-6
4.8 Data Kendaraan II untuk Jalur 3 SMPN..........................................
IV-6
4.9 Data Kendaraan II untuk Jalur 4 SMPN..........................................
IV-7
4.10 Data Kendaraan II untuk Jalur 5 SMPN..........................................
IV-7
4.11 Data Kendaraan II untuk Jalur 6 SMPN..........................................
IV-8
xiv
DAFTAR SIMBOL i
: Indeks titik awal
j
: Indeks titik tujuan
v
: Indeks kendaraan
cij
: jarak dari titik i ke titik j
di
: Jumlah demand di titik i
Kv
: Kapasitas maksimum armada v
t iv
: Waktu yang dibutuhkan armada v pada titik i
t ijv
: Waktu tempuh yang dibutuhkan armada v untuk berangkat dari titik i menuju titik j
Tv
: Total waktu maksimum dari armada untuk menempuh sebuah rute
n
: Total jumlah titik yang ada
NV
: Total jumlah armada yang tersedia
x v ij = 1 : Armada v yang berangkat dari titik i menuju titik j x v ij = 0 : Armada v tidak berangkat dari titik i menuju titik j ,B
: Konstanta yang ditentukan
xv
BAB I PENDAHULUAN 1.1 LATAR BELAKANG Transportasi merupakan salah satu komponen yang sangat penting dalam sistem manajemen logistik. Peningkatan efisiensi dari sistem transportasi dapat dilakukan dengan memaksimalkan utilitas dari alat transportasi yang ada. Untuk mengurangi biaya transportasi dan juga untuk meningkatkan pelayanan terhadap para costumer, perlu dicari jalur atau rute terbaik, yang dapat meminimalkan jarak dan waktu. Permasalahan yang bertujuan untuk membuat suatu rute yang optimal, untuk sekelompok kendaraan, agar dapat melayani sejumlah konsumen, disebut sebagai Vehicle Routing Problems (VRP). Secara umum VRP dapat digambarkan sebagai permasalahan dalam mendesain rute dari suatu depot ke sekumpulan titik (kota, toko, gudang, sekolah, konsumen dan lain-lain) yang tersebar, dengan biaya termurah. Rute tersebut harus dibuat sedemikian rupa, sehingga setiap titik dikunjungi oleh tepat satu kendaraan, semua rute berawal dan berakhir di depot, dan total demand dari semua titik dalam sebuah rute tidak melebihi kapasitas dari kendaraan. Traveling Salesman Problem (TSP) merupakan sebuah permasalahan optimasi yang dapat diterapkan pada berbagai kegiatan seperti routing dan penjadwalan produksi. Masalah optimasi TSP terkenal dan telah menjadi standar untuk mencoba algoritma yang komputational. Pokok permasalahan dari TSP adalah seorang salesman harus mengunjungi sejumlah kota yang diketahui jaraknya satu dengan yang lainnya. Semua kota yang ada harus dikunjungi oleh salesman tersebut dan kota tersebut hanya boleh dikunjungi tepat satu kali. Permasalahannya adalah bagaimana salesman tersebut dapat mengatur rute perjalanannya sehingga jarak yang ditempuhnya merupakan jarak minimum.
Terdapat perbedaan yang sangat berarti antara VRP dan TSP. VRP menggunakan banyak kendaraan untuk menyelesaikan permasalahan perjalanan sedangkan TSP seorang salesman melakukan perjalanan menuju kota untuk menyelesaikan permasalahan perjalanan. VRP merupakan suatu permasalahan penting yang terdapat pada sistem transportasi yang bertujuan meminimalkan total jarak tempuh supaya biaya pengoperasian
kendaraan
minimal.
VRP
termasuk
ke
dalam
kelas
Nondeterministic Polynomial-Hard (NPH) artinya parameter yang mempengaruhi sangat kompleks dan penyelesaiannya tidak dapat diselesaikan dengan sebuah algoritma linier saja, karena membutuhkan waktu yang sangat lama, yang pada umumnya menggunakan pendekatan heuristik untuk mencari solusinya. Pendekatan yang digunakan dalam penelitian tugas akhir ini adalah algoritma genetika. Algoritma genetika ditemukan oleh John Holland pada tahun 1960. Algoritma ini menerapkan suatu proses evolusi biologi. Banyak percobaan dalam menyelesaikan VRP dengan menggunakan metode algoritma genetika, tetapi masih terdapat beberapa percobaan yang menghasilkan solusi yang tidak layak. Ketidak layakan dari solusi dapat dihindari dengan menggunakan suatu skema yang menjelaskan permasalahan kasus VRP dengan baik dan lebih terstruktur. Banyak metode digunakan untuk penyelesaian VRP, salah satunya adalah dengan Algoritma Genetika/Genetic Algorithms (GA), yaitu sebuah teknik pencarian yang berusaha meniru operasi-operasi genetika alami. GA secara simultan dapat mengevaluasi banyak titik yang ada dalam ruang lingkup parameter penelitian secara sekaligus dan kemudian mengarahkannya menuju Global Optimum Solution (solusi optimum untuk keseluruhan ruang lingkup parameter penelitian). Evaluasi ini dapat digunakan untuk persoalan yang menggunakan banyak fungsi tujuan (multi objektif). Selain itu GA dapat
I-2
diprediksi waktu siklus untuk simulasi (dengan bantuan komputer) dalam hitungan jam menjadi menit bahkan detik saja. Algoritma genetika merupakan salah satu metode heuristik yang analognya dengan proses evolusi alam dengan tahap seleksi, crossover dan mutasi. Berdasarkan latar belakang di atas, maka saya tertarik melakukan penelitian dengan judul “PENYELESAIAN VEHICLE ROUTING PROBLEM (VRP) MENGGUNAKAN ALGORITMA GENETIKA”.
1.2 PERUMUSAN MASALAH Permasalahan yang dikaji dalam tugas akhir ini adalah bagaimana menyelesaikan Vehicle Routing Problem (VRP) menggunakan Algoritma Genetika sehingga diperoleh solusi yang mendekati optimal dengan tidak mengabaikan batasan-batasan yang ada. 1.3 BATASAN MASALAH Batasan masalah yang digunakan dalam penyelesaian tugas akhir ini adalah sebagai berikut: a. Kapasitas angkut kendaraan seragam. b. Sejumlah kendaraan pada depot selalu tersedia dan dapat digunakan. c. Data permintaan customer telah ditentukan sebelumnya. d. Titik lokasi berdasarkan koordinat kartesian (jarak antar titik). e. Kecepatan kendaraan berbeda. f. Kemacetan lalu lintas pada lintasan yang diperoleh tidak diabaikan. g. Struktur jalan menjadi salah satu penghambat. h. Kendaraan hanya mengantar pesanan costumer. Proses penyelesaiannya, diasumsikan bahwa jarak berbanding lurus dengan biaya yang dikeluarkan, sehingga jarak yang minimal mewakili biaya yang minimal.
I-3
1.4 TUJUAN DAN MANFAAT 1.4.1Tujuan Penelitian Tujuan yang ingin dicapai pada penelitian ini adalah mendapatkan solusi optimal VRP dengan menggunakan algoritma genetika.
1.4.2Manfaat Penelitian Hasil akhir penelitian diharapkan dapat memberikan manfaat sebagai berikut. 1. Penulis dapat menambah pengetahuan tentang konsep-konsep teori Algoritma Genetika
dan
VRP,
sehingga
dapat
mengaplikasikannya
untuk
mempresentasikan suatu masalah yang terdapat dalam kehidupan nyata (real life). 2. Penelitian ini dapat menjadikan suatu kegiatan pengembangan wawasan keilmuan khususnya dalam bidang matematika tentang Algoritma Genetika untuk menyelesaikan masalah VRP.
1.5 SISTEMATIKA PENULISAN Sistematika dalam pembuatan tulisan ini mencakup lima bab yaitu : BAB I
Pendahuluan Bab ini berisi latar belakang masalah, rumusan masalah, tujuan masalah, dan sistematika penulisan
BAB II
Landasan Teori Bab ini berisi informasi tentang VRP dan Algoritma Genetika yang digunakan dalam penulisan ataupun metode yang dipakai.
BAB III
Metodologi Penelitian
I-4
Bab ini berisikan langkah-langkah dalam menyelesaikan VRP dengan menggunakan Algoritma Genetika. BAB IV
Pembahasan dan Analisa Bab ini berisikan penyelesaian VRP dengan menggunakan Algoritma Genetika.
BAB V
Penutup Bab ini berisikan kesimpulan dan saran.
I-5
BAB II LANDASAN TEORI Landasan teori yang digunakan penulis dalam penyusunan tugas akhir yang berjudul “Penyelesaian Vehicle Routing Problem (VRP) Menggunakan Algoritma Genetika” adalah sebagai berikut: 2.1 GRAF Definisi 2.1 (Munir, Rinaldi : 2003) Graf G didefinisikan sebagai pasangan himpunan (V ,E), ditulis dengan notasi G = (V , E ) , yang dalam hal ini V adalah himpunan tidak kosong dari simpul-simpul (vertex atau node) dan E adalah himpunan sisi (edge atau arcs) yang menghubungkan sepasang simpul. Contoh 2.1 Graf Sederhana:
1
2
3
4
Gambar 2.1 Graf sederhana Graf sederhana di atas adalah graf dengan himpunan simpul V dan sisi E adalah:
V = {1,2,3,4} , E = { (1,2 ) , (1,3) , ( 2,3) , ( 2,4 ) , ( 3,4 )} .
2.1.1
Beberapa Istilah yang Berkaitan dengan Graf
a.
Loop Suatu sisi yang menghubungkan suatu simpul dengan dirinya sendiri.
b.
Lintasan Definisi 8.7 (Munir, Rinaldi : 2003) Lintasan yang panjangnya n dari simpul awal v 0 ke simpul tujuan v n di dalam graf G ialah barisan berselang seling simpul-simpul dan sisi sisi.
c.
Lintasan tertutup atau sirkuit Lintasan tertutup atau sirkuit adalah Lintasan yang berawal dan berakhir pada simpul yang sama. Istilah-istilah di atas dalam Algoritma Genetika simpul- simpul (Vertex)
disebut juga Gen, sisi ( edge) disebut juga Individu, lintasan disebut juga jalur / Kromosom 2.2 VEHICLE ROUTING PROBLEM
Permasalahan dalam proses pendistribusian barang yang bertujuan untuk membuat suatu jalur yang optimal, untuk sekelompok kendaraan yang diketahui kapasitasnya, agar dapat memenuhi pesanan costumer dengan lokasi dan permintaan yang telah diketahui, disebut Vehicle Routing Problem (VRP). Adapun tujuan dari mendesain jalur kendaraan ini adalah untuk meminimasi beberapa fungsi obyektif seperti meminimasi jumlah armada yang digunakan dan mminimasi total jarak atau waktu perjalanan yang ditempuh. Secara khusus, solusi dari VRP adalah menentukan sekelompok jalur perjalanan di mana setiap jalur dilewati oleh sebuah kendaraan yang berawal dari depot dan berakhir pada depot itu pula sehingga semua permintaan costumer dan seluruh kendala operasionalnya terpenuhi dengan biaya transportasi yang seminim mungkin. Beberapa komponen yang terdapat pada VRP, yaitu vehicle, costumer, depot, pengemudi, dan faktor-faktor yang lain.
2.2.1Model Vehicle Routing Problem (VRP) VRP dapat didefinisikan sebagai permasalahan perancangan jalur kendaraan pengiriman yang diketahui kapasitasnya, beroperasi dari satu depot
II-2
untuk memberikan supply pada sekumpulan pelanggan dengan lokasi dan permintaan yang telah diketahui dengan satu atau beberapa komoditi barang yang sudah pasti. Sam R. Tangiah (1995) membuat suatu formulasi Mixed-integer Programing dari permasalahan VRP ini. Parameter dan variabel yang digunakan dalam formulasi tersebut antara lain: Rumus: Model mixed-integer programing: Fungsi tujuan: n
n
Min ∑
NV
∑∑
i= 1 j = 1 v= 1
cij x v ij
(2.1)
Kendala-kendala: n
NV
∑∑
xijv = 1
( j = 2,..., n)
(2.2)
xijv = 1
(i = 2,..., n)
(2.3)
(v = 1,..., NV ; p = 1,..., n)
(2.4)
(v = 1,..., NV )
(2.5)
t ijv xijv ≤ Tv (v = 1,..., NV )
(2.6)
x1vj ≤ 1
(v = 1,..., NV )
(2.7)
xiv1 ≤ 1
(v = 1,..., NV )
(2.8)
untuk semua i, j , v
(2.9)
i= 1 v= 1 n
NV
∑∑
j = 1 v= 1 n
∑
j= 1 n
∑
i= 1 n
∑
i= 1 n
∑
j= 2 n
∑
i= 2
n
∑
xipv −
v= 1
n
∑
di
j= 1
n
x vpj = 0
xijv ≤ K v
t iv ∑ xijv + j= 1
n
n
∑∑
i= 1 j = 1
xijv = 0 atau 1 ;
dengan : i
adalah indeks titik awal
II-3
j adalah indeks titik tujuan v adalah indeks kendaraan p
adalah indeks demand titik
cij adalah jarak dari titik i ke titik j d i adalah jumlah demand di titik i K v adalah kapasitas maksimum armada v t iv adalah waktu yang dibutuhkan armada v pada titik i t ijv adalah waktu tempuh yan dibutuhkan armada v untuk berangkat dari titik i menuju titik j Tv adalah total waktu maksimum dari armada untuk menempuh sebuah jalur n adalah total jumlah titik yang ada NV adalah total jumlah armada yang tersedia
x v ij = 1 adalah armada v yang berangkat dari titik i menuju titik j x v ij = 0 adalah armada v tidak berangkat dari titik i menuju titik j Persamaan (2.2) dan (2.3) menunjukkan setiap demand titik hanya dipenuhi/dilayani oleh tepat satu armada. Persamaan (2.4) menunjukkan bahwa jika sebuah armada memasuki sebuah demand titik, maka armada tersebut harus keluar dari tiitk tersebut ( p = indeks demand titik). Persamaan (2.5) menunjukkan bahwa jumlah demand dari tiap demand titik yang dikunjungi suatu armada tidak boleh melebihi kapasitas armada tersebut. Persamaan (2.6) menunjukkan bahwa jumlah total waktu unoading dan total waktu tempuh dari armada v tidak boleh melebihi total waktu maksimum untuk menempuh sebuah jalur dari armada v. Persamaan (2.7) dan (2.8) menjamin bahwa ketersediaan armada v tidak melebihi jumlah armada v yang tersedia. Persamaan (2.9) menjamin bahwa tiap armada tidak ditugaskan untuk melayani lebih dari satu jalur.
II-4
2.3
JALUR DAN PENJADWALAN Jalur dan penjadwalan kendaraan diklasifikasikan berdasarkan beberapa
karakteristik. Karakteristik tersebut digunakan untuk membantu menganalisa dan mengidentifikasi jenis dari permasalahan. Algoritma-algoritma yang ada dapat diterapkan untuk penyelesaian permasalahan sesuai dengan karakteristikkarakteristik tersebut. Secara garis besar klasifikasi tersebut adalah sebagai berikut ( Bodin L; 1983): Tabel 2.1 Klasifikasi Penentuan Jalur dan Penjadwalan Kendaraan No 1
2
Karakteristik Ukuran armada kendaraan yang tersedia
Jenis Armada kendaraan yang tersedia
• • • • •
3
Penempatan Kendaraan
4
Sifat Permintaan
5
Lokasi Demand
• • • • • • • • •
6
Keterbatasan kapasitas kendaraan
•
• • •
7
Waktu Jalur Maksimal
8
Operasi
• • • •
Pilihan yang Mungkin Satu kendaraan Banyak kendaraan Sejenis (hanya satu jenis kendaraan) Heterogen ( jenis kendaraan banyak) Khusus (jenis kendaraan dikelompokkan) Depot tunggal Depot banyak Determinasik Stokastik/probabilitas Memilih permintaan yang disukai Pada node Pada busur/arc Kombinasi pada node dan busur Memaksakan (sama untuk semua jalur Memaksakan ( berbeda untuk jalur-jalur yang berbeda) Tidak membatasi ( kapasitas tidak terbatas) Dibatasi (sama untuk semua jalur) Dibatasi ( berbeda untuk jalur yang berbeda) Tidak membatasi (kapasitas tidak terbatas). Hanya menjemput (mengambil, membawa) Hanya pengantaran Kombinasi (pengantaran dan penjemputan
II-5
•
9
Biaya
• • • • • •
10
Tujuan
• • •
Membagi pengiriman ( menerima atau menolak) Biaya variabel atau routing Biaya-biaya tambahan operasi tetap atau kendaraan Biaya-biaya karena permintaan tidak dilayani Meminimalkan total biaya perjalanan Menimbulkan jumlah dari biayabiaya tetap dan variabel Meminimalkan jumlah kendaraan yang dibutuhkan Meminimalkan total jarak/waktu yang ditempuh kendaraan Memaksimalkan utilitasi fungsi yang didasarkan pada pelayanan atau waktu yang sebaik-baiknya Memaksimalkan utilisasi fungsi yang didasarkan pada prioritas costumer...
Terdapat dua pendekatan yang digunakan dalam memecahkan masalah jalur dan penjadwalan kendaraan, yaitu metode optimal/eksak dan heuristik. 2.3.1Metode Optimal/Eksak Pendekatan ini menggunakan metode-metode dari program linier atau integer programing yang didasarkan pada pemrograman matematis. Metode pendekatan ini akan diperoleh suatu solusi yang optimal, Tetapi metode pendekatan ini hanya baik jika permasalahan yang dihadapi kecil. Sedangkan untuk permasalahan yang melibatkan jumlah input data yang besar, metode penyelesaian ini terhitung menjadi tidak efesien karena penyelesainannya membutuhkan waktu komputasi yang lama. 2.3.2Metode Heuristik
Metode Heuristik adalah suatu metode yang menggunakan sistem pendekatan dalam melakukan pencarian dalam optimasi Pendekatan heuristik menggunakan suatu algoritma yang secara interaktif akan menghasilkan solusi
II-6
yang akan mendekati optimal. Pendekatan heuristik menghasilkan perhitungan yang cepat karena dilakukan dengan membatasi pencarian dengan mengurangi jumlah alternatif yang ada. Pendekatan heuristik lebih dapat diterapkan ke permasalahan nyata dimana permasalahan melibatkan jumlah input yang besar. Ada beberapa algoritma pada metode heuristik yang biasa digunakan dalam permasalahan
optimasi,
diantaranya
Algoritma
Genetika,
Ant
Colony
Optimization, logika Fuzzy, jaringan syaraf tiruan, Tabu Search, Simulated Annealing, dan lain-lain. 2.4 ALGORITMA GENETIKA Algoritma genetik (GA) merupakan suatu metode heuristik untuk mencari solusi optimum dari suatu permasalahan dengan menggunakan mekanisme pencarian yang meniru proses evolusi biologis. Mekanisme yang digunakan merupakan kombinasi dari pencarian acak dan terstruktur. Algoritma ini sudah berhasil diterapkan dalam berbagai permasalahan kombinatorial, mulai dari Travelling Salesman Problem (VRP),
Vehicle Routing Problem ( VRP),
permasalahan penentuan layout, dan penjadwalan produksi. Dalam algoritma genetika solusi yang dterapkan pada sebuah populasi individu-individu yang masing-masing mewakili solusi yang mungkin disebut dengan kromosom, yang ditunjukkan dengan sekumpulan simbol dalam bentuk string dengan panjang tertentu dan biasanya dari alphabet biner (0,1). Dalam algoritma genetika ada istilah populasi, individu, kromosom, gen, fitness, Pengertian populasi adalah sejumlah solusi yang mungkin. Populasi awal dibangun secara acak, sedangkan populasi berikutnya merupakan hasil evolusi kromosom-kromosom melalui iterasi yang disebut dengan generasi. Individu adalah sekumpulan gen dalam sistem algoritma genetika bisa dikatakan sama dengan kromosom. Generasi adalah individu yang dilakukan untuk menentukan populasi berikutnya.
II-7
2.4.1Individu Algoritma Genetika Individu merupakan kumpulan dari gen. Gen ini bisa biner, float, dan kombinaturial. Individu dalam GA dapat juga menyatakan salah satu kemungkinan solusi yang dicari. Misalkan dalam VRP individu dapat menyatakan suatu jalur terpendek yang akan ditempuh. Definisi individu pada kasus VRP yaitu sebagai berikut: 1. VRP (Vehicle Routing Problem) adalah suatu permasalahan dimana seorang pekerja depot harus mengunjungi N kota dengan jarak yang paling pendek, dengan syarat satu kota hanya dikunjungi satu kali. 2. Solusi VRP adalah jalur yang melewati semua kota dan jaraknya paling pendek. 3. Individu untuk VRP didefinisikan sebagai jalur atau urutan nomor kota yang dikunjungi. Misalkan untuk 10 kota salah satu jalur yang mungkin adalah : 1-2-3-4-5-6-7-8-9-10
4 3 5 2
1 6
7
10 9 8
Gambar 2.2 Individu pada Vehicle Routing Problem
II-8
2.4.2KROMOSOM Kromosom adalah individu yang terdapat dalam satu populasi. Kromosom juga merupakan gabungan gen-gen yang membentuk nilai tertentu. Representasi pengkodean yang digunakan pada algoritma genetika adalah representasi kuncikunci random. Representasi ini mengkodekan sebuah gen dengan membangkitkan bilangan acak antara (0,1) . Nilai acak dalam posisi i menentukan urutan didatanginya kota dalam lintasan VRP. Contoh dari lintasan VRP dapat dilihat pada gambar berikut:
Gambar 2.3 Lintasan VRP Gambar 2.3 di atas merupakan contoh sederhana suatu VRP dengan 2 Vehicle. Ada 1 depot dan 12 node yang setelah di solve maka diperoleh dua jalur yang total jaraknya paling minimum yaitu jalur 1: depot -1-2-3-4-6-depot adalah Kromosom I dan jalur 2: depot-12-11-10-9-8-7-5-depot adalah Kromosom II. 2.4.3FUNGSI FITNESS
Fungsi fitness digunakan untuk proses evaluasi kromosom agar memperoleh kromosom yang diinginkan. Fungsi ini membedakan kualitas dari kromosom untuk mengetahui seberapa baik kromosom yang dihasilkan. A. Strategi menentukan nilai fungsi fitness
II-9
Strategi dalam menentukan nilai fungsi fitness dapat dilakukan dengan cara: 1. Nilai fitness merupakan suatu ukuran baik tidaknya suatu solusi yang dinyatakan sebagai satu individu, atau dengan kata lain nilai fitness menyatakan nilai dari fungsi tujuan. 2. Algoritma genetika mempunyai tujuan untuk memaksimalkan nilai fitness atau mencari nilai fitness maksimal. Kriteria yang digunakan pada proses seleksi ini adalah kriteria fungsi fitness. Masing-masing jalur pada populasi awal dihitung jarak, nilai fitness, probabilitas
fitness
dan
probabilitas
kumulatif
fitnessnya.
Tahap-tahap
perhitungan fitnessnya adalah sebagai berikut: 1. Mencari jarak tempuh tiap jalur ( Z i ) 2. Mencari total jarak dari seluruh jalur (
N
∑
i= 1
Zi )
3. Mencari nilai fitness tiap jalur ( f i ) N
fi =
∑
Zi
i= 1
(2.10)
Zi
4. Mencari total fitness (
N
∑
i= 1
fi )
5. Mencari probabilitas tiap jalur ( p i )
pi =
fi N
∑
i= 1
(2.11)
fi
6. Mencari probabilitas kumulatif tiap jalur (q i )
qi =
i
∑
k= 1
pi
Selanjutnya pemilihan sebuah jalur yang
(2.12) menghasilkan
populasi
berikutnya dilakukan dengan cara mengambil N buah bilangan random r dengan
II-10
0 < r < 1 dan membandingkan bilangan random tersebut dengan probabilitas
kumulatif fitness tiap jalur. 2.4.4
Langkah-langkah Penyelesaian dengan Algoritma Genetika Misalkan P (generasi) adalah populasi dari satu generasi, maka secara
sederhana GA terdiri dari langkah-langkah: a. [Start ]Generasi=0
b. Inisialisasi populasi awal, secara acak. c. [Fitness] Lakukan pencarian nilai fitness dan Probabilitas pada setiap
kromosom. d.
[Replace] Lakukan pengulangan proses sebanyak kromosom dalam populasi
e. [selection] Bandingkan semua nilai probabilitas hingga di dapat nilai yang
terkecil. f.
[Test] jika kondisi akhir dipenuhi maka berhenti dan tampilkan solusi dari populasi.
II-11
BAB III METODOLOGI PENELITIAN
Metodologi penelitian yang penulis gunakan adalah studi literatur yang bersumber dari buku, jurnal dan artikel. Dengan langkah-langkah sebagai berikut: 1). Memahami Vehicle Routing Problem 2). Memahami Algoritma Genetika 3). Menentukan Jarak terpendek menggunakan Algoritma Genetika 4). Menentukan Waktu terkecil menggunakan Algoritma Genetika Langkah-langkah metodologi penelitian di atas dapat digambarkan dalam Flowchart berikut ini: Mulai Metode VRP
Algoritma Genetika
Selesaikan VRP dengan menggunakan Algoritma Genetika 1. 2. 3. 4. 5. 6. 7.
Pilih kendaraan Tetapkan Populasi Pilih Kromosom Lakukan Pencarian nilai Fitness Nilai Probabilitas komulatif Seleksi nilai terkecil probabilitas waktu terkecil Hasil
Selesai
Pilih r
Gambar 3.1 Flowchart Metodologi Penelitian
III-2
BAB IV PENYELESAIAN VEHICLE ROUTING PROBLEM (VRP) MENGGUNAKAN ALGORITMA GENETIKA Berdasarkan uraian dari landasan teori pada Bab II, maka pada bab ini akan dibahas penulis tentang proses dan beberapa teori pendukung untuk penyelesaian Vehicle Routing Problem (VRP) menggunakan Algoritma Genetika. Contoh: Misalkan Dua (2) unit Sepeda Motor
(Honda Supra X dan Honda
Kharisma) yang akan Mengantarkan Air Galon pesanan ke Pelanggan. Pelanggan yang dikunjungi oleh II kendaraan tersebut berjumlah 2 orang (A,B). Pelanggan A adalah Toko Dian Rahayu alamatnya adalah Jl. Geriliya No. 15 dan Pelanggan B adalah SMPN 3 Tembilahan alamatnya adalah Jl. Tanjung Harapan No. 38. Angkutan dari masing-masing kendaraan adalah sama yaitu sebanyak 6 galon. Kendaraan 1 membawa 6 buah air galon menuju ke Pelanggan A dan Kendaraan 2 membawa 6 buah air galon menuju ke pelanggan B dimana di ketahui jarak tempuh dari jalur satu ke jalur berikutnya dan kecepatan rata-rata kendaraan. Data dari perjalanan kendaraan I dan II tersebut dapat dikelompokkan sebagai berikut: Tabel 4.1 Data kendaraan I untuk jalur 1 Dian No 1 2 3 4 5
Costumer/pelanggan Jl. Abdul Manaf (Depot Air Asmira – Toko Barkat ) Jl. H. Arif ( Toko Barkat – Lapangan Tennis) Jl. Kayu Jati ( Lapangan Tennis – Kelenteng Cina) Jl. Saptamarga (Kelenteng Cina – SMAN 2 Tembilahan) Jl. Pelita Jaya ( SMAN 2 Tembilahan – Gudang Bulog)
Jarak
Kecepatan
(Meter)
(Km/Jam)
700 M
30 Km/Jam
650 M
50 Km/Jam
750 M
45 Km/Jam
800 M
50 Km/Jam
700 M
55 Km/Jam
6
Jl. Geriliya (Gudang Bulog- Rumah/Toko Dian Rahayu )
1100 M
35 Km/Jam
Jarak
Kecepatan
(Meter)
(Km/Jam)
Tabel 4.2 Data kendaraan I untuk jalur 2 Dian No 1
Costumer/pelanggan Jl. Abdul Manaf (Depot Air Asmira – Toko
700 M
30 Km/Jam
3
Barkat ) Jl. H. Arif ( Toko Barkat – Lapangan Tennis) Jl. Perintis ( Lapangan tennis – Tk Pertiwi)
650 M 1350 M
50 Km/Jam 35 Km/Jam
4
Jl. Hasan Gani ( Tk Pertiwi – Gudang Bulog)
1270 M
35 Km/Jam
1100 M
35 Km/Jam
Jarak
Kecepatan
(Meter)
(Km/Jam)
700 M
30 Km/Jam
650 M 1350 M
50 Km/Jam 35 Km/Jam
1900 M
40 Km/Jam
2450 M
40 Km/Jam
700 M
35 Km/Jam
Jarak
Kecepatan
(Meter)
(Km/Jam)
2100 M
45 Km/Jam
1900 M 1270 M
40 Km/Jam 35 Km/Jam
2
5
Jl. Geriliya (Gudang Bulog- Rumah/Toko Dian Rahayu )
Tabel 4.3 Data kendaraan I untuk jalur 3 Dian No 1 2 3 4 5 6
Costumer/pelanggan Jl. Abdul Manaf (Depot Air Asmira – Toko Barkat) Jl. H. Arif (Toko Barkat – Lapangan Tennis) Jl. Perintis (Lapangan tennis – Tk Pertiwi) Jl. Manggis (Tk Pertiwi - Simp Pelajar) Jl. Suhada (Simp. Jl Pelajar – Pondok Indragiri) Jl. Geriliya (Pondok Indragiri – Rumah/Toko Dian Rahayu)
Tabel 4.4 Data kendaraan I untuk jalur 4 Dian No 1 2 3
Costumer/pelanggan Jl.Telaga Biru (Depot Air Asmira – Simp. Jl Pelajar) Jl. Manggis ( Simp Pelajar – Tk Pertiwi) Jl. Hasan Gani ( Tk Pertiwi – Gudang Bulog)
IV-2
Jl. Geriliya (Gudang Bulog- Rumah/Toko
4
Dian Rahayu )
1100 M
35 Km/Jam
Jarak
Kecepatan
(Meter)
(Km/Jam)
2100 M
45 Km/Jam
2450 M
40 Km/Jam
700 M
35 Km/Jam
Tabel 4.5 Data kendaraan I untuk jalur 5 Dian No
Costumer/pelanggan Jl.Telaga Biru (Depot Air Asmira – Simp. Jl
1
Pelajar) Jl. Suhada (Simp. Jl Pelajar – Pondok
2
Indragiri) Jl. Geriliya ( Pondok Indragiri –
3
Rumah/Toko Dian Rahayu)
Untuk Kendaraan I akan melalui jalur Dian 1, 2, 3, 4, dan 5 karena pelanggan / costumer berada pada jalur Dian 1, 2, 3, 4, dan 5. Simpul atau titiktitik kota dilambangkan dengan A, A1 , A2 , A3 , A4 , A5 , A6 , A7 , A8 . Dapat dilihat pada gambar 4.1 berikut:
A 1100 M
A4 700M A5
35Km / Jam
35Km / Jam700M
55Km / Jam
A8
800 M 50 Km / Jam
A3
35Km / Jam 1270 M
750 M
A7
45Km / Jam 1350 M
A1
650M
A2
35Km / Jam
50 Km / Jam
40 Km / Jam 2450 M
40 Km / Jam 1900 M
A6 700M
30 Km / Jam
Depot
45 Km / Jam 2100 M
IV-3
Gambar 4.1 Jalur Kendaraan I Keterangan: A
= Jl Geriliya / Toko Dian Rahayu
Depot = Depot air asmira tembilahan A1
= Jl. Abdul Manaf
A2
= Jl. H. Arif
A3
= Jl. Kayu Jati
A4
= Jl. Saptamarga
A5
= Jl. Pelita Jaya
A6
= Jl.Telaga Biru
A7
= Jl. Manggis
A8
= Jl. Suhada
Berdasarkan gambar 4.1, dapat dilihat bahwa kromosom pada jalur yang dilalui oleh kendaraan I adalah: Kromosom 1/Jalur Dian 1: Depot − A1 − A2 − A3 − A4 − A5 − A / Abdul Manaf – H. Arif – Kayu Jati – Sapta Marga – Pelita Jaya – Geriliya. Kromosom 2/Jalur Dian 2: Depot − A1 − A2 − A7 − A5 − A / Abdul Manaf – H. Arif – Perintis – Hasan Gani – Geriliya.
IV-4
Kromosom 3/Jalur Dian 3: Depot − A1 − A2 − A7 − A6 − A8 − A / Abdul Manaf – H. Arif –Perintis – Manggis – Suhada - Geriliya. Kromosom 4/Jalur Dian 4: Depot − A6 − A7 − A5 − A / Telaga Biru – Manggis – Hasan Gani - Geriliya. Kromosom 5/Jalur Dian 5 : Depot − A6 − A8 − A / Telaga Biru – Suhada – Geriliya. Selanjutnya akan diringkas data untuk kendaraan II, adalah sebagai berikut: Tabel 4.6 Data kendaraan II untuk jalur 1 SMPN No 1 2 3 4
Costumer/pelanggan Jl. Batang Tuaka (Depot Air Asmira - Planet Futsal) Jl. Gunung Daek (Planet Futsal – Mesjid Raudhah) Jl. Telaga Biru II (Mesjid Raudhah – Hotel Telaga Puri) Jl. Tanjung Harapan (Hotel TeLaga Puri – SMPN 3 Tembilahan)
Jarak
Kecepatan
(Meter)
(Km/Jam)
1450 M
40 Km/Jam
1510 M
35 Km/Jam
1530 M
40 Km/Jam
2270 M
30 Km/Jam
Jarak
Kecepatan
(Meter)
(Km/Jam)
1450 M
40 Km/Jam
1510 M
35 Km/Jam
1370 M
40 Km/Jam
Tabel 4.7 Data kendaraan II untuk jalur 2 SMPN No 1 2 3
Costumer/pelanggan Jl. Batang Tuaka (Depot Air Asmira - Planet Futsal) Jl. Gunung Daek (Planet Futsal – Mesjid Raudhah) Jl. Swarna Bumi (Mesjid Raudhah – MTSN Tembilahan)
IV-5
4 5 6
Jl. Cahaya (MTSN Tembilahan – Stadion Lapangan Bola) Jl. Telaga Biru II (Stadion Lapangan Bola – Simp 4 tanjung Harapan) Jl. Tanjung Harapan (Simp 4 Tanjung Harapan – SMPN 3 Tembilahan)
1250 M
35 Km/Jam
930 M
45 Km/Jam
1360 M
50 Km/Jam
Jarak
Kecepatan
(Meter)
(Km/Jam)
560 M
30 Km/Jam
2010 M
40 Km/Jam
1370 M
40 Km/Jam
1530 M
40 Km/Jam
2270 M
30 Km/Jam
Jarak
Kecepatan
(Meter)
(Km/Jam)
560 M
30 Km/Jam
2010 M
40 Km/Jam
1250 M
35 Km/Jam
930 M
45 Km/Jam
1360 M
50 Km/Jam
Tabel 4.8 Data kendaraan II untuk jalur 3 SMPN No 1 2 3 4 5
Costumer/pelanggan Jl. Ahmad Yani (Depot Air Asmira – Simp 4 Lampu Merah) Jl. Malagas (Simp 4 Lampu Merah – MTSN Tembilahan) Jl. Swarna Bumi (Mesjid Raudhah – MTSN Tembilahan) Jl. Telaga Biru II (Mesjid Raudhah – Hotel Telaga Puri) Jl. Tanjung Harapan (Hotel TeLaga Puri – SMPN 3 Tembilahan)
Tabel 4.9 Data kendaraan II untuk jalur 4 SMPN No 1 2 3 4 5
Costumer/pelanggan Jl. Ahmad Yani (Depot Air Asmira – Simp 4 Lampu Merah) Jl. Malagas (Simp 4 Lampu Merah – MTSN Tembilahan) Jl. Cahaya (MTSN Tembilahan – Stadion Lapangan Bola) Jl. Telaga Biru II (Stadion Lapangan Bola – Simp 4 tanjung Harapan) Jl. Tanjung Harapan (Simp 4 Tanjung Harapan – SMPN 3 Tembilahan)
IV-6
Tabel 4.10 Data kendaraan II untuk jalur 5 SMPN No 1 2 3 4 5
Costumer/pelanggan Jl. Ahmad Yani (Depot Air Asmira – Simp 4 Lampu Merah) Jl. M. Boya (Simp 4 Lampu Merah – Pasar Pagi) Jl. Telaga Biru (Pasar Pagi – Stadion Lapangan Bola) Jl. Telaga Biru II (Stadion Lapangan Bola – Simp 4 tanjung Harapan) Jl. Tanjung Harapan (Simp 4 Tanjung Harapan – SMPN 3 Tembilahan)
Jarak
Kecepatan
(Meter)
(Km/Jam)
560 M
30 Km/Jam
1020 M
40 Km/Jam
2160 M
50 Km/Jam
930 M
45 Km/Jam
1360 M
50 Km/Jam
Jarak
Kecepatan
(Meter)
(Km/Jam)
560 M
30 Km/Jam
1020 M
40 Km/Jam
2160 M
50 Km/Jam
1250 M
35 Km/Jam
1370 M
40 Km/Jam
1530 M
40 Km/Jam
2270 M
30 Km/Jam
Tabel 4.11 Data kendaraan II untuk jalur 6 SMPN No 1 2 3 4 5 6 7
Costumer/pelanggan Jl. Ahmad Yani (Depot Air Asmira – Simp 4 Lampu Merah) Jl. M. Boya (Simp 4 Lampu Merah – Pasar Pagi) Jl. Telaga Biru (Pasar Pagi – Stadion Lapangan Bola) Jl. Cahaya (MTSN Tembilahan – Stadion Lapangan Bola) Jl. Swarna Bumi (Mesjid Raudhah – MTSN Tembilahan) Jl. Telaga Biru II (Mesjid Raudhah – Hotel Telaga Puri) Jl. Tanjung Harapan (Hotel TeLaga Puri –
IV-7
SMPN 3 Tembilahan) Kendaraan II akan melalui jalur 1, 2, 3, 4, 5 dan 6 SMPN
karena
pelanggan yang memesan air galon pada jalur 1, 2, 3, 4, 5 dan 6 SMPN. Simpul atau titik-titik kota dilambangkan dengan B, B1 , B2 , B3 , B4 , B5 , B6 , B7 , B8 . dapat dilihat pada gambar 4.2 berikut:
Depot 1450 M 40 Km / Jam
560 M 30 Km / Jam
B4
40 Km / Jam 2010M 1020 M
B5
35 Km / Jam1510 M
B7
40 Km / Jam
50 Km / Jam 1250 M
B1
40 Km / Jam 1370 M
B2
1530 M
40 Km / Jam
B3
35 Km / Jam
2160 M 30 Km / Jam
B6
45 Km / Jam 930 M
B8
2270 M 50 Km / Jam
1360 M
B Gambar 4.2 Jalur Kendaraan II Keterangan: B
= Jl. Tanjung Harapan / SMP Negeri 03 Tembilahan
IV-8
Depot = Depot air asmira tembilahan B1
= Jl. Batang Tuaka
B2
= Jl. Gunung Daek
B3
= Jl. Telaga Biru II
B4
= Jl. Ahmad Yani
B5
= Jl. M. Boya
B6
= Jl. Telaga Biru
B7
= Jl. Malagas
B8
= Jl. Telaga Biru II
Berdasarkan gambar 4.2 dapat dilihat bahwa kromosom pada jalur yang dilalui oleh pengendara II adalah: Kromosom 1/Jalur SMPN I: Depot − B1 − B2 − B3 − B / Batang Tuaka – Gunung Daek – Swarna Bumi – Cahaya – Telaga Biru II – Tanjung Harapan. Kromosom 2/Jalur SMPN 2: Depot − B1 − B2 − B7 − B6 − B8 − B / Ahmad Yani – Malagas – Swarna Bumi – Telaga Biru II – Tanjung Harapan.
Kromosom 3/Jalur SMPN 3:
Depot − B4 − B7 − B2 − B3 − B / Ahmad Yani –
Malagas – Cahaya – Telaga Biru II – Tanjung Harapan. Kromosom 4/Jalur SMPN 4: Depot − B4 − B7 − B6 − B8 − B / Ahmad Yani – M. Boya – Telaga Biru – Telaga Biru II – Tanjung Harapan. Kromosom 5/Jalur SMPN 5: Depot − B4 − B5 − B6 − B7 − B2 − B3 − B / Ahmad Yani – M. Boya – Telaga Biru – Cahaya – Swarna Bumi – Telaga Biru II – Tanjung Harapan.
IV-9
Kromosom 6/Jalur SMPN 6 : Depot − B4 − B5 − B6 − B8 − B / Ahmad Yani – M. Boya – Telaga Biru I – Telaga Biru II – Tanjung Harapan. Penyelesaian Berdasarkan data yang sudah diperoleh dan di ringkas maka dilakukan pencarian untuk jalur terpendek perjalanan kendaraan dengan cara: Kendaraan I: A. Generasi = 0 B. Populasi
Awal
yaitu
A − A1 − A2 − A3 − A4 − A5 − A6 − A7 − A8
didapat
Kromosom-kromosomnya adalah: Kromosom/Jalur I : Depot − A1 − A2 − A3 − A4 − A5 − A Kromosom/Jalur 2 : Depot − A1 − A2 − A7 − A5 − A Kromosom/Jalur 3 : Depot − A1 − A2 − A7 − A6 − A8 − A Kromosom/Jalur 4 : Depot − A6 − A7 − A5 − A Kromosom/Jalur 5 : Depot − A6 − A8 − A C. Nilai fitness dan probabilitas dari setiap Kromosom: a. Kromosom I (Jalur Dian 1), Depot − A1 − A2 − A3 − A4 − A5 − A / Abdul
Manaf – H. Arif – Kayu Jati – Sapta Marga – Pelita Jaya – Geriliya. 1). Jarak Tempuh tiap Jalur ( Z i ) A1
= 700 Meter
A4
= 2900 Meter
A2
= 1350 Meter
A5
= 3600 Meter
A3
= 2100 Meter
A
= 4700 Meter
N
2). Total jarak dari seluruh jalur (∑ Z i ) i= 1
= ( A1 + A2 + A3 + A4 + A5 + A ) = 700 + 1350 + 2100 + 2900 + 3600 + 4700
IV-10
= 15350 Meter 3). Nilai fitness tiap jalur ( f i ) N
fi =
∑
i= 1
Zi
Zi
f1 =
15350 = 21.93 700
fi =
15350 = 5.29 2900
f2 =
15350 = 11.37 1350
f5 =
15350 = 4.26 3600
f3 =
15350 = 7.31 2100
f6 =
15350 = 3.26 4700
N
4). Total fitness (∑ f i ) i= 1
= f1 + f 2 + f 3 + f 4 + f 5 + f 6 = 21.93 + 11.37 + 7.31 + 5.29 + 4.26 + 3.26 = 53.42 5). Probabilitas tiap jalur ( p i ) pi =
fi N
∑
i= 1
fi
p1 =
21.93 = 0.41 53.42
p4 =
5.29 = 0.09 53.42
p2 =
11.37 = 0.21 53.42
p5 =
4.26 = 0.07 53.42
p3 =
7.31 = 0.14 53.42
p6 =
3.26 = 0.06 53.42
6). Probabilitas kumulatif tiap jalur (q i ) qi =
N
∑
i= 1
pi
= p1 + p 2 + p3 + p 4 + p5 + p 6
IV-11
= 0.41 + 0.21 + 0.14 + 0.09 + 0.07 + 0.06 = 0.98 b. Kromosom II (Jalur Dian 2), Depot − A1 − A2 − A7 − A5 − A / Abdul
Manaf – H. Arif – Perintis – Hasan Gani – Geriliya. 1). Jarak Tempuh tiap Jalur ( Z i ) A1
= 700 Meter
A2
= 1350 Meter
A5
= 3970 Meter
A7
= 2700 Meter
A
= 5070 Meter
N
2). Total jarak dari seluruh jalur (∑ Z i ) i= 1
= ( A1 + A2 + A7 + A5 + A ) = 700 + 1350 + 2700 + 3970 + 5070 = 13790 Meter 3). Nilai fitness tiap jalur ( f i ) N
fi =
∑
i= 1
Zi
Zi
f1 =
13790 = 19.7 700
f4 =
13790 = 3.47 3970
f2 =
13790 = 10.21 1350
f5 =
13790 = 2.72 5070
f3 =
13790 = 5.11 2700 N
4). Total fitness (∑ f i ) i= 1
= f1 + f 2 + f 3 + f 4 + f 5 = 19.7 + 10.21 + 5.11 + 3.47 + 2.72 = 41.21 5). Probabilitas tiap jalur ( p i )
IV-12
pi =
fi N
∑
i= 1
fi
p1 =
19.7 = 0.48 41.21
p4 =
3.47 = 0.08 41.21
p2 =
10.21 = 0.24 41.21
p5 =
2.72 = 0.07 41.21
p3 =
5.11 = 0.12 41.21
6). Probabilitas kumulatif tiap jalur (q i ) = p1 + p 2 + p3 + p 4 + p5 = 0.48 + 0.24 + 0.12 + 0.08 + 0.07 = 0.99 c. Kromosom III (Jalur Dian 3), Depot − A1 − A2 − A7 − A6 − A8 − A / Abdul
Manaf – H. Arif –Perintis – Manggis – Suhada - Geriliya. 1). Jarak Tempuh tiap Jalur ( Z i ) A1
= 700 Meter
A6
= 4600 Meter
A2
= 1350 Meter
A8
= 7050 Meter
A7
= 2700 Meter
A
= 7750 Meter
N
2). Total jarak dari seluruh jalur (∑ Z i ) i= 1
= ( A1 + A2 + A7 + A6 + A8 + A ) = 700 + 1350 + 2700 + 4600 + 7050 + 7750 = 24150 Meter 3). Nilai fitness tiap jalur ( f i ) N
fi = f1 =
∑
i= 1
Zi
Zi 24150 = 34.5 700
f4 =
24150 = 5.25 4600
IV-13
f2 =
24150 = 17.89 1350
f5 =
24150 = 3.42 7050
f3 =
24150 = 8.94 2700
f6 =
24150 = 3.12 7750
N
4). Total fitness (∑ f i ) i= 1
= f1 + f 2 + f 3 + f 4 + f 5 + f 6 = 34.5 + 17.89 + 8.94 + 5.25 + 3.42 + 3.12 = 73.12 5). Probabilitas tiap jalur ( p i ) pi =
fi N
∑
i= 1
fi
p1 =
34.5 = 0.47 73.12
p4 =
5.25 = 0.07 73.12
p2 =
17.89 = 0.24 73.12
p5 =
3.12 = 0.046 73.12
p3 =
8.94 = 0.12 73.12
p6 =
3.12 = 0.043 73.12
6). Probabilitas kumulatif tiap jalur (q i ) = p1 + p 2 + p3 + p 4 + p5 + p 6 = 0.47 + 0.24 + 0.12 + 0.07 + 0.46 + 0.043 = 0.989 d. Kromosom IV (Jalur Dian 4), Depot − A6 − A7 − A5 − A / Telaga Biru –
Manggis – Hasan Gani - Geriliya. 1). Jarak Tempuh tiap Jalur ( Z i ) A6
= 2100 Meter
A7
= 4000 Meter
A5
= 5270 Meter
A
= 6370 Meter
IV-14
N
2). Total jarak dari seluruh jalur (∑ Z i ) i= 1
= ( A6 + A7 + A5 + A ) = 2100 + 4000 + 5270 + 6370 = 17740 Meter 3). Nilai fitness tiap jalur ( f i ) N
fi =
∑
i= 1
Zi
Zi
f1 =
17740 = 8.45 2100
f3 =
17740 = 3.37 5270
f2 =
17740 = 4.43 4000
f4 =
17740 = 2.78 6370
N
4). Total fitness (∑ f i ) i= 1
= f1 + f 2 + f 3 + f 4 = 8.45 + 4.43 + 3.37 + 2.78 = 19.05 5). Probabilitas tiap jalur ( p i ) pi =
fi N
∑
i= 1
fi
p1 =
8.45 = 0.44 19.05
p3 =
3.37 = 0.18 19.05
p2 =
4.43 = 0.23 19.05
p4 =
2.78 = 0.15 19.05
6). Probabilitas kumulatif tiap jalur (q i ) = p1 + p 2 + p3 + p 4 = 0.44 + 0.23 + 0.18 + 0.15 =1
IV-15
e. Kromosom V (Jalur Dian 5), Depot − A6 − A8 − A / Telaga Biru – Suhada
– Geriliya 1). Jarak Tempuh tiap Jalur ( Z i ) A6
= 2100 Meter
A8
= 4550 Meter
A
= 5250 Meter N
2). Total jarak dari seluruh jalur (∑ Z i ) i= 1
= ( A6 + A8 + A ) = 2100 + 4550 + 5250 = 11900 Meter 3). Nilai fitness tiap jalur ( f i ) N
fi =
∑
i= 1
Zi
Zi
f1 =
11900 = 5.67 2100
f2 =
11900 = 2.62 4550
f3 =
11900 = 2.27 5250
N
4). Total fitness (∑ f i ) i= 1
= f1 + f 2 + f 3 = 5.67 + 2.62 + 2.27 = 10.56 5). Probabilitas tiap jalur ( p i ) pi =
fi N
∑
i= 1
fi
IV-16
p1 =
5.67 = 0.54 10.56
p2 =
2.62 = 0.25 10.56
p3 =
2.27 = 0.21 10.56
6). Probabilitas kumulatif tiap jalur (q i ) = p1 + p 2 + p3 = 0.54 + 0.25 + 0.21 =1 E. Membandingkan Probabilitas Komulatif Tiap Kromosom Kromosom I : 0,98 Kromosom II : 0,99 Kromosom III : 0,989 Kromosom IV : 1 Kromosom V : 1 F. Hasil terbaik adalah kromosom 1 karena memiliki nilai probabilitas terkecil
yaitu 0,98 maka proses dihentikan. Lintasan VRP tersebut dapat dijelaskan bahwa dalam pencarian jarak terpendek dengan kriteria: Kromosom I : Depot − A1 − A2 − A3 − A4 − A5 − A 700 + 650 + 750 + 800 + 700 + 1100 = 4700 Meter Kromosom II : Depot − A1 − A2 − A7 − A5 − A 700 + 650 + 1350 + 1270 + 1100 = 5070 Meter Kromosom III : Depot − A1 − A2 − A7 − A6 − A8 − A 700 + 650 + 1350 + 1900 + 2450 + 700 = 7750 Meter Kromosom IV : Depot − A6 − A7 − A5 − A 2100 + 1900 + 1270 + 1100 = 6370 Meter Kromosom V : Depot − A6 − A8 − A
IV-17
2100 + 2450 + 700 = 5260 Meter Untuk kendaraan I dapat disimpulkan bahwa fungsi fitness dan Probabilitas yang terbaik terdapat pada Kromosom I/Jalur 1 Dian, karena mempunyai nilai probabilitas terkecil yaitu 0, 98 dan memiliki jarak paling pendek yaitu 4700 Meter dibandingkan kromosom II, III, IV, dan V.
A 1100 M
A4 700M A5
35 Km / Jam
35Km / Jam700 M
55Km / Jam
A8
800 M 50 Km / Jam
A3
35Km / Jam
1270 M 750 M
A7
45 Km / Jam 1350 M
A1
650M
A2
35Km / Jam
50 Km / Jam
40 Km / Jam 2450 M
40 Km / Jam 1900 M
A6 700M
30 Km / Jam
Depot
45 Km / Jam 2100 M
Gambar 4.4 Jalur terpendek untuk kendaraan I Kendaraan II A. Generasi = 0
IV-18
B. Populasi awal yaitu
B − B1 − B2 − B3 − B4 − B5 − B6 − B7 − B8
di dapat
kromosom-kromosomnya adalah: Kromosom/Jalur 1 : Depot − B1 − B2 − B3 − B Kromosom/Jalur 2 : Depot − B1 − B2 − B7 − B6 − B8 − B Kromosom/Jalur 3 : Depot − B4 − B7 − B2 − B3 − B Kromosom/Jalur 4 : Depot − B4 − B7 − B6 − B8 − B Kromosom/Jalur 5 : Depot − B4 − B5 − B6 − B7 − B2 − B3 − B Kromosom/Jalur 6 : Depot − B4 − B5 − B6 − B8 − B
C. Nilai fitness dan probabilitas dari setiap Kromosom: a. Kromosom I (Jalur SMPN 1), Depot − B1 − B2 − B3 − B / Batang Tuaka –
Gunung Daek – Swarna Bumi – Cahaya – Telaga Biru II – Tanjung Harapan. 1). Jarak Tempuh tiap Jalur ( Z i ) B1
= 1450 Meter
B3
= 4490 Meter
B2
= 2960 Meter
B
= 6760 Meter
N
2). Total jarak dari seluruh jalur (∑ Z i ) i= 1
= ( B1 + B2 + B3 + B ) = 1450 + 2960 + 4490 + 6760 = 15660 Meter 3). Nilai fitness tiap jalur ( f i ) N
fi =
∑
i= 1
Zi
Zi
IV-19
f1 =
15660 = 10.8 1450
f3 =
15660 = 3.49 4490
f2 =
15660 = 5.29 2960
f4 =
15660 = 2.32 6760
N
4). Total fitness (∑ f i ) i= 1
= f1 + f 2 + f 3 + f 4 = 10.8 + 5.29 + 3.49 + 2.32 = 21.9 5). Probabilitas tiap Jalur ( p i ) pi =
fi N
∑
i= 1
fi
p1 =
10.8 = 0.49 21.9
p3 =
3.49 = 0.16 21.9
p2 =
5.29 = 0.24 21.9
p4 =
2.32 = 0.11 21.9
6). Probabilitas kumulatif tiap jalur (q i ) qi =
N
∑
i= 1
pi
= p1 + p 2 + p3 + p 4 = 0.49 + 0.24 + 0.16 + 0.11 =1
b. Kromosom II (Jalur SMPN 2),
Depot − B1 − B2 − B7 − B6 − B8 − B /
Ahmad Yani – Malagas – Swarna Bumi – Telaga Biru II – Tanjung Harapan. 1). Jarak Tempuh tiap Jalur ( Z i ) B1
= 1450 Meter
B6
= 5580 Meter
IV-20
B2
= 2960 Meter
B8
= 6510 Meter
B7
= 4330 Meter
B
= 7870 Meter
N
2). Total jarak dari seluruh jalur (∑ Z i ) i= 1
= ( B1 + B2 + B7 + B6 + B8 + B ) = 1450 + 2960 + 4330 + 5580 + 6510 + 7870 = 28700 Meter 3). Nilai fitness tiap jalur ( f i ) N
fi =
∑
i= 1
Zi
Zi
f1 =
28700 = 19.79 1450
f4 =
28700 = 5.14 5580
f2 =
28700 = 9.69 2960
f5 =
28700 = 4.41 6510
f3 =
28700 = 6.63 4330
f6 =
28700 = 3.65 7870
N
4). Total fitness (∑ f i ) i= 1
= f1 + f 2 + f 3 + f 4 + f 5 + f 6 = 19.79 + 9.69 + 6.63 + 5.14 + 4.41 + 3.65 = 49.31 5). Probabilitas tiap jalur ( p i ) pi =
fi N
∑
i= 1
fi
p1 =
19.79 = 0.40 49.31
p4 =
5.14 = 0.10 49.31
p2 =
9.69 = 0.19 49.31
p5 =
4.41 = 0.09 49.31
IV-21
p3 =
6.63 = 0.13 49.31
p6 =
3.69 = 0.07 49.31
6). Probabilitas kumulatif tiap jalur (q i ) qi =
N
∑
pi
i= 1
= p1 + p 2 + p3 + p 4 + p5 + p 6 = 0.40 + 0.19 + 0.13 + 0.10 + 0.09 + 0.07 = 0.98 c. Kromosom III (Jalur SMPN 3), Depot − B4 − B7 − B2 − B3 − B / Ahmad
Yani – Malagas – Cahaya – Telaga Biru II – Tanjung Harapan. 1). Jarak Tempuh tiap Jalur ( Z i ) B4
= 650 Meter
B3
= 5470 Meter
B7
= 2570 Meter
B
= 7740 Meter
B2
= 3940 Meter N
2). Total jarak dari seluruh jalur (∑ Z i ) i= 1
= ( B4 + B7 + B2 + B3 + B ) = 650 + 2570 + 3940 + 5470 + 7740 = 20370 Meter 3). Nilai fitness tiap jalur ( f i ) N
fi =
∑
i= 1
Zi
Zi
f1 =
20370 = 31.34 650
f4 =
20370 = 3.72 5470
f2 =
20370 = 7.92 2570
f5 =
20370 = 2.63 7740
f3 =
20370 = 5.17 3940
IV-22
N
4). Total fitness (∑ f i ) i= 1
= f1 + f 2 + f 3 + f 4 + f 5 = 31.34 + 7.92 + 5.17 + 3.72 + 2.63 = 50.78 5). Probabilitas tiap jalur ( p i ) pi =
fi N
∑
i= 1
fi
p1 =
31.34 = 0.61 50.78
p4 =
3.72 = 0.07 50.78
p2 =
7.92 = 0.15 50.78
p5 =
2.63 = 0.05 50.78
p3 =
5.17 = 0.1 50.78
6). Probabilitas kumulatif tiap jalur (q i ) qi =
N
∑
i= 1
pi
= p1 + p 2 + p3 + p 4 + p5 = 0.61 + 0.15 + 0.10 + 0.07 + 0.05 = 0.98 d. Kromosom IV (Jalur SMPN 4), Depot − B4 − B7 − B6 − B8 − B / Ahmad
Yani – M. Boya – Telaga Biru – Telaga Biru II – Tanjung Harapan. 1). Jarak Tempuh tiap Jalur ( Z i ) B4
= 650 Meter
B8
= 4760 Meter
B7
= 2570 Meter
B
= 6120 Meter
B6
= 3830 Meter N
2). Total jarak dari seluruh jalur (∑ Z i ) i= 1
IV-23
= ( B4 + B7 + B6 + B8 + B ) = 650 + 2570 + 3830 + 4760 + 6120 = 17930 Meter 3). Nilai fitness tiap jalur ( f i ) N
fi =
∑
i= 1
Zi
Zi
f1 =
17930 = 27.58 650
f4 =
17930 = 3.77 4670
f2 =
17930 = 6.98 2570
f5 =
17930 = 2.93 6120
f3 =
17930 = 4.68 3830 N
4). Total fitness (∑ f i ) i= 1
= f1 + f 2 + f 3 + f 4 + f 5 = 27.58 + 6.98 + 4.68 + 3.77 + 2.93 = 45.94 5). Probabilitas tiap jalur ( p i ) pi =
fi N
∑
i= 1
fi
p1 =
27.58 = 0.60 45.94
p4 =
3.77 = 0.08 45.94
p2 =
6.98 = 0.15 45.94
p5 =
2.93 = 0.06 45.94
p3 =
4.68 = 0.10 45.94
6). Probabilitas kumulatif tiap jalur (q i ) qi =
N
∑
i= 1
pi
IV-24
= p1 + p 2 + p3 + p 4 + p5 = 0.60 + 0.15 + 0.10 + 0.08 + 0.06 = 0.99 e. Kromosom V (Jalur SMPN 5), Depot − B4 − B5 − B6 − B7 − B2 − B3 − B /
Ahmad Yani – M. Boya – Telaga Biru – Cahaya – Swarna Bumi – Telaga Biru II – Tanjung Harapan. 1). Jarak Tempuh tiap Jalur ( Z i ) B4
= 560 Meter
B2
= 6360 Meter
B5
= 1580 Meter
B3
= 7890 Meter
B6
= 3740 Meter
B
= 10160 Meter
B7
= 4990 Meter N
2). Total jarak dari seluruh jalur (∑ Z i ) i= 1
= ( B4 + B5 + B6 + B7 + B2 + B3 + B ) = 560 + 1580 + 3740 + 4990 + 6360 + 7890 + 10160 = 35280 Meter 3). Nilai fitness tiap jalur ( f i ) N
fi =
∑
i= 1
Zi
Zi
f1 =
35280 = 63 560
f5 =
35280 = 5.55 6360
f2 =
35280 = 22.33 1580
f6 =
35280 = 4.47 7890
f3 =
35280 = 9.43 3740
f7 =
35280 = 3.47 10160
f4 =
35280 = 7.07 4990
IV-25
N
4). Total fitness (∑ f i ) i= 1
= f1 + f 2 + f 3 + f 4 + f 5 + f 6 + f 7 = 63 + 22.33 + 9.43 + 7.07 + 5.55 + 4.47 + 3.47 = 115.32 5). Probabilitas tiap jalur ( p i ) pi =
fi N
∑
i= 1
fi
p1 =
63 = 0.55 115.32
p5 =
5.55 = 0.04 115.32
p2 =
22.33 = 0.19 115.32
p6 =
4.47 = 0.038 115.32
p3 =
9.43 = 0.08 115.32
p7 =
3.47 = 0.03 115.32
p4 =
7.07 = 0.06 115.32
6). Probabilitas kumulatif tiap jalur (q i ) qi =
N
∑
i= 1
pi
= p1 + p 2 + p3 + p 4 + p5 + p 6 + p 7 = 0.55 + 0.19 + 0.08 + 0.06 + 0.04 + 0.038 + 0.03 = 0.988
f.
Kromosom VI (Jalur SMPN 6), Depot − B4 − B5 − B6 − B8 − B / Ahmad Yani – M. Boya – Telaga Biru I – Telaga Biru II – Tanjung Harapan.
1). Jarak Tempuh tiap Jalur ( Z i ) B4
= 560 Meter
B8
= 4670 Meter
B5
= 1580 Meter
B
= 6030 Meter
B6
= 3740 Meter
IV-26
N
2). Total jarak dari seluruh jalur (∑ Z i ) i= 1
= ( B4 + B5 + B6 + B8 + B ) = 560 + 1580 + 3740 + 4670 + 6030 = 16580 Meter 3). Nilai fitness tiap jalur ( f i ) N
fi =
∑
i= 1
Zi
Zi
f1 =
16580 = 29.6 560
f4 =
16580 = 3.55 4670
f2 =
16580 = 10.49 1580
f5 =
16580 = 2.74 6030
f3 =
16580 = 4.43 3740 N
4). Total fitness (∑ f i ) i= 1
= f1 + f 2 + f 3 + f 4 + f 5 = 29.6 + 10.49 + 4.43 + 3.55 + 2.74 = 50.83 5). Probabilitas tiap jalur ( p i ) pi =
fi N
∑
i= 1
fi
p1 =
29.60 = 0.58 50.83
p4 =
3.55 = 0.06 50.83
p2 =
10.49 = 0.20 50.83
p5 =
2.74 = 0.05 50.83
p3 =
4.43 = 0.08 50.83
6). Probabilitas kumulatif tiap jalur (q i )
IV-27
qi =
N
∑
i= 1
pi
= p1 + p 2 + p3 + p 4 + p5 = 0.58 + 0.20 + 0.08 + 0.06 + 0.05 = 0.97 E. Membandingkan Probabilitas Komulatif Tiap Kromosom Kromosom I : 1 Kromosom II : 0,98 Kromosom III : 0,98 Kromosom IV : 0,99 Kromosom V : 0,988 Kromosom VI : 0,97 F. Hasil terbaik adalah kromosom VI karena memiliki nilai probabilitas terkecil
yaitu 0,97 maka proses dihentikan. Lintasan VRP tersebut dapat dijelaskan bahwa dalam pencarian jarak terpendek dengan kriteria: Kromosom I : Depot − B1 − B2 − B3 − B 1450 + 1510 + 1530 + 2270 = 6760 Meter Kromosom II : Depot − B1 − B2 − B7 − B6 − B8 − B 1450 + 1510 + 1370 + 1250 + 930 + 1360 = 7870 Meter Kromosom III : Depot − B4 − B7 − B2 − B3 − B 560 + 2010 + 1370 + 1530 + 2270 = 7740 Meter Kromosom IV : Depot − B4 − B7 − B6 − B8 − B 560 + 2010 + 1250 + 930 + 1360 = 6110 Meter Kromosom V : Depot − B4 − B5 − B6 − B7 − B2 − B3 − B 560 + 1020 + 2160 + 1250 + 1370 + 1530 + 2270 = 10160 Meter
IV-28
Kromosom VI: Depot − B4 − B5 − B6 − B8 − B 560 + 1020 + 2160 + 930 + 1360 = 6030 Meter Untuk kendaraan II dapat disimpulkan bahwa fungsi fitness yang terbaik terdapat pada Kromosom VI/Jalur 6 SMPN, karena mempunyai Probabilitas kumulatif terkecil yaitu 0.97 dan mempunyai jarak paling pendek yaitu 6030 Meter dibandingkan kromosom I, II, III, IV dan V.
Depot 1450 M 40 Km / Jam
560 M 30 Km / Jam
B4
35 Km / Jam1510 M
40 Km / Jam 2010 M
1020 M
B7
40 Km / Jam
B5
B1
50 Km / Jam 1250 M
40 Km / Jam 1370 M
B2
1530 M
40 Km / Jam
B3
35 Km / Jam
2160 M 30 Km / Jam
B6
45 Km / Jam 930 M
B8
2270 M 50 Km / Jam
1360 M
B Gambar 4.5 Jalur terpendek untuk kendaraan II
IV-29
Untuk pencarian waktu terkecil dalam kasus VRP ini ditentukan berdasarkan
jarak ketiga kendaraan dalam melewati jalur-jalur yang sudah kecepa tan
ditentukan, dapat dicari dengan kriteria: a. Kendaraan I
Kromosom I (Jalur Dian 1): Depot − A1 − A2 − A3 − A4 − A5 − A / Abdul Manaf – H. Arif – Kayu Jati – Sapta Marga – Pelita Jaya – Geriliya. 700 = 23,33 30
dimana: A1 = A2 =
650 = 13 50
A3 =
750 = 16,67 45
A4 =
800 = 16 50
A5 =
700 = 12,73 55
A =
1100 = 31,43 35
= 23,33 + 13 + 16,67 + 16 + 12,73 + 31,43 = 113,16Menit
Kromosom II (Jalur Dian 2):
Depot − A1 − A2 − A7 − A5 − A / Abdul
Manaf – H. Arif – Perintis – Hasan Gani – Geriliya. dimana: A1 =
700 = 23,33 30
A2 =
650 = 13 50
A7 =
1350 = 38,57 35
IV-30
A5 =
1270 = 36,28 35
A =
1100 = 31,43 35
= 23,33 + 13 + 38,57 + 36,28 + 31,43 = 142,61Menit Kromosom III (Jalur Dian 3): Depot − A1 − A2 − A7 − A6 − A8 − A / Abdul Manaf – H. Arif –Perintis – Manggis – Suhada - Geriliya. 700 = 23,33 30
dimana: A1 = A2 =
650 = 13 50
A7 =
1350 = 38,57 35
A6 =
1900 = 47,5 40
A8 =
2450 = 61,25 40
A =
700 = 20 35
= 23,33 + 13 + 38,57 + 47,5 + 61,25 + 20 = 203,65Menit Kromosom IV (Jalur Dian 4): Depot − A6 − A7 − A5 − A / Telaga Biru – Manggis – Hasan Gani - Geriliya. dimana: A6 =
2100 = 46,67 45
A7 =
1900 = 47,5 40
A5 =
1270 = 36,28 35
IV-31
1100 = 31,43 35
A =
= 46,67 + 47,5 + 36,28 + 31,43 = 161,88Menit Kromosom V (Jalur Dian 5) : Depot − A6 − A8 − A / Telaga Biru – Suhada – Geriliya. dimana: A6 =
2100 = 46,67 45
A7 =
2450 = 61,25 40
A =
700 = 20 35
= 46,67 + 61,25 + 20 = 127,92Menit Kendaraan I kromosom dengan waktu tercepat adalah Kromosom I yaitu 113,16 Menit. b. Kendaraan II Kromosom I (Jalur SMPN I) : Depot − B1 − B2 − B3 − B / Batang Tuaka – Gunung Daek – Swarna Bumi – Cahaya – Telaga Biru II – Tanjung Harapan. 1450 = 36,25 40
dimana: B1 = B2 =
1510 = 43,14 35
B3 =
1530 = 38,25 40
B =
2270 = 75,67 30
= 36,25 + 43,14 + 38,25 + 75,67 = 193.31Menit
IV-32
Kromosom II (Jalur SMPN 2) :
Depot − B1 − B2 − B7 − B6 − B8 − B /
Ahmad Yani – Malagas – Swarna Bumi – Telaga Biru II – Tanjung Harapan. 1450 = 36,25 40
dimana: B1 = B2 =
1510 = 43,14 35
B7 =
1370 = 34,25 40
B6 =
1250 = 35,71 35
B8 =
930 = 20,67 45
B =
1360 = 27,2 50
= 36,25 + 43,14 + 34,25 + 35,71 + 20,67 + 27,2 = 197,22 Menit Kromosom III (Jalur SMPN 3) : Depot − B4 − B7 − B2 − B3 − B / Ahmad Yani – Malagas – Cahaya – Telaga Biru II – Tanjung Harapan. dimana: B4 =
560 = 18,67 30
B7 =
2010 = 50,25 40
B2 =
1370 = 34,25 40
B3 =
1530 = 38,25 40
B =
2270 = 75,67 30
IV-33
= 18,67 + 50,25 + 34,25 + 38,25 + 75,67 = 217,09Menit Kromosom IV (Jalur SMPN 4): Depot − B4 − B7 − B6 − B8 − B / Ahmad Yani – M. Boya – Telaga Biru – Telaga Biru II – Tanjung Harapan. 560 = 18,67 30
dimana: B4 = B7 =
2010 = 50,25 40
B6 =
1250 = 35,71 35
B8 =
930 = 20,67 45
B =
1360 = 27,2 50
= 18,67 + 50,25 + 35,71 + 20,67 + 27,2 = 152,5Menit Kromosom V (Jalur SMPN 5): Depot − B4 − B5 − B6 − B7 − B2 − B3 − B / Ahmad Yani – M. Boya – Telaga Biru – Cahaya – Swarna Bumi – Telaga Biru II – Tanjung Harapan. dimana: B4 =
560 = 18,67 30
B5 =
1020 = 25,5 40
B6 =
2160 = 43,2 50
B7 =
1250 = 35,71 35
B2 =
1370 = 34,25 40
IV-34
B3 =
1530 = 38,25 40
B =
2270 = 75,67 30
= 18,67 + 25,5 + 43,2 + 35,71 + 34,25 + 38,25 + 75,67 = 271,25Menit Kromosom VI (Jalur SMPN 6) : Depot − B4 − B5 − B6 − B7 − B / Ahmad Yani – M. Boya – Telaga Biru I – Telaga Biru II – Tanjung Harapan. 560 = 18,67 30
dimana: B4 = B5 =
1020 = 25,50 40
B6 =
2160 = 43,2 50
B7 =
930 = 20,67 45
B =
1360 = 27,2 50
= 18,67 + 25,50 + 43,2 + 20,67 + 27,2 = 135,24Menit Kendaraan II kromosom dengan waktu tercepat adalah Kromosom VI yaitu 135,24 Menit.
IV-35
BAB V PENUTUP 5.1 Kesimpulan Berdasarkan pembahasan pada Bab IV, penyelesaian Vehicle Routing Problem menggunakan Algoritma Genetika, dapat diambil kesimpulan sebagai berikut: 1. Vehicle Routing Problem dapat diselesaikan dengan algoritma genetika. 2. Jarak terpendek dan waktu terkecil pada kasus perjalanan dua kendaraan depot air asmira dalam mengantar pesanan air galon dua costumer dapat ditentukan, yaitu: a. Pada Kendaraan I jarak terpendek dan waktu terkecil adalah kromosom I yaitu Abdul Manaf – H. Arif – Kayu Jati – Sapta Marga – Pelita Jaya – Geriliya dengan jarak 4700 Meter dan Waktu 113,16 Menit. b. Pada Kendaraan II Jarak terpendek dan waktu terkecil adalah kromosom VI yaitu Ahmad Yani – M. Boya – Telaga Biru – Telaga Biru II – Tanjung Harapan dengan jarak 6030 Meter dan waktu 135,24 Menit. 5.2 Saran Beberapa hal yang disarankan dalam pengembangan aplikasi Algoritma genetika pada Vehicle Routing Problem sebagai berikut: a. Vehicle Routing Problem pada penelitian diselesaikan dengan aplikasi algoritma genetika, tidak menutup kemungkinan kasus Vehicle Routing Problem ini dapat diselesaikan dengan aplikasi lainnya misalnya algoritma heuristic dan graf berbobot, Vehicle Routing Problem With Time Windows, Vehicle Routing Problem Delipery and Pickup, dan lain-lain. b. Pengembangan
penggunaan
algorima
genetika
dapat
menggunakan
pemograman. pencarian secara manual, dan pemograman yang mendukung terbentuknya simpul-simpul pada kasus Vehicle Routing Problem.
DAFTAR PUSTAKA Basuki, Achmad. ”Starategi menggunakan Algoritma genetika”, Politeknik Elektronika Negeri Surabaya. PENS-ITS. 2003. ______________. ”Tips dan Trik : Algoritma Genetika”, Politeknik Elektronika Negeri Surabaya. PENS-ITS. 2006. Ginting, Rosnani. “ Penjadwalan Mesin”, Graha Ilmu, Yogyakarta. 2009. https://mail.eepisits.edu/~kangedi/materi.kuliah/Kecerdasan.Buatan/Bab.Algoritm a Genetika.pdf. 14 februari 2011. Iing, dkk, ” Pemanfaatan Metode Heuristik dalam Pencarian Jalur Terpendek dengan Algoritma Semut dan Algoritma Genetika”, Seminar Nasional Aplikasi Teknologi Informasi 2007. hlm:1 s/d 7, 2007. Kusumadewi, Sri. “Penyelesaian Masalah Optimasi dengan Teknik-teknik Heuristik”, Graha Ilmu.Yogyakarta. 2005. Munir, Rinaldi. Matematika Diskrit, Edisi ke-2. Bandung: PT. Informatika. 2003.