| Logistics is an emerging discipline and distribution is an important element of modern logistics.The optimization of vehicle routes can cut down transport cost and rise efficiency. Vehicle Routing Problem(VRP)is a combinatorial optimization problem in transportation logistics, which has been applied in many fields. It is an NP-hard problem.The open vehicle routing problem(OVRP)is another kind of the vehicle routing problem and a new research area with wide applications. The important feature of this problem, which distinguishes it from the basic VRP, is that the vehicles are not required to return to the depot, or if they are required to do so by revisiting the customers assigned to them in the reverse order.The OVRP is also an NP-hard problem, too. Traditional algorithms usually are not satisfied. Genetic algorithm is an excellent algorithm to solve vehicle routing problem. Because genetic algorithm is an algorithm which uses for reference the selection and evolution of nature, it is a search algorithm with parallelism, stochastic, adapt-self characteristic.The main content of this thesis is how to apply GA to OVRP. First, it reviews the past studies on vehicle routing problems and their solution methods, focusing on the solution method of the capacitated open vehicle routing problem(COVRP). Then, it introduces basic theoretic of GA. This thesis describes and analyzes the algorithm design in deltailed and carry out it through Delphi 7. Specially, an efficient cross operator and several advanced strategy is used in this genetic algorithm. Finally, through comparing our advanced GA with simple genetic algorithm, it shows the superiority of our advanced GA.Through implementation of the method solving COVRP, The author draws conclusions as follows: the superiority of GA using in OVRP. The excellent solutions are obtained in the application. However, because of the realistic complicacy problem, the algorithm design of GA should be improved. |
PDF Full Text Request