Performance of Gravitational Emulation Local Search Algorithm with Genetic Algorithm on VRP Variants and Its Implementation for Distribution Optimization
Sapti Wahyuningsih, Lucky Tri Oktoviana, Azis Wisnu Wardana, Sinta Ayu Saputri

Universitas Negeri Malang

Abstract

Distribution is one of the important factors in the business sector. Selection of the optimal route in the distribution process can minimize distribution costs and time. The mathematical model that can be used to solve distribution optimization problems is the application of graph theory to the study of the Vehicle Routing Problem (VRP). In this article, we will examine the performance of the Gravitational Emulation Local Search with Genetic Algorithm (GELS-GA) algorithm for VRP variants and its implementation in distribution optimization problems. The focus of discussion on the VRP variant is the Multiple Depot Vehicle Routing Problem With Time Windows (MDVRPTW) and Multiple Trip Vehicle Routing Problems With Time Windows (MTVRPTW). The performance steps of the GELS-GA algorithm are initialization, evaluation, first local search, chromosome selection, crossover, mutation and second local search. Implementation of the GELS-GA algorithm on the VRP variant using Borland Delphi programming. The program was tested at several points and compared with a standardized dataset. Input to the program is in the form of points (depots and customers), requests for each customer, service time, distance, parameters in the form of vehicle capacity, vehicle speed, time windows, population size, crossover probability (Pc), mutation probability (Pm) and number of generations. The output of the program is the result of the route formed with the total distance and travel time and graph visualization. An example of the results of the implementation of the VRP variant and its interpretation for distribution optimization problems is given.

Keywords: Distribution, GELS-GA, VRP variants, MTVRPTW and MDVRPTW

Topic: Mathematics and Statistics