Hybrid intelligence algorithm based on vehicle routing problem with time windows

doi:10.3778/j.issn.1002-8331.2008.20.016

Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (20): 54-56.DOI: 10.3778/j.issn.1002-8331.2008.20.016

• 理论研究 • Previous Articles Next Articles

Hybrid intelligence algorithm based on vehicle routing problem with time windows

ZHANG You-hua,ZHANG Cui-jun,CUI Zhong-qiang

College of Information and Technology，Shijiazhuang University of Economics，Shijiazhuang 050031，China

Received:2007-10-11 Revised:2008-01-04 Online:2008-07-11 Published:2008-07-11
Contact: ZHANG You-hua

有时间窗车辆路径问题的混合智能算法

张有华,张翠军,崔忠强

石家庄经济学院信息工程学院，石家庄 050031

通讯作者: 张有华

Abstract

Abstract: Vehicle routing problem with time windows is a NP-hard problem in combinatorial optimization field.Based on the analysis about it，a mathematical model is built and a hybrid intelligence algorithm for solving it is designed.The algorithm lets ant colony algorithm and genetic algorithm execute alternately and communicate timely in the optimization process.It learns the colony algorithm’s and genetic algorithm’s advantages and makes up their disadvantages.Thus its ability of optimization is enhanced and premature phenomenon is avoided.The experiment results show that the hybrid algorithm is efficient in solving vehicle routing problem with time windows.

Key words: vehicle routing problem with time windows, NP-hard problem, ant colony algorithm, genetic algorithm, hybrid intelligence algorithm

摘要： 有时间窗的车辆路径问题属于组合优化领域中的NP-hard问题。在对该问题进行分析的基础上，为之建立了数学模型，提出了一种求解该问题的混合智能算法。该算法通过使用蚁群算法和遗传算法交替优化，并且及时交换信息，弥补了蚁群算法和遗传算法各自的不足，达到了优势互补的效果，增强了算法的寻优能力，避免了停滞现象。实验结果表明，该算法能有效解决有时间窗的车辆路径问题。

关键词: 有时间窗车辆路径问题, NP-hard问题, 蚁群算法, 遗传算法, 混合智能算法

ZHANG You-hua,ZHANG Cui-jun,CUI Zhong-qiang. Hybrid intelligence algorithm based on vehicle routing problem with time windows[J]. Computer Engineering and Applications, 2008, 44(20): 54-56.

张有华,张翠军,崔忠强. 有时间窗车辆路径问题的混合智能算法[J]. 计算机工程与应用, 2008, 44(20): 54-56.

[1]	SHI Chuntian, ZENG Yanyang, HOU Shouming. Summary of Application of Swarm Intelligence Algorithms in Image Segmentation [J]. Computer Engineering and Applications, 2021, 57(8): 36-47.
[2]	ZHANG Songcan, PU Jiexin, SI Yanna, SUN Lifan. Adaptive Improved Ant Colony Algorithm Based on Population Similarity and Its Application [J]. Computer Engineering and Applications, 2021, 57(8): 70-77.
[3]	BU Guannan, LIU Jianhua, JIANG Lei, ZHANG Dongyang. Ant Colony Algorithm with Adaptive Grouping [J]. Computer Engineering and Applications, 2021, 57(6): 67-73.
[4]	MA Xianghua, ZHANG Qian. Research on Improved Ant Colony Algorithm in Robots Path Planning [J]. Computer Engineering and Applications, 2021, 57(5): 210-215.
[5]	LI Yuqi, LIU Zhiqian, CHENG Ningyi, WANG Yingying, ZHU Chunli. Path Planning of UAV Under Multi-constraint Conditions [J]. Computer Engineering and Applications, 2021, 57(4): 225-230.
[6]	YANG Wei, WU Yingying, WANG Ting. Research on Configuration Optimization Problems of Shuttle-Carrier Storage and Retrieval System [J]. Computer Engineering and Applications, 2021, 57(4): 258-265.
[7]	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.
[8]	DU Shouxin, WU Tao. Study on Application of Double Population Hybrid Genetic Algorithm in Cut Order Planning [J]. Computer Engineering and Applications, 2021, 57(22): 182-189.
[9]	CAO Lijia, LIU Yang. Recent Advances in Scheduling Optimization of Automated Guided Vehicles in Manufacturing Workshops [J]. Computer Engineering and Applications, 2021, 57(21): 59-67.
[10]	WANG Xiaoguang, YANG Peibei. Design and Effect Analysis of Digital Transformation of Shipping Logistics Enterprises [J]. Computer Engineering and Applications, 2021, 57(21): 241-247.
[11]	ZHANG Ziran, HUANG Weihua, CHEN Yang, ZHANG Zheng, LI Ziyuan. Improved Ant Colony Path Planning Algorithm Based on Bidirectional Search [J]. Computer Engineering and Applications, 2021, 57(21): 270-277.
[12]	CHEN Qianru, LI Yali, XU Kequan, LIU Yilong, WANG Shuqin. WKNN Feature Selection Method Based on Self-Tuning Adaptive Genetic Algorithm [J]. Computer Engineering and Applications, 2021, 57(20): 164-171.
[13]	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.
[14]	SHI Yuqiang, TIAN Yongzheng, ZHANG Yuqi, SHI Xiaoqiu. Solving FJSP by Multi-population Genetic Algorithms with Complex Network Structure [J]. Computer Engineering and Applications, 2021, 57(2): 257-266.
[15]	DAI Jiangtao, HAN Xiaolong. Coordinated Scheduling of Equipment in Container Terminals Considering Energy Consumption Under Different Job Status [J]. Computer Engineering and Applications, 2021, 57(19): 290-298.

Hybrid intelligence algorithm based on vehicle routing problem with time windows

有时间窗车辆路径问题的混合智能算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics