Study on multi-depot vehicle routing problem with time windows based on Particle Swarm Optimization

Computer Engineering and Applications ›› 2012, Vol. 48 ›› Issue (27): 27-30.

Previous Articles Next Articles

Study on multi-depot vehicle routing problem with time windows based on Particle Swarm Optimization

WANG Tiejun1, WU Kaijun2

1.School of Mathematics and Computer Science, Northwest University for Nationalities, Lanzhou 730030, China
2.School of Electronic and Information Engineering, Lanzhou Jiaotong Unversity, Lanzhou 730070, China

Online:2012-09-21 Published:2012-09-24

带时间窗的多车场车辆路径优化的粒子群算法

王铁君1，邬开俊2

1.西北民族大学数学与计算机科学学院，兰州 730030
2.兰州交通大学电子与信息工程学院，兰州 730070

Abstract

Abstract: Multi-depot vehicle routing problem with time windows is a variation of the vehicle routing problem constrained by multi-depot and time windows, which is a typical NP-hard problem. Particle swarm optimization with a particle coding method is designed to solve the problem. The mathematic mode is established and the solution algorithm is developed. The simulation results of example indicate that the algorithm has faster search speed and stronger optimization ability than the GA and ACO.

Key words: time windows, multi-depot, vehicle routing problem, Particle Swarm Optimization（PSO）

摘要： 带时间窗的多车场车辆路径问题在基本车辆路径问题的基础上增加了“多车场”与“时间窗”两个约束条件，是一个典型的NP难解问题。将粒子群算法应用于带时间窗的多车场车辆路径优化问题，构造了一种适用于求解车辆路径问题的粒子编码方法，建立了相应的数学模型，在此基础上设计了相应的算法。算例通过和遗传算法、蚁群算法进行比较，证明了其搜索速度和寻优能力的优越性。

关键词: 时间窗, 多车场, 车辆路径优化, 粒子群算法

WANG Tiejun1, WU Kaijun2. Study on multi-depot vehicle routing problem with time windows based on Particle Swarm Optimization[J]. Computer Engineering and Applications, 2012, 48(27): 27-30.

王铁君1，邬开俊2. 带时间窗的多车场车辆路径优化的粒子群算法[J]. 计算机工程与应用, 2012, 48(27): 27-30.

[1]	HU Xiaomin, WANG Mingfeng, ZHANG Shourong, LI Min. New Differential Evolution with Particle Swarm Optimization Algorithm for Text Clustering [J]. Computer Engineering and Applications, 2021, 57(4): 61-67.
[2]	WANG Jiayue, SHI Li. Research on Path Optimization and Charging Strategy of Electric Refrigerated Vehicle Considering Cost of Battery Capacity Degradation [J]. Computer Engineering and Applications, 2021, 57(24): 283-289.
[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]	LIN Weixing, WANG Yujia, CHEN Wanfen, LIANG Haina. High-Dimensional Data Feature Selection Algorithm Based on Multifactor Particle Swarm Optimization [J]. Computer Engineering and Applications, 2021, 57(22): 199-207.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	LIAO Weilin, CHENG Shan, SHANG Dongdong, WEI Zhaobin. Particle Swarm Optimization Algorithm Integrated with Multiple-Strategies [J]. Computer Engineering and Applications, 2021, 57(1): 69-76.
[12]	CHEN Qiuju, XU Jianguo. Optimized Orthogonal Matching Pursuit and Short-Time Spectrum Estimation for Sound Recognition [J]. Computer Engineering and Applications, 2020, 56(7): 162-169.
[13]	ZHOU Rong, LI Jun, WANG Hao. Reverse Learning Particle Swarm Optimization Based on Grey Wolf Optimization [J]. Computer Engineering and Applications, 2020, 56(7): 48-56.
[14]	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.
[15]	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.

Study on multi-depot vehicle routing problem with time windows based on Particle Swarm Optimization

带时间窗的多车场车辆路径优化的粒子群算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics