关键词: 随机需求, 禁忌搜索, 修正算法, 车辆路径问题

Abstract: In the solving process of Vehicle Routing Problem with Stochastic Demand and Soft Time Window (VRPSD-STW),the problems such as high complexity,long planning time and unknown customer's demand of large scale vehicle routing planning are existed.For this reason,an improved two-stage algorithm was proposed.In the first stage,the customer's stochastic demand was determined that made it equal to the expected value.The adaptive tabu length,adaptive penalty coefficient and improved neighborhood structure were introduced to solve the problem of vehicle departure from soft time.The original planning scheme was obtained finally that still had some errors.In the second stage,Select Return to Depot algorithm (SRTD) was used to correct the error of the solution obtained in the first stage.The experimental results showed that the improved two-stage algorithm had strong optimization ability and high robustness,which could quickly find a reasonable solution.

Key words: stochastic demand, tabu search, modified algorithm, vehicle routing problem