Vehicle Scheduling Heuristic For Meal Delivery With Uncertain Picking Time

With the prosperity of the take-away market,the consumption pattern of online ordering has become more and more popular.It has become the main form of catering for office workers,and orders for on-line orders are increasing.However,the cost of order delivery has remained high.One important reason is that the traditional vehicle scheduling problem usually considers the time of produce meals(picking time)as a certain value.while in the actual scenario,the picking time is a uncertain value.When the vehicle arrives at the merchant,if the merchant does not have a meal,the vehicle has to wait for a long time;if the merchant has produced a meal for a long time,the taste of the meal may has changed when it arrives at the customer,they both will reduce the customer's satisfaction.It is necessary to consider how to solve the vehicle routing proble when the picking time is a uncertain value.This thesis researched the vehicle routing proble with multiple merchants and uncertain picking time.The problem has the following three characteristics:(1)The picking time is a random variable,which has the characteristics of the stochastic vehicle routing problem;(2)The distribution order of the merchant and the corresponding customer must be taken into consideration when arranging the vehicle routes,which has the characteristics of the vehicle routing problem with simultaneous delivery and pickup;(3)Customers have requirements of the service time windows.Therefore vehicle routings have to ensure a degree of customer satisfaction.The research goal of this thesis is to plan the vehicle routes with the lowest expected logistics cost and satisfy the relevant constraints.The problem is defined and hypothesized in detail.A two-stage stochastic programming model is established for the problem.Based on the characteristics of the problem,This thesis designed the insertion strategy of merchant,then used a multi-space sampling heuristic(MSH)solved the problem.The MSH algorithm was tested based on Solomon data.The experimental results show that the MSH algorithm is better than insert algorithm.The results generally improved by 6%-9%.Experiments show that the MSH algorithm is feasible and effective in solving the vehicle routing problem with uncertain picking time.