Study On Application Of Multi-Objective Genetic Algorithm For Vehicle Routing Problem

Vehicle Routing Problem (VRP) is a hotspot topic in the subjects of operational research, application mathematics, analysis of networks, theory of chart, computer application and transportation in recent twenty years. It is a key problem especially in the logistics scheduling. Consequently, good vehicle routing can not only increase the profit of the logistics but also make logistics management more scientific.In combinatorial optimization the VRP is a NP-Complete problem provided with many constraints and it is very hard to be solved by traditional methods. So many researchers have been paying much attention to the meta-heuristics algorithm, such as genetic algorithm, simulated annealing, tabu search, ant colony optimization. These approaches seek approximate solutions in polynomial time instead of exact solutions which would be at intolerably high cost. As far as the number of vehicles and the total distances these two objects to be concerned, all the previous VRP researches are biased towards the number of vehicles. This bias always prioritizes the number of vehicles so that the vehicle count is first minimized, and then the distance is minimized with respect to this vehicle value. This is in fact a single objective optimization method with priority. However, this paper treats the number of vehicles and total distances equally and represents the VRP as a multi-objective optimization problem. As a result, this method returns not a single non-dominated solution but a set of no-dominated solutions, which provides powerful decision support to the decision-maker.The multi-objective genetic algorithm for vehicle routing problem is mainly studied in this thesis. Firstly, the previous research works and some theories about multi-objective optimization are introduced. Secondly, a new multi-objective mathematics modal for Vehicle Routing Problem with Time Windows (VRPTW) is presented. Then, a new multi-objective genetic algorithm has been designed to solve the VRPTW. In this algorithm, Arena's Principle is adopted to construct non-dominated set quickly and aλ-interchange local search method with alterable probability is proposed too. In addition, an Best Cost Route Crossover is designed to minimize the number of vehicles and total distances simultaneously while checking feasibility constrains. Finally, I apply the new algorithm to Solomon's VRPTW 100-customer standard instances. The experimental results indicate that this algorithm it is quite effective, as it provides solutions close to the best known in the...