Real-Time Pickup And Delivery Problem With Asymmetric Networks

With the rapid development of takeout industry,the time and scale of distribution are continuously improved,which makes the traffic violations such as retrograde motion and overspeed increase sharply.The rapid development of takeout industry also makes takeout platforms and restaurateurs pay more and more attention to customer satisfaction,and further reduce the distribution time which directly relates to customer satisfaction.O2 O takeout platforms use the straight-line distance to estimate the delivery time,but the transportation network of urban business district actually has an asymmetric structure.Therefore,the distribution problem considering customer satisfaction and actual distribution network has become an important research problem of terminal real-time distribution.Based on the actual distribution network,the survey explores the optimization of online pick-up and delivery path with and without considering customer satisfaction.In view of the real-time and difference of customers’ orders,distribution vehicles are required to adjust the distribution path and determine whether to return to the origin.The survey mainly carries out the following work:(1)The online pick-up and delivery path optimization problem in asymmetric networks is studied.In view of the random and real-time occurrence of customer orders and the need for distribution vehicles to return to the distribution center to pick up goods,the survey discusses the online traveling salesman problem in which distribution vehicles serve all orders in the shortest time.The study analyze the lower bound of the problem,give JLNO(Judge Location of New Orders,JLNO)algorithm on special network for demand points and JPI-rd(Judge the Path Increment with Release Date,JPI-rd)algorithm and W&I(Wait and Ignore,W&I)algorithm on general network for demand points,and also analyze the competitive performance of the three algorithms.Under different network sizes,order quantity and asymmetric coefficient,the survey uses numerical simulation software to analyze the performance of JPI-rd algorithm and W&I algorithm in general network.It is found that JPI-rd algorithm is more suitable when the asymmetric coefficient is larger and the distribution network structure is larger.(2)The real-time pick-up and delivery path optimization problem considering customer satisfaction is studied.On the basis of the first problem,time window constraints are added to characterize customer satisfaction,and a real-time pick-up and delivery path optimization model considering customer satisfaction is established.By defining and adjusting the asymmetric network coefficients,the asymmetric distribution network is constructed,Ignore strategy and Real-time strategy are proposed.The Ignore strategy requires the deliveryman to ignore all new orders before returning to the distribution starting point.The Real-time strategy requires the deliveryman to judge in real-time whether to return to the starting point to pick up goods and re-plan the distribution route when new orders appear.Using the numerical simulation software and calling the genetic algorithm,the applicability of the two strategies is analyzed under different network size,rolling time domain duration,asymmetric coefficient,time windows and order quantity.Numerical example analysis shows that the Real-time strategy is more suitable for the case of larger network,while the Ignore strategy is more suitable when the network is smaller and the number of orders is fewer.The research will provide theoretical support for the real-time distribution platform to scientifically dispatch distribution vehicles.