Local cover image
Local cover image
Local cover image
Local cover image

Ant colony-based algorithm with elitist strategy for capacitated vehicle routing problem / Nancy B. Bohol.

By: Material type: TextTextLanguage: English Publication details: 2011Description: 120 leavesSubject(s): Abstract: 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.
Tags from this library: No tags from this library for this title. Log in to add tags.
Star ratings
    Average rating: 0.0 (0 votes)
Holdings
Cover image Item type Current library Collection Call number Status Date due Barcode
Thesis Thesis University Library General Reference Room-Use Only LG 993.5 2011 A64 B64 (Browse shelf(Opens below)) Not For Loan 3UPML00012790
Thesis Thesis University Library Archives and Records Preservation Copy LG 993.5 2011 A64 B64 (Browse shelf(Opens below)) Not For Loan 3UPML00033554

Thesis, Undergraduate (BS Applied Mathematics)-U.P. Mindanao

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.

There are no comments on this title.

to post a comment.

Click on an image to view it in the image viewer

Local cover image Local cover image
 
University of the Philippines Mindanao
The University Library, UP Mindanao, Mintal, Tugbok District, Davao City, Philippines
Email: library.upmindanao@up.edu.ph
Contact: (082)295-7025
Copyright @ 2022 | All Rights Reserved