Research On Dynamic Demand Vehicle Scheduling Problem Based On Memetic Algorithm

With the development of science and technology,the professional level of logistics continues to increase,and customers' demands for service quality and effectiveness are getting higher and higher.More and more companies use logistics as an important means to increase market competitiveness and core competitiveness.As time changes,there will be many dynamic events such as changes in customer demand,increase in new customers,reduction in existing customers,and modification of existing customer needs.This requires the development of a real-time scheduling plan and the design of suitable algorithms so that the system objectives are better.The vehicle scheduling problem in logistics distribution is a typical NP-hard problem.The general precise algorithm is more difficult to solve dynamic vehicle scheduling problems.At present,the intelligent optimization algorithm has attracted more and more attention from all walks of life.Memetic algorithm is a flexible combination of evolutionary algorithms and some local search algorithms.The main structure is composed of an evolution module and a local search module,which is also a core component of the Memetic algorithm.The memetic algorithm proposes a flexible framework that can select different search strategies based on different problem models,thus forming different Memetic algorithms.Because of its good adaptability,flexibility,high efficiency,portability and other characteristics,it has been widely concerned and developed in recent years.It has been successfully applied in various fields and has achieved good results.In view of the large space for development of this algorithm,the paper adopts this algorithm to improve the three different problem models of dynamic vehicle scheduling problem,and uses improved algorithms to simulate the validity of the algorithm.The work of the thesis mainly includes the following parts:Firstly,for the Capacitated Dynamic Vehicle Routing Problem(DVRP),a two-stage mathematical model is constructed.According to the characteristics of the model,a Memetic algorithm was designed to minimize the total cost of transportation.The global search using Memetic algorithm is improved quantum genetic algorithm,the local search is 2-opt method and swap method.Secondly,for the Heterogenous Fleet Dynamic Vehicle Rounting Problem(HFDVRP),the minimum number of vehicles and the minimum cost of transportation are taken as the optimization objectives,and the problem is divided into two phases to be solved.A new Memetic algorithm is designed for the characteristics of the model.The first stage of global search in this algorithm adopts improved distribution estimation algorithm,and the second stage adopts improved quantum genetic algorithm.Local search uses the customer node reset method and the 2-opt method.Two simulation experiments show the effectiveness and superiority of the proposed algorithm.Finally,for the dynamic demand vehicle scheduling problems with customer demand and time window changes,a disturbance recovery strategy based on Memetic algorithm for interference management is adopted.The Memetic algorithm is selected based on the improved distribution estimation algorithm in the last part,according to the characteristics of the problem model.The time window of the vehicle was introduced into the sampling probability selection function.Finally,the effectiveness of the algorithm was verified by simulation experiments.