| Transportation plays a crucial role in development of the national economy.With the rapid development of social economy, the field of logistics management is given serious attention by the enterprises and scholar, and it has gradually developed from the early traditional transportation into integrated logistics system based on information technology and management technology. As a hotspot in the field of operational research and combinatorial optimization, the vehicle routing problem is closely related to real life, such as enterprise railway intelligent scheduling, vehicle scheduling of logistics company, route of urban bus, rail and air schedule, route of school bus,above-mentioned problems can be abstracted as vehicle scheduling problem.Therefore, the research on vehicle routing problem is of great practical significance.The vehicle routing problem has acquired some researching achievements at present, these achievements mainly focus on: the researches of Multi-depot vehicle routing problem place emphasis on seeking the shortest marched distance or the minimum cost; most researches of Vehicle routing problem with pickups and deliveries and Vehicle routing problem with time windows focus on unitary problem.The number of the published research literature of Min-Max Vehicle Routing Problem is very few, and it requires pioneering work; the researches of Pickup and delivery vehicle routing problem with time windows and Open vehicle routing problem also lack effective algorithms for solving and prompt improvement.In recent years, with the deepening study of vehicle routing problem, various kinds of new types of heuristic algorithm is applied to solve such problems, and among all of these algorithms, the ant colony algorithm with its strong robustness is widely used.The ant colony algorithm is used to solve the vehicle routing problem in this dissertation, and through the simulation optimization, the algorithm can obtain the optimal solution compared to traditional algorithms.The specific research work is as follows:In order to solve the Min-Max Vehicle Routing Problem (MMVRP),a new dynamic adaptive ant colony optimization algorithm named DMMAS-MMVRP(Dynamic Max-Min Ant System Min-Max Vehicle Routing Problem) is presented.The algorithm uses the Dynamic Maximum Minimum Ant System strategy to adjust the optimum solution, it updates τmin per iteration, regarding as the function of maximum in the pheromone matrix, and adjust probability of selecting arc according to the most superior arc, using a grey model to predict and control the boundary of the pheromone matrix, in order to enhance the adaptive performance of the parameters of ant colony algorithm, using pheromone accumulation rules to update pheromone of the multiple nodes with relatively high pheromone concentration and the edge near them. The algorithm is applied to solve the Min-Max Vehicle Routing Problem with 3 examples tested. The simulation results show that compared with LP algorithm and other related ant system algorithm, this new algorithm is characterized by fast convergence and good stability, resulting in well optimization performance and good application effect.In order to solve the Open Vehicle Routing Problem (OVRP), a Hybrid Ant Colony Optimization Algorithm (HACO) based on random distribution of loading and dynamically encoding is proposed. Firstly, the initial solutions are obtained through the method of random loading, and the colony optimization algorithm is adopted to get the optimal solution. Then the optimal solution is encoded as the zeroth particles of particle swarm algorithm. The initial fitness value is regarded as the historical optimal solution for individual. In order to get the best historical of individual and global optimal solution, the global optimal solution and the switching sequence v of each particle is calculated and implemented, combining the climbing hill strategy with sidesteps for local search with side step. Compared with other heuristics algorithms,computer simulations on the benchmark problems show that it can quickly and effectively get the known optimal solution or approximate solution.In order to solve the Vehicle Routing Problem with Time Windows (VRPTW), a Dynamic Hybrid Ant Colony Optimization (DHACO) algorithm is proposed, so as to avoid the disadvantages of traditional ant genetic hybrid algorithm, such as static setting, redundant iteration and slow convergence. Firstly, an initial solution is obtained through Max-Min Ant System (MMAS), and the ant colony algorithm is adopted to get a basic feasible solution to VRPTW. Then the crossing and mutation operations of genetic algorithm are employed to optimize local and global solutions,thus obtaining the optimal solution. Finally, based on the fusion strategy of ant genetic hybrid algorithm and calling algorithm dynamically and alternately, the parameters of ant colony algorithm are self-adaptively controlled according to cloud association rules. The dynamic hybrid ant colony optimization algorithm reduces the times of redundant iteration and speeds up the rate of the convergence. Computer simulations show that it is better than the other related heuristic algorithms as to the optimal solutions.In order to solve the Vehicle Routing Problem with Simultaneously Pickup and Delivery and Time Windows (VRPSPDTW), in view of the heuristic algorithm combined of the traditional ant algorithm and other heuristic algorithms, an Improved Hybrid Ant Colony Optimization (IHACO) algorithm is proposed. Firstly, the ant colony is divided into a number of ants subgroup with the same number, the parameters of the ACO algorithm are optimized by using particle swarm optimization,and the algorithm exchanges the pheromone of each ant subgroup; secondly, the weak feasible solution to the Vehicle Routing Problem with Simultaneously Pickup and Delivery and Time Windows (VRPSPDTW) is constructed by using a heuristic algorithm based on an insertion method, and the weak feasible solution will be transferred into the strong feasible solution by using the similar algorithm; local research using the descent search, crossover, inversion with variable neighborhood benefits the finding of the better solution in the current field. In comparison to other related heuristic algorithm, the improved hybrid ant colony optimization algorithm quickens the convergence speed.In order to verify the feasibility and the effectiveness of the ant colony optimization algorithm using to solve the vehicle routing problem, combining with the actual condition of enterprise railway transportation, the algorithm is applied to the intelligent scheduling system for enterprise railway. This dissertation take railway delivery of the enterprises as the research object, the ant colony optimization algorithm is applied to solve the vehicle scheduling problem in reality. The characteristics of vehicle operation are analyzed in the problem, and the mathematical models of the problems are developed. Then, an improved Dynamic Hybrid Ant Colony Optimization (DHACO) algorithm which combined with the advantages of both the Ant Colony algorithm and genetic algorithm is presented and applied to the intelligent scheduling system for enterprise railway of Maanshan iron and steel Co.,Ltd. Finally the optimal solutions to this problem are presented in form of the software system. |
PDF Full Text Request