Optimization and RealTime Adjustment for Vehicle Routing Problem with Fuzzy Demand

Abstract

Abstract: Abstract： The vehicle routing problem with fuzzy demand was studied. In preoptimized phase with unknown demand, a preoptimized model was presented based on the credibility theory, and a variable neighborhood scatter search algorithm combining scatter search with variable neighborhood search was designed. In realtime adjusted phase with known demand, a novel realtime adjusted strategy was proposed, and a stochastic simulation algorithm was used to simulate the actual demands in the possible realtime scenarios. The results of computational experiments show that the designed algorithm and the proposed strategy have better performances.

Key words: vehicle routing problem, fuzzy demand, realtime adjustment, scatter search(SS), variable neighborhood search(VNS)

ZHANG Xiaonan,FAN Houming. Optimization and RealTime Adjustment for Vehicle Routing Problem with Fuzzy Demand[J]. Journal of Shanghai Jiaotong University, 2016, 50(01): 123-130.

References

［1］孙华丽,周站杰,薛耀峰. 考虑路径风险的不确定需求应急物流定位路径问题［J］.上海交通大学学报,2013,47(6):962966. SUN Huali, ZHOU Zhanjie, XIE Yaofeng. Emergency locationrouting problem with uncertain demand under path risk［J］. Journal of Shanhai Jiaotong University, 2013,47(6):962966. ［2］LAU H C W, JIANG Z Z, IP W H, et al. A credibilitybased fuzzy location model with Hurwicz criteria for the design of distribution systems in B2C ecommerce［J］. Computers & Industrial Engineering, 2010, 59 (4): 873886. ［3］TEODOROVIC D, PAVKOVIC G. The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain［J］. Fuzzy Sets and Systems, 1996,82(3): 307317. ［4］曹二保,赖明勇,李董辉.基于混合差分进化算法的模糊需求车辆路径问题［J］.系统工程理论与实践, 2009, 29(2): 106112. CAO Erbao, LAI Mingyong, Ll Donghui. Vehicle routing problem with fuzzy demands based on hybrid differential evolution［J］. Systems EngineeringTheory & Practice, 2009, 29(2): 106112. ［5］王连峰,宋建社,杨正磊,等.基于模糊期望值模型的车辆路径问题［J］.计算机集成制造系统, 2012, 18(12): 27772782. WANG Lianfeng, SON Jianshe, YANG Zhenglei, et al. Vehicle routing problem based on fuzzy expected value model［J］. Computer Integrated Manufacturing Systems, 2012, 18(12): 27772782. ［6］YANG W, MATHUR K, BALLOU R H. Stochastic vehicle routing problem with restocking［J］. Transportation Science, 2000, 34(1): 99112. ［7］ZACHARIADIS E E, TARANTILIS C D, KIRANOUDIS C T. A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and pickup service［J］. Expert Systems with Applications, 2009,36(2):10701081. ［8］张军,唐加福,潘震东,等.分散搜索算法求解带货物权重的车辆路径问题［J］.系统工程学报,2010,25(1):9197. ZHANG Jun, TANG Jiafu, PAN Zhendong, et al. Scatter search algorithm for solving weighted vehicle routing problem［J］. Journal of Systems Engineering, 2010, 25(1): 9197. ［9］姜大立,杨西龙,杜文,等.车辆路径问题的遗传算法研究［J］.系统工程理论与实践,1999,19(6):4045. JIANG Dali, YANG Xilong, DU Wen, et al. A study on the genetic algorithm for vehicle routing problem［J］. Systems EngineeringTheory& Practice, 1999,19(6):4045. ［10］AUGERAT P, BELENGUER J M, BENAVENT E, et al. Computational results with a branch and cut code for the capacitated vehicle routing problem［R］. France: Institute IMAG, Universite Joseph Fourier, Grenoble, 1995. ［11］赵燕伟,彭典军,张景玲,等.有能力约束车辆路径问题的量子进化算法［J］. 系统工程理论与实践, 2009, 29(2): 159166. ZHAO Yanwei, PENG Dianjun, ZHANG Jingling, et al. Quantum evolutionary algorithm for capacitated vehicle routing problem［J］. Systems EngineeringTheory & Practice, 2009, 29(2): 159166. ［12］罗先国,侍洪波.非满载车辆路径问题的改进粒子群优化算法［J］.华东理工大学学报(自然科学版), 2006, 32(7): 767771. LUO Xianguo, SHI Hongbo. Improved particle swarm optimization for vehicle routing problem with nonfull load［J］. Journal of East China University of Science and Technology(Natural Science Edition), 2006, 32(7): 767771. ［13］姜昌华,戴树贵,胡幼华.求解车辆路径问题的混合遗传算法［J］.计算机集成制造系统, 2007, 13(10):20472052. JIANG Changhua, DAI Shugui, HU Youhua. Hybrid genetic algorithm for capacitated vehicle routing problem［J］. Computer Integrated Manufacturing Systems, 2007, 13(10):20472052. ［14］GOODMAN J C, OHLMANN J W, THOMAS B W. Cyclicorder neighborhoods with application to the vehicle routing problem with stochastic demand［J］. European Journal of Operational Research, 2012, 217(2): 312323. ［15］TLILI T, FAIZ S, KRICHEN S. A hybrid metheuristic for the distanceconstrained capacitated vehicle routing problem［J］. ProcediaSocial and Behavioral Sciences, 2014, 109: 779783. ［16］STANOJEVIC＇ M, STANOJEVIC＇ B, VUJOEVIC＇ M. Enhanced savings calculation and its applications for solving capacitated vehicle routing problem［J］. Applied Mathematics and Computation, 2013,219(20): 1030210312

[1]	BAI Wenchao, BAN Mingfei, SONG Meng, XIA Shiwei, LI Zhiyi, SONG Wenlong. Coordinate Scheduling Model of Electric Vehicle-Unmanned Aerial Vehicle Joint Rescue System [J]. Journal of Shanghai Jiao Tong University, 2024, 58(9): 1443-1453.
[2]	CHEN Yuyi, CHEN Lu. An Inverse Optimization Approach of Vehicle Routing Problem [J]. Journal of Shanghai Jiao Tong University, 2022, 56(1): 81-88.
[3]	FAN Houming,XU Zhenlin,LI Yang,LIU Wenqi,GENG Jing. Hybrid Genetic Algorithm for Solving Multi-Depot Joint Distribution Routing Problem [J]. Journal of Shanghai Jiaotong University, 2019, 53(8): 1000-1009.
[4]	XIONG Hao, YAN Hui-Li, ZHOU He-Ping, LIU Wu-Sheng. Real-Time Optimization Strategy of the Multi-Period Dynamic Vehicle Routing Problems [J]. Journal of Shanghai Jiaotong University, 2013, 47(03): 450-453.
[5]	LIU Ran，JIANG Zhibin，GENG Na，LIU Tiantang . The Half Open Multidepot Vehicle Routing Problem [J]. Journal of Shanghai Jiaotong University, 2010, 44(11): 1539-1544.
[6]	JIANG Guishana,JIANG Zhibinb,LIU Shujunb . Improved Guided Local Searchbased Algorithm for Period Vehicle Routing Problem [J]. Journal of Shanghai Jiaotong University, 2010, 44(09): 1171-1175.