Pengembangan Algoritma Ant Colony System Pada Heterogeneous Vehicle Routing Problem with Soft Time Window Development of Ant Colony System Algorithm in Heterogeneous Vehicle Routing Problem with Soft Time Window Sonna Kristina.
Ricky Sianturi.
Valian Janelven Wijaya Program Studi Teknik Industri.
Institut Teknologi Harapan Bangsa E-mail: sonna@ithb.
id, ricky@ithb.
id, valianjwijaya@gmail.
Abstrak Setiap perusahaan umumnya memiliki sistem distribusi dan transportasi dalam menunjang pengiriman barang kepada customer.
Diperlukan sistem distribusi yang efektif dan efisien sehingga biaya dari transportasi dalam perusahaan dapat diminimasi.
Penelitian ini bertujuan untuk mengembangkan algoritma Ant Colony System (ACS) untuk model matematis Heterogeneous Vehicle Routing Problem with Soft Time Window (HVRPSTW) pada penentuan rute transportasi yang dapat meminimasi biaya pada perusahaan PT XYZ.
HVRPSTW merupakan VRP yang mempertimbangkan kendaraan yang beragam dan jendela waktu dengan adanya biaya penalti yang dibebankan apabila kendaraan tiba di luar waktu yang telah ditentukan.
Salah satu cara yang digunakan untuk menyelesaikan permasalahan VRP adalah metode metaheuristic ACS.
Metode ACS diimplementasikan untuk menemukan rute kendaraan terbaik sesuai dengan kendala-kendala yang sudah ditentukan.
Tahapan awal adalah mencari solusi awal menggunakan metode Nearest Neighbour yang akan digunakan sebagai pheromone awal.
Proses pencarian rute pada ACS menggunakan tahapan tour construction lalu dilakukan update pheromone.
Pemecahan masalah akan dilakukan dengan bantuan aplikasi Python.
Hasil dari penelitian menunjukkan bahwa dihasilkan total jarak sebesar 1448,98 km dan total cost sebesar Rp.
367,86, di mana terjadi selisih jarak dengan penelitian sebelumnya menggunakan metode eksak sebesar 6,48 km .
,45%) dan selisih total biaya sebesar Rp.
248,86 .
,19%).
Kata kunci: ant colony optimization, vehicle routing problem, kapasitas kendaraan yang beragam, jendela waktu, biaya transportasi.
Abstract Every enterprise commonly has distribution and transportation system to support the delivery of goods to customers.
An effective and efficient distribution system is needed so that the costs of transportation can be minimized.
This research is aimed to develop the Ant Colony System (ACS) algorithm for the Heterogeneous Vehicle Routing Problem with Soft Time Window (HVRPSTW) mathematical model in determining transportation routes that can minimize costs at PT XYZ.
HVRPSTW is VRP which considers various vehicles and time window with a penalty fee charged if the vehicle arrives outside the specified time.
One of the methods used to solve VRP problems is the metaheuristic ACS.
ACS method is implemented to find the best vehicle route in accordance with predetermined constraints.
The initial stages in ACS is to discover an initial solution as initial solution using the Nearest Neighbour The routing process in ACS begins with the tour construction stage then continue with updating the pheromone.
The solution to the problem will be generated by Python.
The results showed that the total distance generated using the ACS method is 1448,98 km and total cost is IDR 3.
367,86, where the difference with previous research using the exact method is 6,68 km .
,45%) and IDR 42.
248,86 .
,19%).
Keywords: ant colony optimization, vehicle routing problem, different vehicle capacity, time windows, transportation cost.
Diterima tgl 18 Agustus 2020.
Disetujui tgl 19 November 2020.
Terbit online tgl 28 Desember 2020 PENGEMBANGAN ALGORITMA ANT COLONY SYSTEM (Sonna K.
, dkk.
Pendahuluan Proses distribusi merupakan salah satu bagian yang sangat penting dalam sistem operasional sebuah perusahaan.
Secara umum distribusi memiliki fungsi untuk mengantar produk dari lokasi di mana produk itu diproduksi ke lokasi di mana produk tersebut akan digunakan (Pujawan dan Mahendrawathi, 2.
Distribusi tidak bisa lepas dari kegiatan transportasi yang sangat berperan penting dalam mendukung kegiatan distribusi dalam menyalurkan barang kepada customer.
Demand yang terus bertambah akan membuat biaya transportasi akan semakin besar juga sesuai dengan rute dan moda transportasi yang digunakan.
Pentingnya minimasi biaya transportasi akan membuat proses distribusi menjadi lebih optimal dan kinerja perusahaan menjadi efektif dan juga efisien, salah satunya dengan Vehicle Routing Problem (VRP).
VRP adalah suatu model yang bertujuan untuk menemukan rute dengan biaya minimum untuk pengiriman suatu produk kepada sejumlah customer di beberapa lokasi yang berbeda, dengan menggunakan kendaraan, yang menggambarkan masalah transportasi sebagai model graf (G.
Gunawan et.
, 2.
VRP sendiri sudah banyak dikembangkan oleh berbagai peneliti untuk mendapatkan solusi yang optimum, beberapa diantaranya adalah CVRP yang mempertimbangkan kapasitas kendaraan.
VRPTW yang mempertimbangkan jendela waktu.
CVRPTW merupakan gabungan dari CVRP dengan VRPTW yang mempertimbangkan kapasitas kendaraan sekaligus dengan jendela waktu.
HVRPSTW yang mempertimbangkan kapasitas kendaraan yang berbeda dan jendela waktu dengan biaya penalti yang dibebankan apabila kendaraan datang tidak sesuai waktu permintaan (M.
Zirour, 2.
Heterogeneous Vehicle Routing Problem with Soft Time window (HVRPSTW) merupakan pengembangan VRP yang sudah dikembangkan pada penelitian (H.
Wijaya, 2.
Pengembangan model matematis ini merupakan pengembangan yang memperhatikan moda transportasi yang beragam dan memperhatikan faktor jendela waktu pada setiap lokasi untuk menyelesaikan permasalahan yang berasal dari penelitian sebelumnya dengan mempertimbangkan fixed cost, biaya parkir dan biaya tenaga kerja untuk penentuan rute dan moda transportasi pada PT XYZ, dimana perusahaan tersebut merupakan perusahaan distribusi elektronik dan aksesoris handphone di kota Bandung.
Kelebihan dari penelitian (H.
Wijaya, 2.
adalah dapat menemukan solusi yang optimum dikarenakan menggunakan metode solusi eksak dimana metode ini mencoba semua kemungkinan sampai didapat solusi yang optimum.
Namun, sampai saat ini belum ada suatu metode eksak yang dapat menjamin keberhasilan solusi optimal dan waktu komputasi yang lama seiring dengan jumlah customer dan kendaraan.
HVRPSTW dikarakteristikan ke dalam kelas NPhard (Nondeterministik Polynomial-har.
Berdasarkan hal tersebut, banyak peneliti lebih memusatkan kepada pengembangan metode-metode pendekatan .
seperti Simulated Annealing.
Algoritma Semut (Ant Algorith.
Algoritma Genetika.
Tabu Search, dan lain Penelitian ini mengembangkan metode metaheuristic Ant Colony Sytem (ACS) yang merupakan pengembangan dari ACO untuk model matematis hasil penelitian (H.
Wijaya, 2.
Algoritma ACO telah banyak diaplikasikan dalam berbagai bidang yang mencakup beberapa persoalan yaitu.
Traveling Salesman Problem (TSP) untuk mencari rute terpendek dalam sebuah graph menggunakan rute Hamilton.
Job-shop Scheduling Problem (JSP) untuk mencari lintasan sejumlah n pekerjaan menggunakan sejumlah m mesin demikian sehingga seluruh pekerjaan diselesaikan dalam waktu yang seminimal mungkin dan Vehicle Routing Problem (VRP) untuk pengaturan rute kendaraan sehingga meminimalkan biaya (M.
Dorigo dan T.
StuAtzle, 2.
ACS merupakan metode yang digunakan untuk menyelesaikan masalah optimasi dimana inspirasi dalam memecahkan masalah tersebut berasal dari perilaku kumpulan atau kawanan semut dalam mencari sumber makanan dan metode metaheuristic ini dapat diterapkan dengan mudah pada dunia nyata dengan waktu penyelesaian yang lebih cepat dibandingkan dengan metode eksak (Karjono et.
, 2.
Metode Nearest Neighbour akan diterapkan pada algoritma ACS sebagai solusi awal untuk pembentukan pheromone agar solusi dari metode ACS lebih presisi.
Metode metaheuristic memerlukan metode heuristic di dalamnya agar solusi yang diperoleh tidak terjebak pada solusi local optimum dan melakukan pencarian di ruang solusi untuk menemukan solusi global (B.
Santosa dan T.
Ai, 2.
JOURNAL OF INTEGRATED SYSTEM VOL.
3 NO.
DESEMBER 2020: 85-102
Oleh karena itu rumusan masalah dari penelitian ini adalah bagaimana mengembangkan algoritma yang tepat dari ACS akan menyelesaikan permasalahan dan mendapatkan rute terpendek sehingga didapat minimasi biaya transportasi.
Algoritma yang dikembangkan akan dikodekan menggunakan aplikasi Python.
Tinjauan Pustaka 1 Vehicle Routing Problem VRP memiliki fungsi tujuan untuk meminimalkan biaya transportasi kendaraan dengan digambarkan sebagai suatu kasus dimana ada sejumlah kendaraan dengan kapasitas tertentu yang harus mengirim sejumlah barang dari suatu lokasi atau depot ke lokasi tujuan dengan asumsi jarak antara lokasi telah diketahui (Arvianto et.
, 2.
Formulasi VRP dapat dirumuskan sebagai berikut (S.
Kandou, 2.
Fungsi Tujuan:
MinEu kEaV EuiEaN Eu jAN Cij .
X ijk Dengan batasan:
Eu kEaV Eu jEaN X ijk A 1,Ai Ea N .
Setiap pelanggan hanya dapat dikunjungi oleh satu kendaran tepat satu kali.
EuiEaN di Eu jEaN X ijk C qi ,Ak EaV Total jumlah permintaan dalam satu rute tidak melebihi kapasitas kendaraan.
Eu jEaN X0 jk A 1,Ak EaV Menjamin kendaraan memulai perjalanan dari depot.
EuiEaN X ihk A Eu jEaN X hjk A 0,Ak EaV ,Ak EaV Memastikan bahwa setiap kendaraan yang mengunjungi pelanggan setelah selesai akan meninggalkan pelanggan tersebut.
EuiEaN X i,nA1,k A 1,Ak EaV Memastikan rute berakhir di depot.
Xijk EaA0,1A,Ai, j Ea N,Ak EaV Variabel keputusan ycuycnycyco merupakan bilangan biner.
Dengan Notasi:
: himpunan node : himpunan kendaraan i,j,h : indeks node : indeks kendaraan : biaya perjalanan dari i ke j : jumlah permintaan pelanggan i : kapasitas kendaraan PENGEMBANGAN ALGORITMA ANT COLONY SYSTEM (Sonna K.
, dkk.
2 Heterogeneous Vehicle Routing Problem with Soft Time window (HVRPSTW) HVRPSTW merupakan pengembangan dari VRP yang merupakan penggabungan dari Heterogeneous Vehicle Routing Problem dengan Vehicle Routing Problem with Soft Time Window (H.
Wijaya, 2.
HVRP merupakan pengembangan VRP yang mempertimbangkan kapasitas kendaraan yang bervariasi serta fixed cost dan variabel cost dengan tujuan agar dapat mengetahui penggunaan kendaraan yang tepat sesuai dengan rute dan permintaan pelanggan dan didapat biaya transportasi yang minimal.
VRPSTW merupakan pengembangan dari VRPTW yang mengizinkan kendaraan untuk datang melewati batas waktu namun dengan biaya denda yang harus dibayar.
Perumusan dari HVRPSTW dapat dirumuskan sebagai berikut:
Fungsi Tujuan:
Di mana.
Biaya perjalanan = Biaya penalti = Biaya tenaga kerja = Fixed cost = Biaya parkir = .
Dengan pembatas:
Persamaan .
merupakan pembatas untuk jumlah maximal kendaraan yang dapat melayani satu lokasi.
Persamaan .
merupakan pembatas kekontinuan rute.
Persamaan .
merupakan pembatas eliminasi subrute.
Persamaan .
merupakan pembatas jumlah muatan Pembatas .
merupakan pembatas bilangan biner.
Persamaan .
JOURNAL OF INTEGRATED SYSTEM VOL.
3 NO.
DESEMBER 2020: 85-102
merupakan pembatas waktu perjalanan.
Persamaan .
merupakan pembatas waktu tiba dan keberangkatan kendaraan.
Persamaan .
merupakan pembatas waktu penggunaan kendaraan.
Persamaan .
merupakan pembatas waktu keberangkatan.
Persamaan .
merupakan pembatas eliminasi multi trip.
Persamaan .
merupakan pembatas besar biaya penalti.
Persamaan .
merupakan pembatas lama parkir.
Dengan notasi:
: Demand permintaan pengiriman pada lokasi i : Waktu unloading pada lokasi i : Kapasitas maksimum kendaraan k BBk : Biaya bensin untuk kendaraan k : Kecepatan rata-rata kendaraan k : Batas waktu penggunaan k CPk : Biaya penalti kendaraan k WWk : fixecost untuk kendaraan k BPk : Biaya Parkir : Biaya Tenaga Kerja EPik : Lama waktu early penalti pada lokasi i dengan kendaraan k DPik : Lama waktu delay penalti pada lokasi i dengan kendaraan k Gjk : Waktu kendaraan k tiba di depot Rij : Jarak antara lokasi i ke lokasi i Cijk : Biaya kendaraan dari lokasi i ke lokasi i dengan kendaraan k Tijk : Waktu perjalanan dari lokasi i ke lokasi i dengan menggunakan kendaraan k Aik : Waktu kendaraan k datang ke lokasi i Bik : Waktu keberangkatan kendaraan k dari lokasi i TBPjk : Lama kendaraan k parkir di lokasi j Uij : Variabel bantu untuk eliminasi sub tur Xijk : Rute terpilih dari lokasi i ke lokasi j dengan kendaraan pengiriman k 3 Ant Colony Optimization (ACO) Algoritma semut pertama kali diperkenalkan oleh Moyson dan Manderick, lalu dikembangkan secara meluas oleh Marco Dorigo.
Algoritma semut merupakan salah satu pendekatan metaheuristic pada VRP dengan mengikuti perilaku semut ketika mencari makanannya (M.
Dorigo and T.
StuAtzle, 2.
Semut akan memilih jalan dan menyimpan pheromone sebagai panduan bagi semut yang lain untuk mengikuti jalan mereka.
Pheromone akan membusuk ketika jalur terlalu panjang sehingga probabilitas dari koloni untuk mengikuti jalan dari semut sebelumnya akan menjadi kecil dibanding dengan jalur yang pendek.
ACO memiliki beberapa jenis, yaitu Ant System (AS).
Max-Min Ant System (MMAS) dan Ant Colony System (ACS) makanannya (M.
Dorigo and T.
StuAtzle, 2.
1 Ant System Ant System merupakan jenis ACO yang pertama kali ditemukan.
Karakteristik utamanya adalah pada setiap iterasi, nilai pheromone diperbaharui oleh semua semut yang telah dibangun makanannya (M.
Dorigo and T.
StuAtzle, 2.
Ant System memiliki beberapa tahapan, yaitu:
Tour Construction Dalam menentukan rutenya, semut akan memilih secara acak lokasi tujuan mereka dengan Berikut adalah formulasi probabilitas penentuan lokasi:
PENGEMBANGAN ALGORITMA ANT COLONY SYSTEM (Sonna K.
, dkk.
Di mana, .
Dengan notasi:
: indeks lokasi : node yang belum dikunjungi oleh semut k : semut : probabilitas semut k menuju node selanjutnya : parameter intensitas jejak semut : parameter visibilitas jarak antar node : intensitas pheromone pada node i,j N.
) : kumpulan dari feasible component : invers dari jarak antar node i,j : jarak antar node i,j : intensitas pheromone pada node i,l : invers dari jarak antar node i,l Pheromone Update Setelah semut selesai dalam memilih rute, intensitas dari pheromone akan diperbaharui dengan .
Di mana, .
Dengan notasi:
: indeks lokasi : intensitas penguapan pheromone : semut : jumlah maksimal semut : jumlah pheromone pada node i,j oleh semut m : konstanta : panjang tour yang dibuat oleh semut m 2 Max-Min Ant System (MMAS) Max-Min Ant System merupakan pengembangan dari ACO yang sebelumnya.
Pada MMAS, hanya semut terbaik saja yang dapat mempengaruhi jejak pheromone (M.
Dorigo and T.
StuAtzle, 2.
Berikut adalah tahapan dalam MMAS:
Pheromone Update Di mana nilai merupakan batas atas dan batas bawah pada pheromone, dengan .
JOURNAL OF INTEGRATED SYSTEM VOL.
3 NO.
DESEMBER 2020: 85-102
Dan .
Dengan notasi:
Lbest : intensitas penguapan pheromone : jumlah semut : jumlah pheromone pada node i,j oleh semut terbaik : panjang tour yang dibuat oleh semut terbaik 3 Ant Colony System (ACS) Penelitian ini menggunakan algoritma dari Ant Colony System (ACS) karena Ant Colony System (ACS) merupakan pengembangan dari ACO yang lebih baik dibandingkan dengan Ant System (AS), di mana yang membedakan metode ACS dengan AS adalah adanya penambahan local pheromone update ketika proses update pheromone pada akhir konstruksi rute (T.
Diep dan N.
Van Hop, 2.
Pada update pheromone metode AS, dilakukan pada semua rute yang terbentuk, sedangkan pada metode ACS ada tahapan global update pheromone sehingga semut akan lebih mudah menentukan titik selanjutnya dan tahapan local update pheromone sehingga pheromone pada rute akan berkurang dan tidak akan dilewati lagi oleh semut yang lainnya.
Kebihan dari metode ACS dibandingkan metode ACO yang lain adalah pada tour construction dimana ACS memilih jalur dengan pseudorandom proportional rule, sedangkan metode ACO lainnya berdasarkan random proportional rule (A.
Leksono, 2.
Berikut adalah tahapan dari ACS:
Tour Construction Ketika pada node i, semut k akan memilih node j dengan formulasi:
Di mana.
J merupakan persamaan .
dengan nilai = 1.
Dengan notasi:
: indeks lokasi : node yang belum dikunjungi oleh semut k : parameter visibilitas jarak antar node : intensitas pheromone pada node i,l N.
P) : kumpulan dari feasible component : invers dari jarak antar node i,l : bilangan random yang terdistribusi uniform .
: parameter .
OqoO.
Global Pheromone Update Pembaharuan pheromone hanya dapat dilakukan oleh semut terbaik dengan formulasi:
Di mana, .
PENGEMBANGAN ALGORITMA ANT COLONY SYSTEM (Sonna K.
, dkk.
Dengan notasi:
: indeks lokasi : intensitas penguapan pheromone : intensitas pheromone pada node i,j : intensitas penguapan pheromone : jumlah pheromone pada node i,j oleh semut terbaik TCbest : Total cost yang dibuat oleh semut terbaik Local Pheromone Update Semut menggunakan aturan local pheromone update melewati .
Di mana, .
Dengan notasi:
: indeks lokasi : intensitas penguapan pheromone : total dari jumlah customer : inisialisasi pheromone : total initial cost 4 Nearest Neighbour Metode Nearest Neigbour merupakan metode heuristic yang dapat memecahakan permasalahan penentuan rute kendaraan atau VRP (N.
Mardiani et.
, 2.
Nearest Neighbour adalah sebuah metode untuk melakukan klasifikasi terhadap objek berdasarkan data yang jaraknya paling dekat dengan objek tersebut.
Metode Nearest Neighbour sering disebut juga sebagai pencarian jarak atau pencarian titik terdekat, dimana sebuah kendaraan k akan menuju lokasi selanjutnya yang belum dikunjungi dengan permintaan dari lokasi tersebut tidak melebihi kapasitas kendaraan k berdasarkan jarak yang terdekat dengan lokasi asal.
Apabila demand melebihi kapasitas kendaraan k maka pengiriman dilakukan lebih dari satu kali, di mana kendaraan menuju depot terlebih dahulu untuk loading lalu menuju ke tempat terdekat selanjutnya.
Langkah-langkah secara umum dalam menyelesaikan permasalahan dengan menggunakan Algoritma Nearest Neighbour adalah sebagai berikut:
Untuk tur pertama .
dan rute pertama .
, lokasi awal berada pada depot, lanjutkan ke Cari lokasi tujuan yang paling dekat dengan lokasi awal, lalu hubungkan kedua titik tersebut, lanjutkan ke langkah 3.
Set lokasi terakhir sebagai titik awal, ulangi langkah 2 hingga semua titik terkunjungi.
Jika semua titik sudah terkunjungi lanjutkan ke langkah 4.
Penentuan rute berhenti ketika semua lokasi sudah selasai dilayani.
5 Python Python merupakan salah satu bahasa pemrograman yang mudah untuk dipelajari dibandingkan dengan bahasa pemrograman lainnya (J.
Enterprise, 2.
Python merupakan bahasa pemrograman yang sifatnya interpretatif.
Python pertama kali dikembangkan oleh Guido van Rossum yang merupakan kelahiran Belanda pada tahun 1990 di Amsterdam.
Nama Python sendiri berasal dari acara televisi Monty PyhtonAos Flying Circus yang merukapakan acara televisi kesukaan dari Guido.
JOURNAL OF INTEGRATED SYSTEM VOL.
3 NO.
DESEMBER 2020: 85-102
Python merupakan pemrograman multiplatform yang berarti dapat dijalankan di berbagai platform sistem operasi.
Fitur-fitur pada Python adalah:
C Memiliki modul-modul yang Aosiap pakaiAo untuk berbagai keperluan.
C Memiliki struktur bahasa yang jelas, sederhana, dan mudah dipelajari.
C Memiliki system pengelolaan memori otomatis C Bersifat modular sehingga mudah dikembangkan dengan menciptakan modul-modul baru.
PENGEMBANGAN ALGORITMA ANT COLONY SYSTEM (Sonna K.
, dkk.
Pengembangan Algoritma 1 Tahapan Nearest Neighbour Gambar 1.
Bagan Alir Nearest Neighbour JOURNAL OF INTEGRATED SYSTEM VOL.
3 NO.
DESEMBER 2020: 85-102
Hitung waktu parkir, hitung total biaya parkir Hitung total demand Tidak Total demand < kapasitas Total demand = kapasitas Semua customer sudah terpenuhi Tidak Arahkan kendaraan menuju gudang Tidak Perbarui lokasi sekarang sebagai lokasi awal, r = r 1, t = t Hitung waktu perjalanan, waktu tiba, hitung total biaya perjalanan Pilih customer terdekat yang belum dikunjugi kendaraan yang sama Waktu tiba > batas pemakaian Tidak Hitung total biaya fixed cost dan total biaya tenaga kerja Pilih kapasitas kendaraan lainnya yang lebih besar dari demand Pilih customer terdekat yang belum dikunjungi Hitung total biaya Lokasi awal pada depot, t = t 1, r = 0 Tidak Semua customer sudah terpenuhi Selesai Gambar 1.
Bagan Alir Nearest Neighbour .
PENGEMBANGAN ALGORITMA ANT COLONY SYSTEM (Sonna K.
, dkk.
2 Tahapan Ant Colony System Start Inisialisasi parameter dan variabel ACS Inisialisasi solusi pertama berdasarkan metode Nearest Neighbour sebagai TCinitial, ite = 0, m = 0, trip = 0, rute = 0 Tetapkan lokasi semut awal berada pada gudang Mencari lokasi selanjutnya berdasarkan kriteria tour Pilih kendaraan secara acak Hitung waktu perjalanan, waktu Hitung total biya perjalanan Waktu tiba < batas bawah Tidak Waktu tiba > batas akhir Tidak Hitung waktu early penalty Hitung waktu unloading, dan waktu keberangkatan Gambar 2.
Diagram Alir Ant Colony System JOURNAL OF INTEGRATED SYSTEM VOL.
3 NO.
DESEMBER 2020: 85-102
Waktu batas pemaiakan Tidak Hitung waktu delay penalty, hitung biaya total penalty Hitung waktu parkir, hitung total biaya parkir Hitung total demand Total demand < kapasitas Tidak Tidak Total demand = kapasitas Semua customer sudah terpenuhi Sudah Arahkan kendaraan menuju lokasi gudang Belum Perbarui lokasi sekarang sebagai lokasi awal.
Ite, = ite, m = m, t = t, r = r 1 Hitung waktu pejalanan, waktu tiba, total biaya perjalanan Mencari node selanjutnya yang belum dikunjungi berdasarkan kriteria tour construction menggunakan kendaraan yang Waktu tiba > batas pemakaian Batalkan pemilihan customer Cari customer lainnya berdasarkan kriteria tour Tidak Tidak Ada customer yang layak Gambar 2.
Diagram Alir Ant Colony System .
PENGEMBANGAN ALGORITMA ANT COLONY SYSTEM (Sonna K.
, dkk.
Hitung total biaya fixed cost dan total biaya tenaga kerja Hitung total biaya transportasi Semua customer sudah terpenuhi Update Local Pheromon untuk rute terpilih.
Ite = ite, m = m 1, t = 0, r = 0 Belum Tidak Jumlah semut > jumlah semut max Lokasi awal pada gudang.
Ite = ite, m = m, t = t 1, r = 0 Mencari lokasi selanjutnya yang belum dikunjungi berdasarkan kriteria tour construction Menghitung total biaya untuk rute terbaik (TC), ite = ite 1, m = 0,t = 0, r = 0 Pilih kendaraan yang belum digunakan secara acak TC > TCinitial Tidak TCbest = TCinitial TCbest = TC Update global pheromone Hitung total biaya Bentuk rute terbaik Tidak Iterasi sudah Selesai Gambar 2.
Diagram Alir Ant Colony System .
JOURNAL OF INTEGRATED SYSTEM VOL.
3 NO.
DESEMBER 2020: 85-102
2 Analisis Sensitifitas Parameter memiliki dampak yang signifikan pada kinerja algoritma koloni semut, oleh karena itu, uji sensitifitas dibuat untuk mengetahui hubungan antara parameter dengan hasil dari ACS.
Parameter yang akan diuji adalah:
Visbilitas jarak antar node () Intensitas penguapan pheromone ( Probablitias aturan transisi .
Input dari analisis sensitifitas merupakan data real dari perusahaan pada tanggal 2 Januari 2017 dengan jumlah 8 customer dan 6 kendaraan.
Setiap pengujian dilakukan 50 replikasi.
1 Visibilitas Jarak Antar Node () Nilai memutuskan seberapa besar nilai visibilitas jarak antar node pada heuristic dapat dipertimbangkan dalam mekanisme pemilihan rute.
Ketika nilai meningkat maka peluang semut memilih jalur yang terpendek pun akan meningkat.
Dalam penelitian ini, nilai diuji dengan nilai 1, 3, 5 dan 10 (T.
Diep dan N.
Van Hop, 2.
Masing- masing dengan nilai , q0 = 0,9, iterasi = 100, dan jumlah semut = 10.
Hasil dari pengujian dapat dilihat pada gambar 6.
Gambar 3.
Hasil Pengujian Berdasarkan gambar 3 menunjukkan hubungan antara dengan total biaya transportasi, didapatkan nilai maksimum dan minimum dari hasil pengujian adalah konstan yang berarti nilai dari total biaya transportasi tidak sensitif terhadap perubahan nilai .
Berdasarkan 50 iterasi, didapatkan ratarata nilai optimum berada pada nilai = 0,3.
2 Intensitas Penguapan Pheromone ( ) Nilai A ditetapkan sebagai penunda konvergensi semut yang lebih cepat menuju suboptimal.
Nilai A digunakan sebagai parameter dalam prosedur pembaruan pheromone.
Dalam penelitian ini, nilai A diuji dengan nilai 0.
0,1.
0,3.
0,5 dan 1 (T.
Diep dan N.
Van Hop, 2.
Masing-masing dengan nilai , q0 = 0,9, iterasi = 100, dan jumlah semut = 10.
Hasil dari pengujian dapat dilihat pada gambar 4.
PENGEMBANGAN ALGORITMA ANT COLONY SYSTEM (Sonna K.
, dkk.
Gambar 4.
Hasil Pengujian Berdasarkan gambar 4 menunjukkan hubungan antara A dengan total biaya transportasi, didapatkan untuk nilai maksimum dan minimum dari pengujian tersebut adalah konstan yang berarti nilai dari total biaya transportasi tidak sensitif terhadap perubahan nilai A.
Berdasarkan 50 iterasi, didapatkan rata-rata nilai A optimum berada pada nilai A = 0,1.
3 Probabilitas Aturan Transisi .
Nilai q0 ditetapkan untuk memutuskan apakah semut melakukan eksploitasi atau melakukan eksplorasi dalam pencarian rute.
Semakin besar nilai q0 maka akan semakin besar juga kemungkinan semut dalam melakukan eksploitasi untuk melakukan pencarian rute.
Semakin kecil nilai q0 maka semut akan memiliki kecenderungan memilih rute berikutnya secara acak.
Dalam pengujian ini nilai q0 diuji dengan nilai 0.
0,1.
0,3.
0,5 dan 1 (T.
Diep dan N.
Van Hop, 2.
Masing- masing dengan nilai .
A = 0,1, iterasi = 100, dan jumlah semut = 10.
Hasil dari pengujian dapat dilihat pada gambar 8.
Gambar 5.
Hasil Pengujian q0 Berdasarkan gambar 5, menunjukkan hubungan antara q0 dengan total biaya transportasi, didapatkan pengujian nilai total biaya transportasi sensitif terhadap perubahan nilai q0 dikarenakan total biaya maksimum dan minimum yang didapat tidak konstan.
Sehingga berdasarkan gambar 5, maka nilai q0 yang optimum berada pada nilai q0 = 0,3.
Hasil Perhitungan Biaya Transportasi Perhitungan biaya transportasi dilakukan dengan bantuan dari aplikasi Python untuk mencari rute yang optimum pada model matematis HVRPSTW menggunakan ACS.
Hasil perhitungan transportasi secara lengkap dengan parameter ACS = 3, = 0,1, q0 = 0,3, iterasi = 1000, dan jumlah semut = 10.
JOURNAL OF INTEGRATED SYSTEM VOL.
3 NO.
DESEMBER 2020: 85-102
Berikut hasil perhitungan biaya transportasi untuk bulan Januari 2017 menggunakan metode eksak yang didapat dari penelitian sebelumnya dan metode ACS pada penelitian ini:
Tabel 1.
Hasil Perbandingan Biaya Transportasi
Eksak
ACS
Selisih Total Jarak 1442,5 Km 1448,98 Km 6,48 Km .
,45%) Total Biaya Transportasi Rp 3.
119,00
Rp 3.
367,86
Rp 42.
248,86 .
,19%)
Berdasarkan tabel 1, hasil perhitungan biaya transportasi menggunakan ACS mampu mendekati solusi optimum yang menggunakan metode eksak.
Selisih dari metode ACS dan metode eksak sebesar 1,19%.
Kesimpulan Berdasarkan rumusan masalah dan tujuan penelitian yang sudah dijabarkan, maka dapat diambil kesimpulan bahwa metode metaheuristic ACS dapat diterapkan dan berhasil dikembangkan untuk model matematis HVRPSTW yang terbukti dengan dihasilkannya total biaya dengan selisih sebesar 1,19% dan selisih jarak 0,45% saja terhadap penelitian milik Wijaya, 2019 .
, yang menggunakan metode eksak dengan hasil perhitungan total transportasi pada metode ACS sebesar Rp.
367,86 dan total jarak sebesar 1448,98 Km dengan total waktu komputasi sebesar 98,899 detik.
Daftar Pustaka