Hybrid algorithm for vehicle routing problem

Computer Engineering and Applications ›› 2012, Vol. 48 ›› Issue (8): 226-229.

• 工程与应用 • Previous Articles Next Articles

Hybrid algorithm for vehicle routing problem

ZHANG Siliang, GE Hongwei

School of Information Engineering，Jiangnan University，Wuxi，Jiangsu 214061，China

Received:1900-01-01 Revised:1900-01-01 Online:2012-03-11 Published:2012-03-11

求解车辆路径问题的一种混合方法

张思亮，葛洪伟

江南大学信息工程学院，江苏无锡 214061

Abstract

Abstract: A modified Particle Swarm Optimization（PSO） algorithm is adopted to deal with Vehicle Routing Problem with Time Windows（VRPTW）. Ant Colony System（ACS） algorithm is adopted to produce a stage solution as a template. PSO algorithm is used to optimize the template. And in the ACS, ant chooses client that unvisited and capacity is ultimate as start, when capacity is overrunned. From the test results, it shows that this algorithm is effective and practicable.

Key words: vehicle routing problem, Particle Swarm Optimization（PSO）, Ant Colony System（ACS）

摘要： 提出一种求解带软时间窗车辆路径问题的混合算法。采用蚁群系统算法产生阶段最优解，以此作为粒子模板，随机生成粒子群，利用粒子群算法在阶段最优解基础上进一步优化。且在蚁群系统算法中，当容量超过限制后，从剩余的客户里选择需求量最大的作为新的起点继续探索路径，直到所有客户都被访问一遍。实验表明，该混合算法是解决带软时间窗车辆路径问题的一个有效算法。

关键词: 车辆路径问题, 粒子群算法, 蚁群系统算法

ZHANG Siliang, GE Hongwei. Hybrid algorithm for vehicle routing problem[J]. Computer Engineering and Applications, 2012, 48(8): 226-229.

张思亮，葛洪伟. 求解车辆路径问题的一种混合方法[J]. 计算机工程与应用, 2012, 48(8): 226-229.

[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]	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]	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.
[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]	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.
[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]	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.
[14]	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.
[15]	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.

Hybrid algorithm for vehicle routing problem

求解车辆路径问题的一种混合方法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics