求解选择性单商品配送收集问题的有效蚁群算法  

AN EFFECTIVE ANT COLONY ALGORITHM SOLVING ONE-COMMODITY TRAVELLING SALESMAN PROBLEM WITH SELECTIVE PICKUP AND DELIVERY

作　　者：牟廉明[1] 戴锡笠[2] 

机构地区：[1]内江师范学院四川省高等学校数值仿真重点实验室,四川内江641100 [2]内江师范学院数学与信息科学学院,四川内江641100

出　　处：《计算机应用与软件》2013年第12期93-96,共4页Computer Applications and Software

基　　金：国家自然科学基金项目(10872085);四川科技厅应用基础研究基金项目(07JY029-125);内江师范学院自然科学重点项目基金(12NJZ03);大学生创新性实验计划项目(X201205)

摘　　要：选择性单商品配送收集问题(1-TSP-SELPD)是单商品配送收集问题(1-PDTSP)的推广,在许多实际领域都有广泛应用。1-TSP-SELPD属于NP难题,为了有效求解该问题,设计一个有效的蚁群算法。该算法从三个方面来提高求解性能:第一是启发式参数随着搜索状态自适应调整;第二是信息更新量随着求解质量进行动态变化;第三是设计适用于1-TSP-SELPD特点的、有约束的局部搜索技术用来加快收敛速度和提高解的质量。比较实验表明:该算法在求解质量、稳定性和收敛速度都有显著提高。One-commodity travelling salesman problem with selective pickup and delivery （1-TSP-SELPD） is the generalisation of one-commodity pickup-and-delivery travelling salesman problem （1-PDTSP） and has wide applications in many practical areas. The 1-TSP-SELPD is known as an NP-hard. In order to effectively solve it, in this paper we propose an effective ant colony algorithm. The algorithm improves the performance of the solution from three aspects. The first is that the heuristic parameter will be adjusted adaptively with the searching state; The second is that the updated information amount will be changed dynamically with solution quality; The third is that to design the constrained local searching technique suitable to the characteristics of 1-TSP- SELPD for accelerating the convergence speed and improving the quality of solution. Comparative experiments show that the improved algorithm has noticeable improvements in solution quality, stability and convergence speed.

关 键 词：选择性单商品配送收集问题 蚁群算法 有约束的局部搜索技术 

分 类 号：TN929.5[电子电信—通信与信息系统] TP301.6[电子电信—信息与通信工程]