| For the vehicle routing problem with stochastic travel time,stochastic service time and time window(VRPSTSTW),this paper presents two models,the chance constrained programming(CCP)and the stochastic programming with recourse(SPR).For the two models,the main works are described as follows.For the CCP model,it is the most critical step to conduct the arrival time chance constraint checking,which determines the quality of solutions.A new method which can avoid the calculation of the arrival time distribution function and reduce the solving difficulty is proposed.We design a modified iterated local search algorithm(MILS)to solve the model,and give a new initial solution generation method.To test the MILS and the new method,we conduct a series of simulation experiments based on the Solomon benchmarks.Comparing the results with those in the literature,the results show that MILS can get a good solution for the CCP model in a short time,and the new initial solution generation method helps to reduce the computing time.Comparing the results with those of the other three scenarios considering robustness,the results show that the new method can be used to the chance constraint checking and generate robust solutions with a high service level.In addition,we further analyze the influence of customer classification on the results,and the results show that considering customer classification can reduce the cost,and customer ratio is positively related to the number of used vehicles.For the SPR model,an effective recourse policy can reduce cost and increase the service level of customers.Two new policies,named as the hybrid recourse policy and the preventive recourse policy(PRP),are designed.In the hybrid recourse policy,whether the delayed service is accepted or not depends on whether the delayed service for the customer causes a large scale delay to the subsequent customers on the prior route.In the PRP,the concept of a failure-prone customer(FPC)which is prone to making the prior route failure,is proposed,and the modified new method is used to find and remove FPCs from the prior route.This paper also adopts MILS to get the prior route,and a minimum waiting time heuristic(MWTH)is proposed to generate an initial solution.To test the MILS and the recourse policy,we conduct a series of simulation experiments based on the Solomon benchmarks.The results show that MWTH is valid,the MILS can get approximate optimal solutions for the problem in a short time,and the hybrid recourse policy,which provides the route with a high service level and a low cost,is superior to the common recourse policies.In the PRP,the modified new method can identify FPCs accurately,and the prior route after removing FPCs has a lower failure rate and a higher service level.In addition,the parameters’ value has a large influence on solution quality,so we do a sensitivity analysis on relevant parameters,which provides strong support for the reasonable setting of parameters’ value.The results have a certain reference significance to solve the problem of low customer service level caused by the limited resources and uncertain factors. |
