Algorithms for vehicle routing problem with stochastic demand with soft time window

被引:0
作者
Li G. [1 ]
Li J. [1 ]
机构
[1] Key Laboratory of Jiangxi Province for Image Processing and Pattern Recognition, Nanchang Hangkong University, Nanchang
来源
Jisuanji Jicheng Zhizao Xitong/Computer Integrated Manufacturing Systems, CIMS | 2021年 / 27卷 / 08期
基金
中国国家自然科学基金;
关键词
Modified algorithm; Stochastic demand; Tabu search; Vehicle routing problem;
D O I
10.13196/j.cims.2021.08.010
中图分类号
学科分类号
摘要
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. © 2021, Editorial Department of CIMS. All right reserved.
引用
收藏
页码:2270 / 2281
页数:11
相关论文
共 25 条
[1]  
TILK C, DREXL M, IRNICH S., Nested branch-and-price-and-cut for vehicle routing problems with multiple resource interdependencies, European Journal of Operational Research, 276, 2, pp. 549-565, (2019)
[2]  
LETCHFORD A N, SALAZARGONZALEZ J J., The capacitated vehicle routing problem:Stronger bounds in pseudo-polynomial time, European Journal of Operational Research, 272, 1, pp. 24-31, (2019)
[3]  
REIHANEH M, GHONIEM A., A branch-and-price algorithm for a vehicle routing with demand allocation problem, European Journal of Operational Research, 272, 2, pp. 523-538, (2019)
[4]  
HUANG Yinghua, BLAZQUEZ C A, HUANG S H, Et al., Solving the feeder vehicle routing problem using ant colony optimization, Computers & Industrial Engineering, 127, pp. 520-535, (2019)
[5]  
XU Zefeng, CAI Yanguang, Variable neighborhood search for consistent vehicle routing problem[J], Expert Systems with Applications, 113, 15, pp. 66-76, (2018)
[6]  
BRANDAO J., Iterated local search algorithm with ejection chains for the open vehicle routing problem with time windows, Computers & Industrial Engineering, 120, pp. 146-159, (2018)
[7]  
WANG Chao, LIU Chao, MU Dong, Et al., VRPSDTW problem solving by discrete cuckoo search, Computer Integrated Manufacturing Systems, 24, 3, pp. 570-582, (2018)
[8]  
XU Shenghua, LIU Jiping, ZHANG Fuhao, Et al., A combination of genetic algorithm and particle swarm optimization for vehicle routing problem with time windows, Sensors, 15, 9, pp. 21033-21053, (2015)
[9]  
NIU Yunyun, HE Juanjuan, WANG Zhongyu, Et al., A p-based hybrid evolutionary algorithm for vehicle routing problem with time windows, Mathematical Problems in Engineering, 2014, 3, pp. 1-11, (2014)
[10]  
QI Yuanhang, CAI Yanguang, CAI Hao, Et al., Discrete bat algorithm for vehicle routing problem with time window, Acta Electronica Sinica, 46, 3, pp. 672-679, (2018)