单车场车辆路径问题的蚁群算法求解及程序设计  

RESOLVING SINGLE-DEPOT VEHICLE ROUTING PROBLEM WITH ANT COLONY ALGORITHM AND THE PROGRAM DESIGNING

作　　者：尹朋珍[1] 郭海湘[1,2] 杨娟[1] 诸克军[1] 

机构地区：[1]中国地质大学经济管理学院,湖北武汉430074 [2]西安交通大学管理学院,陕西西安710049

出　　处：《计算机应用与软件》2010年第8期49-51,54,共4页Computer Applications and Software

基　　金：国家自然科学基金项目资助(70573101);高等学校博士学科点专项科研基金资助(20070491011);中国博士后基金资助(20090461293);中央高校基本科研业务费用专项资金资助(CUG09013)

摘　　要：以郑州煤电物资供销有限公司的炸药配送问题为背景,引入蚁群算法对该配送问题进行求解。算法采用蚂蚁系统算法的转移概率策略确定蚂蚁的转移方向,并结合最大最小蚂蚁系统算法的信息素更新机制进行信息素更新。当算法接近停滞状态时,对信息素进行再次初始化,以加强算法的搜索能力。从而,得到一条解决该实际问题的完整最优解,作为该公司物资配送的参考。同时,探讨了在VC++6.0环境中实现该算法的主要编程思想。最后,将得出的结果与遗传算法所得结果进行比较,得出蚁群算法在解决车辆路径问题上具有较好的搜寻能力和收敛能力。In this paper, the algorithm of ant colony is introduced to solve the distribution problem at Zhengzhou Coal and Electricity Mate- rials Supply and Marketing Limited Company, where the dynamite distribution issue of the Company is taken as the background. The algorithm presented in the article employs transfer probability strategy of the ant system algorithm to decide the transfer direction of ants, and updates the pheromone of the trails in conjunction with the pheromone updating mechanism of max-min ant system algorithm. When the algorithm is close to a standstill, the pheromone will be re-initialised in order to strengthen the search capacity. Thus, an integrated optimal solution is gained for this practical problem and it can be used as a reference to the Company for its logistics distribution. Meanwhile, the main programming idea of implementing this algorithm in VC ＋ ＋ 6.0 has been explored. At last, the solution derived from the presented algorithm is compared with the results from the genetic algorithm, what the conclusion obtained is that the ant colony algorithm has better convergent ability and search capacity in resolving vehicle routing problem.

关 键 词：蚁群算法 车辆路径问题 物资配送 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]