Title :
A Hybrid Ant Colony Algorithm for Capacitated Vehicle Routing Problem
Author :
Zhishuo, Liu ; Yueting, Chai
Author_Institution :
Tsinghua Univ., Beijing
Abstract :
A new hybrid ant colony algorithm (ACA) based on sweep algorithm and 2-opt procedure is developed for solving the capacitated vehicle routing problem (CVRP). After all the ants constructed their solutions but before the pheromone in the routes is updated, each solution might be improved by applying sweep algorithm and 2-opt procedure respectively. 2-opt is to act as an improvement heuristic within the subtour found by individual vehicle, and as opposed to that sweep algorithm is employed to improve the clustering of solution by exchanging vertices between different subtours. Experiment shows that our hybrid ant colony algorithm is able to find solutions for CVRP within 0.62% of known optimal solutions and is one of the best ACA heuristics developed so far.
Keywords :
transportation; capacitated vehicle routing problem; hybrid ant colony algorithm; sweep algorithm; Approximation algorithms; Approximation methods; Clustering algorithms; Computer integrated manufacturing; Cybernetics; Genetic algorithms; Nearest neighbor searches; Routing; Simulated annealing; Vehicles;
Conference_Titel :
Systems, Man and Cybernetics, 2006. SMC '06. IEEE International Conference on
Conference_Location :
Taipei
Print_ISBN :
1-4244-0099-6
Electronic_ISBN :
1-4244-0100-3
DOI :
10.1109/ICSMC.2006.384741
