A two-phase constructive approach for capacitated vehicle routing problem in constructing population of solutions

Abstract

The Capacitated Vehicle Routing Problem (CVRP) is a variant of VRP that has a fleet of same capacity vehicles in order to serve customers with the shortest distances. The tendency of researchers to employ population-based metaheuristics in solving CVRP requires constructing the population of initial solutions to be improved later. However, the initial solutions constructed should be feasible to ensure that the solutions can be converged in a reasonable computation time. This study proposed a two-phase constructive approach for CVRP that shows the ability to generate feasible solutions for all instances of datasets used in this study. The approach starts with the descending order of the customers according to their demands followed by assigning customers to vehicles in sequence considering the capacity of vehicles. If there are customers still unassigned, neighborhood structures are applied on the already assigned customers to get more space to accommodate the unassigned customers aiming to produce the base feasible solution. In the second phase, the population is generated by applying neighborhood structures to get a variety of feasible solutions. The proposed approach was applied on CVRP benchmark datasets A, B, P and E. The results show the superiority of the proposed approach in comparison with random construction method in terms of cost and run time. In addition, the two-phase construction approach shows feasibility-oriented results when compared with other constructive approaches proposed in the literature.