Research Of Genetic Algorithm For Allied Vehicle Routing Problems With Transfer Stations

Allied Vehicle Routing Problem(AVRP) deals with the optimization of vehicle routing and scheduling problem based on logistic alliance, which is a hot topic in operations research, application mathematics, network analysis, graph theory, computer application and transportation, etc. the paper discusses some theories of Genetic Algorithm(GA) and its improved algorithm, and several models of AVRP are created and solved. The main work as follows:1. Research on AVRP with single supply station and transfer stations: Considering the characteristics of urban freight transportation, the advantage and the characteristics of the Allied Vehicle Routing Problem(AVRP)with transfer stations is analyzed, on the basis of which an optimized mathematical model to solve the problem is established and the effective genetic algorithm for the model is constructed. In this algorithm, the new crossover operator is designed.2 Research on AVRP with multi-supply stations and transfer stations: In the actual transportation routing process, usually the service were supplied by multi-supply stations together, moreover transportation process can influenced by many kinds of factors.such as the limitation of the vehicle capacity. In chapter 2, the mathematical model of the multi-supply stations was established. And the Genetic algorithm was designed.3 Research on AVRP with the stochastic demand and transfer stations: During the realistic application process of vehicle routing problem, demand of customer is usually stochastic. the vehicle routing problems(VRP) with the stochastic demand is studied, the demand at service nodes is subjected to the binomial distribution, the influence of distribution parameter on the VRP with stochastic demand is analyzed firstly, on the basis of which the mathematical model to solve the problem is established, Because the number of route failures in the nod is not restricted, the new models are suitable for many kinds of practical problems, and then the genetic algorithm for the mathematical model is designed. 4 Research on the parallel genetic algorithm: AVRP with transfer stations is NP-hard problem in combinatorial optimization. It is important to designed efficient parallel algorithm via analyzing the thinking of GA. the BSP parallel computing model is extended to the grid computing. The design strategy of parallel genetic algorithm on grid is given.