Two Types Of Periodic Vehicle Routing Problem With Variable Service Time

Periodic vehicle routing problem(PVRP)has wide applications,such as supermarket distribution and elevator maintenance,where customers have strict requirements for timeliness.As the change of service time has significant influence on the timeliness,it is crucial to study routes optimization based on variable service time.In this paper,we consider two types of PVRP with variable service time from the following two aspects: the influence of driver experience on service time and the service time uncertainty.The influence of driver's experience on service time can be depicted by learning curve(LC).Previous study of the LC in vehicle routing problem(VRP)focuses on continuous single day problem which means that there is no need to determine the visit combination for each request.We are the first to propose periodic vehicle routing problem with learning curve(PVRP-LC)by combining PVRP and LC.And a linear programing model is built after piece-wise linearization of LC.As for the service time uncertainty,which has significant influence on the cost and customer experience,it is necessary to using robust optimization building routes that would be less sensitive to uncertainty.Previous study focuses on the single day robust VRP.In this paper,we combine robust optimization and PVRP for the first time,and propose robust periodic vehicle routing problem with uncertain service time(RPVRPUST).Besides,a linear robust model is established based on the analysis of worst-case.Both PVRP-LC and RPVRP-UST belong to NP-hard problem,which is difficult to solve with exact algorithm.Therefore,we design two variable neighborhood search(VNS)algorithms for PVRP-LC and RPVRP-UST each,and both two algorithms are based on the same framework.In order to verify the effectiveness and feasibility of the algorithm's framework,6 benchmarks of periodic vehicle routing problem with time windows(PVRPTW)are selected,and the average gap between our optimal solution and the best known solution is 1.13%,which fully illustrates the feasibility and effectiveness of the algorithm.Then,6 PVRP-LC instances and 6 RPVRP-UST instances are designed for testing and analysis.The results of PVRP-LC instances show that after considering the learning curve,the cost decreases,the frequency of rest driver increases,and the region covered by each driver tends to be more concentrated.What's more,we provide suggestions for managers to recruit employees and shorten their working hours through the sensitivity analysis of the learning rate and maximum working hours.On the other hand,numerical experiments of RPVRP-UST instances prove that when uncertainty occurs,the robust solution outperforms the deterministic one in total cost,average number of technicians' working overtime,and delay rate of customers' service.Besides,we prove that a large uncertainty set parameters might lead to overly conservative robust solution with higher cost.