Study on vehicle routing problem based on heuristic ant colony optimization

Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (32): 246-248.

• 工程与应用 • Previous Articles

Study on vehicle routing problem based on heuristic ant colony optimization

LIU Xiaoyong，FU Hui

Department of Computer Science，Guangdong Polytechnic Normal University，Guangzhou 510665，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-11-11 Published:2011-11-11

基于启发式蚁群算法的VRP问题研究

刘晓勇，付辉

广东技术师范学院计算机科学学院，广州 510665

Abstract

Abstract: When Ant Colony Optimization algorithm（ACO） is applied to vehicle routing problem，it always spends much time and has worse solutions.This paper uses ACO based on a heuristic method for vehicle routing problem.This heuristic method combines distance matrix with saving route matrix to assign initial pheromone matrix.Three benchmark datasets are chosen to verify performance of the new algorithm.Experiments show that ant colony optimization based on heuristic information has better solution and spends less time.

Key words: vehicle routing problem, ant colony optimization, heuristic method

摘要： 针对蚁群算法求解VRP问题时收敛速度慢，求解质量不高的缺点，把城市和仓库间的距离矩阵和路径节约矩阵信息融入到初始信息素矩阵中作为启发式信息引入到蚁群算法中用于求解有容量限制的车辆路径规划问题（CVRP），在三个基准数据集上的实验研究表明，基于启发式信息的蚁群算法与基本蚁群算法相比能够以较快的速度收敛到较好的解。

关键词: 车辆路径规划问题, 蚁群算法, 启发式方法

LIU Xiaoyong，FU Hui. Study on vehicle routing problem based on heuristic ant colony optimization[J]. Computer Engineering and Applications, 2011, 47(32): 246-248.

刘晓勇，付辉. 基于启发式蚁群算法的VRP问题研究[J]. 计算机工程与应用, 2011, 47(32): 246-248.

[1]	ZHU Jiaying, GAO Maoting. AUV Path Planning Based on Particle Swarm Optimization and Improved Ant Colony Optimization [J]. Computer Engineering and Applications, 2021, 57(6): 267-273.
[2]	LI Zhuangkuo, CHANG Kaixuan. Ant Colony Optimization for Continuous Domains Applied to Cooperative Game [J]. Computer Engineering and Applications, 2021, 57(24): 198-204.
[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]	HE Yaying, FAN Xinwei. Application of Improved Ant Colony Optimization in Robot Path Planning [J]. Computer Engineering and Applications, 2021, 57(16): 276-282.
[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 Ming, DENG Wenhan, LIN Juan, ZHONG Yiwen. Modified Ant Colony Optimization Algorithm for Discounted {0-1} Knapsack Problem [J]. Computer Engineering and Applications, 2021, 57(13): 85-95.
[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]	HU Chunyang, JIANG Ping, ZHOU Genrong. Application of Improved Ant Colony Optimization in AGV Path Planning [J]. Computer Engineering and Applications, 2020, 56(8): 270-278.
[12]	ZHANG Hainan, YOU Xiaoming, LIU Sheng, LIU Zhongqiang. Interactive Learning Cuckoo Search Algorithm [J]. Computer Engineering and Applications, 2020, 56(7): 147-154.
[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]	LIU Ximei, PAN Lijun. Clonal Selection Algorithm for Solving Bike Sharing Rebalancing Problem [J]. Computer Engineering and Applications, 2020, 56(11): 252-258.

Study on vehicle routing problem based on heuristic ant colony optimization

基于启发式蚁群算法的VRP问题研究

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics