Ant colony-based algorithm with elitist strategy for capacitated vehicle routing problem - Bohol, Nancy B. (2011)
Vehicle Routing Problem aims to construct a solution set of routes for geographically scattered nodes with the least distance. Capacitated VRP is a variant where there is an additional constraint of fixed vehicle capacity. Ant Colony Optimization is a metaheuristics patterned after the behavior of ants as they observe pheromone trails in their search for optimal routes from their nest to a food source. The objective of this study was to solve CVRPs using an ant colony-based system with a modified state transition rule, having the additional savings and the available vehicle capacity terms, and using elitist strategy in its trail updating. Datasets used have 20 and 50 customer nodes for the small-scaled and 100 and 150 for the large-scaled. Two sets of parameters were also used with the first having the number of ants equal to the number of customer nodes, while the second one had it at only half. Performances between parameter settings were compared through independent sample t-tests of average relative errors. Results showed that the difference was only significant for the CVRP with 150 customer nodes. Results of the study wee also compared to the results of application of original ant colony system and to the published best known solutions for each CVRP instance. Independent samples t-tests was conducted between the average relative errors for the modified and original algorithms, where the proposed algorithm was shown to produce smaller solution lengths. There was also an increase in rate of convergence for the proposed algorithm. In comparison to the best known solution, the best of the best solutions generated by the proposed algorithm had relative errors not more than 15.5% with the least at 3%. In conclusion, the proposed algorithm was able to reach near optimal solutions and generally performed better than the original and colony system.