Comparison of greedy method and greedy estimate in generating initial solutions to closed small-scale capacitated vehicle routing problems

Abstract

In the population based meta-heuristic methods, initial solution plays a significant role to reach a near optimal solution in a reasonable computational time. Initial solution is usually generated randomly but it consumes more time to reach the optimal solution. Greedy approach is a better way than the results obtain through randomly generated initial population approach to reach an optimal solution in a lesser time. Two heuristic techniques to generate initial solutions to meta-heuristic algorithms are compared in this study. The Greedy Method (GM) is purely based only on travelling cost. However, the Greedy Estimate (GE) incorporates not only travelling cost but also quantity requested by each customer. In GE approach, the ratio of travelling cost and quantity is considered. The GM and GE are compared with the optimal solution obtained by the Branch and Bound (BB) algorithm. To compare the results, randomly generated small scale capacitated vehicle routing problems are employed. It can be concluded that the GE method is much more efficient than the GM method in terms of reaching the near optimal solutions in a reasonable computational time. Moreover, when generating initial solutions to solve vehicle routing problems using population based meta-heuristic methods, it is recommended to hybridize GM and GE with random method for not only to preserve the diversity of solution space, but also to reach optimal solution with less computational time. It is observed from this study that the GE method is more appropriate for the instances with high variance among both quantities requested by customers and travelling cost between them.