1.1 研究目的及意义

组合优化问题（或称为离散优化）作为一门古老而又年轻的学科，早在二十世纪后半叶，伴随着工业科技革命和现代管理科学的发展，特别是计算机技术的突飞猛进和在各行业的广泛应用，其已壮大成为运筹学的一个独立分支。一些数百年前数学家们偶然想到的问题和方法，已在网络通信、物流管理、交通规划等行业发挥了重要的作用。

随着实践的发展，出现了越来越多的组合优化问题都很难找到求最优解的多项式时间算法。人们研究整理了一类难以求解的组合优化问题，迄今为止还没有一个能我到最优解的多项式时间算法。其中TSP就属于这一类问题。

旅行商问题(Traveling Salesman Problem，TSP)是一个经典的组合优化问题。它具有重要的实际意义和工程背景。它一开始是为交通运输而提出的，比如飞机航线安排、送邮件、快递服务、设计校车行进路线等等。实际上其应用范围扩展到了许多其他领域。

印制电路板转孔是TSP应用的经典例子，在一块电路板上打成百上千个孔，转头在这些孔之间移动，相当于对所有的孔进行一次巡游。把这个问题转化为TSP，也相当于城市。孔到孔之问的移动时间就是距离。此外，旅行商问题还有电缆和光缆布线、晶体结构分析、数据串聚类等多种用途。更重要的是．它提供了一个研究组合优化问题的理想平台。很多组合优化问题，比如背包问题、分配问题、车间调度问题都和TSP同属NP完全问题，它们都是同等难度的。如果其中一个能用多项式确定性算法解决，那么其他所有的NP完全问题也能用多项式算法解决。很多方法本来是从TSP发展起来的，后来推广到其他NP完全问题上去。

因此，研究TSP问题不仅会对工程应用具有一定的指导意义，而且随着实践的发展，对于组合优化问题的研究走向更加成熟具有重要意义。

传统优化算法难以在多项式时间内找到问题的最优解，群智能优化算法的出现，如遗传算法(Genetic Algorithm，GA)，粒子群优化算法(Particle Swarm Optimization，PSO)，人工鱼群算(Artificial Fish School Algorithm，AFSA)和人工蜂群(Artificial Bee Colony，ABC)算法等使求解旅行商问题取得新的进展。

人工蜂群算法(artificial bee colony，ABC)是由土耳其学者Karaboga于2005年提出，它是模拟蜜蜂的采蜜行为来解决生活中一些多维和多模的优化问题，它最初应用于数值优化问题，自提出以来受到了众多学者极大的关注，并广泛应用到神经网络、数据挖掘、工程应用、图像识别等多个领域。

蜂群算法的思路，为在没有集中控制且不提供全局模型的前提下寻找复杂的分布式问题求解方案提供了基础。已有的蜂群算法理论和应用研究证明蜂群算法是一种能够解决大多数优化问题的新方法，更重要的是，蜂群算法潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还是应用研究的角度分析，蜂群算法理论及应用研究都是具有重要学术意义和现实价值的。

1.2 国内外研究现状