MATHunesa

Jurnal Ilmiah Matematika Volume 11 No 03

Tahun 2023

PENERAPAN ALGORITMA GENETIKA DALAM MENENTUKAN RUTE TERPENDEK PT.

POS CABANG LAMONGAN

Ahmad Tohari
Program Studi Matematika, FMIPA, Universitas Negeri Surabaya,
email: ahmad.19019@[Link]

Yuliani Puji Astuti

Program Studi Matematika, FMIPA, Universitas Negeri Surabaya,
Penulis Korespondensi: yulianipuji@[Link]

Abstrak
Ekspedisi menjadi salahisatu hal penting dalam pengiriman barang di era perkembangan saat ini karena
dapat memudahkan masyarakat yang membutuhkan jasa pengiriman. Permasalahan pengiriman barang
oleh kurir termasuk dalam permasalahaniTravelling Salesman Problem (TSP) yang mana kurir harus
menentukan rute terpendek untuk ditempuh dari titik awal hingga kembali ke titik awal lagi dan setiap titik
harus dilalui satu kali. Solusi pada permasalahan ini adalah menggunakan algoritma genetika untuk
mencari rute terpendek yang optimal. Tujuan penelitian ini adalah unutuk menerapkan Algoritma Genetika
dalam pencarian rute terpendek dilakukan pada PT. Pos Cabang Lamongan dan menghitung biaya
perjalanan kuirir. Metode penelitianiyang digunakaniadalah deskriptif kuantitatif. Penelitian dilakukan
menggunakan perhitungan secara manual dan pengkodean menggunakan aplikasi python. Tahapan
algoritma genetika adalah populasi awal, proses evaluasi, seleksi, crossover, dan mutasi hingga
menghasilkan solusi. Hasil pencarian rute terpendek pada 2 siklus adalah pada jalur dengan total jarak
tempuh sebesar 158 km dengan melewati 12 titik adalah A-L-K-J-I-H-G-F-E-D-C-B-A . Kemudian dilakukan
perhitungan cost memperoleh hasil sebesar Rp. 158.000.
Kata Kunci: Pengiriman, Rute Terpendek, Algoritma Genetika, Traveling Salesman Problem

Abstract
Expedition is one of the important things in shipping goods in the current era of development because it can make it easier for
people who need shipping services. The problem of shipping goods by couriers is included in the Traveling Salesman Problem
(TSP) where the courier must determine the shortest route to be taken from the starting point to return to the starting point
again and each point must be passed once. The solution to this problem is to use a genetic algorithm to find the optimal shortest
route. The purpose of thisiresearch is to applyithe Genetic Algorithm in finding the shortest route at PT. Lamongan Branch
Post and calculate the courier’s travel costs. The research methodiused is descriptiveiquantitative. The research was carried out
using manual calculations and coding using the python application. The stages of the genetic algorithm are the initial
population, the process of evaluation, selection, crossover and mutation to produce a solution. The search result for the shortest
route for 2 cycles is the path with a total distance of 158 km by passing 12 points, namely A-L-K-J-I-H-G-F-E-D-CB-A . Then
the cost calculation is carried out to obtain a result of Rp. 158.000.
Keywords: Distribution, shortest route, Genetic Algorithm, Traveling Salesman Problem

dalam permasalahan kombinatorial yang biasanya

PENDAHULUAN disebut dengan Travelling Salessman Problem (TSP).
Transportasi adalah hal yang penting bagi TSP adalah bentuk dari permasalahan optimasi yang
suatu perusahaan logistik untuk menjalankan proses dapat digambarkan dalam bentuk graf G=(V,E)
pendistribusian barang. Salah satu permasalahan dengan konsep yang mudah dipecahkan (Apriyani,
dalam bidang transportasi perusahaan adalah 2018). Graf (G) dapat terbentuk dari kumpulan vertex
mencari rute perjalanan terpendek untuk ditempuh. (V) dan kumpulan edge (E).Proses optimasi dari TSP
Hal tersebut dilakukan agar waktu tempuh dan yaitu ipenentuan irute iperjalanan isalesman iyang
biaya perjalanan yang dikeluarkan bisa minimum. dimulai dari satu ilokasi ke beberapa lokasi,
Permasalahan tentang rute perjalanan dikategorikan

458
 AHMAD TOHARI, YULIANI PUJI ASTUTI

kemudian kembali ke lokasi awal dan setiap kantor baru. Solusi yang ada pada metode Algoritma
tepat dikunjungi satu kali. Genetika disebut kromosom. Sebuah kromosom
Perkembangan TSP pada kehidupan sehari- dapat berupa bilanganinumerik, ibiner, isimbol, atau
hari yang bermanfaat salah satunya pada persoalan karakter tergantung masalah yang diselesaikan.
pengiriman barang jarak jauh. Salah satu perusahaan Setelah itu dilakukan proses reproduksi dengan
logistik yang menyediakan beberapa jenis memilih individu yang dikembangbiakkan. Pada
pengiriman barang adalah PT. Pos Indonesia. Seiring penelitian ini metode Algoritma Genetika digunakan
dengan perkembangan teknologi, yang dulunya untuk menganalisis optimasi rute PT. Pos Indonesia
hanya menyediakan jasa pengiriman surat saat ini cabang Lamongan ke drop point “PosAja” yang
PT. Pos Indonesia memiliki strategi bisnis yang tersebar dibeberapa kecamatan yang ada.
bagus dalam menanggapinya.
. PT. Pos Indonesia memiliki keunggulan
KAJIAN TEORI
lebih terpercaya dalam memberikan pelayanan A. Travelling Salesman Problem
kepada pelanggan karena PT. Pos sudah berdiri dari Traveling iSalesman Problem iadalah

tahun 1746 dan memiliki tarif yang terjangkau. Jasa permasalahan yang digunakan untuk mencari
pengiriman PT. Pos Indonesia memiliki layanan biaya touriminimal dari sekumpulanikantor yang
yang lebih lengkap dibandingkan pengiriman mana tiap kantor hanya dikunjungi satu kali
logistik lainnya. Strategi yang digunakan PT. Pos (Candrawati, 2017). Travelling Salesman Problem
Indonesia untuk memberikan kepuasan pelanggan awalnya berkembang sebagai bagian masalah
salah satunya dengan memberikan fasilitas kantor logistik dan transportasi. Logistik dan Supply
atau drop point “PosAja” yang tersebar dibeberapa Chain secara umum memiliki arti sebagai suatu
kecamatan. Seperti PT. Pos Indonesia cabang system untuk mengelola orang, sumber daya,
lamongan yang memiliki drop point diantaranya : teknologi, aktivitas, dan sebagainya yang
Kecamatan Lamongan, Karanggeneng, Sukodadi, digunakan untuk mengantar barang dan jasa dari
Babat, Ngimbang, Sambeng, Mantup, Tikung, titik supplier ke titik tujuan. Penggunaan TSP
Kembangbahu, Paciran, Laren, dan Sekaran. Adanya dalam sektor logistik sangat penting bag
banyak rute yang dilalui perusahaan maka perusahaan pengiriman barang dan jasa,
perusahaan harus tepat dalam menentukan rute perusahaan travel, dan biro perjalanan, distribusi
yang optimal sehingga proses distribusi tidak dan pemasaran bahan baku atau bahan jadi
dilakukan berdasarkan keinginan petugas pos dan perusahaan. Dari definisi tersebut dapat
adanya rute yang optimal tidak berpengaruh pada disimpulkanibahwaikonsep TSPimemiliki aturan
proses distribusi (Paillin, 2019). sebagai berikut :
Penyelesaian masalah TSP dapat 1. Harus mengunjungi setiapikantor satu kali
menggunakan beberapa metode diantaranya tidak bolehikurang atau lebih,
Algoritma Genetika, Algoritma Semut, Simulated 2. Semua kantor harus dikunjungi dalam satu
Annealing, Hill Climbing, dan Tabu Search. Untuk kali perjalanan,
menyelesaikan permasalahan TSP pada pengiriman 3. Dimulai dan diakhiri pada kantor yang
barang PT. Pos Indonesia tersebut, maka analisis rute sama.
dilakukan dengan menggunakan metode Algoritma B. Algoritma Genetika
Genetika untuk mencari rute terpendek yang Algoritma genetika adalah algoritma
optimal dalam pengiriman barang karena Algoritma digunakan untuk pencarian yang didasarkan
Genetika memiliki kelebihan yaitu waktu komputasi pada teori evolusi dan seleksi alam
yang dibutuhkan cenderung stabil dan memberikan (Nugroho,2007). Algoritma genetikaimerupakan
jarak terpendek walaupun dengan jumlah kantor metode ipemecahan iyang idisesuaikan idengan
yang besar. proses genetika dari proses organisme-organisme
Metode Algoritma Genetika memiliki 5 biologi yang digunakan berdasarkan iteori
tahapan yaitu populasi awal, proses evaluasi, Charles Darwin. Sifat algoritma genetika adalah
seleksi, crossover, mutasi yang nantinya akan mencariikemungkinan-kemungkinanidari solusi
menghasilkan sebuah hasil akhir berupa genenerasi untuk imendapatkan iyang ioptimal iuntuk

459
 PENERAPAN ALGORITMA GENETIKA …

menyelesaikan masalah. Tahap-tahap Algoritma 3) Munculkan bilangan random r yang

Gnetika: memiliki nilai antara 0 sampai 1 (0 < r <
a. Populasi awal 1)
Populasi awal terbentuk dari 4) Jika r < 𝑞1 maka dipilih kromosom
kromosom sejumlah ukuran populasi pertama, jika 𝑞𝑖 <r< 𝑞(𝑖+𝑗) dengan
(UkPop). Setiap kromosom menyatakan j=(1,2,...,UkPop) maka pilih kromosom
urutan kantor yang harusidikunjungi oleh ke-i+j (Utami,2014).
salesman,sehingga representasi kromosom 5) Ulangi kedua langkah tersebut
paling isederhanai untuki menyatakan sebanyak kromosom dalam sebuah
penyelesaian masalah ini adalah dijelaskan populasi.
dalamipermutasi dari indeks kantor pada
masalah ini dan dapat dinyatakanisebagai d. Crossover
kromosom viberikut : Crossover (pindah silang) adalah salah
Vi=[g1,g2, …,gN], satu ioperator iAlgoritma iGenetika iyang
Dengan 1 ≤ i ≤ UkPop. melibatkan dua indukiuntuk menghasilkan
gen baru. Cara kerja crossover adalah
b. Proses evaluasi membangkitkan ioffspring ibaru idengan
Proses evaluasi adalah suatu proses mengganti sebagian informasi dari parents.
untuk imenghitungi nilai ifitness iyang Berikut ini adalah contoh dari proses
menyatakan itingkat ikualitas ikromosom crossover :
sebagai representasi penyelesaianimasalah.
Nilai fitnessiadalah nilai yangimenyatakan
baik atau tidaknyaisuatu solusi. Semakin
tinggi nilai fitnessimaka semakinitinggi nilai
kromosom. Proses inversi dapat dilakukan
dengani rumusani 𝐹𝑖 = ,
1
idengan i Pemilihan titik penyilangan dilakukan
𝑓𝑖
dengan posisi pemotongan secara acak.
merupakan kromosom (Basuki,2003:17).
Kromosom induk dipilih dari dua
kromosom awal dan dilakukan pemotongan
Keterangan :
titik penyilangan.
Fi : Nilai Fitness kromosom ke-i.
fi : Panjang Lintasan kromosom ke-i.
e. Mutasi
Mutasi iadalah iproses iuntuk
c. Seleksi
menciptakani individu ibaru idengan
Seleksi adalah proses pemilihan
memodifikasi igeni individu. Prosesi ini
kromosom-kromosom yang akan
dimodelkan seperti kehidupan yang terjadi
dipertahankan pada populasi selanjutnya.
di alam. Probabilitas dari suatuigen biasanya
Pada penelitian ini menggunakan konsep
dipilih sangat kecil, sama sepertiikejadian
kerja metode roulette wheel sama seperti
yang sebenarnya dalam kehidupan sehingga
sebuah roda roulet yang dapat dilakukan
memungkinkan terjadinya mutasi genetis
dengan pemilihan secara acak
tetapi dalam prosentasi sangat kecil. Berikut
menggunakan bilangan real. Pada penelitian
ini adalah ilustrasi mutasi :
Rohman,dkk (2020) pencarian seleksi dapat
dilakukan dengan langkah-langkah :
1) Menghitung nilai fitness relatif dengan f. Syarat berhenti
rumus relatif 𝑝𝑖 =
𝐹𝑖 Proses ioptimasi idalam iAlgoritma
𝑈𝑘𝑃𝑜𝑝
∑𝑖=1 𝐹𝑖
Genetika akan berhenti ketika syarat
2) Menghitung nilai fitness komulatif berhentiidipenuhi. Beberapaisyarat berhenti
dengan rumus komulatif 𝑞1 = yang dapat digunakan yaitu batas nilai
𝑝1 dan𝑞𝑖 = 𝑞(𝑖−1) + 𝑝𝑖 , i=2,3,...,UkPop

460
 AHMAD TOHARI, YULIANI PUJI ASTUTI

fungsi ifitness, ibatas inilai ifungsi iobjektif, dilakukan dengan cara observasi, wawancara, dan
batas iwaktu ikomputasi, banyak igenerasi, pengamatan jalur pada google maps.
dan terjadiikonvergensi. Populasi dalam penelitian ini adalah 19 titik
Pemilihan syarat berhenti yang paling sesuai kantor pos yang ada di beberapa kecamatan di
sangat bergantung pada tingkat kerumitan Kabupatten Lamongan. Penerapan Algoritma
masalah idan iperangkat ikeras iyang Genetika dilakukan dengan menentukan jarak,
digunakan. Pada kasus-kasus tertentu yang menghitung jarak optimal melalui tahap-tahap
biasanya digunakan adalah banyak algoritma genetika seperti:
generasi, tetapi belum tentu syaratiberhenti 1. Populasi awal
tersebut dapat diterapkan pada kasus 2. Proses evaluasi
lainnya. Namun, tidak imenutup 3. Seleksi
kemungkinan untuk melakukan kombinasi 4. Crossover
beberapa syaratiberhenti (Zukhri,2014). 5. Mutasi

C. Biaya optimasi HASIL DAN PEMBAHASAN

Pada penelitian ini peneliti A. HASIL
melakukan perhitungan biaya bahan bakar 1. Penerapan Algoritma Genetika
yang dilakukan oleh PT. Pos Indonesia Penelitian ini mengkaji tentang pengiriman
Cabang Lamongan pada 12 lokasi dalam surat dan barang di PT. Pos Indonesia Cabang
satu kali perjalanan. Perhitungan bahan Lamongan dengan permasalahan menentukan
bakar disesuaikan dengan harga bahan rute terpendek. Setiap perusahaan jasa
bakar yang berlaku. Dalam website pengiriman memiliki tujuan untuk
idxchannel menjelaskan bahwa konsumsi mempermudah pengiriman barang dari
bahan bakar untuk mobil rata-rata dapat pengirim agar dapat diterima oleh penerima
menempuh 10 Km/liter. Maka dapat dengan cepat. Pencarian rute terpendek
disumpulkan bahwa 1 liter bensin pertalite menggunakan TSP terbaik dengan rute yang
dengan harga Rp 10.000,00 untuk saat ini akan dilalui oleh kurir. Pengacakan populasi
dapat menempuh 10 Km dan dalam 1 Km dilakukan menggunakan aplikasi python dan
menghabiskan 0,1 liter atau senilai Rp pernerapan algoritma genetika menggunakan
1.000,00 (Sihombing, 2023). Peneliti perhitungan manual. Dalam penelitian ini jarak
menggunakan rumus berikut untuk yang digunakan diinteger dalam satuan
menentukan total biaya yang akan kilometer (km).
dikeluarkan oleh jasa ekspedisi : Peneliti memperoleh data nama dan
Z = 𝑣𝑖 𝐶 alamat drop point beberapa kantor pos cabang
Z = 𝑣𝑖 𝑥 𝑅𝑝 1.000,00 Lamongan dari internet, kemudian dilakukan
Keterangan : proses pencarian alamat berdasarkan titik
𝑣𝑖 : Panjang lintasan kromosom ke-i koordinat menggunakan Google Maps. Jarak dari
C : Biaya bahan bakar setiap 1 Km kantor cabang ke drop point kantor pos
METODE Lamongan dalam satuan km sebagai berikut:
1. Kantor Pos Cabang Lamongan menuju
Penelitian ini menggunakan pendekatan
Kantor Pos Sukodadi = 11 Km
kuantitatif dengan jenis penelitian deskriptif
2. Kantor Pos Cabang Lamongan menuju
kuantitatif. Jenis penelitian kuantitatif deskriptif
Kantor Pos Karanggeneng = 23 Km
dilakukan untuk memperoleh informasi tentang
3. Kantor Pos Cabang Lamongan menuju
pencarian rute terpendek yang ditempuh kurir
Kantor Pos Paciran = 51 Km
dalam pengantaran barang dari kantor PT. Pos
4. Kantor Pos Cabang Lamongan menuju
Indonesia Cabang Lamongan menuju drop point
Kantor Pos Tikung = 8 Km
“PosAja”. Jenis penelitian deskriptif kuantitatif
difokuskan pada permasalahan dasar fakta yang

461
 PENERAPAN ALGORITMA GENETIKA …

5. Kantor Pos Cabang Lamongan menuju Kromosom 1 (v1)

Kantor Pos Kembangbahu = 14 Km = A-B-C-D-E-F-G-H-I-K-J-L-A
6. Kantor Pos Sukodadi menuju Kantor Pos Kromosom 2 (v2)
Karanggeneng = 12 Km = A-C-B-K-L-J-I-H-G-F-E-D-A
7. Kantor Pos Sukodadi menuju Kantor Pos Kromosom 3 (v3)
Sekaran = 11 Km = A-L-J-I-H-K-G-F-E-D-C-B-A
8. Kantor Pos Sukodadi menuju Kantor Pos Kromosom 4 (v4)
Kembangbahu = 14 Km = A-B-K-L-J-I-H-G-F-E-D-C-A
9. Kantor Pos Sukodadi menuju Kantor Pos Kromosom 5 (v5)
Babat = 19 Km = A-D-E-C-F-G-H-I-J-L-K-B-A
10. Kantor Pos Karanggeneng menuju Kantor Kromosom 6 (v6)
Pos Paciran = 23 Km = A-B-C-D-E-F-G-H-K-I-J-L-A
11. Kantor Pos Karanggeneng menuju Kantor b. Proses Evaluasi
Pos Laren = 11 Km Pada tahap evaluasi dilakukan
12. Kantor Pos Karanggeneng menuju Kantor pencarian nilai evaluai dan nilai fittnes setiap
Pos Sekaran = 17 Km kromosom. Hasil perhitungan Panjang
13. Kantor Pos Paciran menuju Kantor Pos Laren lintasan dan nilai fitness adalah sebagai
= 17 Km berikut:
14. Kantor Pos Laren menuju Kantor Pos Sekaran f1 (A-B-C-D-E-F-G-H-I-K-J-L-A) = 171
= 10 Km f2 (A-C-B-K-L-J-I-H-G-F-E-D-A) = 203
15. Kantor Pos Sekaran menuju Kantor Pos Babat f3 (A-L-J-I-H-K-G-F-E-D-C-B-A) = 182
= 15 Km f4 (A-B-K-L-J-I-H-G-F-E-D-C-A) = 174
16. Kantor Pos Babat menuju Kantor Pos f5 (A-D-E-C-F-G-H-I-J-L-K-B-A) = 197
Kembangbahu = 30 Km f6 (A-B-C-D-E-F-G-H-K-I-J-L-A)=186
17. Kantor Pos Babat menuju Kantor Pos Perhitungan nilai fitness dilakukan
1
Ngimbang = 23 Km menggunakan rumus 𝐹𝑖 = dengan hasil :
𝑓𝑖
18. Kantor Pos Ngimbang menuju Kantor Pos Kromosom fi Fi
Sambeng = 9 Km
v1 171 0,0058
19. Kantor Pos Sambeng menuju Kantor Pos
Kembangbahu = 20 Km v2 203 0,0049
20. Kantor Pos Sambeng menuju Kantor Pos v3 182 0,0055
Mantup = 12 Km
v4 174 0,0057
21. Kantor Pos Mantup menuju Kantor Pos
Kembangbahu = 12 Km v5 197 0,0051
22. Kantor Pos Mantup menuju Kantor Pos v6 186 0,0054
Tikung = 11 Km
TOTAL 0,0324
23. Kantor Pos Kembangbahu menuju Kantor
Pos Tikung = 6 Km
c. Seleksi

Tahap-Tahap Algoritma Genetika Proses iseleksi iadalah isuatu iproses

Siklus Pertama : untuk mencari kromosomiterbaikidalam satu
generasi. Pada tahap ini kromosomidiseleksi
a. Populasi awal
sesuai dengan nilai fitness yang telah
Populasi awalidiambil secaraiacak dari dihitung. Proses seleksi dilakukan dengan
banyaknya solusi jaluriyang memungkinkan membandingkaninilai probabilitasikomulatif
untukidilalui kurir. Setiap kode huruf hanya dengan nilai acak roulette whell. Rumus
boleh muncul 1 kali dalam 1 kromosom yang digunakan dalam proses seleksi adalah
𝐹𝑖
kecuali titik awal. Hasil yang diperoleh fitness relatif 𝑃𝑖 = 𝑈𝑘𝑃𝑜𝑝 dengan hasil
∑𝑖=1 𝐹𝑖
adalah sebagai berikut: sebagai berikut:

462
 AHMAD TOHARI, YULIANI PUJI ASTUTI

Tahap crossover dilakukan setelah

mendapatkan induk dari proses seleksi.
Semakin besar nilai probabilitas persilangan
menjadikan semakin cepat terbentuknya
struktur tunggal baru dalam populasi.
Terlihat pada Tabel 4.6 terdapat calon induk
terpilih menggunakan probabilitas
penyilangan sebesar 50% yang akan
dilakukan crossover:
Caloon R Induk
Kromo fi Fi P Q
Induk Terpilih
som
v3 0,241 v3
v1 171 0,0058 0,179 0,179
v5 0,488 v5
v2 203 0,0049 0,151 0,33
v6 0,849
v3 182 0,0055 0,17 0,5
v4 0,737
v4 174 0,0057 0,176 0,676
v3 0,334 v3
v5 197 0,0051 0,157 0,833
v1 0,458 v1
v6 186 0,0054 0,167 1
Terdapat 4 kromosom terpilih yaitu
TOTA 0,0324
v3, v5, v3, v1 yang akan dipasangkan menjadi
L
v3, v5, v3, v1 seperti halnya perkawinan silang
Ketika sudah menemukan nilai
yang saling menukar gen. dapat dilihat dari
fitness komulatif maka dilakukan
perhitungan random permutasi dengan crossover berikut :
menggunakan python. Random permutasi
Crossover 1 : v3,v5
ini dilakukan agar menciptakan calon induk
baru pada crossover. Hasil random
permutasi yang diperoleh:

Kromo P q r Calon Crossover 2 : v3,v1

som Induk
v1 0,179 0,179 0,358 v3
v2 0,151 0,33 0,745 v5
v3 0,17 0,5 0,917 v6 e. Mutasi
Setelah dilakukan proses crossover
v4 0,176 0,676 0,541 v4
didapatkan keturunan-keturunan yang akan
v5 0,157 0,833 0,473 v3 di proses mutasi. Proses mutasi yang
v6 0,167 1 0,063 v1 digunakan adalah mutasi untuk optimasi
kombinatorial order based mutation, position
Dari pencarian random permutasi
based mutation, dan scramble mutation.
didapatkan calon induk crossover dengan
Dengan perhitungan manual dan
ketentuan jika r < q1 maka dipilih kromosom
pertama, jika qi < r < q(i+j) dengan berdasarkan rute pada graf Gambar 4.1
j=(1,2,...,UkPop) maka pilih kromosom ke- berikut mutasi yang diperoleh:
(i+j). 1. Anak 1 (v7)
A D E F H C G I J L K B A
d. Crossover

463
 PENERAPAN ALGORITMA GENETIKA …

Dengan mutasi berurutan peneliti

memindahkan titik H dan G. Sehingga titik Kromosom fi Fi
G dan H bertukar posisi menjadi : v7 203 0,0049
A D E F G C H I J L K B A v8 171 0,0058
Tetapi setelah dilakukan mutasi v6 186 0,0054
berurutan tidak terdapat jalur yang valid v4 174 0,0057
atau dapat ditempuh maka dilakukan v9 171 0,0058
mutasi posisi C dikarenakan titik C yang v10 158 0,0063
tidak dapat dilalui setelah titik G. TOTAL 0,0339
A D E F G H I J L K B C A
b. Seleksi
2. Anak 2 (v8)
Rumus yang digunakan dalam proses
A L J K I G H F E D C B A 𝐹𝑖
seleksi adalah fitness relatif 𝑃𝑖 =
Dengan mutasi berurutan peneliti 𝑈𝑘𝑃𝑜𝑝
∑𝑖=1 𝐹𝑖
memindahkan titik G dan H. Sehingga titik dengan hasil sebagai berikut:
G dan H bertukar posisi menjadi : Kromo fi Fi P q
A L J K I H G F E D C B A som
3. Anak 3 (v9) v1 203 0,0049 0,145 0,145
A B C E F D G H I K J L A v2 171 0,0058 0,171 0,316
Setelah dilihat dari graf, kromosom v3 186 0,0054 0,159 0,475
diatas tidak valid ketika menuju ke titik D v4 174 0,0057 0,168 0,643
maka dilakukan mutasi posisi titik D. v5 171 0,0058 0,171 0,814
A B C D E F G H I K J L A v6 158 0,0063 0,186 1
4. Anak 4 (v10) TOTA 0,0339
A L J K I H G F E D C B A L
Dengan mutasi berurutan Ketika sudah menemukan nilai fitness
memindahkan titik J dan K. Sehingga titik K komulatif maka dilakukan perhitungan
dan J bertukar posisi menjadi : random permutasi dengan menggunakan
A L K J I H G F E D C B A python. Random permutasi ini dilakukan
agar menciptakan calon induk baru pada
crossover. Hasil random permutasi yang
Siklus Kedua :
diperoleh:
a. Proses Evaluasi
Kromo P Q R Calon
Pada siklus kedua dilakukan proses
som Induk
serupa dimulai dari Proses Evaluasi sampai
v1 0,145 0,145 0,041 v7
dengan Mutasi. Dengan hasil yang telah
v2 0,171 0,316 0,613 v4
diperoleh pada siklus pertama dan
v3 0,159 0,475 0,832 v10
mempertahankan kromosom yang tidak
v4 0,168 0,643 0,351 v6
terpilih sebagai induk crossover sehingga
menghasilkan perhitungan jarak dan nilai v5 0,171 0,814 0,794 v9
fitness sebagai berikut: v6 0,186 1 0,991 v10
f7 (A-D-E-F-G-H-I-J-L-K-B-C-A) = 203 Dari pencarian random permutasi
f8 (A-L-J-K-I-H-G-F-E-D-C-B-A) = 171 didapatkan calon induk crossover dengan
f6 (A-B-C-D-E-F-G-H-K-I-J-L-A) = 186 ketentuan jika r < q1 maka dipilih kromosom
f4 (A-B-K-L-J-I-H-G-F-E-D-C-A) = 174 pertama, jika qi < r < q(i+j) dengan
f9 (A-B-C-D-E-F-G-H-I-K-J-L-A) = 171 j=(1,2,...,UkPop) maka pilih kromosom ke-
f10 (A-L-K-J-I-H-G-F-E-D-C-B-A) = 158 (i+j).
Perhitungan nilai fitness dilakukan
1 c. Crossover
menggunakan rumus 𝐹𝑖 = dengan hasil :
𝑓𝑖

464
 AHMAD TOHARI, YULIANI PUJI ASTUTI

Terlihat pada Tabel 4.11 terdapat terpendek PT. Ps Indonesia cabang Lamongan
calon induk terpilih menggunakan selanjutnya peneliti melakukan perhitungan
probabilitas penyilangan sebesar 50% yang
cost untuk menentukan besar biaya yang
akan dilakukan crossover :
CALON R Induk harus dikeluarkan dalam satu kali perjalanan
INDUK Terpilih untuk mengantarkan paket surat dan barang.
v7 0,675
Selain itu perhitungan cost digunakan untuk
v4 0,745
v10 0,808 memudahkan dalam menentukan biaya
v6 0,796 pengiriman surat dan barang.
v9 0,343 v9 Langkah pertama yang dilakukan
v10 0,127 v10
untuk mengitung cost adalah memasukkan
Terdapat 2 kromosom terpilih yaitu
v9, v10 seperti pada siklus pertama, hasil kromosom yang telah didapatkan dari
dilakukan perkawinan silang yang saling penerapan algoritma genetika.
menukar gen. dapat dilihat dari crossover
𝑓1 (A-B-C-D-E-F-G-H-I-K-J-L-A) = 171
berikut :
Crossover : v9,v10 𝑓2 (A-C-B-K-L-J-I-H-G-F-E-D-A) = 203
𝑓3 (A-L-J-I-H-K-G-F-E-D-C-B-A) = 182
𝑓4 (A-B-K-L-J-I-H-G-F-E-D-C-A) = 174
𝑓5 (A-D-E-C-F-G-H-I-J-L-K-B-A) = 197
d. Mutasi
𝑓6 (A-B-C-D-E-F-G-H-K-I-J-L-A) = 186
Setelah dilakukan proses crossover
didapatkan keturunan-keturunan yang akan Kromosom baru :
di proses mutasi. Dengan perhitungan 𝑓7 (A-D-E-F-G-H-I-J-L-K-B-C-A) = 203
manual seperti siklus pertama mutasi yang
𝑓8 (A-L-J-K-I-H-G-F-E-D-C-B-A) = 171
diperoleh adalah :
1. Anak 1 (v11) 𝑓9 (A-B-C-D-E-F-G-H-I-K-J-L-A) = 171
A L J K I H G F E D C B A 𝑓10 (A-L-K-J-I-H-G-F-E-D-C-B-A)= 158
Dengan mutasi berurutan peneliti 𝑓11 (A-L-K-J-I-H-G-F-E-D-C-B-A)= 158
memindahkan titik J dan K. Sehingga
𝑓12 (A-B-C-D-E-F-G-H-I-K-J-L-A)= 171
titik J dan K bertukar posisi menjadi :
A L K J I H G F E D C B A Dari 12 kromosom diatas dapat diketahui
2. Anak 2 (v12) jalur terpendek terdapat pada kromosom ke
A B D C E F G H I K J L A 10 dan 11 yaitu 158 KM. Dapat diperoleh
Dengan mutasi berurutan peneliti
perhitungan berikut :
memindahkan titik D dan C. Sehingga
titik D dan C bertukar posisi menjadi : Z = 𝑓𝑖 C
A B C D E F G H I K J L A Z = 158 . Rp 1.000,00
Pada siklus kedua ini dikarenakan
Z = Rp 158.000,00
terdapat kromosom yang sama maka
terjadi konvergensi pada kromosom Jadi hasil perhitungan biaya yang harus
9,10,11, dan 12 Sehingga dapat dikeluarkan perusahaan untuk melakukan
memenuhi syarat berhenti. pengriman surat dan barang dengan
2. Perhitungan Cost
menggunakan rumus tersebut adalah Rp.
Setelah melakukan penerapan
158.000.
algoritma genetika dalam menentukan rute

465
 PENERAPAN ALGORITMA GENETIKA …

B. PEMBAHASAN kelemahan menggunakan perhitungan algoritma

Berdasarkan ihasil ipenelitian iyang itelah genetika.
dilakukan di PT. Pos Indonesia cabang Keunggulan algoritma genetika adalah
Lamongan peneliti memperoleh hasil pencarian waktu komputasi yang dibutuhkan untuk
titik lokasi penelitian dengan bantuan Google penyelesaian permasalahan cenderung stabil dan
maps dan menghasikan koordinat yang cukup memberikan hasil rute terpendek meskipun
akurat. Penggunaan Googleimaps bisaimenghemat dengan jumlah kantor yang besar. Sedangkan
waktu dan biaya dalam pencarian jarak antar kelemahan algoritma genetika adalah
lokasi drop point. Hasil pencarian solusi yang bergantung pada ukuran populasi, besar
optimal dengan menggunakan metode algoritma generasi, ukuran peluang crossover dan mutasi.
genetika dilakukan dengan perhitungan manual. Pada skripsi ini peneliti melakukan 2
Perhitungan yang dilakukan diberhentikan pada siklusdan ternyata pada siklus kedua memiliki
2 siklus karena setelah melakukan perhitungan 2 hasil yang sama dengan siklus pertama, maka
siklus peneliti menemukan hasil yang sama dan peneliti beranggapan bahwa dengan 2 siklus
dianggap sudah cukup optimal. tersebut dirasa sudah cukup untuk menentukan
Solusi optimal dari hasil permasalahan TSP rute terpendek dikarenakan pada dasarnya sifat
dengan imenggunakan ialgoritma igenetika dari algoritma genetika adalah randomisehingga
menghasilkan irute iterbaik ipengiriman ibarang untuk mengetahui kapan hasil yang optimal
dan surat PT. Pos Indonesia cabang Lamongan muncul tidak diketahui pada generasi dan
adalah rute dari Kantor Pos Cabang Lamongan - populasi keberapa.
Kantor Pos Sukodadi, Kantor Pos Cabang
PENUTUP
Lamongan - Kantor Pos Karanggeneng, Kantor
Pos Cabang Lamongan - Kantor Pos Paciran, SIMPULAN
Kantor Pos Cabang Lamongan - Kantor Pos Dari hasil dan pembahasan penelitian dapat
Tikung, Kantor Pos Cabang Lamongan - Kantor disimpulkan bahwa:
Pos Kembangbahu, Kantor Pos Sukodadi - 1. Hasil penerapan Algoritma genetika pada
Kantor Pos Karanggeneng, Kantor Pos Sukodadi rute pengiriman PT. Pos Cabang Lamongan
- Kantor Pos Sekaran, Kantor Pos Sukodadi - dilakukan 2 siklus. Solusi rute terpendek
Kantor Pos Kembangbahu, Kantor Pos Sukodadi pada 12 titik adalah A-L-K-J-I-H-G-F-E-D-
- Kantor Pos Babat, Kantor Pos Karanggeneng - C-B-A dengan total jarak tempuh sebesar
Kantor Pos Paciran, Kantor Pos Karanggeneng - 158km.
Kantor Pos Laren, Kantor Pos Karanggeneng - 2. Perhitungan cost yang dilakukan setelah
Kantor Pos Sekaran, Kantor Pos Paciran - Kantor menemukan rute terpendek mendapatkan
Pos Laren, Kantor Pos Laren - Kantor Pos hasil Rp. 158.000 dalam 1 kali perjalanan.
Sekaran, Kantor Pos Sekaran - Kantor Pos Babat,
Kantor Pos Babat - Kantor Pos Kembangbahu, SARAN
Kantor Pos Babat - Kantor Pos Ngimbang, Kantor Dari hasil dan pembahasan penelitian
Pos Ngimbang - Kantor Pos Sambeng, Kantor Pos diatas, peneliti memberikan beberapa saran yang
Sambeng - Kantor Pos Kembangbahu, Kantor Pos diharapkan dapat menjadi bahanipertimbangan bagi
Sambeng - Kantor Pos Mantup, Kantor Pos perusahaanidan penelitianiselanjutnya seperti:
Mantup - Kantor Pos Kembangbahu, Kantor Pos 1. Bagi perusahaan: Agar penelitian ini dapat
Mantup - Kantor Pos Tikung, Kantor Pos dijadikan pertimangan kurir dalam
Kembangbahu - Kantor Pos Tikung. melakukan mengantaran barang melalui
Berdasarkan hasil pencarian solusi rute jalur yang optimal.
terpendek dalam mengiriman barang dari kantor 2. Bagi penelitian selanjutnya: Agar dapat
cabang menuju drop point dengan 12 populasi mengembangkan metode Algoritma
menghasilkan 1 solusi yang paling baik Genetika berbasis aplikasi python agar
dibandingkan dengan yang lain. Keunggulan dan dapat digunakan pada platform dan dapat
dikembangkan menggunakan jenis

466
 AHMAD TOHARI, YULIANI PUJI ASTUTI

Algoritma yang lainnya agar memperoleh

hasil yang lebih optimal.

DAFTAR PUSTAKA
Basuki, A. (2003). Strategi menggunakan algoritma
genetika. Politeknik Elektronika Negeri Surabaya
PENSITS.
Candrawati, L. G. A., & Kadyanan, I. G. A. G. A.
(2017). Optimasi Traveling Salesman Problem
(TSP) Untuk Rute Paket Wisata Di Bali dengan
Algoritma Genetika. Jurnal Ilmiah Komputer,
10(1), 27–32.
Nugroho Wahyu Trianto, dkk. (2007). ALGORITMA
GENETIKA DALAM PROGRAM PENCARIAN
JALUR ALTERNATIF. 1, 2–9.
Paillin, D. B., & Tamaela, M. (2019). Analisis Pola
Rute Distribusi Paket Pada [Link] Indonesia
(Persero) Ambon Dengan Menggunakan
Metode Travelling Salesman Problem Dan
Differential Evolution. Arika, 13(2), 75–86.
[Link]
Rohman, S., Zakaria, L., Asmiati, A., & Nuryaman,
A. (2020). Optimisasi Travelling Salesman
Problem dengan Algoritma Genetika pada
Kasus Pendistribusian Barang PT. Pos
Indonesia di Kota Bandar Lampung. Jurnal
Matematika Integratif, 16(1), 61.
[Link]
73
Sihombing Tigor. (2023). 1 Liter Bensin Berapa
Kilometer Mobil Bisa Melaju? Moladin.
[Link]
berapa-kilometer-mobil-bisa-melaju/
Utami, P. Y., Suhery, C., & Ilhamsyah. (2014).
Aplikasi Pencarian Rute Terpendek
Menggunakan Algoritma Genetika (Studi
Kasus: Pencarian Rute Terpendek Untuk
Pemadam Kebakaran Di Wilayah Kota
Pontianak). Jurnal Coding Sistem Komputer
Universitas Tanjungpura, 02(1), 19–25.
Zukhri, Z. (2014). Algoritma Genetika Metode
Komputasi Evolusioner untuk Menyelesaikan
Masalah Optimasi. CV. Andi Offset.

467