Algoritma genetika dengan operator Partially Mapped Crossover untuk menyelesaikan optimasi Vehicle Routing Problem

INDONESIA:

Peningkatan efisiensi dari sistem transportasi dapat dilakukan dengan memaksimalkan utilitas dari alat transportasi yang ada. Untuk mengurangi waktu transportasi dan juga untuk meningkatkan pelayanan kepada para pelanggan, perlu dicari jalur atau rute transportasi terbaik yang dapat meminimalkan jarak dan waktu. Dalam hal ini metode yang digunakan peneliti adalah algoritma genetika dengan partially mapped crossover. Pemecahan permasalahan rute menggunakan algoritma genetika menghasilkan rute yang meminimalkan jarak dan mengoptimalkan proses pengangkutan dengan satu kali putaran.

Dalam penelitian ini akan dilakukan perhitungan rute terhadap lima belas daerah pelayanan untuk mendapatkan rute optimal berdasarkan lima kendala vehicle routing problem yang telah ditetapkan. Adapun proses algoritma genetika terhadap daerah-daerah pelayanan tersebut antara lain: proses membangkitkan populasi awal dengan menggunakan algoritma random generator, proses seleksi dengan menggunakan roulette wheel selection, proses crossover dengan menggunakan partially mapped crossover, dan proses mutasi dengan menggunakan swapping mutation.

Menggunakan algoritma genetika yang dipadukan dengan graf dan statistik, diperoleh visualisasi rute terpendek. Rute yang dihasilkan untuk kedua truk dapat menghemat jarak tempuh sejumlah 31,35 km dengan jumlah angkutan 9.080 liter sampah. Untuk penelitian selanjutnya, diharapkan untuk melakukan pengembangan kasus dengan menambah batasan-batasan pada vehicle routing problem, sehingga dapat menjadi lebih spesifik. Kemudian dilakukan perbandingan crossover dalam algoritma genetika dengan crossover yang lain dan dilakukan dalam beberapa generasi sampai diperoleh nilai fitness yang tidak berubah agar mendapatkan nilai yang lebih optimal.

ENGLISH:

Increasing the efficiency of the transportation system can be done by maximizing the utility of existing transportation. To reduce transportation time and improve service to customers, is necessary to find the best path or route to minimize transport distance and time. In this case, the method used by researchers is a genetic algorithm with the partially mapped crossover. Solving these problems using genetic algorithm produces routes that minimize distances and optimizing processes with one round.

This study will be conducted in the calculation of the fifteen service area to obtain the optimal route based on five predefined constraints vehicle routing problem. The process of genetic algorithms to the areas of service include: processes generate the initial population by using algorithm random generator, the selection process by using the roulette wheel selection, the crossover process by using partially mapped crossover, and the mutation processes by using the swapping mutation.

Using a genetic algorithm combined with graph and statistics, obtained by visualizing the shortest route. Routes generated for two trucks managed to save 31.35 kilometres with total transport 9,080 liters of rubbish.

Forfurther research, are expected to conduct development case by adding restrictions on the vehicle routing problem, so it could be more specific. Then do a comparison crossover in genetic algorithms with crossover others and performed in several generations until a fitness value has not changed in order to get a more optimal.