Research On Real-time Vehicle Routing Problem Under O2O Delivery

With the rapid development of the take-away market under O2 O mode,the demand for last-3-kilometers delivery has been increasing rapidly,thus delivery effectiveness has been given considerable attention.The timely delivery of take-away,which is the routing of delivery vehicles has become an important research issue in the catering service industry.Point to the pick-up and delivery problem and service flexibility.This paper discusses the real-time vehicle routing problem with pick-up and delivery and service flexibility.For the real-time and difference of demand orders in the O2 O platform,when the new request is released,the vehicle must return to the origin to pick up goods and adjust the vehicle route in real time.The goal is to minimize the distribution time.This paper considers the service flexibility with the objective to minimize the cost(i.e.the sum of the makespan and the penalty).This paper has two principal aspects:(1)Real-time vehicle routing problem with pick-up and delivery.In the takeaway delivery service under O2 O platform,the releasing time of the requests is uncertain and the delivery vehicle must return to the origin to pick up goods.This chapter discusses the online traveling salesman problem with pick-up and delivery and the goal is to minimize the makespan.We give the lower bounds of the problem.TAIB algorithm is presented on the positive half-line.For general metric space,IGNORE algorithm is presented,and competitive analysis is given for the two algorithms respectively.Through the numerical analysis,we show the IGNORE algorithm is feasible on the general metric space.(2)Real-time vehicle routing problem with pick-up and delivery and service flexibility.Considering the reality of takeout service and overall customer satisfaction,we introduce service flexibility into the online traveling salesman problem with pick-up and delivery.If the distribution vehicle refuses to serve the request,it will suffer penalty.The objective is to minimize the service cost which is the sum of the makespan and the penalty.We give the lower bounds of the problem.WAO algorithm is presented on the positive half-line.For general metric space,WAE algorithm is presented,and competitive analysis is given for the two algorithms respectively.Through the numerical analysis,we show that the WAE algorithm is feasible on the general metric space.