Algoritma Genetika Ganda untuk Capacitated Vehicle Routing Problem

Muhammad Luthfi Shahab, Mohammad Isa Irawan
Submission Date: 2015-07-30 12:24:16
Accepted Date: 2016-01-20 13:37:58

Abstract


Capacitated vehicle routing problem (CVRP) adalah salah satu variasi dari vehicle routing problem (VRP) yang menggunakan batasan kapasitas pada kendaraan yang dipakai. Ada banyak metode yang telah diteliti untuk bisa menyelesaikan CVRP, namun penggunaan algoritma genetika masih belum memberikan hasil yang memuaskan. Untuk mempermudah menyelesaikan CVRP, dapat dilakukan dekomposisi pada CVRP agar terbagi menjadi beberapa daerah yang dapat diselesaikan secara independen. Berdasarkan hal tersebut, dirumuskan algoritma genetika ganda yang terlebih dahulu berusaha untuk mendekomposisi CVRP dan kemudian mencari rute terpendek pada setiap daerah menggunakan dua algoritma genetika sederhana yang berbeda. Algoritma genetika ganda kemudian dibandingkan dengan algoritma genetika. Untuk membandingkan dua algoritma tersebut, dibuat empat permasalahan yaitu P50, P75, P100, dan P125 dengan pengujian pada setiap permasalahan menggunakan empat belas variasi kapasitas kendaraan yang berbeda. Didapatkan hasil bahwa algoritma genetika ganda lebih baik dari algoritma genetika dari segi waktu komputasi dan generasi. Dari segi jarak, algoritma genetika ganda juga lebih baik dari algoritma genetika kecuali untuk beberapa kapasitas kendaraan yang kecil pada permasalahan P50 dan P75.

Keywords


CVRP; algoritma genetika; algoritma genetika ganda

References


Ahmed, Z.H. 2005. “Genetic Algorithm for Travelling Salesman Problem using Sequential Constructive Crossover Operator”. International Journal of Biometrics & Bioinformatics 3, 96-105.

Coley, D.A. 1999. An Indtroduction to Genetic Algorithms for Scientists and Engineers. New Jersey: World Scientific.

Eiben, A.E. dan Smith, J.E. 2003. Introduction to Evolutionary Computing. Berlin: Springer.

Hermawan, A. 2012. “Penentuan Rute yang Optimal pada Kegiatan Distribusi BBM Menggunakan Ant Colony System”. Surabaya: Tugas Akhir, Jurusan Matematika, Institut Teknologi Sepuluh Nopember.

Hozairi, Buda, K., Masroeri, dan Irawan, M.I. 2014. “Implementation of Nondominated Sorting Genetic Algorithm – II (NSGA-II) for Multiobjective Optimization Problems on Distribution of Indonesian Navy Warship”. Journal of Theoretical and Applied Information Technology 64, 274-281.

Karakatic, S. dan Podgorelec, V. 2015. “A Suvey of Genetic Algorithms for Solving Multi Depot Vehicle Routing Problem”. Applied Soft Computing 27, 519-532.

Nazif, H. dan Lee, L.S. 2012. “Optimised Crossover Genetic Algorithm for Capacitated Vehicle Routing Problem”. Applied Mathematical Modelling 36, 2110-2117.

Pramsistya, Y. 2010. “Optimasi Penempatan BTS dengan Menggunakan Algoritma Genetika”. Surabaya: Tugas Akhir, Jurusan Matematika, Institut Teknologi Sepuluh Nopember.

Soelistyowati, R. 2010. “Pendekatan Algoritma Genetika untuk Menyelesaikan Masalah Transportasi Nonlinier”. Surabaya: Tugas Akhir, Jurusan Matematika, Institut Teknologi Sepuluh Nopember.

Taillard, E. 1993. “Parallel Iterative Search Methods for Vehicle Routing Problem”. Network 23, 661-673.

Toth, P. dan Vigo, D. 2002. The Vehicle Routing Problem. Philadelpia: University City Science Center.

Yucenur, G.N. dan Demirel, N.C. 2011. “A New Geometric Shape-Based Genetic Clustering Algorithm for The Multi-Depot Vehicle Routing Problem”. Expert System with Applications 38, 11859-11865.


Full Text: PDF

CC Licencing


Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).

Refbacks

  • There are currently no refbacks.


Lembaga Penjaminan Mutu, Pengelolaan dan Perlindungan Kekayaan Intelektual (LPMP2KI) ITS
Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.