Research On Dynamic Pickup And Delivery Problem Based On Real Time Information

With the characteristics of point-to-point,small and multi-batch,real-time urban distribution has developed rapidly and the demand has doubled,which puts forward new technical requirements for timely response and flexibility of logistics distribution.In order to meet the new technical requirements,the dynamic pick-up and delivery problem based on real-time information was studied based on dynamic pickup and delivery problem with time windows,considering both real-time pick-up and delivery and vehicle routing.It has important theoretical and practical significance for exploring the optimization method of dynamic route planning and solving practical problems which lack of guidance of dynamic algorithm framework.In this paper,the routing and scheduling plan are updated continuously in the whole scheduling time to minimize the total cost of vehicle distribution in the scheduling time.The total cost of vehicle distribution includes the sum of penalty cost and vehicle operation cost that exceed the time window.Considering Four kinds of realtime information comprehensively,including the emergence of new requests,modification or cancellation of old requests,traffic congestion and vehicle breakdown,Influences of information,the basic constraints,time window constraints,capacity constraints and scheduling time constraints of vehicle routing problem are determined.Then a dynamic pick-up and delivery vehicle routing planning model based on realtime information is established.Aiming at the lack of effective dynamic algorithm guidance for solving dynamic path planning problems,a dynamic algorithm framework was designed.Based on realtime optimization method,the execution rules and computational rules of static subproblems in scheduling time are given.Then,for specific static sub-problems,constructive heuristic algorithm is used to generate initial feasible solutions,and two intelligent optimization algorithms,tabu search algorithm and adaptive large-scale neighborhood search algorithm,are used to improve the quality of initial feasible solutions.In the scheme,dynamic insertion method is used to solve the problem of synchronous processing of unfixed requests and new requests in planning.The experimental results show that the method can effectively solve the dynamic pick-up and delivery problem based on real-time information.The dynamic algorithm framework based on real-time optimization method provides an important reference for solving dynamic route planning problem.