Perturbation operator analysis on ILS-RVND algorithm to solve CVRP

摘要

Vehicle Routing Problem (VRP) determines a distribution route of goods with a minimum distance. VRP has many variants, one of them is CVRP that has vehicle capacity constraints. One of algorithms that can be used to determine CVRP solutions is the ILS-RVND algorithm. The calculation of the ILS-RVND algorithm is carried out in a multi-start manner in which each iteration produces different initial solutions. In the ILS-RVND there are two stages of improvement, namely the local search stage and the perturbation stage. In this research, we had an experiment to determine the combination of perturbation operators which produces the most optimum solution. Perturbation operators used in this research are Double Replace, Double Cross, Triple Shift, Triple Replace and Triple Cross. To facilitate the calculation, the program of the CVRP solution with the ILS-RVND algorithm is needed. This program is made using Delphi which then will be tested on different perturbation operators and also a number of different operators. Result from datasets used is that combination of (Double Replace, Triple Shift) gave more optimum result than other combinations of the operators used in the experiment, with only less than 2% of deviation to the best-noted result. This combination can bes used as a reference in implementing perturbation stage in ILS-RVND on other variants of VRP or other datasets.