An Application of Hybrid Method Between Saving Method and GA for Solving Vehicle Routing Problem

Abstract

This research aims to study on improving transportation routes using Saving Algorithm and Genetic Algorithm (GA). The main objective of this study is to find and improve transportation routes efficiency in a case study. In order to improve the efficient transport, the load capacity of a vehicle, customer locations, customer demands, and the road distance from distribution center to customers including customer to customer were taken into consideration to search the best routes for ice transportation. from the investigation, this factory delivers ice to 31 customers, and the total of customer demand is 3,812 liters. Then, Saving Algorithm and GA were used to find and improve ice transportation routes to shorten distance effectively. In the case of GA, crossover rate = 0.8, mutation rate = 0.01, population = 100, and generation = 100 were used as GA parameters. The results have shown that there were 3 vehicle routes improved by both methods, and the total traveling distance calculated by Saving method gave shorter distance, which was about 708.5 kilometers. On the other hand, the total distance calculated by GA was 793.1 kilometers. Therefore, in order to shorten the distance effectively, both Saving Algorithm and GA were combined and presented in this study. The total route distance which is presented in this study was about 637.1 kilometers. It is reduced by 24.48% compared with the total distance calculated by and GA.