Solving Vehicle Routing Problem with Stochastic Demands Based on Adaptive Cross-Entropy Method

Computer Engineering and Applications ›› 2006, Vol. 42 ›› Issue (29): 20-.

• 博士论坛 • Previous Articles

Solving Vehicle Routing Problem with Stochastic Demands Based on Adaptive Cross-Entropy Method

Shanzuo Lou,

西北工业大学空中交通管理研究所

Received:2006-07-21 Revised:1900-01-01 Online:2006-10-11 Published:2006-10-11
Contact: Shanzuo Lou

基于交叉熵法解决随机需求车辆路径问题

娄山佐、史忠科

西北工业大学空中交通管理研究所

通讯作者: 娄山佐 lshanzuo

Abstract

Abstract: A new method is proposed for solving vehicle routing problem with stochastic demands (VRPSD). Firstly, a mathematical model for VRPSD is established by using preventive recourse action. Secondly, in order to improve the performance of standard cross-entropy (SCE) algorithm, an adaptive adjustment scheme is developed for the routes used to update Markov transition matrix in terms of the improvement level of quintiles. Finally, simulation results prove the validity of the proposed method for solving VRPSD.

Key words: stochastic programming, vehicle routing, cross-entropy

摘要： 提出一种解决随机需求车辆路径问题(VRPSD)新方法。首先，采用预防性补救措施，建立了VRPSD模型，其次，为提高标准交叉熵(SCE)法性能，对用于更新Markov转移矩阵的路径，设计了根据分位值改变大小的自适应调整方法。最后，仿真结果验证了该算法解决VRPSD的有效性。

关键词: 随机规划, 车辆路径, 交叉熵

Shanzuo Lou,. Solving Vehicle Routing Problem with Stochastic Demands Based on Adaptive Cross-Entropy Method[J]. Computer Engineering and Applications, 2006, 42(29): 20-.

娄山佐、史忠科

基于交叉熵法解决随机需求车辆路径问题

[J]. 计算机工程与应用, 2006, 42(29): 20-.

[1]	GE Xianlong, ZHANG Xiaoxiao, WANG Bo. Optimization of Two-Echelon Fresh Distribution Routing with Front-Warehouse Cooperation [J]. Computer Engineering and Applications, 2022, 58(15): 330-340.
[2]	NIU Pengfei, WANG Xiaofeng, LU Lei, ZHANG Jiulong. Survey on Vehicle Reinforcement Learning in Routing Problem [J]. Computer Engineering and Applications, 2022, 58(1): 41-55.
[3]	LI Qian, JIANG Li, LIANG Changyong. Multi-objective Cold Chain Distribution Optimization Based on Fuzzy Time Window [J]. Computer Engineering and Applications, 2021, 57(23): 255-262.
[4]	MA Yanfang, LI Baoyu, YANG Yifu, FENG Cuiying. Two-Echelon Capacitated Vehicle Routing Model and Algorithm for Fresh Products Distribution with Customer Classification [J]. Computer Engineering and Applications, 2021, 57(20): 287-298.
[5]	MA Long, WANG Chunxi, ZHANG Zhengyi, DONG Rui. Pigeon-Inspired Optimization and Intelligent Water Drops Algorithm for Multiple-objective Vehicle Routing Problem with Multiple Time Windows [J]. Computer Engineering and Applications, 2021, 57(2): 237-250.
[6]	FU Zhaohui, LIU Changshi. Research on Multi-depot Vehicle Routing Problem Based on Joint Distribution Mode [J]. Computer Engineering and Applications, 2021, 57(16): 291-298.
[7]	ZHANG Kai, JIN Peng, CUI Yong. Multi-vehicle Split Pickup and Delivery Problem with Time Windows [J]. Computer Engineering and Applications, 2021, 57(14): 281-288.
[8]	ZHANG Xiaonan, JIANG Shuai, NAN Jingwen. Research on Multi-depots Vehicle Routing Problem with Semi-flexible Coverage Service [J]. Computer Engineering and Applications, 2021, 57(10): 225-232.
[9]	FU Zhaohui, LIU Changshi. Research on Open Time-Dependent Vehicle Routing Problem of Fresh Food E-commerce Distribution [J]. Computer Engineering and Applications, 2021, 57(1): 271-278.
[10]	SONG Juan. Pythagorean Decision-Making Model Considering Fusion Algorithms and Cross-Entropy [J]. Computer Engineering and Applications, 2020, 56(5): 74-79.
[11]	XU Chuanglai, HU Jiankun, HUANG Youfang. Robust Optimization of Express Delivery Network with Uncertain Demand [J]. Computer Engineering and Applications, 2020, 56(3): 272-278.
[12]	ZHANG Mingwei, LI Bo, QU Xiaolong, GUO Ying. Research on Low Carbon VRP of Heterogeneous Fleet Based on Hybrid Ant Colony Algorithm [J]. Computer Engineering and Applications, 2020, 56(14): 240-249.
[13]	PENG Lu, CHEN Huaili. Optimization of Collection Path of Dry Port Under Improved Genetic Algorithm [J]. Computer Engineering and Applications, 2020, 56(14): 250-256.
[14]	LIU Ximei, PAN Lijun. Clonal Selection Algorithm for Solving Bike Sharing Rebalancing Problem [J]. Computer Engineering and Applications, 2020, 56(11): 252-258.
[15]	ZHAO Zhixue, LI Xiamiao, ZHOU Xiancheng, LIU Changshi. Research on Green Vehicle Routing Problem of Cold Chain Distribution：Considering Traffic Congestion [J]. Computer Engineering and Applications, 2020, 56(1): 224-231.

Solving Vehicle Routing Problem with Stochastic Demands Based on Adaptive Cross-Entropy Method

基于交叉熵法解决随机需求车辆路径问题

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics