Improved Particle Swarm Optimization for Vehicle Routing Problem with time windows

doi:10.3778/j.issn.1002-8331.2009.27.061

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (27): 200-202.DOI: 10.3778/j.issn.1002-8331.2009.27.061

• 工程与应用 • Previous Articles Next Articles

Improved Particle Swarm Optimization for Vehicle Routing Problem with time windows

MA Xuan，PENG Peng，LIU Qing

School of Automation and Information Engineering，Xi’an University of Technology，Xi’an 710048，China

Received:2009-03-23 Revised:2009-06-01 Online:2009-09-21 Published:2009-09-21
Contact: MA Xuan

求解带时间窗车辆路径问题的改进粒子群算法

马炫，彭芃，刘庆

西安理工大学自动化与信息工程学院，西安 710048

通讯作者: 马炫

Abstract

Abstract: Through analysing the reason that the existing particle swarm optimization algorithms can not find good solutions of solving the vehicle routing problem with tim windows，this paper proposes a method of updating integer particle based on transposition.The algorithm that consists of double-layer Particle Swarm Optimization（PSO） is tested on the problem instances of 8 and 20 mission points，respectively.The numerical simmulation results show that the proposed algorithm is superior to the existing algorithms in searching high quality solutions and time-consuming.

Key words: Vehicle Routing Problem（VRP） with time windows, Particle Swarm Optimization（PSO）, principle of transposition

摘要： 通过分析已有粒子群算法对有时间窗约束的车辆路径问题求解质量不高的原因，提出了一种基于粒子交换原理的整数粒子更新方法。采用构造的双层粒子进化算法分别对8个和20个任务点的有时间窗约束的车辆路径问题求解，数值实验结果表明算法的求解精度和耗时均优于已有算法。

关键词: 带时间窗车辆路径问题, 粒子群算法, 交换原理

CLC Number:

TP301

MA Xuan，PENG Peng，LIU Qing. Improved Particle Swarm Optimization for Vehicle Routing Problem with time windows[J]. Computer Engineering and Applications, 2009, 45(27): 200-202.

马炫，彭芃，刘庆. 求解带时间窗车辆路径问题的改进粒子群算法[J]. 计算机工程与应用, 2009, 45(27): 200-202.

[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]	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.
[4]	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.
[5]	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.
[6]	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.
[7]	YANG Yanrong, SONG Rongjie, ZHOU Zhaoyong. Network Intrusion Detection Method Based on GAN-PSO-ELM [J]. Computer Engineering and Applications, 2020, 56(12): 66-72.
[8]	JIANG Li1，2, YE Runzhou1，2, LIANG Changyong1，2, LU Wenxing1，2. Improved Second-Order Oscillatory Particle Swarm Optimization [J]. Computer Engineering and Applications, 2019, 55(9): 130-138.
[9]	FENG Jianxin1，2, LI Hui1，2, LIU Zhiguo1，2. New Flame Color Space—IFCS [J]. Computer Engineering and Applications, 2019, 55(5): 203-210.
[10]	YUAN Luo1，2, GE Hongwei1，2. Dispersion Particle Swarm Optimization Algorithm Based on Random Whip Mechanism [J]. Computer Engineering and Applications, 2019, 55(4): 66-71.
[11]	YAN Xuelong, CHEN Zhuo. Analog Circuit Fault Prognostic Utilizing Particle Swarm Optimized Multi-Kernel Relevance Vector Machine [J]. Computer Engineering and Applications, 2019, 55(12): 140-144.
[12]	HONG Tianlong, XIE Lijun, HE Lisha, NI Zhongyi, ZHENG Yao. Auto Tunning for In-Situ Volume Depth Image Generation Based on Particle Swarm Optimization Algorithm [J]. Computer Engineering and Applications, 2019, 55(11): 237-243.
[13]	KANG Kai, PU Wei, HAN Jie, MA Yanfang. Inventory-allocation planning problem with defective item disposal under fuzzy random environment [J]. Computer Engineering and Applications, 2018, 54(24): 241-251.
[14]	HU Min, WANG Tengfei, HUANG Hongcheng. Software-defined wireless sensor networks routing algorithm based on extremum disturbed particle swarm optimization [J]. Computer Engineering and Applications, 2018, 54(22): 113-118.
[15]	SHI Jianli1, ZHANG Jin2. Particle swarm optimization for split delivery vehicle routing problem with stochastic demands [J]. Computer Engineering and Applications, 2018, 54(21): 230-239.

Improved Particle Swarm Optimization for Vehicle Routing Problem with time windows

求解带时间窗车辆路径问题的改进粒子群算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics