Cheapest Insertion Constructive Heuristic based on Two Combination Seed Customer Criterion for the Capacitated Vehicle Routing Problem

Mansour Alssager, Zulaiha Ali Othman, Masri Ayob


The heuristic method is a well-known constructive method for initialize trail quality solutions in capacitated vehicle routing problem. Cheapest insertion heuristic is a popular construction heuristic known for being fast, producing decent solutions, simple to implement and easy to extend handling complicated constraints. However, in previous work, there was less focus on diverse initial quality solutions. Therefore, this study proposed an extension to the cheapest insertion heuristic which consider various combinations of seed customer criteria (the first customer inserted on a route) to preserve solutions diversification. Three seed customer criteria proposed which based on the combination of two criteria based on (farthest, nearest and random criteria). The best performing criteria selected and tested on benchmark dataset, later compared with Clarke and Wright saving heuristic. The results shown that the combination of (farthest and random) criteria obtained the best initial solution which preserve balance between the quality and diversity, with less time when compared to Clarke and wright saving heuristic. This approach is for generating diverse and quality starting solutions for the capacitated vehicle routing problem.


insertion heuristic; capacitated vehicle; routing problem; initial solution construction.

Full Text:




  • There are currently no refbacks.

Published by INSIGHT - Indonesian Society for Knowledge and Human Development