Research On The Vehicle Routing Problem Solving Based On ACO

The convenient and quick character of e-commerce makes more and more people choose thiskind of shopping way with its development.E-commerce plays an increasingly important rolein people’s lives. People are increasingly accustomed to this shopping style. Due to the remotephysical characteristics of online shopping, logistics industry assumes the role of distribution.Because of the high cost and inefficient of delivery in the logistics business, it is significantfor reducing the cost of the online shopping by means of increasing efficiency and reducingtransportation costs of delivery.Vehicle routing problem is a theoretical model of logistics and delivery services. Thedistribution service of goods concerns the service and speed, in a given time period of a set ofcustomers by a set of vehicles, which are located in one or more depots are operated by a setof crews(drivers) and perform their movements by using an appropriate road network.In particular, the solution of a VRP calls for the determination of a set of routes, eachperformed by a single vehicle that starts and ends at its own depot, such that all therequirements of the customers are fulfilled, all the operation constraints are satisfied, and theglobal transportation cost is minimized. In the past decades, the plan to decrease the deliverycost study scale is increasing. So many practical example confirmed that using more computerapplication in the distribution plan can reduce a large number of saving in the overalltransportation(usually5%-20%less than with no plan). It is easy to see that the impact ofthese savings on the global economic system is significant. Indeed, the transportation processinvolves all stages of the production and distribution systems and represents a relevantcomponent of the final cost of the goods.The study of VRP problem can save a lot of logistics cost. So far, there are a lot ofalgorithms to solve VRP problem,including accurate algorithm and heuristics algorithm.Accurate algorithms use rigorous mathematical approach, and the optimal solution can beobtained. But with the expansion of the scale of the problem, with the calculated cost growsexponentially. The accurate algorithm can not be directly applied to the solving of practicalproblem. Heuristic algorithms evaluate the position of the state space to find a better location.And from this location it start the search until find the target. Based on the nature of the VRPproblem, there are no accurate algorithm can solve big scale instances. So more method arebased on heuristics algorithm to find the approximate solution. Many heuistics has been used to this domain.Based on the nature of VRP problem, it can not use the accurate method to solve bigscale instances.So many heuristics have been used to solve this problem.like ant colonyalgorithm、genetic algorithm、simulated annealing and constraint programming. Here we focuson metaheuristic algorithm, particular ant colony algorithm.Ant colony algorithm is a popularalgorithm in heuristic algorithm. Marco Dorigo proposed ant algorithm and applied it tocomputer combinatorial optimization problem solutions in1992. Experimental results showthat the ant colony optimization is able to find a better solution, and has strong robustness.In this article, based on previous research, we have applied adaptive thinking to themaximum and minimum ant system(MMAS). In every cycle of the search, we can determinethe number of elite ants adaptively. In the search process, as long as the ant reach a certainrequirement, we can think of it as the elite ants, and it’s pheromone maintained. Whenupdating the pheromone of path, we consider the distance between two points, rather than auniform release of the pheromone in the path. Punishment and reward system is proposed.Based on the comparison the current path of the ants walked and the optimal path of last circle,the ants were grading. Ant pheromone on the first paths are strengthen, and those on the lastpaths and weaken. Experiments show that, in most cases, our algorithm can find a bettersolution.