Vehicle Routing Problem Modeling And Multiobjective Evolutionary Algorithm

Vehicle routing problem (VRP) has been being a research hotspot for nearly two decades in operations research, graph theory, network analyst, application mathematics, computer application, transportation, etc. It is a well-known NP-complete problem with constraints in the field of combinatorial optimization and is hard to be solved by the traditional method. Many domestic and foreign scholars have been appllying intelligent optimization algorithms, such as genetic algorithm, ant colony algorithm, tabu search algorithm and so on, to solve VRP for decades.Based on the study situation at home and abroad, this paper constructs a multi-objective optimization model for VRP, solves the problem through multi-objective evolutionary algorithm based on subregion (MOEAS), realizes the application and software simulation of MOEAS in VRP and validates the effectiveness of the model and the feasibility of the algorithm.The main research work and the new innovation is described as follows:(1) The research of the multi-depot collaborative vehicle route problem with time windows(MDCVRPTW).On the basis that available literatures only set the minimum of vehicle scheduling cost as objective, this paper set the maximum of customer satisfaction index as another objective and constructs a mathematical model of multi-objective optimization on MDCVRPTW. This paper applies MOEAS to solve the problem and proposes a new coding method which produces feasible solution to improve the efficiency of the algorithm. It tests a instance to prove the effectiveness of the new model and obtains a non-dominated set which can provide policy makers with a more powerful decision support through multi-objective evolutionary algorithm.(2) The research of the linehaul-feeder vehicle routing problem with time windows and virtual depots (LFVRPTW-VD).On the basis that original literatures only set the minimum of vehicle scheduling cost as objective, this paper set the maximum of customer satisfaction index as another objective and firstly proposes a mathematical model of multi-objective optimization on LFVRPTW-VD.The new model economizes the replenishment number of round trips, distance and time. This paper applies K-means clustering method to select part of customers as the replenishment points, solves the problem through MOEAS and tests some instances in the VRP web question bank. The result obtained shows that the proposed model is more effective than the traditional non linehaul-feeder VRPTW.