Research Of Multi-trip Vehicle Routing Problem Based On Swarm Intelligence Optimization Algorithm

Logistics industry is the bloodline about the development of national economy,the 13^th five year planning outline of our country further programmes the development key points of modern logistics industry from all levels of the national economic development.As the key part of logistics system optimization,combined with the basic situation of logistics vehicles dispatching operation in urban area,this paper regarded the multi-trip vehicle routing problem based on swarm intelligence optimization algorithm as the main research object,respectively studied the followings:?1?using an modified firework algorithm to optimize the scheduling of multi-trip vehicle routing in logistics distribution.?2?using a hybrid Beam-PSO algorithm to solve the multi-trip vehicle routing problem with time window and the release time based on dynamic demand;?3?using a hybrid teaching and learning optimization algorithm to slove mutli-trip vehicle routing problem with time windows to delivery incompatible goods;?4?using a novel shuffled frog leaping algorithm to optimize the location of the distribution center and the effective route planning of the vehicle.Finally via a detail vehicle dispatching and optimization platform of company,the proposed the swarm intelligence algorithm is verified.The main research content is as follows:At first,the source of the problem and research purposes are introduced,the definition,model and basic elements of vehicle routing optimization are discussed,and the solving strategy and related algorithms of VRP based on dynamic demand is introduced.At the same time the basic problems and characteristics of urban logistics domestic and overseas are introduced,that is,time-dependency,multi-level,multi-trip and dynamic information.Also the VRP based on swarm intelligence algorithm and dynamic demand is integrated into the research.Finally the technical route and organization of the main research work in this paper are pointed out.Aiming to the multi-trip vehicle routing problem,this section proposes a modified firework algorithm based on the standard firework algorithm.This algorithm combines the nature of multi-trip VRP,adopts the encoding and decoding method of roulette to overcome the shortcomings of the standard firework algorithm which are not applicable to discrete problem.At the same time,using bee colony search technology to further strengthen the depth development capability and search performance of the standard firework algorithm,and embodied in the firework algorithm with initialization method based on unlearning to improve the quality of the initial solution,and the complexity of the algorithm is analyzed and compared.Through the parameter setting and parameter correction,in the MATLAB simulation the algorithm's reliability and feasibility are verified.The algorithm is tested comparing with genetic algorithm,artificial bee colony algorithm,and particle swarm optimization algorithm in the literatures,encouraging results are obtained.Finally it is proved that this algorithm can obtain the shortest delivery time when solving the problem of multi-trip vehicle routing,and the total percentage of time deviation can reach above 5%.Aiming to solve the problem of the multi-trip VRP with time windows and release date based on dynamic demand,this section proposes a kind of hybrid Beam-PSO optimization algorithm to solve.At first this section constructs the corresponding encoding and decoding method via the random key coding mechanism,overcomes the shortcomings of standard PSO algorithm which is not applicable to the discrete problem.At the same time the local search procedure based on Beam Search is introduced to enhance the global search capability of the algorithm,and the complexity of the algorithm is analyzed and compared.Here the customer location,quantity demanded,release date and customer service time are all supposed random factors,finally through the MATLAB simulation,comparing with the artificial bee colony algorithm,genetic algorithm,as well as teaching-learning algorithm in related literatures,the experiments prove this Beam-PSO algorithm can gain the least amount of trips,the shortest delivery time and the minimum transportation cost.Aiming to solve the multi-trip vehicle routing problem with time windows and incompatible commodities,it is necessary to make a clear routing planning to serve a set of customers that meets the requirement of customer carrying large amount of commodities.This section design a hybrid teaching and learning optimization algorithm,and introduced the dynamic factors such as customer location,quantity of requirement,service time,customer type,and load capacity.This algorithm overcomes the shortcomings of standard teaching-learning algorithm which is not applicable to the discrete problem,constructs the local optimization variance based on Tabu search algorithm;further enhances the optimization capability of standard teaching-learning optimization algorithm,and the complexity of the algorithm is analyzed and compared.In order to test the proposed hybrid teaching-learning algorithm,comparing with artificial bee colony algorithm,particle swarm optimization algorithm,and invasive weed optimization algorithm,the MATLAB simulation results verify that the hybrid algorithm can obtain the minimum number of trips,the shortest delivery time and the lowest transportation cost in solving the problem.In order to solve both the multi-trip vehicle routing problem and the distribution center location problem at the same time,a mathematic model is developed at first.The objective of this model is to minimize the total costs including the transportation costs and the activated vehicle costs.A novel shuffled frog leaping algorithm is then developed for solving the problem.The coding and decoding method is designed,the neighborhood search model of invasion weeds optimization algorithm is further referred,and locally searching for the optimal solution of the frog subgroups,the evolution ability of algorithm is strengthened.This method is completely different with the common way of dividing distribution center location and path optimization into two separate stages to solve LRP method,but considering the mutual influence and restriction relationship between the facility location of distribution center and vehicle routing problem,the LRP is regarded as an entirety to do structural analysis and solving.Then MATLAB simulation is respectively done for the contrast experiment with other three kinds of optimization algorithm.Finally,this paper discusses the problem of large scale customer point in theory and verifies it through simulation.The results show that the novel shuffled frog leaping algorithm can obtain better distribution center location and effective route arrangement with the lowest cost of objective function and the least number of distribution centers,comparing with other three algorithms its practicability is stronger,and the optimization efficiency is higher.Finally a vehicle scheduling and routing optimization platform based on the dynamic demand is presented,the instance effectively integrates the modified firework algorithm,the hybrid Beam-PSO algorithm,a hybrid teaching and learning optimization algorithm and a novel shuffled frog leaping algorithm presented in the paper,and takes them as optimization seeds imbedded into the SDK algorithm package by GIS interface.For the uncertain factors in the process of scheduling,the platform adopts the strategy of real-time update of data and re-optimization,taking three delivery vehicles as examples,the optimization process of the current vehicle driving route is verified.Finally the optimized path results by scheduling personnel selection and decisions,via text message are sent to the drivers,to realize the process of dynamic scheduling.In the conclusion of the whole study,this section makes a comprehensive summary to the above research content,proposes the main innovative points,and points out the next research direction.Above theoretical results have certain guiding significance to the multi-trip vehicle routing problem in urban logistics environment,are helpful to improve the efficiency of urban distribution system,with good social and economic benefits.