A Hybrid Ant Colony Algorithm for Capacitated Vehicle Routing Problem

Author

Zhishuo, Liu ; Yueting, Chai

Author_Institution

Tsinghua Univ., Beijing

Volume

5

fYear

2006

fDate

8-11 Oct. 2006

Firstpage

3907

Lastpage

3911

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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/ICSMC.2006.384741

Filename

4274506