Combination of Taboo Search and Ant Colony System Approach to Solve the Vehicle Routing Problem

The Vehicle Routing Problem (VRP) is one of the most important combinational optimization problems that is received much attention because of wide applications in routing problems. In this problem, fleet vehicles with Q capacity start to move from the depot and return after servicing to customers in which visit only ones each customer and load more than its capacity not at all. The objective is to minimize the number of used vehicles and total distance traversed. This paper proposes a hybrid tabu search for the VRP. In this algorithm, three types of neighborhood moves including insert, swap and ant colony system are used for searching the neighborhood and moving from current solution to next solution. Computational experience with the benchmark test instances involving from 50 to 199 confirms that proposed algorithm is competitive in compared to the famous meta-heuristic algorithms in terms of the quality of generated solutions. In addition, this algorithm finds closely the best-known solutions (BKS) for most of the instances in which three best-known solutions are also found.