2。1。2 TSP 问题的定义和分类

一、TSP 问题的数学模型

旅行商问题的文字描述可以表达为：给出一组 N 个城市坐标和他们彼此之间的欧 式距离找出一条闭合的路径，使给出的每个城市都有到达并且每个城市仅通过一次10。 数学定义如下：

记为赋权图，为顶点集，E 为边集，各顶点消耗为 dij，已知（dij>0,dii=+）。要求 G

的哈密尔顿回路上消耗达到最小值,并设：

1  边(i，j)在哈密尔顿圈上

则旅行商问题的数学模型可写成如下线性规划形式：

∑ � ≠ j