Research On Solving Method Of Extended Model Of Vehicle Routing Problem Based On Genetic Algorithm

Vehicle routing problem(VRP)is a typical combinatorial optimization problem,which has a wide range of application backgrounds.In order to meet the actual needs,the basic model of VRP is extended and effective algorithms are proposed.In this thesis,two complex VRP extension models are explored:(1)the extension of the central point from a single center to multiple centers;(2)the extension of the service demand from statics to dynamic.Combined with actual problems,this thesis first analyzes a complex refuse collection problem——multi-station refuse collection problem(MSRCP).The MSRCP is mapped to the multi-depot vehicle routing problem(MDVRP).A model for MSRCP with the goal of minimum vehicle transportation cost is established,and an approach based on Cooperative Co-evolutionary(CC)as external framework is designed for the problem.Firstly,the improved clustering algorithm is used to assign each collection point to the appropriate station.Then,a hybrid genetic algorithm(HGA)is designed for vehicle routing problem(VRP)with regarding the stations as the depots and MSRCP being divided into some VRPs.Finally,the refuse collection in Daguan District of Anqing City was taken as an example to verify the above model and its algorithm,the results show that the algorithm proposed in this thesis has good performance in reducing complex refuse collection problems.Since many factors in the actual problem are uncertain,the impact of dynamic factors on vehicle routing problem is further considered.We present a predictive material distribution model with the lowest cost for dynamic vehicle routing problem(DVRP)in a special environment.In the model,uncertain actual demand is considered for it may lead to the increase of the distribution cost,and Poisson distribution is used to simulate the change of demand.Moreover,a genetic algorithm with adjustable forecasting demand(GAAFD)is designed to solve the model.Due to the impact of the special circumstances,there exists a certain law of the demand changes.Thus,a demand adjustment operator is proposed so that the impact of previous demand forecast deviations can be reduced.The adjustment operator is embedded into GAAFD with purpose of minimizing the distribution cost through customer adjustment among vehicles in a dynamic environment to increase the vehicle capacity utilization.Finally,to verify the proposed GAAFD,ten representative instances from benchmark data set are tested.The experimental results show that the algorithm results are better than the other classical algorithms,i.e.Neighbor(NN)and genetic algorithm(GA)in terms of total cost,vehicle cost,and transportation cost.