Research On Dynamic Vehicle Routing Problem Under Traffic Restriction

The increasing number of cars and the rapid development of express delivery industry not only promote the development of China's economy,but also bring a series of problems,such as urban traffic congestion,haze and so on.In express delivery,the selection of distribution route is very important.Whether the distribution route is reasonable and efficient is directly related to the logistics cost of enterprises.Although the level of specialization of urban logistics distribution in China has been continuously improved,due to the large amount of cars in China,it still faces severe traffic congestion,vehicle "difficult to pass" and other problems.In order to improve traffic congestion,Shanghai,Beijing,Tianjin and other domestic cities have successively introduced measures such as road restrictions based on different regions and models to restrict the passage of urban distribution vehicles.In real life,the vehicle capacity is limited,the time window of customer request is mostly a time period,the vehicle arrival time earlier than the customer start time will increase the time cost of logistics enterprises,and later than the customer end time will reduce customer satisfaction.In order to ensure the long-term healthy development of the enterprise and the good experience of the customers,it is necessary to plan a reasonable vehicle route under the condition of meeting the traffic restriction,so as to distribute within the specified time window.In addition,due to traffic congestion,weather changes and changes in customer demand,the planned vehicle route often cannot be carried out as planned,and the original vehicle route needs to be adjusted again.Therefore,it is of great practical significance and practical value to study the vehicle routing optimization problem of dynamic urban logistics distribution with capacity and time window constraints under traffic restrictions.This paper first studies the static vehicle routing problem with finite row constraints with capacity and soft time window constraints.Then the dynamic vehicle routing problem with unknown customer demand under infinite row constraint is studied.Finally,the dynamic vehicle routing problem under the restriction is studied.The main research results are as follows:(1)In the study of vehicle routing problem under traffic restriction,considering regional traffic restriction,road traffic restriction,soft time window,capacity restriction and other factors,a new optimization model is constructed,and an improved bat algorithm is designed to solve the model.A discrete bat algorithm with variable neighborhood(VDBA)is designed by introducing the difference algorithm to update the population and adopting the idea of variable neighborhood in local search.Based on Solomon data,experimental data were constructed and compared with genetic algorithm(GA)and particle swarm optimization(PSO).The experimental results verified the superiority of VDBA algorithm.(2)When we study the dynamic vehicle routing problem with infinite row constraints,we consider the dynamic arrival of customer demand,soft time window and capacity constraints,and build the dynamic vehicle routing problem model with periodic strategy.The whole working day is divided into initial planning stage and dynamic optimization stage by using two-stage algorithm,and VDBA algorithm is used in both stages.In the dynamic optimization stage,the dynamic vehicle routing problems are transformed into transient and static vehicle routing problems by dividing time slices.Through the analysis and comparison of the experimental results,the following conclusions are obtained.Among the 12 test cases in the Lackner test library,11 of them are better than the results of genetic algorithm(GA)and particle swarm optimization algorithm(PSO)by using VDBA algorithm;when solving the dynamic vehicle routing problem,it is not the smaller the time slice,the better the results.(3)This paper studies the dynamic vehicle routing problem under the traffic restriction by combining the vehicle routing problem under the traffic restriction with the dynamic vehicle routing problem.The model of dynamic vehicle routing problem under traffic restriction is constructed,and the periodic strategy and two-stage algorithm are adopted.Twelve test examples were constructed on the basis of Lackner data and analyzed and compared with particle swarm optimization(PSO)of genetic algorithm(GA).The experimental results show that the results obtained by USING VDBA algorithm are slightly better than those obtained by GA particle swarm optimization(PSO)for solving the problem with limited row constraints.In the actual case test,VDBA algorithm shows good performance,can plan a reasonable distribution route for enterprises,and effectively reduce costs.