Improved Ant Colony Algorithms For Vehicle Routing Problems

With the development of Internet economy and trade,the scale of logistics industry is growing.The impact of the distribution on economic activities is more and more obvious.Vehicle routing problem(VRP)is the core part of distribution optimization.Reasonable optimization of the distribution vehicle routing can effectively reduce distribution costs,delivery time and improve customer satisfaction.So study on this problem is of great practical significance.Since the VRP belongs to the class of NP hard problems,no efficient exact algorithms are available for solving large scale instances with reasonable computational time.Therefore,various of heuristic algorithms are developed to achieve the approximate solution of the VRP.Ant colony optimization(ACO)is a population-based heuristic algorithm,which is inspired by the behaviour of ant colonies for food-seeking.ACO is effective in solving combinatorial optimization problems such as VRP.Comparing to other algorithms,ACO has significant superiority,for it can be performed in parallel,and is easy to be combined with other algorithms.However,the original ACO is prone to achieve the stagnation,due to the pheromone overaccumulation in some local optimal solutions.This paper mainly studies the ACO for solving VRP and proposes a new hybrid ant colony algorithm to overcome the shortcomings of the original ACO.The efficiency of the algorithm is also an important indicator to evaluate the performance of an algorithm.In order to improve the efficiency of ACO,this paper presents two approaches.The first approach uses the divide and conquer strategy.The whole problem is divided into several sub-problems,and each sub-problem is solved independently and concurrently.The second approach adopts a parallel ACO running on GPU.This approach is based on OpenCL,a heterogeneous parallel framework.The main contributions are listed as following.1.A new hybrid ant colony algorithm(SACO)is proposed,which is based on the framework of ACO and is hybridized with the merits of simulated annealing(SA).As is widely known,SA performs single-starting-point neighbour-hood search,and its convergence speed heavily depends on the initial state.Note that ACO can rapidly achieve a local optima,which can be used as the initial solution of SA,and meanwhile SA can explore better solution using neighbourhood search.Then,an intuitional idea is to combine both of the two algorithms to search for a global optima.We additionally add a new pheromone perturbation strategy to further avoid pheromone stagnation.2.In order to improve the efficiency of SACO,we further extend the SACO algorithm into the decomposed version called DSACO,which shows better performance comparing to SACO in terms of the solution quality and the computational time.3.A parallel ant colony algorithm based on OpenCL called OCL-ACO is proposed.In this approach,the main computational process of ACO is programmed into OpenCL kernel that can be executed in parallel on GPU,and the CPU host is used to manage and schedule kernels.The solution construction stage and pheromone update stage in ACO are implemented in dataparallelism to increase the parallelism of OCL-ACO.