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.
