Research Of Vehicle Routing Problem Based On Ant Colony Optimization

Along with the Society Progress, The Development of Logistics isfaster and faster, Logistics is already a big industry. Delivery plays a keyrole in the Logistics Enterprise, How to reduce the cost of Logisticsefficiently,satisfythedemandofcustomerandsoseekforgreatestdegreeofprofit for the Enterprise was the thing that the Enterprise cares about andwas studied by many scholar in many aspect. Vehicle Routing Problem(VRP) is a question that more important than the others in LogisticsDelivery.Reducingthecost ofLogistics bythewayoptimizingtheDeliveryRoutingtomakethenumberofvehicleis least andthedistanceofroutingisthe shortest becomes a very important research question. This paperintroducesasolutiontooptimizethedeliveryroutingbytakingadvantageofthestudyresultofsolvingVRPbyAntColonyOptimization(ACO)VRPis the problem that this paper has to study. VRPwas a problem inwhich given a set of customer, a fleet of vehicle, making some objective byorganizing a proper traveling routing to deliver all customers with knowndemand and respect to the constraints. VRP that this paper studied containsCapacitated Vehicle Routing Problem (CVRP), Split Delivery VehicleRouting Problem (SDVRP) and Split Delivery Vehicle Routing Problemwith Time Windows (SDVRPTW). These problems have some additionalConstraintsbasedonthe VRP.InCVRP,eachvehiclehaveuniform capacity,the total demand of each routing cannot exceed the vehicle capacity.SDVRPis a relaxation of the VRPwherein each customer can be served bydifferent vehicles, each vehicle deliver part demand of the customer and allthe vehicles together to finish the demand of the customer. Comparing toSDVRP, SDVRPTW has the additional restriction that a time window isassociatedwitheachcustomer,eachcustomermustbeservedwithinitstimewindow, It is not allowed to be served by vehicle when before the earliestservice timeor afterthe latest servicetime and all thevehiclemust start andend within the time window associated with the depot. This paper gives thedetail problem description and general mathematic model of above threeproblems,designsresponseACOwiththeirowncharacteristictosolvethem,test them in the standard test data sets and the result show that ACO cansolve the VRP successfully, Split Delivery has practice meaning foroptimizingtravelroutinginthefieldofLogisticsDelivery.This paper takes advantage of the algorithm of ACO to solve theproblem of VRP. ACO is a novel method of natural optimization thatbelongs to stochastic optimization based on the research of the foragingbehavior of real ant colony in nature. It mimics real ant's collaborativeinteraction. Algorithm builds the solution byCollective Operation of all theants. They deposit the pheromone on the solution path and exchangeinformation about solution by the pheromone to improve goodness ofsolution path, in this way to find the shortest path. Algorithm allows theexploitation of positive feedback as a search mechanism, has thecharacteristic of distributed computation and robust, and is easy to couplewith other algorithms. This paper solves the problem of CVRP bymodifyingtheAntSystem(AS)belongstoACO.AccordingtodisadvantageofASthatthespeedofconvergentisslowandenteringthestagnationeasily,improving the AS in some aspect by the way that importing pheromonewindows that the value of pheromone cannot exceed the window, onlydeposit the pheromone on the edge that belongs to the iteration shortestsolution path, releasing additional pheromone to the edge belongs to theso-far shortest solution path, judging the situation of convergent and toreinitializepheromone,optimizingthesolutionsbylocalsearchprocedureatthe end of every iteration, modifying the transition probability by add someproblem specific parameters and so on. On the basis of CVRP AntAlgorithm, Adding the rule of split delivery to become the Ant Algorithmthatsolvingtheproblem ofSDVRP.Onthebasis ofSDVRPAntAlgorithm,adding the constraint of time window on the candidate list of normal visitcustomer and split customer to finishing the solving to the problemSDVRPTW. Testing above three algorithms on the standard data set,experiments verify the characteristic of the base parameters of AntAlgorithm,DeepentherealizationofthecharacteristicofAntAlgorithm.The thesis is sponsored by the Ministry of Communications of theproject of the application research in distribution center in Western area ofChina,inchargeofthemoduleofvehicleroutingoptimizationbelongtotheLogistics Management Information System that is a sub-problem. make useof the research result that take advantage of ACO algorithm to solve theproblem of SDVRP to optimize the vehicle routing and apply to theLogistics Management Information System of West Project, helping solvethe real problem of vehicle routing optimization of SDVRP. It is significantforLogistics,DistributeandtransportationofWesternRegion..