Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (5): 214-216.DOI: 10.3778/j.issn.1002-8331.2010.05.065

• 工程与应用 • Previous Articles     Next Articles

Wasp colony algorithm for vehicle routing problem

YANG Jin1,MA Liang2   

  1. 1.School of Science,University of Shanghai for Science and Technology,Shanghai 200093,China
    2.School of Management,University of Shanghai for Science and Technology,Shanghai 200093,China
  • Received:2008-08-14 Revised:2008-09-29 Online:2010-02-11 Published:2010-02-11
  • Contact: YANG Jin


杨 进1,马 良2   

  1. 1.上海理工大学 理学院,上海 200093
    2.上海理工大学 管理学院,上海 200093
  • 通讯作者: 杨 进

Abstract: Vehicle Routing Problem(VRP) is the typical NP-hard problem in combinatorial optimization.This paper proposes a new algorithm,wasp colony algorithm,for vehicle routing problem through comparing the two target function:vehicle number and total distance.Series of benchmark problems are tested and verify the validity of the algorithm through comparing the results with the other algortihms.The wasp colony algorithm has just begun to develop and due to now it is only used in few problems at home and abroad.Therefore this paper not only expands the application scope of the wasp colony algorithm but also gives a new method to solve the vehicle routing problem.

Key words: Vehicle Routing Problem(VRP), wasp colony algorithm, optimization

摘要: 车辆路径问题(VRP)是组合优化中典型的NP难题。根据车辆路径问题的实际情况,考察车辆数和总行程两个目标函数,给出了该问题的一种新的算法,蜂群算法。通过计算若干benchmark问题,并将结果与其他算法相比较与分析,验证了算法的有效性。蜂群算法是刚刚起步的智能优化算法,目前国内外关于蜂群算法的文献较少,故不仅是拓宽蜂群算法的应用范围的有效的尝试,同时也给车辆路径问题提供了一种新的解决方法。

关键词: 车辆路径问题, 蜂群算法, 优化

CLC Number: