Decomposing and solving capacitated vehicle routing problem (CVRP) using two-step genetic algorithm (TSGA)

Capacitated vehicle routing problem (CVRP) is one of the vehicle routing problem (VRP) that uses capacity restriction on the vehiclesk used. There are many methods have been studied to solve CVRP. To solve CVRP, it is possible to decompose CVRP into regions (sub problems) that can be solved independently. A two-step genetic algorithm (TSGA) is formulated in this paper. TSGA is used to decompose CVRP and then find the shortest route for each region using two different simple genetic algorithms. TSGA is then compared with genetic algorithm (GA). To compare these two algorithms, four instances is formed, those are P50, P75, P100, and P125. For each instance, fourteen different vehicle capacities is used. The results show that TSGA is better than GA in terms of computational time and distance except for some small vehicle capacities at P50 and P75.