Research On Improved Hormany Search Algorithms For VRP

Logistics is also named "the source of profit" for industry. In today’s competitive environment, how to optimize logistics system and decrease cost of logistics becomes an important issue for industry. Vehicle routing problem is a core problem of logistics distribution. Arranging vehicle routes reasonably is important way to decrease operation cost and improve service quality for industry.Vehicle routing problem is a typical NP-hard problems, mostly solved by a heuristic algorithm. Harmony search algorithm, as a novel heuristic algorithm, has been developing rapidly in recent years. However, the research on vehicle routing problem by the harmony search algorithm is not sufficient.This thesis investigates the method of solving the vehicle routing problem by harmony search algorithm, and proposes some effective improved methods. The main contributes are as follows.(1) The traditional harmony algorithm and its improved algorithms are investigated.2-opt is added into these algorithms. These algorithms are applied in VRP. Experiments show that these harmony algorithms can achieve high quality solution.(2) An improved global-best harmony search algorithm is proposed for capacity vehicle routing problem (CVRP), which uses natural number coding. The algorithm adds constraints to new harmonies to avoid generating invalid solutions, and optimizes new harmonies by 2-opt algorithm, so that the proposed algorithm can compress the search solution space and improve the efficiency. Experiments show that the proposed algorithm outperforms the existing algorithms on efficiency.(3) A firefly global-best harmony search algorithm (FGHS) is proposed for CVRP to solve some problems of harmony search, such as the search process easy falling into local optimum and natural number coding uneasy combining with other algorithms. The proposed algorithm uses a real-coded. The updated formula in firefly algorithm is introduced in the new solution generation process. The tone adjustment of harmony search algorithm is improved by biomimetic properties of firefly, so that the search not easy to fall into local optimal algorithm. The algorithm also proposes a harmony memory reset method, while the algorithm traps into a local optimum, based on chaotic disturbance system to increase the diversity of solutions in harmony memory to help the algorithm to escape from local optimum. At the same time the use of 2-opt local search to enhance the exploitation ability.