Research On Hybrid Optimization Method Combining Column Generation And Multi-objective Evolutionary Algorithm

Branch pricing method and evolutionary algorithm are two mainstream methods to solve large-scale combinatorial optimization problems.The hybrid optimization method combining column generation and evolutionary algorithm is a hybrid method which uses evolutionary algorithm instead of branch and bound algorithm in branch pricing method and integrates the advantages and disadvantages of the two methods.Nowadays,the effectiveness of hybrid optimization method combining column generation and evolutionary algorithm in solving large-scale combinatorial optimization problems has been verified.However,in the face of multi-objective optimization problems,the weight method is often used to convert multi-objective into single objective,and the weight of the objective is difficult to determine.Aiming at the problems of the existing hybrid optimization methods combining column generation and evolutionary algorithm in solving multi-objective optimization problems,this paper proposes a hybrid optimization method combining column generation and fast non dominated sorting genetic algorithm(NSGA-?)to solve the electric bus scheduling problem.Based on Dantzig-Wolfe decomposition,the electric bus scheduling problem is decomposed into main problem and sub problem,and the mathematical model is constructed.The label correction algorithm is used to quickly generate columns.Taking the total operating cost and the number of vehicles not covered as the optimization objective function,this paper uses the actual bus line data of a northern coastal city to carry out the experiment,and compares the experimental results of the hybrid optimization method with the manual scheduling scheme.The experimental results show that the hybrid optimization method can get better Pareto solution than the manual scheduling scheme,and with the increase of the number of trains involved in the problem,the advantages of the hybrid optimization method are more obvious.Although the hybrid optimization method combining column generation and NSGA-? can effectively deal with multi-objective optimization problems,because coverage is also an optimization objective,there are some solutions with low coverage in the Pareto solution set,which can not be used in practice.This paper further proposes a hybrid optimization method combining column generation and partial multi-objective evolutionary algorithm,which sets the preference region as[0.95,1],that is,the scheduling scheme needs to cover at least 95%of the trains.The Pareto solutions obtained by this method are compared with the experimental results of manual scheduling,column generation and NSGA-?,respectively.The results show that the proportion of available solutions in Pareto solutions generated by this method is significantly higher than that of column generation and NSGA-?,and it is better than manual scheduling.