TY  - BOOK
AU  - Bohol, Nancy B.
TI  - Ant colony-based algorithm with elitist strategy for capacitated vehicle routing problem
PY  - 2011///
KW  - Vehicle Routing Problem
KW  - Ant Colony Optimization
KW  - Elitist strategy
KW  - Metaheuristics
KW  - Datasets
KW  - CVRP (Capacitated Vehicle Routing Problem)
KW  - Undergraduate Thesis
KW  - AMAT200
N1  - Thesis, Undergraduate (BS Applied Mathematics)-U.P. Mindanao
N2  - 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
ER  -