两种提法。种旅行售货员问题的简单描述是名商人欲到个城市推销商品，每两个城市和之间的距离为，如何选择条路径是的商人每个城市走遍回到起点后，所走的路径最短。其数学模型为在加权图上求个圈，使得圈的权各个上述经典的定义比实际问题就要狭隘了，因为实际上旅行售货员可以在段路程上往返，往往反而节省了整个巡回的总费用大都用距离来表示。此外，如果有图所示的用上述经典的定义找不到解得，但在实际中的旅行售货员仍可选择条最优路线，只不过顶点要被访问两次。图旅行售货员问题举例则另种提法是商人从城市出发，遍历各个城市至少次后返回出发点，设计出条路线使总路程最短。此时，数学模型是在加权图,上求个生成回路，使各个生成回路的权。这个叫做理想回路。从算法理论上讲，这两种提法难度是相当的。旅行售货员问题的分类从问题对应到图的类型，通常有两种基本的分类任意两个城市之间来往的路径均相等或可以不相等就可以归结为无向图或有向图问题。任意两个城市之间来回均存在路径或至少有两个城市之间仅存在单行路径这种类型可以归结为完全图或者非完全图问题。将上述两种情况加以组合，便可得到以下四种的路径关系完全有向图完全无向图非完全有向图非完全无向图。从问题本身的限制条件的强弱，主要有三类，第类不作任何限制，只给出距离矩阵，求最小回路第二类要求距离间要满足三角不等式对于个旅行售货员问题中的任意三个城市，假如从经过到达的旅行费用不低于从到的旅行费用，那么称这个旅行售货员问题满足三角不等性，满足三角不等性的旅行售货员问题，具有许多优良的性质，可以大大方便计算。但另方面，已经证明，满足三角不等性的对称旅，是种典型的群智能优化算法，最早是由美国社会心理学家和电气工程于年共同提出的。基本的微粒群算法利用了生物学家的生物群体模型，模拟了鸟群寻找栖息地的过程，参照提出的鸟群计算机仿真模型，算法将鸟群类比为群没有体积及质量的微粒，每个微粒的运动通过速度和位移两种进化方程来描述。鸟群飞向的栖息地类比为优化算法可能解的位置。在寻优的过程中，通过认知，记忆和信息交互，每个微粒可以根据自身和周围微粒的飞行经圈问题。由于其在许多领域都有着广泛的应用，因而寻找其实际而又有效的算法显得颇为重要，遗憾的是，计算复杂性理论给予我们的结论是这种可能性尚属未知。在理论上已归结为所谓的完备问题类，即非确定性多项式完备问题。关于这类十分困难的问题，现在所知道的仅仅是任何完备问题都不能用己知的多项式算法来解决用多项式算法去研究问题起于五十年代，如线性规划算法动态规划算法分枝定界法。这些算法虽然对些小规模的问题可精确求解，但计算的复杂度与城市的数目成指数增长。在大规模的问题上，这些精确算法显得无能为力，而且容易产生组合爆炸，因而人们退而寻求非尽善尽美的所谓启发式算法近似算法，来处理各种实际问题。七十年代和八十年代是启发式算法的全盛时期，但由于绝大多数启发式算法都是按种确定性的搜索规则来运行，想要改进所得解的可能性极小。因此，从八十年代后期直到九十年代，些来自其它学科的新代求解方法相继出现，在组合优化问题的求解中取得相当的成功和系列成果。尽管仍未找到最优解，但是求解它的算法逐渐改进。年，马良总结归纳出年到年国内外近几十年求解的算法，可分为两类类是精确算法如线性规划动态规划分枝定界法等另类是近似算法启发式算法，如插入算法算法神经网络算法模拟退火算法遗传算法蚂蚁算法等。目前，对于求解问题，国内外都有相当好的进展，年，周培德用点集凸壳的多项式时间算法解决了个顶点的中国货郎担问题。年，美国加利弗利亚大学根据出度入度均为的的有向图中有条路的这特性，提出了用算法求解出度入度均为的。几十年来对于求解问题出现了很多传统方法，其中有精确算法如线性规划方法动态规划方法分支定界方法近似优化算法有插入法最近邻算法灯混合算法概率算法等。近年来，有很多解决该问题的较为有效的智能方法不断被推出，例如禁忌搜索方法遗传算法模拟退火算法等。时至今日，人们己经发现有许多问题本质上都可归结为个或是将其作为个子问题来处理，但要想!