Application Of Ant Colony Optimization In Vehicle Routing Problems

Vehicle routing problems is one of the key issues in the field of logistic management. Since its complexity and diversity,how to deliver right goods to right customers timely with the least cost by means of rationally dispatching vehicles and arranging time and routes is a challenging problem. This dissertation sponsored by the scientific research foundation for the returned overseas chinese scholars, State Education Ministry, considering the status of vehicle routing problems, improving ant colony system to solve the vehicle routing problems are described in time window, demand and travel time. Simulation road network and optimal parameters of support vector machine for travel time prediction are discussed .The detailed contents studied in the paper are as follows:Based on analysis of parameters in ant colony system,two improved ant colony systems are proposed. One is the multi-ant colony optimization using dynamic parameters (M-ACO). The other is combination of ant colony system and large neighborhood algorithm. Complexity and convergence analysis of improved algorithems are presented. Vehicle routing problem with time window (VRPTW) is solved by M-ACO and the hybrid algorithm. Simulation results show that the proposed approach is very effective in preventing the premature convergence and avoiding the local optimum problem.Ant colony optimization algorithm is applied to solve two uncertainty vehicle routing problems--vehicle routing problem with stochastic demand and vehicle routing problem with fuzzy demand (VRPFD). Stochastic vehicle routing problems is the expansion of the standard vehicle routing problem. According to optimization standard,the chance constrained model and confidence model for vehicle routing problems with stochastic demand are proposed afer introducing the statistical law for stochastic demand. The models for fuzzy demand are presented by using experience of handling stochastic demand for reference. The demand data set was handled by the theory of probability and fuzzy mathematics which make VRPFD become a general vehicle routing problems.Algorithm combined with M-ACO and local optimization is proposed for dynamic vehicle routing problem (DVRP). DVRP is researched when statistical work cannot get the law for stochastic demand. Based on analysis the relationship between logistics delivering and DVRP,road network model which can describe road network topology and intersection delay and stochastic customer demand generation are presented. DVRP generator is designed by modifying Solomon dataset and simulating urban road network.The model in accord with urban transport system can be used to test algorithm efficiency of dynamic vehicle routing problem.ACO heuristic factor was modified by travel time is presented for time dependent vehicle routing problem (TDVRP). TDVRP is another expansion of standard Vehicle Routing Problems. Based on known travel time-distance function of the road network,under the prerequisite for satisfying the First-in-First-out rule,time dependent vehicle routing problem is solved in optimization of routing and departing time. The results show that two-stage optimization strategy can get the optimal route under dynamic road net work.A hybrid kernel of support vector regression is presented using the ant colony system to optimize the parameters to improve performance.Travel time of road is important factor in path searching. The improved model is used to predict travel time. The results show that the proposed model improves computability and achieve a better forecasting accuracy than neural network.